graph.h

eC++编译器源码

/* Definition Module for a Graph */

#pragma Graph
#include <SYSTEM.h>
 

typedef enum  {Directed, UnDirected} GraphType;
typedef void *Vertex ;
typedef void *Graph  ;
typedef void *SubIterator ;
typedef void *ReachIterator ;
typedef void *AllEdgeIterator ;
typedef void *AllIterator ;

void OpenGraph ( Graph &newgraph,
                          GraphType graphtype,
                          unsigned int maxvertex,
                          unsigned int maxedge);

          /* Initialize a Graph which can hold as many as maxvertex
             vertices and maxedge edges.                             */


void CloseGraph ( Graph &oldgraph);

          /* Deallocate a Graph.  */

void CopyGraph ( Graph source,
                      Graph &dest);

          /* Copy a graph with all vertices, edges, and data
             pointers */

boolean OpenVertex (Graph &graph,
                        WORD &udata[],
                        Vertex &newvertex);

          /* Initialize a vertex which references the user-
             supplied udata.  Return FALSE if all allowed
             vertices have been allocated.                 */


void StorePointer (Graph &graph,
                         Vertex &vertex,
                         WORD &newudata[]);

            /* re-set the data pointer on an existing
               vertex */

void CloseVertex (Graph &graph, Vertex &vertex);

           /* close a vertex and all associated edges */

ADDRESS GetPointer (Graph graph, Vertex vertex);

          /* Return the user's data pointer associated with
             a vertex. NIL indicates an invalid graph or vertex. */

boolean AddEdge (Graph &graph, Vertex v1, Vertex v2,
                      WORD &udata[]);

           /* Add an edge between two previously initalized 
              vertices.  Return FALSE if all allocated edges
              have been used.  

              This routine adds a NEW edge in CONSTANT time.
              If an edge already exists between v1 and v2,
              the graph will be put in an inconsistent state!  */

boolean StoreEdge (Graph &graph, Vertex v1, Vertex v2,
                      WORD &udata[]);

           /* Add an edge between two previously initalized 
              vertices.  Return FALSE if all allocated edges
              have been used.  
              If the edge already exists, the weight will
              be changed to the new value. */

ADDRESS TestEdge (Graph graph,
                     Vertex v1, Vertex v2);

           /* Tests for an edge between v1 and v2.  If an edge
              exists, returns the user's edge data pointer.
              If there is no edge, returns NULL */


void CloseEdge (Graph  graph,
                       Vertex v1, Vertex v2);

           /* Close the edge between v1 and v2. */


unsigned int GetNVertex (Graph graph);

/* how many vertices are in the graph? */

unsigned int GetNEdge (Graph graph);

/* how many edges are in the graph? */

unsigned int GetNeighbors (Graph graph, 
                          Vertex sourcevert,
                          Vertex &nbrlist[]);

            /* put the vertices adjacent to sourcevert into nbrlist.
               Returns the number of neighbors.              
               returns all vertices with edges into or from sourcevert */

unsigned int GetChildren (Graph graph, 
                          Vertex sourcevert,
                          Vertex &nbrlist[],
                          ADDRESS &edgelist[]);

            /* put the children of sourcevert into nbrlist.
               put the corresponding edge pointers in edgelist.
               Returns the number of neighbors.              */

void OpenSubIterator (Graph graph, 
                          Vertex vertex,
                          SubIterator &iterator);                

/* allocate and open an iterator for all vertices in the same subgraph
   as "vertex" */

void CloseSubIterator (SubIterator &iterator) ;

/* de-allocate and close a SubIterator */

boolean NextSubVertex (SubIterator &Iterator,
                       Vertex &vertex);

/* get the next vertex out of a SubIterator.  Returns FALSE if
   there is no next vertex */

void OpenReachIterator (Graph graph, 
                          Vertex vertex,
                          ReachIterator &iterator);                

/* allocate and open an iterator for all vertices reachable from
   "vertex" */

void CloseReachIterator (ReachIterator &iterator);

/* de-allocate and close a ReachIterator */

boolean NextReachVertex (ReachIterator &iterator,
                            Vertex &vertex);

/* get the next vertex out of a ReachIterator.  Returns FALSE if
   there is no next vertex */

void OpenAllEdgeIterator (Graph graph,
                                AllEdgeIterator &iterator);

/*  open an iterator that returns ALL edges in a graph.  */

void CloseAllEdgeIterator (AllEdgeIterator &iterator);

boolean NextAllEdge (AllEdgeIterator &iterator,
                        Vertex &v1 , Vertex &v2,
                        ADDRESS &udata);

/* returns TRUE if there is a next edge, and sets v1,v2, and udata.
   otherwise returns FALSE */


void OpenAllIterator (Graph graph,
                            AllIterator &iterator);

/*  open an iterator that returns ALL open vertices in a graph.  */

void CloseAllIterator (AllIterator &iterator);

boolean NextAllVertex (AllIterator &iterator,
                          Vertex &v1);

/* returns TRUE if there is a next vertex, and sets v1.
   otherwise returns FALSE */