lib/dgRange.c File Reference

#include "common.h"
#include "diGraph.h"

Include dependency graph for dgRange.c:

Go to the source code of this file.

Data Structures
struct	bfEdge
struct	bfVertex
struct	bfGraph
struct	bfRange
Functions
static void	bfGraphFree (struct bfGraph **pGraph)
static struct bfGraph *	bfGraphFromRangeGraph (struct diGraph *rangeGraph, boolean(*findEdgeRange)(struct dgEdge *edge, int *retMin, int *retMax), struct dgNode *a, struct dgNode *b, int abMin, int abMax)
static boolean	bfCheckGraph (struct bfGraph *graph)
boolean	dgAddedRangeConsistent (struct diGraph *rangeGraph, struct dgNode *a, struct dgNode *b, int abMin, int abMax, boolean(*findEdgeRange)(struct dgEdge *edge, int *retMin, int *retMax))
boolean	dgRangesConsistent (struct diGraph *rangeGraph, boolean(*findEdgeRange)(struct dgEdge *edge, int *retMin, int *retMax))
Variables
static char const	rcsid [] = "$Id: dgRange.c,v 1.3 2003/05/06 07:33:42 kate Exp $"

---

Function Documentation

static boolean bfCheckGraph

(

struct bfGraph *

graph

)

[static]

Definition at line 163 of file dgRange.c.

References bfGraph::edgeCount, bfGraph::edges, FALSE, bfEdge::in, bfVertex::position, TRUE, bfGraph::vertexCount, and bfGraph::vertices.

Referenced by dgAddedRangeConsistent().

{
struct bfVertex *vertices = graph->vertices, *in, *out;
int vertexCount = graph->vertexCount;
int edgeCount = graph->edgeCount;
struct bfEdge *edges = graph->edges, *edge;
int i, edgeIx;
int maxIterations = vertexCount - 1;
boolean anyChange = FALSE;
int newPos;

for (i=0; i<vertexCount; ++i)
    vertices[i].position = 0x3fffffff;    /* Mighty big number. */
for (i=0; i<maxIterations; ++i)
    {
    anyChange = FALSE;
    for (edgeIx = 0, edge = edges; edgeIx < edgeCount; ++edgeIx, ++edge)
        {
        in = edge->in;
        out = edge->out;
        newPos = in->position + edge->distance;
        if (newPos < out->position)
            {
            out->position = newPos;
            anyChange = TRUE;
            }
        }
    if (!anyChange)
        break;
    }
return !anyChange;
}

Here is the caller graph for this function:

static void bfGraphFree

(

struct bfGraph **

pGraph

)

[static]

Definition at line 41 of file dgRange.c.

References bfGraph::edges, freeMem(), freez(), and bfGraph::vertices.

Referenced by dgAddedRangeConsistent().

{
struct bfGraph *graph = *pGraph;
if (graph != NULL)
    {
    freeMem(graph->vertices);
    freeMem(graph->edges);
    freez(pGraph);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct bfGraph* bfGraphFromRangeGraph	(	struct diGraph *	rangeGraph,
		boolean(*)(struct dgEdge *edge, int *retMin, int *retMax)	findEdgeRange,
		struct dgNode *	a,
		struct dgNode *	b,
		int	abMin,
		int	abMax
	)			[static, read]

Definition at line 53 of file dgRange.c.

References AllocArray, AllocVar, dlCount(), bfGraph::edgeCount, diGraph::edgeList, dgConnection::edgeOnList, bfGraph::edges, newEdge(), dgConnection::next, dgNode::next, dgNode::nextList, dgConnection::node, diGraph::nodeList, slAddHead, dgNode::topoOrder, dlNode::val, bfGraph::vertexCount, bfGraph::vertices, and bfVertex::waysOut.

Referenced by dgAddedRangeConsistent().

                         :
 *     sourceNode destNode minDistance maxDistance
 *    -------------------------------------------
 *         A         B         2          5
 * The bfGraph would have:
 *     sourceNode destNode   edgeVal  meaning
 *    --------------------------------------------
 *         A         B         5     D(A) - D(B) <= 5 
 *         B         A        -2     D(B) - D(A) <= -2
 * Furthermore the bfGraph introduces a new node,
 * "zero", which has a zero-valued connection to
 * all other nodes.
 *
 * This graph can then be processed via the Bellman-
 * Ford algorithm (see p. 532 of Cormen,Leiserson and
 * Rivest's Introduction to Algorithms, MIT Press 1990)
 * to see if the bfGraph, and by extension the range
 * graph, is consistent.
 */
{
struct bfGraph *bfGraph;
struct bfVertex *vertices, *freeVertex, *newSource, *newDest, *zeroVertex;
struct bfEdge *edges, *newEdge, *freeEdge;
struct dgNode *oldSource, *oldDest, *oldNode;
int oldEdgeCount = dlCount(rangeGraph->edgeList);
int oldVertexCount = 0;

/* Coopt topoOrder field to store unique ID for each
 * node, starting at 1.  (We'll reserve 0 for the
 * node we insert - the Belman Ford "zero" node.)*/
for (oldNode = rangeGraph->nodeList; oldNode != NULL; oldNode = oldNode->next)
    oldNode->topoOrder = ++oldVertexCount;

/* Allocate space for new graph. */
AllocVar(bfGraph);
bfGraph->vertexCount = oldVertexCount + 1;
bfGraph->vertices = freeVertex = AllocArray(vertices, bfGraph->vertexCount);
bfGraph->edgeCount = 2*oldEdgeCount + oldVertexCount;
if (a != NULL)
  bfGraph->edgeCount += 2;
bfGraph->edges = freeEdge = AllocArray(edges, bfGraph->edgeCount);

/* Get zero vertex. */
zeroVertex = freeVertex++;

/* Scan through old graph and add vertices to new graph. */
for (oldSource = rangeGraph->nodeList; oldSource != NULL; 
    oldSource = oldSource->next)
    {
    struct dgConnection *dgConn;
    int rangeMin, rangeMax;

    /* Allocate new source vertex. */
    newSource = freeVertex++;

    /* Make connection from zero vertex to this one. */
    newEdge = freeEdge++;
    newEdge->distance = 0;
    newEdge->in = zeroVertex;
    newEdge->out = newSource;
    slAddHead(&zeroVertex->waysOut, newEdge);

    /* Loop through all ways out of source. */
    for (dgConn = oldSource->nextList; dgConn != NULL; dgConn = dgConn->next)
        {
        /* Find destination vertex and size range of edge. */
        if ((*findEdgeRange)(dgConn->edgeOnList->val, &rangeMin, &rangeMax))
            {
            oldDest = dgConn->node;
            newDest = &vertices[oldDest->topoOrder];

            /* Make two new edges corresponding to old edge. */
            newEdge = freeEdge++;
            newEdge->distance = rangeMax;
            newEdge->in = newSource;
            newEdge->out = newDest;
            slAddHead(&newSource->waysOut, newEdge);
            newEdge = freeEdge++;
            newEdge->distance = -rangeMin;
            newEdge->in = newDest;
            newEdge->out = newSource;
            slAddHead(&newDest->waysOut, newEdge);
            }
        }
    }
/* Add additional pair of edges for extra range if applicable. */
if (a != NULL)
    {
    newSource = &vertices[a->topoOrder];
    newDest = &vertices[b->topoOrder];
    newEdge = freeEdge++;
    newEdge->distance = abMax;
    newEdge->in = newSource;
    newEdge->out = newDest;
    slAddHead(&newSource->waysOut, newEdge);
    newEdge = freeEdge++;
    newEdge->distance = -abMin;
    newEdge->in = newDest;
    newEdge->out = newSource;
    slAddHead(&newDest->waysOut, newEdge);
    }
bfGraph->edgeCount = freeEdge - bfGraph->edges;
return bfGraph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean dgAddedRangeConsistent	(	struct diGraph *	rangeGraph,
		struct dgNode *	a,
		struct dgNode *	b,
		int	abMin,
		int	abMax,
		boolean(*)(struct dgEdge *edge, int *retMin, int *retMax)	findEdgeRange
	)

Definition at line 197 of file dgRange.c.

References bfCheckGraph(), bfGraphFree(), and bfGraphFromRangeGraph().

Referenced by dgRangesConsistent().

{
struct bfGraph *bfGraph;
boolean ok; 

bfGraph = bfGraphFromRangeGraph(rangeGraph, findEdgeRange, a, b, abMin, abMax);
ok = bfCheckGraph(bfGraph);
bfGraphFree(&bfGraph);
return ok;
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean dgRangesConsistent	(	struct diGraph *	rangeGraph,
		boolean(*)(struct dgEdge *edge, int *retMin, int *retMax)	findEdgeRange
	)

Definition at line 213 of file dgRange.c.

References dgAddedRangeConsistent().

{
return dgAddedRangeConsistent(rangeGraph, NULL, NULL, 0, 0, findEdgeRange);
}

Here is the call graph for this function:

---

Variable Documentation

char const rcsid[] = "$Id: dgRange.c,v 1.3 2003/05/06 07:33:42 kate Exp $" [static]

Definition at line 8 of file dgRange.c.

---