Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members
dbm

infimum.cpp File Reference

#include <iostream>
#include "debug/macros.h"
#include "base/bitstring.h"
#include "dbm/mingraph.h"
#include "infimum.h"
#include <stdexcept>

Defines

#define constraintValue(i, j)   (dbm_raw2bound(dbm[(i) * dim + (j)]))
#define b(i)   (-rates[i])
#define index(n)   ((n) - nodes)
#define pred(i)   index(nodes[i].pred)
#define depth(i)   nodes[i].depth
#define thread(i)   index(nodes[i].thread)
#define inbound(i)   nodes[i].inbound
#define flow(i)   nodes[i].flow
#define potential(i)   nodes[i].potential

Functions

static void printSimpleNodeInfo (Node *nodes, uint32_t i)
static void printNodeInfo (Node *nodes, const int32_t *rates, uint32_t i)
static void printAllNodeInfo (Node *nodes, const int32_t *rates, uint32_t dim)
static void printSimpleAllNodeInfo (Node *nodes, uint32_t dim)
static bool checkTreeIntegrity (const raw_t *dbm, const int32_t *rates, Node *nodes, uint32_t dim)
static bool nodeHasNoChildren (Node *node)
static void printSolution (int32_t *valuation, const int32_t *rates, uint32_t dim)
static void printClockLowerBounds (const raw_t *dbm, uint32_t dim)
static void printAllConstraints (const raw_t *dbm, uint32_t dim, arc_t *arcs, uint32_t nbConstraints)
static void printAllRates (const int32_t *rates, uint32_t dim)
static void findInitialSpanningTreeSolution (const raw_t *dbm, uint32_t dim, const int32_t *rates, Node *nodes)
static void updatePotentials (Node *leave, int32_t change)
static Node * findLastNodeBefore (Node *node, Node *exclude)
 Returns the last node according to preorder before exclude but not before node.
static Node * findLastNodeBefore (Node *node, uint32_t depth)
 Starting from node, returns the first node according to preorder for which the preorder successor has a depth not higher than depth.
static Node * findNthPredecessor (Node *node, int32_t n)
 Returns the n'th predecessor of node.
static bool isPredecessorOf (Node *n, Node *m)
 Returns true if and only if n is on the path to the root from m.
static void updateNonRootSubtree (Node *rootNode, Node *nonRootNode, Node *leave, bool sourceInRootSubtree, uint32_t flow)
 Update all node information in the subtree not containing the root.
static void updateFlowInCycle (Node *k, Node *l, Node *root, uint32_t flowToAugment)
static void updateSpanningTree (Node *k, Node *l, Node *leave, Node *root, int32_t costEnter)
 Update the spanning tree so the node information is updated including flow and node potentials.
static arc_t * enteringArcDanzig (arc_t *firstArc, arc_t *lastArc, Node *nodes, const raw_t *dbm, uint32_t dim)
 Danzig's entering rule chooses the eligible arc with the lowest cost.
static Node * discoverCycleRoot (Node *k, Node *l)
 Returns the common ancestor of nodes k and l with the biggest depth.
static Node * findLeavingArc (Node *k, Node *l, Node *root)
static void testAndRemoveArtificialArcs (const raw_t *dbm, const int32_t *rates, Node *nodes, uint32_t dim)
static bool allPositive (const int32_t *first, const int32_t *last)
 Returns true if and only if all elements in [first, last) are non-negative.
static void infimumNetSimplex (const raw_t *dbm, uint32_t dim, const int32_t *rates, Node *nodes)
int32_t pdbm_infimum (const raw_t *dbm, uint32_t dim, uint32_t offsetCost, const int32_t *rates)
void pdbm_infimum (const raw_t *dbm, uint32_t dim, uint32_t offsetCost, const int32_t *rates, int32_t *valuation)

Define Documentation

#define b (  i   )     (-rates[i])
 

#define constraintValue (  i,
j   )     (dbm_raw2bound(dbm[(i) * dim + (j)]))
 

#define depth (  i   )     nodes[i].depth
 

#define flow (  i   )     nodes[i].flow
 

#define inbound (  i   )     nodes[i].inbound
 

#define index (  n   )     ((n) - nodes)
 

#define potential (  i   )     nodes[i].potential
 

#define pred (  i   )     index(nodes[i].pred)
 

