Go to the source code of this file.
Functions 
struct graph *  new_graph (int) 
void  dump_graph (FILE *, struct graph *) 
struct graph_edge *  add_edge (struct graph *, int, int) 
void  identify_vertices (struct graph *, int, int) 
int  graphds_dfs (struct graph *, int *, int, vec< int > *, bool, bitmap) 
int  graphds_scc (struct graph *, bitmap) 
void  graphds_domtree (struct graph *, int, int *, int *, int *) 
void  for_each_edge (struct graph *, graphds_edge_callback) 
void  free_graph (struct graph *g) 
Typedef Documentation
Function Documentation
void dump_graph 
( 
FILE * 
, 


struct graph * 


) 
 
void free_graph 
( 
struct graph * 
g  ) 

int graphds_dfs 
( 
struct graph * 
g, 


int * 
qs, 


int 
nq, 


vec< int > * 
qt, 


bool 
forward, 


bitmap 
subgraph 

) 
 
Runs dfs search over vertices of G, from NQ vertices in queue QS.
The vertices in postorder are stored into QT. If FORWARD is false,
backward dfs is run. If SUBGRAPH is not NULL, it specifies the
subgraph of G to run DFS on. Returns the number of the components
of the graph (number of the restarts of DFS).
References vertex::component, vertex::post, and graph::vertices.
void graphds_domtree 
( 
struct graph * 
g, 


int 
entry, 


int * 
parent, 


int * 
son, 


int * 
brother 

) 
 
Determines the dominance tree of G (stored in the PARENT, SON and BROTHER
arrays), where the entry node is ENTRY.
We use a slight modification of the standard iterative algorithm, as
described in
K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
Algorithm
sort vertices in reverse postorder
foreach v
dom(v) = everything
dom(entry) = entry;
while (anything changes)
foreach v
dom(v) = {v} union (intersection of dom(p) over all predecessors of v)
The sets dom(v) are represented by the parent links in the current version
of the dominance tree.
void identify_vertices 
( 
struct graph * 
, 


int 
, 


int 


) 
 
struct graph* new_graph 
( 
int 
 ) 


read 