/***************************************************************************
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. |