/* Graph.h */ #include "../IVL.h" #include "../IV.h" #include "../cfiles.h" /*--------------------------------------------------------------------*/ /* --------------------------------------------------------------- The Graph object represents one of three types of graphs, defined by its "type" field. The Graph object uses IVL objects to store the vertex adjacency lists and edge weight lists (for types 2 and 3). The Graph object also supports graphs with "boundaries". This need arose from ordering graphs using constrained minimum degree where boundary vertices contribute to the degree but are not eliminated. created : 95-sep27, cca --------------------------------------------------------------- */ /*--------------------------------------------------------------------*/ /* --------------------------------------------------------- data fields type -- type of graph type vertices weighted? edges weighted? 0 no no 1 yes no 2 no yes 3 yes yes nvtx -- number of vertices, also equals adjIVL->nlist and ewghtIVL->nlist nvbnd -- number of boundary vertices nedges -- number of edges, also equals adjIVL->tsize and ewghtIVL->tsize totvwght -- total vertex weight totewght -- total edge weight adjIVL -- IVL object that holds the adjacency lists vwghts -- int vector that holds the vertex weights, size nvtx + nvbnd, not NULL if type % 2 == 1 ewghtIVL -- IVL object that holds the edge weight lists, not NULL if type >= 2 --------------------------------------------------------- */ typedef struct _Graph Graph ; struct _Graph { int type ; int nvtx ; int nvbnd ; int nedges ; int totvwght ; int totewght ; IVL *adjIVL ; int *vwghts ; IVL *ewghtIVL ; } ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in basics.c ------------------------------------------- ------------------------------------------------------------------------ */ /* ----------------------------------------------- purpose -- create and return a new Graph object created -- 95sep27, cca ----------------------------------------------- */ Graph * Graph_new ( void ) ; /* ------------------------------------------------------ purpose -- set the default fields for the Graph object created -- 95sep27, cca ------------------------------------------------------ */ void Graph_setDefaultFields ( Graph *g ) ; /* -------------------------------- purpose -- clear the data fields created -- 95sep27, cca -------------------------------- */ void Graph_clearData ( Graph *g ) ; /* -------------------------------- purpose -- free the Graph object created -- 95sep27, cca -------------------------------- */ void Graph_free ( Graph *g ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in compress.c ----------------------------------------- ------------------------------------------------------------------------ */ /* --------------------------------------------------------------- given a graph g and a fine-to-coarse map vector cmap[], return a compressed graph with type coarseType. note, the compressed graph will have no trivial boundary even if the original graph did have a boundary. created -- 95sep29, cca --------------------------------------------------------------- */ Graph * Graph_compress ( Graph *g, int cmap[], int coarseType ) ; /* --------------------------------------------------------------- given a graph g and a fine-to-coarse map vector *mapIV, return a compressed graph with type coarseType. note, the compressed graph will have no trivial boundary even if the original graph did have a boundary. created -- 96mar02, cca --------------------------------------------------------------- */ Graph * Graph_compress2 ( Graph *g, IV *mapIV, int coarseType ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in equivMap.c ----------------------------------------- ------------------------------------------------------------------------ */ /* ----------------------------------------------------------- fill an IV object with an equivalence map if ( map[u] == map[v] ) then then u and v are adjacent to the same vertices endif NOTE : each empty list is mapped to a different value return value -- IV object that contains the equivalence map created -- 96feb23, cca ----------------------------------------------------------- */ IV * Graph_equivMap ( Graph *g ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in expand.c ------------------------------------------- ------------------------------------------------------------------------ */ /* --------------------------------------------------------------------- purpose -- take a Graph object and a map to expand it, create and return a bigger unit weight Graph object. this is useful for expanding a compressed graph into a unit weight graph. created -- 96mar02, cca --------------------------------------------------------------------- */ Graph * Graph_expand ( Graph *g, int nvtxbig, int map[] ) ; /* --------------------------------------------------------------------- purpose -- take a Graph object and a map to expand it, create and return a bigger unit weight Graph object. this is useful for expanding a compressed graph into a unit weight graph. created -- 96mar02, cca --------------------------------------------------------------------- */ Graph * Graph_expand2 ( Graph *g, IV *mapIV ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in fillFromOffsets.c ---------------------------------- ------------------------------------------------------------------------ */ /* ------------------------------------------------------------------- purpose -- take an adjacency structure in the (offsets[neqns+1], adjncy[*]) form and load the Graph object g -- pointer to Graph object, must be initialized with nvtx = neqns neqns -- # of equations offsets -- offsets vector adjncy -- big adjacency vector note, the adjacency for list v is found in adjncy[offsets[v]:offsets[v+1]-1] also note, offsets[] and adjncy[] must be zero based, if (offsets,adjncy) come from a harwell-boeing file, they use the fortran numbering, so each value must be decremented to conform with C's zero based numbering flag -- task flag flag = 0 --> just set the adjacency list for v to be that found in adjncy[offsets[v]:offsets[v+1]-1] flag = 1 --> the input adjancency is just the upper triangle (or strict upper triangle) as from a harwell-boeing file. fill the Graph object with the full adjacency structure, including (v,v) edges created -- 96mar16, cca ------------------------------------------------------------------- */ void Graph_fillFromOffsets ( Graph *g, int neqns, int offsets[], int adjncy[], int flag ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in init.c --------------------------------------------- ------------------------------------------------------------------------ */ /* --------------------------------------------- basic initializer for the Graph object type -- graph type nvtx -- # of vertices nvbnd -- # of boundary vertices nedges -- # of edges adjType -- IVL type for adjacency object ewghtType -- IVL type for edge weights object created -- 95sep27, cca --------------------------------------------- */ void Graph_init1 ( Graph *g, int type, int nvtx, int nvbnd, int nedges, int adjType, int ewghtType ) ; /* -------------------------------------------------------- second initializer for the Graph object. this function is used in the I/O routines Graph_readFromFormattedFile(Graph *g, FILE *fp) and Graph_readFromBinaryFile(Graph *g, FILE *fp) where the IVL object(s) and vwghts[] vector are created independently. type -- graph type nvtx -- # of vertices nvbnd -- # of boundary vertices nedges -- # of edges totvwght -- total vertex weight totewght -- total edge weight adjIVL -- IVL object for adjacency structure vwghts -- pointer to integer vector for vertex weights ewghtIVL -- IVL object for edge weights created -- 95sep27, cca -------------------------------------------------------- */ void Graph_init2 ( Graph *g, int type, int nvtx, int nvbnd, int nedges, int totvwght, int totewght, IVL *adjIVL, int *vwghts, IVL *ewghtIVL ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in util.c --------------------------------------------- ------------------------------------------------------------------------ */ /* --------------------------------------------------------------------- return the external degree (in terms of vertex weight) of vertex v created -- 95oct05, cca --------------------------------------------------------------------- */ int Graph_externalDegree ( Graph *g, int v ) ; /* ----------------------------------- method to access the adjacency list created -- 95oct05, cca ----------------------------------- */ void Graph_adjAndSize ( Graph *g, int jvtx, int *psize, int **padj ) ; /* ----------------------------------------------- method to access the adjacency list and possibly the edge weight list for a vertex. created -- 95sep29, cca ----------------------------------------------- */ void Graph_adjAndEweights ( Graph *g, int jvtx, int *psize, int **padj, int **pewghts ) ; /* ---------------------------------------------------- return the number of bytes taken by the Graph object created -- 95oct05, cca ---------------------------------------------------- */ int Graph_sizeOf ( Graph *g ) ; /* -------------------------------------- create and return an IV object filled with a map from vertices to components created -- 96feb25, cca -------------------------------------- */ IV * Graph_componentMap ( Graph *g ) ; /* ----------------------------------------------------------------- given a Graph g and map from vertices to components, fill counts[icomp] with the number of vertices in component icomp and fill weight[icomp] with their weight created -- 96feb25, cca ----------------------------------------------------------------- */ void Graph_componentStats ( Graph *g, int map[], int counts[], int weights[] ) ; /* ------------------------------------------------------------------- create and return a subgraph and a map from its vertices to the vertices of the graph. g -- graph from which to extract the subgraph icomp -- component from which comes the vertices of the subgraph, icomp > 0 compids -- component ids vector of graph pmap -- pointer to hold address of map vector, the map from the subgraph's vertices to the graph's vertices return value -- pointer to subgraph Graph object created -- 95nov10, cca ------------------------------------------------------------------- */ Graph * Graph_subGraph ( Graph *g, int icomp, int compids[], int **pmap ) ; /* ---------------------------------- return 1 if the graph is symmetric return 0 otherwise created -- 96oct31, cca ---------------------------------- */ int Graph_isSymmetric ( Graph *graph ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in polar.c -------------------------------------------- ------------------------------------------------------------------------ */ /* ----------------------------------------------------------- perform a breadth-first search v -- vertex to check out levelsIV -- IV object that holds the levels vector listIV -- IV object to hold order of search parIV -- IV object to hold parent vector return value -- depth of the search tree created -- 96jul13, cca ----------------------------------------------------------- */ int Graph_BFS ( Graph *graph, int v, IV *levelsIV, IV *listIV, IV *parIV ) ; /* ------------------------------------------------------------ perform a breadth-first search from a list of seed vertices. seedsIV -- IV object that holds the seed vertices levelsIV -- IV object that holds the levels vector listIV -- IV object to hold order of search parIV -- IV object to hold parent vector return value -- depth of the search tree created -- 96jul19, cca ------------------------------------------------------------ */ int Graph_BFS2 ( Graph *graph, IV *seedsIV, IV *levelsIV, IV *listIV, IV *parIV ) ; /* ---------------------------------------------------------- find a pseudodiameter of a graph. fill *pstart and *pend with the endpoint vertices. fill startLevelsIV and endLevelsIV with the level vectors for the BFS from the start and end vertices, respectively. created -- 96jul13, cca ---------------------------------------------------------- */ void Graph_pseudodiameter ( Graph *g, int root, IV *startLevelsIV, IV *endLevelsIV, int *pstart, int *pend ) ; /* ---------------------------------------------------------- create and return an IV object that contains a list of vertices that are in the major axis of the graph. we have dropped two levels structures from end vertices to approximate the diameter of the graph. a vertex v is in the major axis if levels1[v] + levels2[v] - tolerance <= d(s,e) fill *pstart and *pend with the endpoint vertices. created -- 96jul13, cca ---------------------------------------------------------- */ IV * Graph_majorAxis ( Graph *graph, int vstart, int vend, IV *startLevelsIV, IV *endLevelsIV, int tolerance ) ; /* ----------------------------------------------------------- compute and return the polar moment of inertia for a vertex v -- vertex to check out levelsIV -- IV object that holds the levels vector listIV -- IV object for workspace created -- 96jul13, cca ----------------------------------------------------------- */ double Graph_polarMoment ( Graph *graph, int v, IV *levelsIV, IV *listIV ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in setListsFromOffsets.c ------------------------------ ------------------------------------------------------------------------ */ /* ------------------------------------------------------------------- purpose -- take an adjacency structure in the (offsets[neqns+1], adjncy[*]) form and load the Graph object. note, pointers to the lists are set, no new storage is allocated for the adjacency lists. however, during the ordering process each adjacency lists may be shuffled. g -- pointer to Graph object, must be initialized with nvtx = neqns neqns -- # of equations offsets -- offsets vector adjncy -- big adjacency vector note, the adjacency for list v is found in adjncy[offsets[v]:offsets[v+1]-1] also note, offsets[] and adjncy[] must be zero based, if (offsets,adjncy) come from a harwell-boeing file, they use the fortran numbering, so each value must be decremented to conform with C's zero based numbering created -- 96oct24, cca ------------------------------------------------------------------- */ void Graph_setListsFromOffsets ( Graph *g, int neqns, int offsets[], int adjncy[] ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in wirebasket.c --------------------------------------- ------------------------------------------------------------------------ */ /* ----------------------------------------------------------- on input stages[v] = 0 --> vertex is in a domain stages[v] > 0 --> vertex is in the multisector this remains true on output, but the stage of a multisector vertex is equal to the number of different domains that are found within radius edges from itself created -- 97jul30, cca ----------------------------------------------------------- */ void Graph_wirebasketStages ( Graph *graph, IV *stagesIV, int radius ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in IO.c ----------------------------------------------- ------------------------------------------------------------------------ */ /* ------------------------------------------------- purpose -- to read in a Graph object from a file input -- fn -- filename, must be *.graphb or *.graphf return value -- 1 if success, 0 if failure created -- 95sep29, cca ------------------------------------------------- */ int Graph_readFromFile ( Graph *graph, char *fn ) ; /* ------------------------------------------------------- purpose -- to read in a Graph object from a CHACO file input -- fn -- filename return value -- 1 if success, 0 if failure created -- 98sep20, jjs -------------------------------------------------------- */ int Graph_readFromChacoFile ( Graph *graph, char *fn ) ; /* -------------------------------------------------------- purpose -- to read a Graph object from a formatted file return value -- 1 if success, 0 if failure created -- 95sep29, cca -------------------------------------------------------- */ int Graph_readFromFormattedFile ( Graph *graph, FILE *fp ) ; /* ---------------------------------------------------- purpose -- to read a Graph object from a binary file return value -- 1 if success, 0 if failure created -- 95sep29, cca ---------------------------------------------------- */ int Graph_readFromBinaryFile ( Graph *graph, FILE *fp ) ; /* -------------------------------------------- purpose -- to write a Graph object to a file input -- fn -- filename *.graphb -- binary *.graphf -- formatted anything else -- for human eye return value -- 1 if success, 0 otherwise created -- 95sep29, cca -------------------------------------------- */ int Graph_writeToFile ( Graph *graph, char *fn ) ; /* ------------------------------------------------------ purpose -- to write a Graph object to a formatted file return value -- 1 if success, 0 otherwise created -- 95sep29, cca ------------------------------------------------------ */ int Graph_writeToFormattedFile ( Graph *graph, FILE *fp ) ; /* --------------------------------------------------- purpose -- to write a Graph object to a binary file return value -- 1 if success, 0 otherwise created -- 95sep29, cca --------------------------------------------------- */ int Graph_writeToBinaryFile ( Graph *graph, FILE *fp ) ; /* ------------------------------------------------- purpose -- to write a Graph object for a human eye return value -- 1 if success, 0 otherwise created -- 95sep29, cca ------------------------------------------------- */ int Graph_writeForHumanEye ( Graph *graph, FILE *fp ) ; /* ----------------------------------------------------------- purpose -- to write out the statistics for the Graph object return value -- 1 if success, 0 otherwise created -- 95sep29, cca ----------------------------------------------------------- */ int Graph_writeStats ( Graph *graph, FILE *fp ) ; /* --------------------------------- write out a graph to a METIS file created -- 95oct18, cca --------------------------------- */ int Graph_writeToMetisFile ( Graph *g, FILE *fp ) ; /*--------------------------------------------------------------------*/ /* ------------------------------------------------------------------------ ---- functions in getTree.c ------------------------------------------ ------------------------------------------------------------------------ */ /* ------------------------------------------------- purpose -- to extract a maximal tree from a graph on input, if mark[v] == 'N' then v is eligible to be placed in the tree endif i.e., mark[] serves as a mask vector on return, if ( mark[v] == 'Y' ) then v is in the tree, parent of v = par[v] else mark[v] = 'N', not in tree endif created -- 98apr10, cca ------------------------------------------------- */ void Graph_getTree ( Graph *graph, int par[], char mark[], int seed, int msglvl, FILE *msgFile ) ; /* -------------------------------------------------------- purpose -- to extract a maximal nlevel-tree from a graph (a vertex v can have an edge in the graph with itself and any ancestor within nlevel levels in the tree.) on input, if mark[v] == 'N' then v is eligible to be placed in the tree endif i.e., mark[] serves as a mask vector on return, if ( mark[v] == 'Y' ) then v is in the tree, parent of v = par[v] else mark[v] = 'N', not in tree endif created -- 98apr10, cca -------------------------------------------------------- */ void Graph_getTree2 ( Graph *graph, int nlevel, int par[], char mark[], int seed, int msglvl, FILE *msgFile ) ; /*--------------------------------------------------------------------*/