1 /* Copyright 2004,2007,2008,2010-2012,2014 IPB, Universite de Bordeaux, INRIA & CNRS 2 ** 3 ** This file is part of the Scotch software package for static mapping, 4 ** graph partitioning and sparse matrix ordering. 5 ** 6 ** This software is governed by the CeCILL-C license under French law 7 ** and abiding by the rules of distribution of free software. You can 8 ** use, modify and/or redistribute the software under the terms of the 9 ** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 10 ** URL: "http://www.cecill.info". 11 ** 12 ** As a counterpart to the access to the source code and rights to copy, 13 ** modify and redistribute granted by the license, users are provided 14 ** only with a limited warranty and the software's author, the holder of 15 ** the economic rights, and the successive licensors have only limited 16 ** liability. 17 ** 18 ** In this respect, the user's attention is drawn to the risks associated 19 ** with loading, using, modifying and/or developing or reproducing the 20 ** software by the user in light of its specific status of free software, 21 ** that may mean that it is complicated to manipulate, and that also 22 ** therefore means that it is reserved for developers and experienced 23 ** professionals having in-depth computer knowledge. Users are therefore 24 ** encouraged to load and test the software's suitability as regards 25 ** their requirements in conditions enabling the security of their 26 ** systems and/or data to be ensured and, more generally, to use and 27 ** operate it in the same conditions as regards security. 28 ** 29 ** The fact that you are presently reading this means that you have had 30 ** knowledge of the CeCILL-C license and that you accept its terms. 31 */ 32 /************************************************************/ 33 /** **/ 34 /** NAME : graph.h **/ 35 /** **/ 36 /** AUTHOR : Francois PELLEGRINI **/ 37 /** Sebastien FOURESTIER (v6.0) **/ 38 /** **/ 39 /** FUNCTION : These lines are the data declarations **/ 40 /** for the source graph functions. **/ 41 /** **/ 42 /** DATES : # Version 0.0 : from : 02 dec 1992 **/ 43 /** to 18 may 1993 **/ 44 /** # Version 1.3 : from : 30 apr 1994 **/ 45 /** to 18 may 1994 **/ 46 /** # Version 2.0 : from : 06 jun 1994 **/ 47 /** to 18 aug 1994 **/ 48 /** # Version 3.0 : from : 07 jul 1995 **/ 49 /** to 28 sep 1995 **/ 50 /** # Version 3.1 : from : 28 nov 1995 **/ 51 /** to 28 nov 1995 **/ 52 /** # Version 3.2 : from : 07 sep 1996 **/ 53 /** to 15 sep 1998 **/ 54 /** # Version 3.3 : from : 28 sep 1998 **/ 55 /** to 23 mar 1999 **/ 56 /** # Version 3.4 : from : 20 mar 2000 **/ 57 /** to 20 mar 2000 **/ 58 /** # Version 4.0 : from : 24 nov 2001 **/ 59 /** to 03 mar 2006 **/ 60 /** # Version 5.0 : from : 03 mar 2006 **/ 61 /** to 01 jun 2008 **/ 62 /** # Version 5.1 : from : 11 aug 2010 **/ 63 /** to 04 nov 2010 **/ 64 /** # Version 6.0 : from : 03 mar 2011 **/ 65 /** to 09 aug 2014 **/ 66 /** **/ 67 /************************************************************/ 68 69 #define GRAPH_H 70 71 /* 72 ** The defines. 73 */ 74 75 /*+ Graph option flags. +*/ 76 77 #define GRAPHNONE 0x0000 /* No options set */ 78 79 #define GRAPHFREEEDGE 0x0001 /* Free edgetab array */ 80 #define GRAPHFREEVERT 0x0002 /* Free verttab array */ 81 #define GRAPHFREEVNUM 0x0004 /* Free vnumtab array */ 82 #define GRAPHFREEOTHR 0x0008 /* Free all other arrays */ 83 #define GRAPHFREETABS 0x000F /* Free all graph arrays */ 84 #define GRAPHVERTGROUP 0x0010 /* All vertex arrays grouped */ 85 #define GRAPHEDGEGROUP 0x0020 /* All edge arrays grouped */ 86 87 #define GRAPHBITSUSED 0x003F /* Significant bits for plain graph routines */ 88 #define GRAPHBITSNOTUSED 0x0040 /* Value above which bits not used by plain graph routines */ 89 90 #define GRAPHIONOLOADVERT 1 /* Remove vertex loads on loading */ 91 #define GRAPHIONOLOADEDGE 2 /* Remove edge loads on loading */ 92 93 /* 94 ** The type and structure definitions. 95 */ 96 97 #ifndef GNUMMAX /* If dgraph.h not included */ 98 typedef INT Gnum; /* Vertex and edge numbers */ 99 typedef UINT Gunum; /* Unsigned type of same width */ 100 #define GNUMMAX (INTVALMAX) /* Maximum signed Gnum value */ 101 #define GNUMSTRING INTSTRING /* String to printf a Gnum */ 102 #endif /* GNUMMAX */ 103 104 /*+ The vertex part type, in compressed form. +*/ 105 106 typedef byte GraphPart; 107 108 /*+ The vertex list structure. Since a vertex list 109 always refers to a given graph, vertex indices 110 contained in the vertex list array are based with 111 respect to the base value of the associated graph. 112 However, the array itself is not based. +*/ 113 114 typedef struct VertList_ { 115 Gnum vnumnbr; /*+ Number of vertices in list +*/ 116 Gnum * vnumtab; /*+ Pointer to vertex array +*/ 117 } VertList; 118 119 /*+ The graph flag type. +*/ 120 121 typedef int GraphFlag; /*+ Graph property flags +*/ 122 123 /*+ The graph parallel context structure. +*/ 124 125 typedef struct GraphProc_ { 126 #ifdef SCOTCH_PTSCOTCH 127 MPI_Comm proccomm; /*+ Communicator used for parallel algorithm +*/ 128 int procglbnbr; /*+ Number of processes in communicator +*/ 129 int proclocnum; /*+ Rank of process in current communicator +*/ 130 #endif /* SCOTCH_PTSCOTCH */ 131 } GraphProc; 132 133 /*+ The graph structure. +*/ 134 135 typedef struct Graph_ { 136 GraphFlag flagval; /*+ Graph properties +*/ 137 Gnum baseval; /*+ Base index for edge/vertex arrays +*/ 138 Gnum vertnbr; /*+ Number of vertices in graph +*/ 139 Gnum vertnnd; /*+ Number of vertices in graph, plus baseval +*/ 140 Gnum * verttax; /*+ Vertex array [based] +*/ 141 Gnum * vendtax; /*+ End vertex array [based] +*/ 142 Gnum * velotax; /*+ Vertex load array (if present) +*/ 143 Gnum velosum; /*+ Overall graph vertex load +*/ 144 Gnum * vnumtax; /*+ Vertex number in ancestor graph +*/ 145 Gnum * vlbltax; /*+ Vertex label (from file) +*/ 146 Gnum edgenbr; /*+ Number of edges (arcs) in graph +*/ 147 Gnum * edgetax; /*+ Edge array [based] +*/ 148 Gnum * edlotax; /*+ Edge load array (if present) +*/ 149 Gnum edlosum; /*+ Sum of edge (in fact arc) loads +*/ 150 Gnum degrmax; /*+ Maximum degree +*/ 151 GraphProc * procptr; /*+ Pointer to parallel context (if any) +*/ 152 } Graph; 153 154 /* 155 ** The function prototypes. 156 */ 157 158 #ifndef GRAPH 159 #define static 160 #endif 161 162 int listInit (VertList *); 163 void listExit (VertList *); 164 int listAlloc (VertList *, Gnum); 165 int listFree (VertList *); 166 int listLoad (VertList *, FILE *); 167 int listSave (VertList *, FILE *); 168 void listSort (VertList *); 169 int listCopy (VertList *, VertList *); 170 171 int graphInit (Graph * const); 172 void graphExit (Graph * const); 173 void graphFree (Graph * const); 174 Gnum graphBase (Graph * const, const Gnum); 175 int graphBand (const Graph * restrict const, const Gnum, Gnum * restrict const, const Gnum, Gnum * restrict * restrict const, Gnum * restrict const, Gnum * restrict const, Gnum * restrict const, const Gnum * restrict const, Gnum * restrict const); 176 int graphCheck (const Graph *); 177 int graphInduceList (const Graph * const, const VertList * const, Graph * const); 178 int graphInducePart (const Graph * const, const GraphPart *, const Gnum, const GraphPart, Graph * const); 179 int graphLoad (Graph * const, FILE * const, const Gnum, const GraphFlag); 180 int graphLoad2 (const Gnum, const Gnum, const Gnum * const, const Gnum * const, Gnum * restrict const, const Gnum, const Gnum * const); 181 int graphSave (const Graph * const, FILE * const); 182 183 #ifdef GEOM_H 184 int graphGeomLoadChac (Graph * restrict const, Geom * restrict const, FILE * const, FILE * const, const char * const); 185 int graphGeomSaveChac (const Graph * restrict const, const Geom * restrict const, FILE * const, FILE * const, const char * const); 186 int graphGeomLoadHabo (Graph * restrict const, Geom * restrict const, FILE * const, FILE * const, const char * const); 187 int graphGeomLoadMmkt (Graph * restrict const, Geom * restrict const, FILE * const, FILE * const, const char * const); 188 int graphGeomSaveMmkt (const Graph * restrict const, const Geom * restrict const, FILE * const, FILE * const, const char * const); 189 int graphGeomLoadScot (Graph * restrict const, Geom * restrict const, FILE * const, FILE * const, const char * const); 190 int graphGeomSaveScot (const Graph * restrict const, const Geom * restrict const, FILE * const, FILE * const, const char * const); 191 #endif /* GEOM_H */ 192 193 #undef static 194