MOCHA 0.9
/usr/src/RPM/BUILD/CoinMOCHA-1.0.0/MOCHA/src/graph.h
Go to the documentation of this file.
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
 All Classes Files Functions Variables Friends Defines