Classes | Defines | Typedefs | Functions | Variables

mcmyto.cc File Reference

#include "mcmgraph.h"
#include "../../base/hsdf/check.h"
#include "../../base/algo/components.h"
#include <float.h>
Include dependency graph for mcmyto.cc:

Classes

class  Node
struct  Arc
struct  Graph
struct  D_heap

Defines

#define NILN   (node *) NULL
#define NILA   (arc *) NULL
#define dh   4L

Typedefs

typedef struct Node node
typedef struct Arc arc
typedef struct Graph graph
typedef arc * item
typedef struct D_heap d_heap

Functions

static long MAXCHILD (long x, d_heap *h)
static void SHIFTDOWN (d_heap *h, item i, long x)
static void SHIFTUP (d_heap *h, item i, long x)
static void INSERT (d_heap *h, item i)
static void DELETE (d_heap *h, item i)
static item DELETE_MAX (d_heap *h)
static item GET_MAX (d_heap *h)
static bool ALLOC_HEAP (d_heap *h, long k)
static void DEALLOC_HEAP (d_heap *h)
static void update_subtree (node *root)
static void mmcycle (graph *gr, double *lambda, arc **cycle, long *len)
static void convertMCMgraphToYTOgraph (MCMgraph *g, graph *gr)
static CFraction mcmYoungTarjanOrlin (TimedSDFgraph *g, bool mcmFormulation)
CFraction maximumCycleYoungTarjanOrlin (TimedSDFgraph *g, bool mcmFormulation)

Variables

static long update_level
static node * upd_nodes

Define Documentation

#define dh   4L

Referenced by MAXCHILD().

#define NILA   (arc *) NULL

Referenced by DELETE_MAX(), GET_MAX(), and mmcycle().

#define NILN   (node *) NULL

Referenced by mmcycle(), and update_subtree().

Typedef Documentation

typedef struct Arc arc
typedef struct D_heap d_heap
typedef struct Graph graph
typedef arc* item
typedef struct Node node

Function Documentation

static bool ALLOC_HEAP ( d_heap *  h,
long  k 
) [inline, static]

References D_heap::items, D_heap::max_size, and D_heap::size.

Referenced by mmcycle().

static void convertMCMgraphToYTOgraph ( MCMgraph *  g,
graph *  gr 
) [static]

convertMCMgraphToYTOgraph () The function converts a weighted directed graph used in the MCM algorithms to graph input for Young-Tarjan-Orlin's algorithm.

References a, Graph::arcs, Arc::cost, _MCMedge::d, _MCMedge::dst, MCMgraph::edges, Node::first_arc_in, Node::first_arc_out, Arc::head, _MCMnode::id, Node::id, Graph::n_arcs, Graph::n_nodes, Arc::next_in, Arc::next_out, MCMgraph::nodes, Graph::nodes, MCMgraph::nrEdges(), MCMgraph::nrNodes(), _MCMedge::src, Arc::tail, Arc::transit_time, v, _MCMedge::visible, Graph::vs, and _MCMedge::w.

Referenced by mcmYoungTarjanOrlin().

Here is the call graph for this function:

static void DEALLOC_HEAP ( d_heap *  h  )  [inline, static]

References D_heap::items.

Referenced by mmcycle().

static void DELETE ( d_heap *  h,
item  i 
) [inline, static]

References Arc::hpos, D_heap::items, Arc::key, SHIFTDOWN(), SHIFTUP(), and D_heap::size.

Referenced by DELETE_MAX(), and mmcycle().

Here is the call graph for this function:

static item DELETE_MAX ( d_heap *  h  )  [inline, static]

References DELETE(), D_heap::items, NILA, and D_heap::size.

Here is the call graph for this function:

static item GET_MAX ( d_heap *  h  )  [inline, static]

References D_heap::items, NILA, and D_heap::size.

Referenced by mmcycle().

static void INSERT ( d_heap *  h,
item  i 
) [inline, static]

References SHIFTUP(), and D_heap::size.

Referenced by mmcycle().

Here is the call graph for this function:

static long MAXCHILD ( long  x,
d_heap *  h 
) [inline, static]

References dh, D_heap::items, Arc::key, and D_heap::size.

Referenced by SHIFTDOWN().

CFraction maximumCycleYoungTarjanOrlin ( TimedSDFgraph *  g,
bool  mcmFormulation 
)

maximumCycleMeanYoungTarjanOrlin () The function computes the maximum cycle mean of a HSDF graph using Young-Tarjan-Orlin's algorithm.

References isHSDFgraph(), isStronglyConnectedGraph(), and mcmYoungTarjanOrlin().

Referenced by analyzeSDFG().

Here is the call graph for this function:

static CFraction mcmYoungTarjanOrlin ( TimedSDFgraph *  g,
bool  mcmFormulation 
) [static]

mcmYoungTarjanOrlin () The function computes the maximum cycle mean of a HSDF graph using Young-Tarjan-Orlin's algorithm.

