csdf/base/algo/dfs.cc File Reference

#include "dfs.h"
Include dependency graph for csdf/base/algo/dfs.cc:

Functions

static CSDFactors getAdjacentActors (CSDFactor *a, bool transpose)
static CSDFactorgetNextActor (CSDFactors &actors, v_int &order)
static void dfsVisit (CSDFactor *u, int &time, v_int &color, v_int &d, v_int &f, CSDFactor **pi, bool transpose)
void dfs (CSDFgraph *g, v_int &d, v_int &f, CSDFactor **pi, bool transpose)

Function Documentation

void dfs ( CSDFgraph g,
v_int d,
v_int f,
CSDFactor **  pi,
bool  transpose 
)

dfs () The function performs a depth first search on the graph. The discover time (d), finish time (f) and predecessor tree (pi) are passed back. The graph is transposed if the argument 't' is 'true'. Vertices are considered in decreasing order of f[u].

The function derives an 'order' vector from the vector 'f'. Actors are considered in decreasing order according to this vector. When an actor is visited, its order is set to -1. At the end, all actors must have order -1 (i.e. all actors are visited).

References a, color, dfsVisit(), CSDFgraph::getActors(), getNextActor(), and CSDFgraph::nrActors().

Referenced by stronglyConnectedComponents().

Here is the call graph for this function:

static void dfsVisit ( CSDFactor u,
int &  time,
v_int color,
v_int d,
v_int f,
CSDFactor **  pi,
bool  transpose 
) [static]

dfsVisit () The visitor function of the DFS algorithm.

References getAdjacentActors(), CSDFcomponent::getId(), and v.

Referenced by dfs().

Here is the call graph for this function:

static CSDFactors getAdjacentActors ( CSDFactor a,
bool  transpose 
) [static]

getAdjacentActors () The function returns a list with actors directly reachable from actor a (in case transpose if false). If transpose is 'true', the graph is transposed and the function returns a list with actors which are directly reachable from a in the transposed graph.

References CSDFport::getChannel(), CSDFchannel::getDstActor(), CSDFchannel::getSrcActor(), CSDFport::getType(), CSDFactor::portsBegin(), and CSDFactor::portsEnd().

Referenced by dfsVisit().

Here is the call graph for this function:

static CSDFactor* getNextActor ( CSDFactors actors,
v_int order 
) [static]

getNextActor () The function returns the actor from the list of actors with the highest order. Its order is set to -1. If all actors have order -1, a NULL pointer is returned.

References a, and CSDFcomponent::getId().

Referenced by dfs().

Here is the call graph for this function: