# 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 10^{6} nodes and 10^{7} 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 10^{4} 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.