sdf/base/algo/dfs.cc File Reference
#include "dfs.h"
Functions | |
static SDFactors | getAdjacentActors (SDFactor *a, bool transpose) |
static SDFactor * | getNextActor (SDFactors &actors, v_int &order) |
static void | dfsVisit (SDFactor *u, int &time, v_int &color, v_int &d, v_int &f, SDFactor **pi, bool transpose) |
void | dfs (SDFgraph *g, v_int &d, v_int &f, SDFactor **pi, bool transpose) |
Function Documentation
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(), SDFgraph::getActors(), getNextActor(), and SDFgraph::nrActors().
static void dfsVisit | ( | SDFactor * | u, | |
int & | time, | |||
v_int & | color, | |||
v_int & | d, | |||
v_int & | f, | |||
SDFactor ** | pi, | |||
bool | transpose | |||
) | [static] |
dfsVisit () The visitor function of the DFS algorithm.
References getAdjacentActors(), SDFcomponent::getId(), and v.
Referenced by dfs().
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 SDFport::getChannel(), SDFchannel::getDstActor(), SDFchannel::getSrcActor(), SDFport::getType(), SDFactor::portsBegin(), and SDFactor::portsEnd().
Referenced by dfsVisit().
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 SDFcomponent::getId().
Referenced by dfs().