|
|
#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 . }
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.
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.
typedef int GApredicate(V)(const V* v); This creates the necessary type definition for parameters and results of the 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.