#define thread (  i   )     index(nodes[i].thread)
 

Function Documentation

static bool allPositive (  const int32_t *  first,
const int32_t *  last
)  [static]
 

Returns true if and only if all elements in [first, last) are non-negative.

static bool checkTreeIntegrity (  const raw_t *  dbm,
const int32_t *  rates,
Node *  nodes,
uint32_t  dim
)  [static]
 

static Node* discoverCycleRoot (  Node *  k,
Node *  l
)  [static]
 

Returns the common ancestor of nodes k and l with the biggest depth.

static arc_t* enteringArcDanzig (  arc_t *  firstArc,
arc_t *  lastArc,
Node *  nodes,
const raw_t *  dbm,
uint32_t  dim
)  [static]
 

Danzig's entering rule chooses the eligible arc with the lowest cost.

static void findInitialSpanningTreeSolution (  const raw_t *  dbm,
uint32_t  dim,
const int32_t *  rates,
Node *  nodes
)  [static]
 

static Node* findLastNodeBefore (  Node *  node,
uint32_t  depth
)  [static]
 

Starting from node, returns the first node according to preorder for which the preorder successor has a depth not higher than depth.

static Node* findLastNodeBefore (  Node *  node,
Node *  exclude
)  [static]
 

Returns the last node according to preorder before exclude but not before node.

Node that this might be startNode itself.

static Node* findLeavingArc (  Node *  k,
Node *  l,
Node *  root
)  [static]
 

static Node* findNthPredecessor (  Node *  node,
int32_t  n
)  [static]
 

Returns the n'th predecessor of node.

Returns node if n is zero or negative.

static void infimumNetSimplex (  const raw_t *  dbm,
uint32_t  dim,
const int32_t *  rates,
Node *  nodes
)  [static]
 

static bool isPredecessorOf (  Node *  n,
Node *  m
)  [inline, static]
 

Returns true if and only if n is on the path to the root from m.

static bool nodeHasNoChildren (  Node *  node  )  [inline, static]
 

void pdbm_infimum (  const raw_t *  dbm,
uint32_t  dim,
uint32_t  offsetCost,
const int32_t *  rates,
int32_t *  valuation
) 
 

int32_t pdbm_infimum (  const raw_t *  dbm,
uint32_t  dim,
uint32_t  offsetCost,
const int32_t *  rates
) 
 

static void printAllConstraints (  const raw_t *  dbm,
uint32_t  dim,
arc_t *  arcs,
uint32_t  nbConstraints
)  [static]
 

static void printAllNodeInfo (  Node *  nodes,
const int32_t *  rates,
uint32_t  dim
)  [static]
 

static void printAllRates (  const int32_t *  rates,
uint32_t  dim
)  [static]
 

static void printClockLowerBounds (  const raw_t *  dbm,
uint32_t  dim
)  [static]
 

static void printNodeInfo (  Node *  nodes,
const int32_t *  rates,
uint32_t  i
)  [static]
 

static void printSimpleAllNodeInfo (  Node *  nodes,
uint32_t  dim
)  [static]
 

static void printSimpleNodeInfo (  Node *  nodes,
uint32_t  i
)  [static]
 

static void printSolution (  int32_t *  valuation,
const int32_t *  rates,
uint32_t  dim
)  [static]
 

static void testAndRemoveArtificialArcs (  const raw_t *  dbm,
const int32_t *  rates,
Node *  nodes,
uint32_t  dim
)  [static]
 

static void updateFlowInCycle (  Node *  k,
Node *  l,
Node *  root,
uint32_t  flowToAugment
)  [static]
 

static void updateNonRootSubtree (  Node *  rootNode,
Node *  nonRootNode,
Node *  leave,
bool  sourceInRootSubtree,
uint32_t  flow
)  [static]
 

Update all node information in the subtree not containing the root.

I.e., pred, depth, and thread.

static void updatePotentials (  Node *  leave,
int32_t  change
)  [static]
 

static void updateSpanningTree (  Node *  k,
Node *  l,
Node *  leave,
Node *  root,
int32_t  costEnter
)  [static]
 

Update the spanning tree so the node information is updated including flow and node potentials.

Generated on Fri Jun 30 00:02:45 2006 for Module dbm by  doxygen 1.4.2