class Graph

Public Types

• enum Geometry {SIMPLE_SQUARE, SIMPLE_CUBIC}

Public Methods

•  Graph ()
•  Graph (Geometry type, int L)
• ~ Graph ()
• int  maxFlow (Vertex& s, Vertex& t)
• int  shortestPath (Vertex& s, Vertex& t,vector<Edge>& path)
• int  shortestPath (Vertex& t)
• void  bfs (Vertex& v)
• void  bbfs (Vertex& v)
• Vertex&  addVertex ()
• void  removeVertex (Vertex& v)
• Edge&  addEdge (Vertex& u, Vertex& v)
• Edge&  addEdge (Vertex& u, Vertex& v, int cap, int cost)
• void  removeEdge (Edge& e)
• Vertex&  getFirstVertex ()
• Vertex&  getLastVertex ()
• void  readEdgeWeights (istream& inputStream)
• Edge*  reverseEdge (Edge* e)
• void  writeFlowToPOV (const char* filename, int length)
• Edge*  hideEdge (Edge* e)
• void  restoreAllEdges ()
• void  writeToFile (const char* filename)
• bool  checkMaxFlow (Vertex& s,Vertex& t)

Public Members

• int relabelHeuristics
• vector<Vertex*> vertices

Private Methods

• void  setupSimpleCubic (int L)
• bool  validVertex (Vertex& v)
• void  setupSimpleSquare (int L)

Private Members

• const static int INFINITY
• list<int> freeSlots
• int lastVertex
• int maxDist
• list<Edge*> hiddenEdges
• int numberOfReachableVertices
• int numberOfEdges
• int numberOfVertices
• int linearLength

Geometry indicates the geometry a graph is mimicking. It is used for creating and displaying the graph.

Preflow-push relabel is an algorithm to find the maximum-flow/minimum cut in a capacitated network. The following procedure is implemented:

Step 1:Assign a distance label to every vertex using BFS starting from the sink.

Step 2:Add the source to the list of active vertices

Step 3:Remove the vertex a with the highest distance label from the list of active vertices. If list is empty the algortihm terminates.

Step 4:Get a list of all outgoing edges from a.

PUSH:

Step 5:If there exist a reachable vertex with smaller distance label push as much flow through as allowed by the capacity of the edge to this node up to the excess(a). Continue with 4 until all excess flow is removed from a. Otherwise RELABEL

RELABEL:

Step 6:Increase the distance label min(dist(neighbors)+1

Step 7:After N relabel operations do a global relabel as in Step 1

END

This function finds the shortest path between s and t.

This function finds the shortest path between s and t.

Returns: distance

This function performs a breadth first search starting a vertex v

This function adds a vertex with no attributes associated to it.

Returns: The new vertex

This function removes the Vertex v from the Graph. It also removes all Edges that either originate or terminate in v

This function adds an Edge connecting vertex u and v.

Returns: The new Edge

This function adds an Edge connecting vertex u and v and gives its capacity.

Returns: The new Edge

Return the first Vertex added to the Graph.

Returns a reference to the Vertex that was added to the graph last.

Edge capacities (weights) are read from a file. This way it is possible to calculate the maximum flow/minimum cut for a predefinede configuration.

The file has to be in the following format:

<!SMAGL v.0.3 : direct>

1: cap11, cap12, cap13, ... , cap1n

2: cap21, cap22, cap23, ... , cap2n

...

N: capN1, capN2, capN3, ... , capNn

Here the first line defines the format of the upcoming file In this case it is the format for a direct outgoing edge list. This means that the first label indicates the order of the vertex in which it was added to the graph and the list of capacities is the same as in its outEdge list which is again the order in which they were added.

This is defined as a direct list since it requires a direct and intimate knowledge of the way the graph is constructed. Later other formats will allow easier definition of edge capacities.

[private]

Sets up a graph that has a geometry equivalent to that of a simple cubic lattice.

Parameters:

L	Linear size of the cube

[private]

Check if Vertex v is in Graph

Parameters:

v	The vertex to be checked

Returns: true if v is in the graph, false otherwise

[private]

Creates a graph that has the symmetry of a square lattice of length L.

Parameters:

L	length of the side of the lattice

Gets the reverse edge to e. If A is the origin of e and B is the target then the reverse edge has B as its origin and A as its target.

Parameters:

e	Pointer to an Edge e

Returns: Pointer to reverse Edge to e.

Opens an output stream and writes a scene description file as used by POVRay. This file can then be rendered with POVRay to get a visual representation of the flow pattern.

Parameters:

length

Length of the edge of a cube.

Hide an edge in the graph. While an edge is hidden it effectively does does not exist for any algorithm running on the graph afterwards. The edge can be restored with unhideEdge or unhideAllEdges.

Insert all edges that were previously hidden with the hideEdge function.

Verfies that the current flow stored in the graph is a maximum flow.

[private]

INFINITY is set to 2^31-1 which should work on most newer computers. It would be much nicer to use std::numeric_limits, but it is not available everywhere. Maybe I could use conditionals and use the std::numeric_limits if available.

[private]

Keeps a record of removed vertices for reuse.

[private]

Index of the last added Vertex. It this variable is zero we have an empty graph.

[private]

maxDist found in bfs algorithm. This is used to guarantee that the source is above all other vertices.

[private]

Keeps track of hidden Edges so they can be restored.

[private]

The number of vertices reachable from t in bfs.

[private]

The number of edges in the graph.

[private]

The number of vertices in the graph

[private]

Keeps track of the original linar size of the Graph. This is obviously only relevant for cubic and other lattices that have a structure.

Number of relabel operations in the maximum flow algorithm before a global update of the distance labels.

Contains all vertices in the Graph in the order in which they were added.

• Author: Jan Meinke
• Generated: meinke@orion on Mon May 8 18:18:46 2000, using kdoc 2.0a35.