|
|
This class represents a basic directed graph with vertices and edges. Currently I am using a list of out edges to store the edge. The vertices of the graph can be accessed through iterators as for the containers of the standard library
enum |
Geometry indicates the geometry a graph is mimicking. It is used for creating and displaying the graph.
int |
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
int |
This function finds the shortest path between s and t.
int |
This function finds the shortest path between s and t.
Returns: distance
void |
This function performs a breadth first search starting a vertex v
Vertex& |
This function adds a vertex with no attributes associated to it.
Returns: The new vertex
void |
This function removes the Vertex v from the Graph. It also removes all Edges that either originate or terminate in v
Edge& |
This function adds an Edge connecting vertex u and v.
Returns: The new Edge
Edge& |
This function adds an Edge connecting vertex u and v and gives its capacity.
Returns: The new Edge
Vertex& |
Return the first Vertex added to the Graph.
Vertex& |
Returns a reference to the Vertex that was added to the graph last.
void |
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.
void |
[private]
Sets up a graph that has a geometry equivalent to that of a simple cubic lattice.
Parameters:
L | Linear size of the cube |
bool |
[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
void |
[private]
Creates a graph that has the symmetry of a square lattice of length L.
Parameters:
L | length of the side of the lattice |
Edge* |
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.
void |
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. |
Edge* |
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.
void |
Insert all edges that were previously hidden with the hideEdge function.
void |
bool |
Verfies that the current flow stored in the graph is a maximum flow.
const static int |
[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.
list<int> |
[private]
Keeps a record of removed vertices for reuse.
int |
[private]
Index of the last added Vertex. It this variable is zero we have an empty graph.
int |
[private]
maxDist found in bfs algorithm. This is used to guarantee that the source is above all other vertices.
list<Edge*> |
[private]
Keeps track of hidden Edges so they can be restored.
int |
[private]
The number of vertices reachable from t in bfs.
int |
[private]
The number of edges in the graph.
int |
[private]
The number of vertices in the graph
int |
[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.
int |
Number of relabel operations in the maximum flow algorithm before a global update of the distance labels.
vector<Vertex*> |
Contains all vertices in the Graph in the order in which they were added.