sdf/analysis/mcm/mcmgraph.h File Reference

#include "../../base/timed/graph.h"

Include dependency graph for sdf/analysis/mcm/mcmgraph.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	_MCMedge
struct	_MCMnode
class	MCMgraph
Typedefs
typedef struct _MCMedge	MCMedge
typedef list< MCMedge * >	MCMedges
typedef MCMedges::iterator	MCMedgesIter
typedef struct _MCMnode	MCMnode
typedef list< MCMnode * >	MCMnodes
typedef MCMnodes::iterator	MCMnodesIter
typedef list< MCMgraph * >	MCMgraphs
typedef MCMgraphs::iterator	MCMgraphsIter
Functions
MCMgraph *	transformHSDFtoMCMgraph (TimedSDFgraph *g, bool mcmFormulation=true)
void	stronglyConnectedMCMgraph (MCMgraph *g, MCMgraphs &components)
void	relabelMCMgraph (MCMgraph *g)

---

Typedef Documentation

typedef struct _MCMedge MCMedge

typedef list<MCMedge*> MCMedges

typedef MCMedges::iterator MCMedgesIter

typedef list<MCMgraph*> MCMgraphs

typedef MCMgraphs::iterator MCMgraphsIter

typedef struct _MCMnode MCMnode

typedef list<MCMnode*> MCMnodes

typedef MCMnodes::iterator MCMnodesIter

---

Function Documentation

void relabelMCMgraph

(

MCMgraph *

g

)

relabelMCMgraph () The function removes all hidden nodes and edges from the graph. All visible edges are assigned a new id starting in the range [0,nrNodes()).

References MCMgraph::edges, _MCMedge::id, _MCMnode::id, _MCMnode::in, MCMgraph::nodes, _MCMnode::out, _MCMedge::visible, and _MCMnode::visible.

Referenced by mcmDasdanGupta(), mcmKarp(), and mcmYoungTarjanOrlin().

void stronglyConnectedMCMgraph	(	MCMgraph *	g,
		MCMgraphs &	components
	)

Extract the strongly connected components from the graph. These components are returned as a set of MCM graphs. All nodes which belong to at least one of the strongly connected components are set to visible in the graph g, all other nodes are made invisible. Also edges between two nodes in (possibly different) strongly connected components are made visible and all others invisible. The graph g consists in the end of only nodes which are part of a strongly connnected component and all the edges between these nodes. Some MCM algorithms work also on this graph (which reduces the execution time needed in some of the conversion algorithms).

References ASSERT, dfsMCMgraph(), _MCMedge::dst, MCMgraph::edges, findComponentsInMCMgraph(), _MCMnode::id, MCMgraph::nrNodes(), pi, _MCMedge::src, _MCMedge::visible, and _MCMedge::w.

Referenced by mcmDasdanGupta(), mcmHoward(), mcmKarp(), and mcmYoungTarjanOrlin().

Here is the call graph for this function:

MCMgraph* transformHSDFtoMCMgraph	(	TimedSDFgraph *	g,
		bool	mcmFormulation
	)

transformHSDFtoMCMgraph () The function converts an HSDF graph to a weighted directed graph used in the MCM algorithm of Karp (and its variants). By default, the a longest path calculation is performed to make the graph suitable as input for an MCM algorithm. Setting the flag 'mcmFormulation' to false result in an MCM graph which is suitable for an MCR (cycle ratio) formulation. This avoids running the longest path algo.

References addLongestDelayEdgesToMCMgraph(), createInitialMCMgraph(), _MCMedge::d, _MCMedge::dst, MCMgraph::edges, _MCMnode::id, isHSDFgraph(), _MCMedge::src, _MCMedge::visible, and _MCMedge::w.

Referenced by mcmDasdanGupta(), mcmHoward(), mcmKarp(), and mcmYoungTarjanOrlin().

Here is the call graph for this function: