/* 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 ) ; /*--------------------------------------------------------------------*/