References Graph::arcs, convertMCMgraphToYTOgraph(), mmcycle(), Graph::nodes, relabelMCMgraph(), stronglyConnectedMCMgraph(), and transformHSDFtoMCMgraph().

Referenced by maximumCycleYoungTarjanOrlin().

Here is the call graph for this function:

static void mmcycle ( graph *  gr,
double *  lambda,
arc **  cycle,
long *  len 
) [static]

mmcycle ()

Determines maximum mean cycle in a directed graph G = (V, E, c), c: E->IR a "cost" function on the edges, alternatively called "length" or "weight".

Input parameter: --------------- gr - graph structure with incidence lists of incoming and outgoing edges for each node

Output parameters: ----------------- lambda - maximum cycle mean

cycle - pointers to arcs on maximum mean cycle, ordered in array from top to bottom with respect to subsequent arcs on cycle

len - number of elements of "cycle"

If cycle or len is a NULL-pointer, then these parameters are not assigned a value.

Reference --------- N.E. Young, R. E. Tarjan, J. B. Orlin: "Faster Parametric Shortest Path and Minimum-Balance Algorithms", Networks 21 (1991), 205-221

Sketch of algorithm: -------------------

1) Introduce an extra node s and an emanating arc with cost zero to each node of the graph, let V' and E' be the extended node and edge sets respectively and G' = (V',E',c).

2) Let lambda = lambda_ini = sum (abs(c(e)) + 1.0 over all edges e of E';

3) Introduce edge costs c_lambda(e) = c(e) - lambda for all edges e of E', let G'_lambda = (V', E', c_lambda), (all edge costs c_lambda(e) are positive);

4) Set up tree T_lambda of shortest paths from s to all other nodes in G'_lambda, i.e. with respect to edge costs c_lambda, this tree consists of all edges ema- nating from node s, for each node v retain cost ct(v) of tree path in G' and the number of edges on the path from s to v, i.e. the tree level of v;

5) For all edges e = (u,v) in G - T_lambda compute edge (pivot) key pk as

pk(e) = (ct(u) + c(u,v) - ct(v))/(lev(u) + 1 - lev(v))

if lev(u) + 1 > lev(v), otherwise set pk(e) = -infinite

For each node v select an incoming edge whose key is maximum among all incoming edges and assign it to v as vertex key.

6) Determine an edge emin = (u',v') such that pk(u',v') is maximum among all edge keys by way of vertex keys - such a key always exists at this point - let lambda = pk(u', v');

7) If v' is an ancestor of u' in the tree, inserting edge (u',v') into it creates a cycle with mean value lambda, this is a maximum mean cycle, return cycle and lambda;

8) Delete edge (u'',v') from the tree and insert edge (u',v') instead, for all nodes v of subtree rooted at v', update lev (v) and ct(v) by adding lev(u') + 1 - lev (v') and ct(u') + c(u',v') - ct(v') respectively, compute edge key for edge (u'',v'), remove edge key of (u',v') and update edge keys for all edges (u,v) with exactly one of its incident nodes u or v in subtree rooted at v' (such edges are the final ones on new shortest paths to destination node v), determine new vertex key for each vertex that has an incoming edge whose key has been changed;

9) goto (6);

References ALLOC_HEAP(), Graph::arcs, ASSERT, Arc::cost, Node::cost_t, DEALLOC_HEAP(), DELETE(), Node::first_arc_in, Node::first_arc_out, Node::first_child, GET_MAX(), Arc::head, Arc::hpos, Node::in_list, Arc::in_tree, INSERT(), Arc::key, Node::left_sibl, Node::level, Node::link, Graph::n_arcs, Graph::n_nodes, Arc::next_in, Arc::next_out, NILA, NILN, Graph::nodes, Node::parent_in, Node::right_sibl, Arc::tail, Arc::transit_time, update_level, update_subtree(), Node::vkey, and Graph::vs.

Referenced by mcmYoungTarjanOrlin().

Here is the call graph for this function:

static void SHIFTDOWN ( d_heap *  h,
item  i,
long  x 
) [inline, static]

References c, Arc::hpos, D_heap::items, Arc::key, and MAXCHILD().

Referenced by DELETE().

Here is the call graph for this function:

static void SHIFTUP ( d_heap *  h,
item  i,
long  x 
) [inline, static]

References Arc::hpos, D_heap::items, and Arc::key.

Referenced by DELETE(), and INSERT().

static void update_subtree ( node *  root  )  [static]

update_subtree () recursive subtree traversal function, produces a one-way liked list of nodes * contained in subtree updates node levels and costs of paths along sub-tree to nodes contained in it.

References Arc::cost, Node::cost_t, Node::first_child, Node::in_list, Node::level, Node::link, NILN, Node::parent_in, Node::right_sibl, and update_level.

Referenced by mmcycle().

Variable Documentation

node* upd_nodes [static]
long update_level [static]

Referenced by mmcycle(), and update_subtree().