Challenge 6

I know what you were thinking – “It is high time for a new challenge”. I hear you. Here it is; topic is network flow.

1. Graph

The graph is arguably the most fundamental data structure in all computer science. Today you have the chance to implement one. Here is a pseudo skeleton that you need to fill in:

Java:

// Represents a single vertex of the graph.
public class Vertex {
public Vertex (int id);
public int getId();
}
// Represents a weighted edge connecting two vertices
public class Edge {
public Edge(int weight, Vertex thisV, Vertex other);
// Gets the vertex which is not v
public Vertex getOtherVertex(Vertex v);
public int getWeight();
public Vertex getTarget();
public Vertex getSource();
}
// Represents the whole graph
public class Graph {
public Graph(Vertex [] vertices, ArrayList [] neighbours);
public int getNumberOfVertices();
// Literally, returns any vertex of the graph
public Vertex getAnyVertex();
public ArrayList getEdgesOf(Vertex v);
}

C++:

#include <fstream>
#include <vector>
using namespace std;
// Represents a single vertex of the graph.
class Vertex {
public:
Vertex (int id);
int Id();
}
// Represents a weighted edge connecting two vertices
class Edge {
public:
Edge(int weight, Vertex& thisV, Vertex& other);
// Gets the vertex which is not v
Vertex& GetOtherVertex(Vertex& v);
int Weight();
Vertex& GetTarget();
Vertex& GetSource();
}
// Represents the whole graph
class Graph {
public:
Graph(Vertex vertices[], vector neighbours[]);
int getNumberOfVertices();
// Literally, returns any vertex of the graph
Vertex& getAnyVertex();
vector getEdgesOf(Vertex& v);
}

Note that this graph of yours can be used for directed, weighted graphs, which is how residual networks can be represented. Also, you don’t have to necessarily use one of these two skeletons, but they can be a good starting point. Anything that will help you solve 2 and 3 will do.

2. The Edmons-Karp Heuristic

In order to have a good implementation of Ford-Fulkerson, we need to use the Edmons-Karp heuristic. Thankfully, it is quite a simple thing. Read the notes: ADS Network Flow, page 39. Then code up a method of the format:

Java:

Graph edmonsKarp(Graph residualNetwork);

C++

Graph EdmonsKarp(Graph const& residualNetwork);

[If you wonder, why the const is misplaced, read this.]

For a test network of less than 106 nodes and 107 edges, your algorithm should run in less than 1 second.

3. The Ford-Fulkerson Algorithm

This one finds the maximum flow of a network. You can go and read the description in the lecture notes again, but to be honest, looking at examples will give you understanding what the algorithm is about faster than trying to understand its formal definition. You can find examples on pages 22, 26, and 38. Then implement the algorithm in the following format:

Java:

int fordFulkerson(Graph residualNetwork);

C++:

int FordFulkerson(Graph& residualNetwork);

For a test network of less than 1000 nodes and 104 edges, your algorithm should run in less than 1 second. Oh, and the maximum flow will be less than 1000.

How to Submit

After you’re done, put the functions in one file called winchal6.cpp or WinChal6.java. In case you are using Java, obviously you need a class. Call it WinChal6 and let it reside in a package called uoeadspractice.<nickname>.challenge6. Also, add a comment with your nickname in the beginning of the file.

When you’re done with that, send the file(s), together with a nickname, and optionally degree, year and university (if it is not University of Edinburgh) to uoeadspractice a t gmail d o t com. The deadline for submitting your code is Sunday 28 October 2012 2359 GMT.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: