|
|
/*************************************************************************** graph.h ------------------- begin : Thu Aug 19 1999 copyright : (C) 1999 by Jan Meinke email : meinke@bigfoot.com ***************************************************************************/ /*************************************************************************** * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * ***************************************************************************/ #ifndef GRAPH_H #define GRAPH_H #include "vertex.h" #include "edge.h" #include "parser.h" //#include <limits> #include <iostream> #include <fstream> #include <string> #include <list> #include <vector> #include <queue> #include <algorithm> /**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 * *@author Jan Meinke */ class Graph { public: /** Geometry indicates the geometry a graph is mimicking. It is used for * creating and displaying the graph. */ enum Geometry {SIMPLE_SQUARE, SIMPLE_CUBIC}; // Constructors /* This creates an empty graph which is useful if you want to construct a * graph that is not predefined. */ Graph(); /* Constructs a graph imitating some simple geometric setups */ Graph(Geometry type, int L); // Destructor ~Graph(); // Accessors /** 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 * * @author Jan H. Meinke */ int maxFlow(Vertex& s, Vertex& t); /** This function finds the shortest path between s and t. */ int shortestPath(Vertex& s, Vertex& t,vector<Edge>& path); /** This function finds the shortest path between s and t. * @return distance */ int shortestPath(Vertex& t); /** This function performs a breadth first search starting a vertex v */ void bfs(Vertex& v); void bbfs(Vertex& v); // Modifiers /** This function adds a vertex with no attributes associated to it. * @return The new vertex */ Vertex& addVertex(); /** This function removes the Vertex v from the Graph. It also removes all * Edges that either originate or terminate in v */ void removeVertex(Vertex& v); /** This function adds an Edge connecting vertex u and v. * @return The new Edge */ Edge& addEdge(Vertex& u, Vertex& v); /** This function adds an Edge connecting vertex u and v and gives its * capacity. * @return The new Edge */ Edge& addEdge(Vertex& u, Vertex& v, int cap, int cost); /* This function removes an Edge from the Graph */ void removeEdge(Edge& e); /** Return the first Vertex added to the Graph. */ Vertex& getFirstVertex(); /** Returns a reference to the Vertex that was * added to the graph last. */ Vertex& getLastVertex(); /** 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 readEdgeWeights(istream& inputStream); private: // Private functions /** Sets up a graph that has a geometry equivalent to * that of a simple cubic lattice. * @param L Linear size of the cube */ void setupSimpleCubic(int L); /** Check if Vertex v is in Graph * @param v The vertex to be checked * @return true if v is in the graph, false otherwise */ bool validVertex(Vertex& v); /** Creates a graph that has the symmetry of a square lattice of length L. * *@param L length of the side of the lattice */ void setupSimpleSquare(int L); public: /** 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. * @param e Pointer to an Edge e * @return Pointer to reverse Edge to e. */ Edge* reverseEdge(Edge* 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. * @param filename * @param length Length of the edge of a cube. */ void writeFlowToPOV(const char* filename, int length); /** 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. */ Edge* hideEdge(Edge* e); /** Insert all edges that were previously hidden with the hideEdge function. */ void restoreAllEdges(); /** */ void writeToFile(const char* filename); /** Verfies that the current flow stored in the graph is a maximum flow. */ bool checkMaxFlow(Vertex& s,Vertex& t); private: // Private attributes /** 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. */ const static int INFINITY = 2147483647; /** Keeps a record of removed vertices for reuse. */ list<int> freeSlots; /** Index of the last added Vertex. It this variable is zero we have an empty graph. */ int lastVertex; /** maxDist found in bfs algorithm. This is used to guarantee that the source * is above all other vertices. */ int maxDist; /** Keeps track of hidden Edges so they can be restored. */ list<Edge*> hiddenEdges; /** The number of vertices reachable from t in bfs. */ int numberOfReachableVertices; /** The number of edges in the graph. */ int numberOfEdges; /** The number of vertices in the graph */ int numberOfVertices; /** 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 linearLength; public: /** Number of relabel operations in the maximum flow algorithm before a global * update of the distance labels. */ int relabelHeuristics; /** Contains all vertices in the Graph in the order * in which they were added. */ vector<Vertex*> vertices; }; #endif
Generated by: meinke@orion on Mon May 8 18:18:46 2000, using kdoc 2.0a35. |