/usr/include/spooles/Network/Network.h is in libspooles-dev 2.2-9.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 | /* Network.h */
#include "../cfiles.h"
#include "../Ideq.h"
/*--------------------------------------------------------------------*/
/*
---------------------------------
forward declarations of typedef's
---------------------------------
*/
typedef struct _Network Network ;
typedef struct _Arc Arc ;
typedef struct _ArcChunk ArcChunk ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------
structure to hold a network.
nnode -- number of nodes in the network.
the source node is 0, the sink node is nnode - 1
narc -- number of arcs in the network
ntrav -- number of arcs that are traversed,
used as a measure of complexity
inheads -- array of pointers used to point to the first arc
in the in list for the nodes
outheads -- array of pointers used to point to the first arc
in the out list for the nodes
chunk -- pointer to the first ArcChunk structure
msglvl -- message level, default is 0
msgFile -- message file, default is stdout
------------------------------------------------------------
*/
struct _Network {
int nnode ;
int narc ;
int ntrav ;
Arc **inheads ;
Arc **outheads ;
ArcChunk *chunk ;
int msglvl ;
FILE *msgFile ;
} ;
/*
----------------------------------------------------------------
arc structure
vertices in the arc are (first, second). there is one arc that
is linked into the out list for vertex first and the in list for
vertex second via the nextOut and nextIn fields, respectively.
----------------------------------------------------------------
*/
struct _Arc {
int first ;
int second ;
int capacity ;
int flow ;
Arc *nextOut ;
Arc *nextIn ;
} ;
/*
---------------------------------------------------------------
structure to hold a vector of arcs, used in forming the network
when the total number of arcs is not known ahead of time.
size -- dimension of base[] array
inuse -- number of arc structures in use,
next free arc is located at &base[inuse]
base -- vector of Arc structures
next -- link to the next ArcChunk structure,
used to free the storage when finished
---------------------------------------------------------------
*/
struct _ArcChunk {
int size ;
int inuse ;
Arc *base ;
ArcChunk *next ;
} ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in basics.c --------------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------
construct a new instance of the Network object
created -- 96jun08, cca
--------------------------------------------
*/
Network *
Network_new (
void
) ;
/*
---------------------------------------------
set the default fields of the Network object
created -- 96jun08, cca
---------------------------------------------
*/
void
Network_setDefaultFields (
Network *network
) ;
/*
---------------------------------------------
clear the data fields for a Network object
created -- 96jun08, cca
---------------------------------------------
*/
void
Network_clearData (
Network *network
) ;
/*
------------------------
free the Network object
created -- 96jun08, cca
------------------------
*/
void
Network_free (
Network *network
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in init.c ----------------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------------------------------------------
initialize the Network object
nnode -- number of nodes in the network, must be > 2,
source node is 0, sink node is nnode - 1
narc -- number of arcs. this value can be zero if the number
of arcs is not known at initialization time.
storage for the arcs will grow as needed
created -- 96jun08, cca
-------------------------------------------------------------
*/
void
Network_init (
Network *network,
int nnode,
int narc
) ;
/*
---------------------------------
purpose -- set the message fields
created -- 96oct23, cca
---------------------------------
*/
void
Network_setMessageInfo (
Network *network,
int msglvl,
FILE *msgFile
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in addArc.c --------------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------
add an arc to the network
created -- 96jun08, cca
-------------------------
*/
void
Network_addArc (
Network *network,
int firstNode,
int secondNode,
int capacity,
int flow
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in findAugmentingPath.c --------------------------
------------------------------------------------------------------------
*/
/*
-----------------------------------------------------------------
find an augmenting path from the source to the sink through node.
node -- (source, node) is an arc below capacity
delta -- capacity(source, node) - flow(source, node)
tag -- tag used to build this traversal tree
deq -- dequeue object to handle traversal,
out-nodes get put at head of list,
in-nodes get put at tail of list
tags -- tags vector for the nodes
deltas -- flow increment vector for the nodes
pred -- predecessor vector for the nodes
created -- 96jun08, cca
-----------------------------------------------------------------
*/
int
Network_findAugmentingPath (
Network *network,
int node,
int delta,
int tag,
Ideq *deq,
int tags[],
int deltas[],
int pred[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in augmentingPath.c ------------------------------
------------------------------------------------------------------------
*/
/*
----------------------------------------------------------------
given an augmenting path defined by the pred[] vector and delta,
the change in flow, augment the path from the source to the sink
created -- 86jun08, cca
----------------------------------------------------------------
*/
void
Network_augmentPath (
Network *network,
int delta,
int pred[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in findMaxFlow.c ---------------------------------
------------------------------------------------------------------------
*/
/*
----------------------------------
find the maximum flow of a network
created -- 96jun08, cca
----------------------------------
*/
void
Network_findMaxFlow (
Network *network
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in findMincut.c ----------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------------------------
mark the nodes 1 or 2 to define a min-cut,
where source in X and sink in Y.
start the search from the source node.
for x in X and y in Y
arc (x,y) is in the min-cut when flow(x,y) == capacity(x,y)
arc (y,x) is in the min-cut when flow(y,x) == 0
on return, mark[*] is filled with 1 or 2,
where the mark[source] = 1 and mark[sink] = 2
created -- 96jun08, cca
--------------------------------------------------------------
*/
void
Network_findMincutFromSource (
Network *network,
Ideq *deq,
int mark[]
) ;
/*
--------------------------------------------------------------
mark the nodes 1 or 2 to define a min-cut,
where source in X and sink in Y.
start the search from the sink node.
for x in X and y in Y
arc (x,y) is in the min-cut when flow(x,y) == capacity(x,y)
arc (y,x) is in the min-cut when flow(y,x) == 0
on return, mark[*] is filled with 1 or 2,
where the mark[source] = 1 and mark[sink] = 2
created -- 96jun08, cca
--------------------------------------------------------------
*/
void
Network_findMincutFromSink (
Network *network,
Ideq *deq,
int mark[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in IO.c ------------------------------------------
------------------------------------------------------------------------
*/
/*
----------------------------------------
print the network for debugging purposes
created -- 96jun08, cca
----------------------------------------
*/
void
Network_writeForHumanEye (
Network *network,
FILE *fp
) ;
/*
---------------------------------------------------
print the network statistics for debugging purposes
created -- 96jun08, cca
---------------------------------------------------
*/
void
Network_writeStats (
Network *network,
FILE *fp
) ;
/*--------------------------------------------------------------------*/
|