Graph_alg(C++)

Synopsis

   #include <Graph_alg.h>
   namespace SCO_SC {
   

   //  Macros used to simulate parameterized types
   #define GApredicate(T) ... 
   #define Graph_algdeclare(G,V,E) ... 
   #define Graph_algimplement(G,V,E) ... 
   Graph_algdeclare(Graph,Vertex,Edge)   //see Graph(3C++)
   //Expanding Graph_algdeclare(G,V,E) produces
   //the following text:
   //  Auxiliary definition needed by Graph algorithms
   typedef int GApredicate(V)(const V* v);
   //  Graph algorithms
   List_of_p<V> dfs(G& g,V*
   v,GApredicate(V)* f = 0);
   List_of_p<V> dfs_u(G& g,V*
   v,GApredicate(V)* f = 0);
   . 
   .  etc. for the remaining algorithms
   . 
   }

Description

Graph Algorithms are a collection of functions implementing some of the most basic algorithms on directed and undirected Graphs. Functions with the suffix _u treat Graphs as undirected (that is, they ignore Edge directionality), while functions without this suffix treat Graphs as directed. See Graph(3C++) for a description of the base classes Graph, Edge, and Vertex, and the rules for deriving application-specific classes G, V, and E from these.

All Graph Algorithms are declared in header Graph_alg.h and within namespace SCO_SC.

The functions in this collection are parameterized by the Graph, Vertex, and Edge type. Type parameterization is simulated by two preprocessor macros, Graph_algdeclare and Graph_algimplement, both of which take three arguments specifying (respectively) the Graph, Edge, and Vertex types. As a convenience to users who would like to apply Graph Algorithms to the "vanilla" types defined in Graph(3C++), the macros are pre-expanded for Vertex, Graph and Edge; such users can ignore the following macros.

Macros used to simulate parameterized types

In all cases, parameters must be single tokens (use typedef to create typenames for complex types).

#define GApredicate(T) ... Used to create a unique typename, which you may write as either GApredicate(T) or T_GA_predicate.

#define Graph_algdeclare(G,V,E) ... Expanding this macro creates declarations for 17 functions implementing algorithms that operate on Graphs, Vertices, and Edges of type G, V, and E, respectively. They also create auxiliary definitions needed by the functions. The macro must be expanded in any compilation unit that uses any of the algorithms, prior to the first such use. Expanding the macro for two or more different sets of types in the same compilation unit simply overloads the function names.

#define Graph_algimplement(G,V,E) ... Expanding this macro creates definitions for all 17 functions. Must be expanded exactly once in any executable that expands Graph_algdeclare(G,V,E). Expanding all implement macros in the same .c file is the only way to ensure that these definitions do not conflict.

Auxiliary definition needed by Graph algorithms

typedef int GApredicate(V)(const V* v); This creates the necessary type definition for parameters and results of the Graph algorithms.

Graph algorithms

List_of_p<V> dfs(G& g,V* v,GApredicate(V)* f = 0);"

List_of_p<V> dfs_u(G& g,V* v,GApredicate(V)* f = 0);" (and others) See the individual Graph_alg(3C++) manual entries for descriptions of these functions.

References