MOCHA
0.9
|
00001 // Copyright 2009 by Jesus De Loera, David Haws, Jon Lee, Allison O'Hair, University 00002 // of California at Davis, IBM, Inc. All rights reserved. 00003 // 00004 // Distributed under the Eclipse Public License v 1.0. See ../LICENSE 00005 00006 // $Rev$ $Date$ 00007 00009 #ifndef GRAPH_H 00010 #define GRAPH_H 00011 00012 #include <iostream> 00013 #include "matrix.h" 00014 #include <set> 00015 #include <map> 00016 #include <vector> 00017 #include <list> 00018 00019 00020 //set <unsigned> setUnionUnsigned (set <unsigned> &, set <unsigned> &); 00021 //set <unsigned> setDifferenceUnsigned (set <unsigned> &, set <unsigned> &); 00022 00023 00024 // The primary data structure of the graph will be its adjacency matrix 00025 // Will not change underlying graph data. Using copying and functions 00026 // for such things. 00027 00028 class VertexBucket 00029 { 00030 public: 00031 list <unsigned> vertices; 00032 int r; 00033 VertexBucket(int rvalue); 00034 protected: 00035 }; 00036 00037 class Graph 00038 { 00039 public: 00040 Graph (); 00041 ~Graph (); 00042 Graph (const Graph &G); 00043 Graph (Matrix &M); // Creates a graph based off an adjacency matrix M 00044 Graph &operator = (const Graph &G); 00045 Graph (std::istream &in); 00046 00047 friend std::ostream &operator<< (std::ostream &o, const Graph &G); 00048 friend std::istream &operator>> (std::istream &in, Graph &G); 00049 00050 // This is an implementation of Matsui's reverse-search spanning tree enumeration algorithm. 00051 // It takes as input a spanning tree T and H(T) (see Matsui), and an index of the edges as 00052 // a Matrix. We use a modified version for better space complexity. 00053 // If edge e has incident vertices i and j, then (i,j) is the index of e. 00054 // The ordering of the edge index is assumed to be given by Nagamachi and Ibaraki (Allison's part). 00055 // It is a BFS procedure, so it will recurse on itself. 00056 // Currently it will print out all spanning trees to standard output. 00057 // G is the underlying graph, initTree is the first tree given by order edgeIndex. 00058 // The current tree we care about is initTree\g union f. 00059 // initTree, f, g are all edges indexed according to G. 00060 // printMod specifies the mod value to print tree count. 0 none 00061 friend void findChildren(Graph &G, set <unsigned> &initTree, set <unsigned> &deltaf, set <unsigned> &deltag, set <unsigned> deltaH, Matrix &edgeIndex, unsigned printMod, unsigned printTrees); 00062 00063 friend void findChildren(Graph &G, set <unsigned> &initTree, set <unsigned> &deltaf, set <unsigned> &deltag, set <unsigned> deltaH, Matrix &edgeIndex, Matrix &Weight, set <Matrix, ltcolvec> &projTrees, unsigned printMod, unsigned printTrees); 00064 00065 00066 // This will return the ``bottom'' edge of this graph as given by edgeIndex 00067 // Returns edge with lowest index. Returns this graphs edge index, NOT index provided. 00068 unsigned MatsuiBottom(Matrix &edgeIndex); 00069 unsigned MatsuiBottom(Matrix &edgeIndex, set <unsigned> &someEdges); 00070 00071 // This will return the ``top'' edge of this graph as given by edgeIndex 00072 // Returns edge with highest index. Returns this graphs edge index, NOT index provided. 00073 unsigned MatsuiTop(Matrix &edgeIndex); 00074 unsigned MatsuiTop(Matrix &edgeIndex, set <unsigned> &someEdges); 00075 00076 // returns the edge index of someEdge given by the matrix edgeIndex 00077 unsigned getEdgeIndex(unsigned someEdge, Matrix &edgeIndex); 00078 00079 // Returns a subgraph with same number of nodes but only 00080 // Those edges in someEdges 00081 Graph subGraph(set <unsigned> &someEdges); 00082 Graph subGraph(list <vector <unsigned> > &someEdges); 00083 00084 // Returns a subgraph with same number of nodes but only 00085 // Those edges NOT in someEdges 00086 Graph subGraphDiff(set <unsigned> &someEdges); 00087 Graph subGraphDiff(list <vector <unsigned> > &someEdges); 00088 00089 // This returns a matrix of same size of adjMatrix where 00090 // (i,j) = 1 if there exists a path between i and j 00091 // Computes the transitive closure 00092 // Saves an internal copy of transitive closure 00093 Matrix connComp (); 00094 00095 // Returns 1 if the two nodes are connected on this graph. 00096 // Uses transitive closure and computes it if first call 00097 int nodesConnected(int, int); 00098 00099 void readGraph (std::istream &in); 00100 00101 // Returns the edges of a random spanning forest 00102 // Uses BFS 00103 // This also computes this graphs number of connected components 00104 set <unsigned> randSpanningForest(); 00105 00106 // Same as above but it will set cycleFree to 1 if 00107 // the underlying graph is cycle free. 0 else. 00108 set <unsigned> randSpanningForest(int &cycleFree); 00109 00110 // Returns 1 if someEdges is a spanning forest. 0 Else. 00111 int isSpanningForest (list <vector <unsigned> > someEdges); 00112 00113 // Returns 1 if someEdges is a spanning forest. 0 Else. 00114 int isSpanningForest (set <unsigned> someEdges); 00115 00116 // Returns 1 if someEdges is cycle free. 0 Else. 00117 int isCycleFree (set <unsigned> someEdges); 00118 00119 // Returns the shortest path (as edge subset) 00120 // Uses FloydWarshall. Computes predMatrix needed. 00121 set <unsigned> shortestPath (unsigned n1, unsigned n2); 00122 00123 // Returns the shortest path (as edge subset) 00124 // Uses FloydWarshall. Computes predMatrix needed. 00125 list <vector <unsigned> > shortestPathList (unsigned n1, unsigned n2); 00126 00127 // Converts a list of edges given by end nodes to a set of their edge numbers 00128 set <unsigned> listEdgesToSet (list <vector <unsigned> > &); 00129 00130 int getNumConnComponents (); 00131 int rank(); 00132 int getNumEdges (); 00133 void deleteDoubleArray(int **, int); 00134 00135 // This performs Floyd-Warshall's algorithm to find all pairs shortest 00136 //paths. It returns the predecessor matrix 00137 Matrix FloydWarshall (); 00138 00139 // Nagamochi Ibariki Algorithm. To be implemented by Allison 00140 list <set <unsigned> > NagIbar(); 00141 00142 // This takes the output of NagIbar and returns a matrix which indexes 00143 // the edges given by the input. The index of each set is orbitally chosen 00144 Matrix calcEdgeIndex(list <set <unsigned> > &); 00145 00146 // This compares if a <= b + c where we assume a,b,c are non-negative and -1 means infinity 00147 // Returns 1 if a <= b + c, 0 else. If a and (b or c) is infinity return -1 00148 int leftLessThanEqualRight (double a, double b, double c); 00149 00150 void edgeToNode(unsigned someEdge, unsigned &, unsigned &); 00151 00152 void static edgeToNodeEdgeIndex(unsigned someEdge, unsigned &, unsigned &, Matrix &edgeIndex); 00153 00154 // Returns edge number between nodes (a,b) 00155 // Returns -1 if (a,b) is not an edge 00156 unsigned edgeNumber(int a, int b); 00157 00158 // Print out the vertex edge matrix. Prints with arbitrary directions to edges 00159 void printVertexEdgeMatrix(); 00160 00161 unsigned findChildrenSpanningTreeCount; 00162 unsigned findChildrenBFSLevel; 00163 protected: 00164 // Returns a random adjacent node to startNode. 00165 // If no node exists, returns startNode 00166 //unsigned randAdjNode(unsigned startNode); 00167 void initGraph (); 00168 // The edges are ordered from upper left to lower right as read on the adjMatrix 00169 Matrix adjMatrix; 00170 Matrix nodesToEdgeNumber; // This simplifies retrieving edge numbers based on nodes 00171 map <unsigned, vector <unsigned> > edges; 00172 int numEdges; 00173 int numNodes; 00174 int numConnComponents; 00175 Matrix transClosure; 00176 int transClosureComputed; 00177 int predMatrixComputed; 00178 Matrix predMatrix; 00179 }; 00180 #endif