This class defines a directed graph with very limited number of operations, and a few specific algorithms implemented on it, like DFS. More...
#include <digraph.h>
Classes | |
| struct | edgeTriple |
| An edge with a weight (used by the Edmonds algorithm). More... | |
| class | posWeight |
| A class for representing a positive number with negative values serving as the infinity (used in the Dijkstra algorithm). More... | |
Public Types | |
| typedef wType | weight_type |
| The type of the weight of edges. | |
Public Member Functions | |
| diGraph () | |
| The default constructor of an empty graph. | |
| ~diGraph () | |
| The destructor. | |
| void | swap (diGraph< wType > &g) |
| Swaps the data with another graph. | |
| void | addVertex (void) |
| Adds a vertex. | |
| void | addEdge (int_t target) |
| Adds an edge starting at the last vertex. | |
| void | addEdge (int_t target, const wType &weight) |
| Adds an edge from the last vertex to the given one and sets the weight of this edge. | |
| void | setWeight (int_t vertex, int_t i, const wType &weight) |
| Sets the weight of the given edge. | |
| void | setWeight (int_t edge, const wType &weight) |
| Sets the weight of the given edge. | |
| template<class Table > | |
| void | setWeights (const Table &tab) |
| Sets the weights of all the edges at a time. | |
| void | removeVertex (void) |
| Removes the last vertex and all the edges going out from it. | |
| void | removeVertex (int_t vertex, bool updateweights=false) |
| Removes the given vertex and all the edges going out from it, as well as the edges going towards it. | |
| int_t | countVertices (void) const |
| Returns the number of vertices. | |
| int_t | countEdges (void) const |
| Returns the number of edges. | |
| int_t | countEdges (int_t vertex) const |
| Counts the number of edges leaving the given vertex. | |
| int_t | getEdge (int_t vertex, int_t i) const |
| Retrieves the given edge that leaves the given vertex. | |
| const wType & | getWeight (int_t vertex, int_t i) const |
| Retrieves the weight of the given edge. | |
| const wType & | getWeight (int_t edge) const |
| Retrieves the weight of the given edge. | |
| template<class Table > | |
| void | getWeights (Table &tab) const |
| Gets the weights of all the edges at a time. | |
| template<class Table > | |
| void | writeEdges (Table &tab) const |
| Fills out a table that represents all the edges of the graph. | |
| template<class wType1 > | |
| void | transpose (diGraph< wType1 > &result, bool copyweights=false) const |
| Creates a transposed graph. | |
| template<class Table , class wType1 > | |
| void | subgraph (diGraph< wType1 > &result, const Table &tab, bool copyweights=false) const |
| Computes a restriction of the graph to its subgraph. | |
| template<class Table , class Color > | |
| void | DFScolor (Table &tab, const Color &color, int_t vertex=0) const |
| Marks each vertex visited by DFS with the given color, starting with the given vertex. | |
| template<class Table , class Color > | |
| void | DFScolorRecurrent (Table &tab, const Color &color, int_t vertex=0) const |
| The recurrent procedure for DFScolor. | |
| template<class Table , class Color > | |
| void | DFScolorStack (Table &tab, const Color &color, int_t vertex=0) const |
| A stack version of the recurrent procedure for DFScolor. | |
| template<class Table > | |
| void | DFSfinishTime (Table &tab) const |
| Computes the DFS finishing time for each vertex. | |
| template<class Table1 , class Table2 , class Table3 > | |
| int_t | DFSforest (const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, diGraph< wType > *sccGraph=0) const |
| Computes the DFS forest. | |
| int_t | shortestPath (int_t source, int_t destination) const |
| Computes the length of the shortest nontrivial path from the given vertex to another one. | |
| int_t | shortestLoop (int_t origin) const |
| Computes the length of the shortest loop from the given vertex to itself. | |
| template<class lenTable , class weightsType , class roundType > | |
| void | Dijkstra (const roundType &rounding, int_t source, lenTable &len, weightsType &edgeWeights) const |
| Dijkstra's algorithm for solving the single-source shortest paths problem if all the edge weights are nonnegative. | |
| template<class lenTable , class roundType > | |
| void | Dijkstra (const roundType &rounding, int_t source, lenTable &len) const |
| Dijkstra's algorithm running on the graph's own weights. | |
| template<class lenTable > | |
| void | Dijkstra (int_t source, lenTable &len) const |
| The above algorithm without rounding control. | |
| template<class lenTable , class predTable , class roundType > | |
| bool | BellmanFord (const roundType &rounding, int_t source, lenTable &len, wType *infinity, predTable pred) const |
| Runs the Bellman-Ford algorithm which computes the single-source shortest paths in a weighted directed graph, where some edge weights may be negative. | |
| template<class lenTable , class predTable > | |
| bool | BellmanFord (int_t source, lenTable &len, wType *infinity, predTable pred) const |
| The above algorithm without rounding control. | |
| template<class roundType > | |
| bool | BellmanFord (const roundType &rounding, int_t source) const |
| Runs the Bellman-Ford algorithm (see above) without storing the distances, only returns the information about the existence of a negative-weight cycle. | |
| bool | BellmanFord (int_t source) const |
| The above algorithm without rounding control. | |
| wType | Edmonds () const |
| Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the graph. | |
| wType | EdmondsOld () const |
| An old implementation of the Edmonds algorithm (less efficient). | |
| template<class arrayType , class roundType > | |
| wType | FloydWarshall (const roundType &rounding, arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const |
| Runs the Floyd-Warshall algorithm to compute the shortest paths between all pairs of vertices in the graph. | |
| template<class arrayType > | |
| wType | FloydWarshall (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const |
| The above algorithm without rounding control. | |
| template<class arrayType , class roundType > | |
| wType | Johnson (const roundType &rounding, arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const |
| Runs Johnson's algorithm to compute the minimum path weight between any vertices in the graph. | |
| template<class arrayType > | |
| wType | Johnson (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const |
| The above algorithm without rounding control. | |
| template<class roundType > | |
| wType | minPathWeight (const roundType &rounding, bool ignoreNegLoop=false, int sparseGraph=-1) const |
| Uses the Floyd-Warshall algorithm or Johnson's algorithm, depending on the number of edges, to compute the minimum path weight between any vertices in the graph. | |
| wType | minPathWeight (bool ignoreNegLoop=false, int sparseGraph=-1) const |
| The above algorithm without rounding control. | |
| wType | minMeanCycleWeight (diGraph< wType > *transposed=0) const |
| Runs the Karp algorithm for each strongly connected component of the graph and returns the minimum mean cycle weight, which can be negative. | |
| template<class roundType > | |
| wType | minMeanCycleWeight (const roundType &rounding, diGraph< wType > *transposed) const |
| A version of the above function modified for the purpose of interval arithmetic to provide the correct lower bound for the minimum mean cycle weight in a graph. | |
| template<class arrayType , class roundType > | |
| wType | minMeanPathWeight (const roundType &rounding, const arrayType &starting, int_t n) const |
| Runs an algorithm based on Karp's idea to compute the minimum mean path weight for paths starting at any of the given n vertices and of length not exceeding the number of vertices in the graph. | |
| template<class arrayType > | |
| wType | minMeanPathWeight (const arrayType &starting, int_t n) const |
| The above algorithm without rounding control. | |
| template<class outType > | |
| outType & | show (outType &out, bool showWeights=false) const |
| Outputs the graph to a text stream in a human-readable format. | |
Protected Attributes | |
| int_t | nVertices |
| The number of vertices. | |
| multitable< int_t > | edgeEnds |
| A table with the offsets of the one-after-the-last edge of each vertex. | |
| multitable< int_t > | edges |
| A table with edge target numbers. | |
| multitable< wType > | weights |
| A table with edge weights. | |
Private Member Functions | |
| template<class Table > | |
| void | DFSfinishTimeRecurrent (Table &tab, int_t vertex, int_t &counter) const |
| The recurrent procedure for DFSfinishTime. | |
| template<class Table > | |
| void | DFSfinishTimeStack (Table &tab, int_t vertex, int_t &counter) const |
| A stack version of the recurrent procedure for DFSfinishTime. | |
| template<class Table1 , class Table2 > | |
| bool | DFSforestRecurrent (Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded) const |
| The recurrent procedure for DFSforest. | |
| template<class Table1 , class Table2 > | |
| bool | DFSforestStack (Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded) const |
| A stack version of the recurrent procedure for DFSforest. | |
Friends | |
| template<class wType1 , class wType2 > | |
| bool | operator== (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2) |
| Operator == for comparing digraphs. | |
This class defines a directed graph with very limited number of operations, and a few specific algorithms implemented on it, like DFS.
The graph can be treated as weighted if necessary.
Definition at line 142 of file digraph.h.
| typedef wType chomp::homology::diGraph< wType >::weight_type |
| chomp::homology::diGraph< wType >::diGraph | ( | ) | [inline] |
| chomp::homology::diGraph< wType >::~diGraph | ( | ) | [inline] |
| void chomp::homology::diGraph< wType >::addEdge | ( | int_t | target | ) | [inline] |
Adds an edge starting at the last vertex.
Note: The range of the target vertex number is not verified.
Definition at line 634 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), and chomp::homology::diGraph< wType >::subgraph().
{
if (!nVertices)
throw "Trying to add an edge to an empty graph.";
// if (target >= nVertices)
// throw "Trying to add an edge to a nonexistent vertex.";
if (target < 0)
throw "Trying to add an edge to a negative vertex.";
int_t &offset = edgeEnds [nVertices - 1];
if (offset + 1 <= 0)
throw "Too many edges in a diGraph (limit = 2,147,483,647).";
edges [offset] = target;
++ offset;
return;
} /* diGraph::addEdge */
| void chomp::homology::diGraph< wType >::addEdge | ( | int_t | target, | |
| const wType & | weight | |||
| ) | [inline] |
Adds an edge from the last vertex to the given one and sets the weight of this edge.
Definition at line 651 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
{
if (!nVertices)
throw "Trying to add an edge to an empty graph.";
// if (target >= nVertices)
// throw "Trying to add an edge to a nonexistent vertex.";
if (target < 0)
throw "Trying to add an edge to a negative vertex.";
int_t &offset = edgeEnds [nVertices - 1];
if (offset + 1 <= 0)
throw "Too many edges in a diGraph (limit = 2,147,483,647).";
edges [offset] = target;
weights [offset] = weight;
++ offset;
return;
} /* diGraph::addEdge */
| void chomp::homology::diGraph< wType >::addVertex | ( | void | ) | [inline] |
Adds a vertex.
Definition at line 625 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::DFSforest(), and chomp::homology::diGraph< wType >::subgraph().
| bool chomp::homology::diGraph< wType >::BellmanFord | ( | const roundType & | rounding, | |
| int_t | source | |||
| ) | const [inline] |
Runs the Bellman-Ford algorithm (see above) without storing the distances, only returns the information about the existence of a negative-weight cycle.
Definition at line 1775 of file digraph.h.
References chomp::homology::diGraph< wType >::BellmanFord(), and chomp::homology::diGraph< wType >::nVertices.
{
std::auto_ptr<wType> len_ptr (new wType [nVertices]);
wType *len = len_ptr. get ();
wType *infinity = 0;
dummyArray tab;
return BellmanFord (rounding, source, len, infinity, tab);
} /* diGraph::BellmanFord */
| bool chomp::homology::diGraph< wType >::BellmanFord | ( | int_t | source | ) | const [inline] |
The above algorithm without rounding control.
Definition at line 1786 of file digraph.h.
References chomp::homology::diGraph< wType >::BellmanFord().
{
const dummyRounding<wType> rounding = dummyRounding<wType> ();
return BellmanFord (rounding, source);
} /* diGraph::BellmanFord */
| bool chomp::homology::diGraph< wType >::BellmanFord | ( | const roundType & | rounding, | |
| int_t | source, | |||
| lenTable & | len, | |||
| wType * | infinity, | |||
| predTable | pred | |||
| ) | const [inline] |
Runs the Bellman-Ford algorithm which computes the single-source shortest paths in a weighted directed graph, where some edge weights may be negative.
Runs in O(V*E). The table 'len' is used to store the path lengths during the computations and contains the final result. The number for infinity is set to indicate unreachable vertices. The table with predecessors allows to retrieve shortest paths; this must be a pointer to an array-like structure, e.g., int **. To ignore this data, use an object of the 'dummyArray' class. Returns true if successful, false if a negative cycle is found.
Definition at line 1646 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, chomp::homology::sbug, chomp::homology::diGraph< wType >::show(), and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::BellmanFord().
{
// make sure the source vertex number is correct
if ((source < 0) || (source >= nVertices))
throw "Bellman-Ford: Wrong source vertex number.";
// prepare marks to indicate finite values (not "infinity")
BitField finite;
finite. allocate (nVertices);
finite. clearall (nVertices);
finite. set (source);
len [source] = 0;
// count the negative vertices
int_t countNegative = 0;
// set the initial predecessors
for (int_t i = 0; i < nVertices; ++ i)
pred [i] = -1;
// update the lenghts of the paths repeatedly (max nVertices times)
bool noNegativeLoop = false;
int_t counter = 0;
for (; counter <= nVertices; ++ counter)
{
bool modified = false;
int_t curEdge = 0;
for (int_t vertex = 0; vertex < nVertices; ++ vertex)
{
int_t maxEdge = edgeEnds [vertex];
if (!finite. test (vertex))
{
curEdge = maxEdge;
continue;
}
for (; curEdge < maxEdge; ++ curEdge)
{
int_t next = edges [curEdge];
wType newlen = rounding. add_down
(len [vertex], weights [curEdge]);
if (!finite. test (next))
{
finite. set (next);
modified = true;
len [next] = newlen;
pred [next] = vertex;
if (newlen < 0)
++ countNegative;
}
else if (newlen < len [next])
{
modified = true;
if (!(len [next] < 0) &&
(newlen < 0))
{
++ countNegative;
}
len [next] = newlen;
pred [next] = vertex;
}
}
}
if (countNegative == nVertices)
{
noNegativeLoop = false;
++ counter;
break;
}
if (!modified)
{
noNegativeLoop = true;
++ counter;
break;
}
}
// show a message on how many loops have been done
if (false && chomp::homology::sbug. show)
{
chomp::homology::sbug << "Bellman-Ford: " <<
counter << ((counter > 1) ? " loops (" : " loop (") <<
nVertices << " vertices, " << countNegative <<
" negative). " <<
(noNegativeLoop ? "No negative loops.\n" :
"A negative loop found.\n");
}
// compute the value for the infinity and set the undefined distances
if (infinity && noNegativeLoop)
{
wType infty (0);
bool first = true;
for (int_t i = 0; i < nVertices; ++ i)
{
if (!finite. test (i))
continue;
if (first)
{
infty = len [i];
first = false;
}
else if (infty < len [i])
{
infty = len [i];
}
}
infty = infty + 1;
for (int_t i = 0; i < nVertices; ++ i)
{
if (!finite. test (i))
len [i] = infty;
}
*infinity = infty;
}
finite. free ();
return noNegativeLoop;
} /* diGraph::BellmanFord */
| bool chomp::homology::diGraph< wType >::BellmanFord | ( | int_t | source, | |
| lenTable & | len, | |||
| wType * | infinity, | |||
| predTable | pred | |||
| ) | const [inline] |
The above algorithm without rounding control.
Definition at line 1767 of file digraph.h.
References chomp::homology::diGraph< wType >::BellmanFord().
{
const dummyRounding<wType> rounding = dummyRounding<wType> ();
return this -> BellmanFord (rounding, source, len, infinity, pred);
} /* diGraph::BellmanFord */
| int_t chomp::homology::diGraph< wType >::countEdges | ( | void | ) | const [inline] |
Returns the number of edges.
Definition at line 756 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), and chomp::homology::diGraph< wType >::minPathWeight().
| int_t chomp::homology::diGraph< wType >::countEdges | ( | int_t | vertex | ) | const [inline] |
| int_t chomp::homology::diGraph< wType >::countVertices | ( | void | ) | const [inline] |
Returns the number of vertices.
Definition at line 750 of file digraph.h.
References chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::minPathWeight().
{
return nVertices;
} /* diGraph::countVertices */
| void chomp::homology::diGraph< wType >::DFScolor | ( | Table & | tab, | |
| const Color & | color, | |||
| int_t | vertex = 0 | |||
| ) | const [inline] |
Marks each vertex visited by DFS with the given color, starting with the given vertex.
Runs for one component only. The initial color in 'tab' must be different than the given one.
Definition at line 985 of file digraph.h.
References chomp::homology::diGraph< wType >::DFScolorStack().
{
DFScolorStack (tab, color, vertex);
return;
} /* diGraph::DFScolor */
| void chomp::homology::diGraph< wType >::DFScolorRecurrent | ( | Table & | tab, | |
| const Color & | color, | |||
| int_t | vertex = 0 | |||
| ) | const [inline] |
The recurrent procedure for DFScolor.
Definition at line 909 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
| void chomp::homology::diGraph< wType >::DFScolorStack | ( | Table & | tab, | |
| const Color & | color, | |||
| int_t | vertex = 0 | |||
| ) | const [inline] |
A stack version of the recurrent procedure for DFScolor.
Definition at line 925 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFScolor().
{
// prepare stacks for the recursion
std::stack<int_t> s_vertex;
std::stack<int_t> s_edge;
std::stack<int_t> s_maxedge;
// mark the current vertex as visited
tab [vertex] = color;
// determine the edges to be visited
int_t edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
int_t maxedge = edgeEnds [vertex];
while (1)
{
// return to the previous recursion level
// if all the edges have been followed
if (edge >= maxedge)
{
// return if this is the initial recursion level
if (s_vertex. empty ())
return;
// restore the variables from the previous level
vertex = s_vertex. top ();
s_vertex. pop ();
edge = s_edge. top ();
s_edge. pop ();
maxedge = s_maxedge. top ();
s_maxedge. pop ();
continue;
}
// go to the deeper recursion level if possible
int_t next = edges [edge ++];
if (tab [next] != color)
{
// store the previous variables at the stacks
s_vertex. push (vertex);
s_edge. push (edge);
s_maxedge. push (maxedge);
// set the new vertex
vertex = next;
// mark the new vertex as visited
tab [vertex] = color;
// determine the edges to be visited
edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
maxedge = edgeEnds [vertex];
}
}
} /* diGraph::DFScolorStack */
| void chomp::homology::diGraph< wType >::DFSfinishTime | ( | Table & | tab | ) | const [inline] |
Computes the DFS finishing time for each vertex.
Note: The time begins with 1, not with 0.
Definition at line 1083 of file digraph.h.
References chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent(), chomp::homology::diGraph< wType >::DFSfinishTimeStack(), chomp::homology::diGraph< wType >::nVertices, and chomp::homology::sbug.
{
// initialize the table and the counter
for (int_t i = 0; i < nVertices; ++ i)
tab [i] = 0;
int_t counter = 0;
// compute the finishing time for each tree in the DFS forest
for (int_t i = 0; i < nVertices; ++ i)
{
if (!tab [i])
DFSfinishTimeStack (tab, i, counter);
}
#ifdef DIGRAPH_DEBUG
int_t *tabdebug = new int_t [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
tabdebug [i] = 0;
int_t counterdebug = 0;
for (int_t i = 0; i < nVertices; ++ i)
if (!tabdebug [i])
DFSfinishTimeRecurrent (tabdebug, i, counterdebug);
if (counter != counterdebug)
throw "DFSfinishTime: Wrong counter.";
for (int_t i = 0; i < nVertices; ++ i)
{
if (tab [i] != tabdebug [i])
{
sbug << "\nDFSfinishTime error: tabRec [" << i <<
"] = " << tab [i] << ", tabStack [" << i <<
"] = " << tabdebug [i] << ".\n";
throw "DFSfinishTime: Wrong numbers.";
}
}
sbug << "DEBUG: DFSfinishTime OK. ";
#endif // DIGRAPH_DEBUG
return;
} /* diGraph::DFSfinishTime */
| void chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent | ( | Table & | tab, | |
| int_t | vertex, | |||
| int_t & | counter | |||
| ) | const [inline, private] |
The recurrent procedure for DFSfinishTime.
Definition at line 995 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSfinishTime().
{
// mark the current vertex as visited
tab [vertex] = -1;
// call DFS for the other vertices
for (int_t edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
edge < edgeEnds [vertex]; ++ edge)
{
int_t next = edges [edge];
if (!tab [next])
DFSfinishTimeRecurrent (tab, next, counter);
}
// record the finishing time for the current vertex and return
tab [vertex] = ++ counter;
return;
} /* diGraph::DFSfinishTimeRecurrent */
| void chomp::homology::diGraph< wType >::DFSfinishTimeStack | ( | Table & | tab, | |
| int_t | vertex, | |||
| int_t & | counter | |||
| ) | const [inline, private] |
A stack version of the recurrent procedure for DFSfinishTime.
Definition at line 1017 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSfinishTime().
{
// prepare stacks for the recursion
std::stack<int_t> s_vertex;
std::stack<int_t> s_edge;
std::stack<int_t> s_maxedge;
// mark the current vertex as visited
tab [vertex] = -1;
// determine the edges to be visited
int_t edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
int_t maxedge = edgeEnds [vertex];
while (1)
{
// return to the previous recursion level
// if all the edges have been followed
if (edge >= maxedge)
{
// record the finishing time
// for the current vertex
tab [vertex] = ++ counter;
// return if this is the initial recursion level
if (s_vertex. empty ())
return;
// restore the variables from the previous level
vertex = s_vertex. top ();
s_vertex. pop ();
edge = s_edge. top ();
s_edge. pop ();
maxedge = s_maxedge. top ();
s_maxedge. pop ();
continue;
}
// go to the deeper recursion level if possible
int_t next = edges [edge ++];
if (!tab [next])
{
// store the previous variables at the stacks
s_vertex. push (vertex);
s_edge. push (edge);
s_maxedge. push (maxedge);
// set the new vertex
vertex = next;
// mark the new vertex as visited
tab [vertex] = -1;
// determine the edges to be visited
edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
maxedge = edgeEnds [vertex];
}
}
return;
} /* diGraph::DFSfinishTimeStack */
| int_t chomp::homology::diGraph< wType >::DFSforest | ( | const Table1 & | ordered, | |
| Table2 & | compVertices, | |||
| Table3 & | compEnds, | |||
| bool | nontrivial = false, |
|||
| diGraph< wType > * | sccGraph = 0 | |||
| ) | const [inline] |
Computes the DFS forest.
Considers the vertices in the given order. Saves the numbers of vertices of each tree in 'compVertices', and keeps the one-beyond-the-end offsets of the trees in the table 'compEnds'. Records the connections between the trees in 'scc' (which must be empty when this function is called). If requested, only those single-vertex trees are counted which have an edge that loops back to themselves. Returns the number of trees in the computed forest.
Definition at line 1278 of file digraph.h.
References chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), chomp::homology::diGraph< wType >::nVertices, chomp::homology::diGraph< wType >::removeVertex(), and chomp::homology::sbug.
{
// prepare a table to record the numbers of DFS trees
// to which the vertices belong (the tree numbers begin with 1)
int_t *tab = new int_t [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
tab [i] = 0;
// prepare a table to record the numbers of nontrivial trees
// that correspond to the trees in 'tab' (these numbers begin with 0)
int_t *ntab = new int_t [nVertices];
// prepare a table to record the numbers of edges already in the
// scc graph; "sccEdgeAdded [n] = m" indicates that the edge
// m -> n has been added to the scc graph
int_t *sccEdgeAdded = sccGraph ? new int_t [nVertices] :
static_cast<int_t *> (0);
if (sccGraph)
{
for (int_t n = 0; n < nVertices; ++ n)
sccEdgeAdded [n] = -1;
}
// prepare the official DFS tree number
int_t treeNumber = 0;
// prepare the data for keeping the nontrivial trees information
int_t countTrees = 0;
int_t curVertex = 0;
// compute the DFS trees and connections between them
for (int_t i = 0; i < nVertices; ++ i)
{
// take the next vertex
int_t vertex = ordered [i];
// if the vertex already belongs to some tree, skip it
if (tab [vertex])
continue;
// add a vertex corresponding to the component
if (sccGraph)
sccGraph -> addVertex ();
// remember the previous vertex number
int_t prevVertex = curVertex;
// mark the entire component and record connections graph
if (sccGraph)
ntab [treeNumber] = countTrees;
++ treeNumber;
bool loop = DFSforestStack (tab, ntab, vertex,
treeNumber, countTrees, compVertices,
curVertex, sccGraph, sccEdgeAdded);
// update the index bound for the vertex list
compEnds [countTrees ++] = curVertex;
// remove the component if it is trivial
if (nontrivial && !loop)
{
-- countTrees;
curVertex = prevVertex;
if (sccGraph)
{
ntab [treeNumber - 1] = -1;
sccGraph -> removeVertex ();
}
}
}
#ifdef DIGRAPH_DEBUG
diGraph<wType> *sccGraphdebug = 0;
if (sccGraph)
sccGraphdebug = new diGraph<wType>;
// prepare a table to record the numbers of DFS trees
// to which the vertices belong (the tree numbers begin with 1)
int_t *tabdebug = new int_t [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
tabdebug [i] = 0;
// prepare a table to record the numbers of nontrivial trees
// to which the vertices belong (the tree numbers begin with 0)
int_t *ntabdebug = new int_t [nVertices];
// prepare a table to record the numbers of vertices from which
// edges were added to the scc graph
int_t *sccEdgeAddeddebug = sccGraph ? new int_t [nVertices] :
static_cast<int_t> (0);
if (sccGraph)
{
for (int_t n = 0; n < nVertices; ++ n)
sccEdgeAddeddebug [n] = -1;
}
// prepare the official DFS tree number
int_t treeNumberdebug = 0;
// prepare the data for keeping the nontrivial trees information
int_t countTreesdebug = 0;
int_t curVertexdebug = 0;
int_t *compVerticesdebug = new int_t [nVertices];
int_t *compEndsdebug = new int_t [nVertices];
// compute the DFS trees and connections between them
for (int_t i = 0; i < nVertices; ++ i)
{
// take the next vertex
int_t vertex = ordered [i];
// if the vertex already belongs to some tree, skip it
if (tabdebug [vertex])
continue;
// add a vertex corresponding to the component
if (sccGraphdebug)
sccGraphdebug -> addVertex ();
// remember the previous vertex number
int_t prevVertex = curVertexdebug;
// mark the entire component and record connections graph
if (sccGraphdebug)
ntabdebug [treeNumberdebug] = countTreesdebug;
++ treeNumberdebug;
bool loop = DFSforestRecurrent (tabdebug, ntabdebug, vertex,
treeNumberdebug, countTreesdebug, compVerticesdebug,
curVertexdebug, sccGraphdebug, sccEdgeAddeddebug);
// update the index bound for the vertex list
compEndsdebug [countTreesdebug ++] = curVertexdebug;
// remove the component if it is trivial
if (nontrivial && !loop)
{
-- countTreesdebug;
curVertexdebug = prevVertex;
if (sccGraphdebug)
{
ntabdebug [treeNumberdebug - 1] = -1;
sccGraphdebug -> removeVertex ();
}
}
}
if (countTrees != countTreesdebug)
throw "DFSforest: Wrong countTrees.";
for (int_t i = 0; i < countTrees; ++ i)
if (compEnds [i] != compEndsdebug [i])
throw "DFSforest: Wrong compEnds.";
for (int_t i = 0; i < compEndsdebug [countTrees - 1]; ++ i)
if (compVertices [i] != compVerticesdebug [i])
throw "DFSforest: Wrong vertices.";
if (curVertex != curVertexdebug)
throw "DFSforest: Wrong curVertex.";
for (int_t i = 0; i < nVertices; ++ i)
if (tab [i] != tabdebug [i])
throw "DFSforest: Wrong tab.";
if (sccGraph)
{
for (int_t i = 0; i < nVertices; ++ i)
if (ntab [i] != ntabdebug [i])
throw "DFSforest: Wrong ntab.";
if (*sccGraph != *sccGraphdebug)
throw "DFSforest: Wrong graph.";
}
if (sccEdgeAdded)
{
for (int_t i = 0; i < nVertices; ++ i)
if (sccEdgeAdded [i] != sccEdgeAddeddebug [i])
throw "DFSforest: Wrong sccEdgeAdded.";
}
if (treeNumber != treeNumberdebug)
throw "DFSforest: Wrong treeNumber.";
sbug << "DEBUG: DFSforest OK. ";
if (!sccGraph)
sbug << "(Graphs not compared.) ";
delete [] compVerticesdebug;
delete [] compEndsdebug;
if (sccGraphdebug)
delete sccGraphdebug;
delete [] ntabdebug;
delete [] tabdebug;
if (sccEdgeAddeddebug)
delete [] sccEdgeAddeddebug;
#endif // DIGRAPH_DEBUG
if (sccEdgeAdded)
delete [] sccEdgeAdded;
delete [] ntab;
delete [] tab;
return countTrees;
} /* diGraph::DFSforest */
| bool chomp::homology::diGraph< wType >::DFSforestRecurrent | ( | Table1 & | tab, | |
| Table1 & | ntab, | |||
| int_t | vertex, | |||
| int_t | treeNumber, | |||
| int_t | countTrees, | |||
| Table2 & | compVertices, | |||
| int_t & | curVertex, | |||
| diGraph< wType > * | sccGraph, | |||
| int_t * | sccEdgeAdded | |||
| ) | const [inline, private] |
The recurrent procedure for DFSforest.
Returns true iff there is a loop within the tree found.
Definition at line 1125 of file digraph.h.
References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSforest().
{
// add the vertex to the tree
compVertices [curVertex ++] = vertex;
// mark the vertex as belonging to the current tree
tab [vertex] = treeNumber;
// if (sccGraph)
// ntab [treeNumber - 1] = countTrees;
// build the tree recursively or record connections
bool loop = false;
for (int_t edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
edge < edgeEnds [vertex]; ++ edge)
{
int_t next = edges [edge];
if (!tab [next])
loop |= DFSforestRecurrent (tab, ntab, next,
treeNumber, countTrees, compVertices,
curVertex, sccGraph, sccEdgeAdded);
else if (tab [next] == treeNumber)
{
if (sccGraph)
{
int_t target = ntab [treeNumber - 1];
if (sccEdgeAdded [target] != treeNumber)
{
sccGraph -> addEdge (target);
sccEdgeAdded [target] = treeNumber;
}
}
loop = true;
}
else if (sccGraph)
{
int_t target = ntab [tab [next] - 1];
if ((target >= 0) &&
(sccEdgeAdded [target] != treeNumber))
{
sccGraph -> addEdge (target);
sccEdgeAdded [target] = treeNumber;
}
}
}
return loop;
} /* diGraph::DFSforestRecurrent */
| bool chomp::homology::diGraph< wType >::DFSforestStack | ( | Table1 & | tab, | |
| Table1 & | ntab, | |||
| int_t | vertex, | |||
| int_t | treeNumber, | |||
| int_t | countTrees, | |||
| Table2 & | compVertices, | |||
| int_t & | curVertex, | |||
| diGraph< wType > * | sccGraph, | |||
| int_t * | sccEdgeAdded | |||
| ) | const [inline, private] |
A stack version of the recurrent procedure for DFSforest.
Definition at line 1178 of file digraph.h.
References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
Referenced by chomp::homology::diGraph< wType >::DFSforest().
{
// prepare stacks for the recursion
std::stack<int_t> s_vertex;
std::stack<int_t> s_edge;
std::stack<int_t> s_maxedge;
std::stack<bool> s_loop;
// add the vertex to the tree
compVertices [curVertex ++] = vertex;
// mark the vertex as belonging to the current tree
tab [vertex] = treeNumber;
// if (sccGraph)
// ntab [vertex] = countTrees;
// build the tree recursively or record connections
bool loop = false;
int_t edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
int_t maxedge = edgeEnds [vertex];
while (1)
{
// return to the previous recursion level
// if all the edges have been followed
if (edge >= maxedge)
{
// return if this is the initial recursion level
if (s_vertex. empty ())
return loop;
// restore the variables from the previous level
vertex = s_vertex. top ();
s_vertex. pop ();
edge = s_edge. top ();
s_edge. pop ();
maxedge = s_maxedge. top ();
s_maxedge. pop ();
loop |= s_loop. top ();
s_loop. pop ();
continue;
}
// go to the deeper recursion level if possible
int_t next = edges [edge ++];
if (!tab [next])
{
// store the previous variables at the stacks
s_vertex. push (vertex);
s_edge. push (edge);
s_maxedge. push (maxedge);
s_loop. push (loop);
// set the new vertex
vertex = next;
// add the vertex to the tree
compVertices [curVertex ++] = vertex;
// mark the vertex as belonging to the current tree
tab [vertex] = treeNumber;
// determine the edges to be visited
loop = false;
edge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
maxedge = edgeEnds [vertex];
}
else if (tab [next] == treeNumber)
{
if (sccGraph)
{
int_t target = ntab [treeNumber - 1];
if (sccEdgeAdded [target] != treeNumber)
{
sccGraph -> addEdge (target);
sccEdgeAdded [target] = treeNumber;
}
}
loop = true;
}
else if (sccGraph)
{
int_t target = ntab [tab [next] - 1];
if ((target >= 0) &&
(sccEdgeAdded [target] != treeNumber))
{
sccGraph -> addEdge (target);
sccEdgeAdded [target] = treeNumber;
}
}
}
return loop;
} /* diGraph::DFSforestStack */
| void chomp::homology::diGraph< wType >::Dijkstra | ( | const roundType & | rounding, | |
| int_t | source, | |||
| lenTable & | len, | |||
| weightsType & | edgeWeights | |||
| ) | const [inline] |
Dijkstra's algorithm for solving the single-source shortest paths problem if all the edge weights are nonnegative.
The table 'len' is used to store the path lengths during the computations and contains the final result. A negative value stands for the infinity (no path to the given vertex). This is a special version that uses the given edge weights instead of the weights contained in the definition of the graph.
Definition at line 1561 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::Dijkstra(), and chomp::homology::diGraph< wType >::Johnson().
{
// use the Fibonacci heap as a priority queue
FibonacciHeap<posWeight> Q (nVertices);
// add the vertices to the heap with the initial shortest path
// lengths: 0 to the source, plus infinity to all the others
for (int_t v = 0; v < nVertices; ++ v)
{
posWeight w (0);
if (v != source)
w. setInfinity ();
int_t number = Q. Insert (w);
if (number != v)
{
throw "Wrong implementation of Fibonacci heap "
"for this version of Dijkstra.";
}
}
// pick up vertices from the priority queue, record the length
// of the shortest path to them, and modify the remaining paths
for (int_t i = 0; i < nVertices; ++ i)
{
// extract the minimal vertex from the queue
int_t minVertex = Q. Minimum ();
posWeight minWeight = Q. ExtractMinimum ();
if (minWeight. isInfinity ())
{
len [minVertex] = -1;
continue;
}
wType minValue = minWeight. getValue ();
len [minVertex] = minValue;
// go through all the edges emanating from this vertex
// and update the path lengths for the target vertices
int_t edge = minVertex ? edgeEnds [minVertex - 1] :
static_cast<int_t> (0);
int_t maxEdge = edgeEnds [minVertex];
for (; edge < maxEdge; ++ edge)
{
// determine the vertex at the other end of the edge
int_t nextVertex = edges [edge];
// if the path that runs through the extracted
// vertex is shorter, then make a correction
const posWeight &nextWeight = Q. Value (nextVertex);
wType newWeight = rounding. add_down (minValue,
edgeWeights [edge]);
if (newWeight < 0)
newWeight = 0;
if (nextWeight. isInfinity () ||
(newWeight < nextWeight. getValue ()))
{
Q. DecreaseKey (nextVertex,
posWeight (newWeight));
}
}
}
return;
} /* diGraph::Dijkstra */
| void chomp::homology::diGraph< wType >::Dijkstra | ( | int_t | source, | |
| lenTable & | len | |||
| ) | const [inline] |
The above algorithm without rounding control.
Definition at line 1637 of file digraph.h.
References chomp::homology::diGraph< wType >::Dijkstra().
{
const dummyRounding<wType> rounding = dummyRounding<wType> ();
this -> Dijkstra (rounding, source, len);
return;
} /* diGraph::Dijkstra */
| void chomp::homology::diGraph< wType >::Dijkstra | ( | const roundType & | rounding, | |
| int_t | source, | |||
| lenTable & | len | |||
| ) | const [inline] |
Dijkstra's algorithm running on the graph's own weights.
Definition at line 1628 of file digraph.h.
References chomp::homology::diGraph< wType >::Dijkstra(), and chomp::homology::diGraph< wType >::weights.
| wType chomp::homology::diGraph< wType >::Edmonds | ( | ) | const [inline] |
Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the graph.
Computation time: O (n log n). The length of the path is measured as the sum of the weights of the edges. The path does not contain any loops. The graph should be strongly connected.
Definition at line 1793 of file digraph.h.
References chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
{
// create a list of edges with weights and sort this list
std::vector<edgeTriple> edgeTriples (countEdges ());
int_t prevEdge = 0;
int_t curEdge = 0;
for (int_t vert = 0; vert < nVertices; ++ vert)
{
while (curEdge < edgeEnds [vert])
{
edgeTriple &e = edgeTriples [curEdge];
e. vert1 = vert;
e. vert2 = edges [curEdge];
e. weight = weights [curEdge];
++ curEdge;
}
prevEdge = curEdge;
}
std::sort (edgeTriples. begin (), edgeTriples. end ());
// create a forest which initially contains single vertices
std::auto_ptr<int_t> root_ptr (new int_t [nVertices]);
int_t *root = root_ptr. get ();
for (int_t vert = 0; vert < nVertices; ++ vert)
{
root [vert] = -1;
}
// go through the edges and join the trees, but avoid loops
wType totalWeight = 0;
int_t nEdges = countEdges ();
for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
{
// determine the roots of both vertices of the edge
// and compress the paths
edgeTriple &e = edgeTriples [curEdge];
int_t root1 = e. vert1;
while (root [root1] >= 0)
{
root1 = root [root1];
}
int_t vert1 = e. vert1;
while (root [vert1] >= 0)
{
int_t next = root [vert1];
root [vert1] = root1;
vert1 = next;
}
int_t root2 = e. vert2;
while (root [root2] >= 0)
{
root2 = root [root2];
}
int_t vert2 = e. vert2;
while (root [vert2] >= 0)
{
int_t next = root [vert2];
root [vert2] = root2;
vert2 = next;
}
// skip the edge if it closes a loop
if (root1 == root2)
continue;
// add the weight
totalWeight += e. weight;
// join the trees
root [root1] = root2;
}
return totalWeight;
} /* diGraph::Edmonds */
| wType chomp::homology::diGraph< wType >::EdmondsOld | ( | ) | const [inline] |
An old implementation of the Edmonds algorithm (less efficient).
Definition at line 1868 of file digraph.h.
References chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
{
// create a list of edges with weights and sort this list
std::vector<edgeTriple> edgeTriples (countEdges ());
int_t prevEdge = 0;
int_t curEdge = 0;
for (int_t vert = 0; vert < nVertices; ++ vert)
{
while (curEdge < edgeEnds [vert])
{
edgeTriple &e = edgeTriples [curEdge];
e. vert1 = vert;
e. vert2 = edges [curEdge];
e. weight = weights [curEdge];
++ curEdge;
}
prevEdge = curEdge;
}
std::sort (edgeTriples. begin (), edgeTriples. end ());
// create a forest which initially contains single vertices
std::auto_ptr<int_t> forest_ptr (new int_t [nVertices]);
int_t *forest = forest_ptr. get ();
std::auto_ptr<int_t> next_ptr (new int_t [nVertices]);
int_t *next = next_ptr. get ();
std::auto_ptr<int_t> prev_ptr (new int_t [nVertices]);
int_t *prev = prev_ptr. get ();
for (int_t vert = 0; vert < nVertices; ++ vert)
{
forest [vert] = vert;
next [vert] = -1;
prev [vert] = -1;
}
// go through the edges and join the trees, but avoid loops
wType totalWeight = 0;
int_t nEdges = countEdges ();
for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
{
// check the edge and skip it if it closes a loop
edgeTriple &e = edgeTriples [curEdge];
if (forest [e. vert1] == forest [e. vert2])
continue;
// add the weight
totalWeight += e. weight;
// go to the end of the first tree
int_t vert1 = e. vert1;
while (next [vert1] >= 0)
{
vert1 = next [vert1];
}
// go to the beginning of the second tree
int_t vert2 = e. vert2;
while (prev [vert2] >= 0)
{
vert2 = prev [vert2];
}
// join the trees and modify the numbers
next [vert1] = vert2;
prev [vert2] = vert1;
int_t treeNumber = forest [vert1];
while (vert2 >= 0)
{
forest [vert2] = treeNumber;
vert2 = next [vert2];
}
}
return totalWeight;
} /* diGraph::EdmondsOld */
| wType chomp::homology::diGraph< wType >::FloydWarshall | ( | const roundType & | rounding, | |
| arrayType & | arr, | |||
| bool | setInfinity = true, |
|||
| bool | ignoreNegLoop = false | |||
| ) | const [inline] |
Runs the Floyd-Warshall algorithm to compute the shortest paths between all pairs of vertices in the graph.
The position [i] [j] of the array contains the length of the shortest path from vertex i to vertex j. Provides a rigorous lower bound in interval arithmetic, provided that intervals are compared with "<" and "<=" by comparing their lower ends only. If "setInfinity" is "true", then computes a value that serves as the infinity, fills in the corresponding entries in "arr", and returns this value. Otherwise, returns the length of the shortest path. In this case, arr [i] [j] is undefined if there is no path i -> j. Throws an error message if a negative loop is found, unless "ignoreNegLoop" is set to "true".
Definition at line 1944 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::Johnson(), and chomp::homology::diGraph< wType >::minPathWeight().
{
// do nothing if the graph is empty
if (!nVertices)
return 0;
// prepare marks to indicate finite values (not "infinity")
BitField *finite = new BitField [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
{
finite [i]. allocate (nVertices);
finite [i]. clearall (nVertices);
}
// create the initial values of the array based on the edge weights
int_t curEdge = 0;
for (int_t source = 0; source < nVertices; ++ source)
{
bool diagset = false;
while (curEdge < edgeEnds [source])
{
int_t target = edges [curEdge];
const wType &weight = weights [curEdge];
if (source == target)
{
if (weight < 0)
{
arr [source] [target] = weight;
diagset = true;
}
}
else
{
arr [source] [target] = weight;
finite [source]. set (target);
}
++ curEdge;
}
if (!diagset)
arr [source] [source] = 0;
finite [source]. set (source);
}
// find the shortest paths between the vertices (dynamic programming)
for (int_t k = 0; k < nVertices; ++ k)
{
for (int_t i = 0; i < nVertices; ++ i)
{
if (!finite [i]. test (k))
continue;
for (int_t j = 0; j < nVertices; ++ j)
{
if (!finite [k]. test (j))
continue;
const wType sum = rounding. add_down
(arr [i] [k], arr [k] [j]);
if (finite [i]. test (j))
{
if (sum < arr [i] [j])
arr [i] [j] = sum;
}
else
{
arr [i] [j] = sum;
finite [i]. set (j);
}
}
}
}
// verify if a negative loop exists by checking for a negative
// result in the diagonal
if (!ignoreNegLoop)
{
for (int_t i = 0; i < nVertices; ++ i)
{
if (arr [i] [i] < 0)
throw "Negative loop in Floyd-Warshall.";
}
}
// prepare a variable to store the returned result
wType result = 0;
// compute the value for the infinity and fill in the array
// if requested to do so
if (setInfinity)
{
wType &infinity = result;
for (int_t i = 0; i < nVertices; ++ i)
{
for (int_t j = 0; j < nVertices; ++ j)
{
if (finite [i]. test (j) &&
(infinity <= arr [i] [j]))
{
infinity = rounding. add_up
(arr [i] [j], 1);
}
}
}
for (int_t i = 0; i < nVertices; ++ i)
{
for (int_t j = 0; j < nVertices; ++ j)
{
if (!finite [i]. test (j))
arr [i] [j] = infinity;
}
}
}
// otherwise, only compute the minimum path weight
else
{
wType &minWeight = result;
bool firstTime = true;
for (int_t i = 0; i < nVertices; ++ i)
{
for (int_t j = 0; j < nVertices; ++ j)
{
if (finite [i]. test (j))
{
if (firstTime)
{
minWeight = arr [i] [j];
firstTime = false;
}
else if (arr [i] [j] < minWeight)
{
minWeight = arr [i] [j];
}
}
}
}
}
// release the 'finite' bitfields
for (int_t i = 0; i < nVertices; ++ i)
finite [i]. free ();
delete [] finite;
return result;
} /* diGraph::FloydWarshall */
| wType chomp::homology::diGraph< wType >::FloydWarshall | ( | arrayType & | arr, | |
| bool | setInfinity = true, |
|||
| bool | ignoreNegLoop = false | |||
| ) | const [inline] |
The above algorithm without rounding control.
Definition at line 2091 of file digraph.h.
References chomp::homology::diGraph< wType >::FloydWarshall().
{
const dummyRounding<wType> rounding = dummyRounding<wType> ();
return FloydWarshall (rounding, arr, setInfinity, ignoreNegLoop);
} /* diGraph::FloydWarshall */
| int_t chomp::homology::diGraph< wType >::getEdge | ( | int_t | vertex, | |
| int_t | i | |||
| ) | const [inline] |
Retrieves the given edge that leaves the given vertex.
Definition at line 774 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::edges.
| const wType & chomp::homology::diGraph< wType >::getWeight | ( | int_t | vertex, | |
| int_t | i | |||
| ) | const [inline] |
Retrieves the weight of the given edge.
Definition at line 783 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::weights.
| const wType & chomp::homology::diGraph< wType >::getWeight | ( | int_t | edge | ) | const [inline] |
Retrieves the weight of the given edge.
Definition at line 792 of file digraph.h.
References chomp::homology::diGraph< wType >::weights.
{
return weights [edge];
} /* diGraph::getWeight */
| void chomp::homology::diGraph< wType >::getWeights | ( | Table & | tab | ) | const [inline] |
Gets the weights of all the edges at a time.
The weights are put into the table with the [] operator.
Definition at line 798 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
| wType chomp::homology::diGraph< wType >::Johnson | ( | const roundType & | rounding, | |
| arrayType & | arr, | |||
| bool | setInfinity = true, |
|||
| bool | ignoreNegLoop = false | |||
| ) | const [inline] |
Runs Johnson's algorithm to compute the minimum path weight between any vertices in the graph.
The time complexity of this algorithm is essentially O (V^2 log V + VE log V), which is better than the complexity of the Warshall-Floyd algorithm for sparse graphs, that is, graphs in which the number of edges E is of order smaller than V^2. The meaning of the arguments and the returned value is the same as in 'FloydWarshall'.
Definition at line 2100 of file digraph.h.
References chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::nVertices, chomp::homology::sbug, chomp::homology::diGraph< wType >::show(), and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::Johnson(), and chomp::homology::diGraph< wType >::minPathWeight().
{
// DEBUG VERIFICATION
if (false && sbug. show)
{
timeused stopWatch;
wType res = FloydWarshall (rounding,
arr, setInfinity, ignoreNegLoop);
chomp::homology::sbug << "\n[Floyd-Warshall: " << res <<
", " << (double) stopWatch << " sec]\n";
}
// debug time measurement (see below)
// timeused stopWatch;
// do nothing if the graph is empty
if (!nVertices)
return 0;
// STEP 1: Compute the shortest paths to any vertex from an
// artificial extra vertex connected to every other vertex in the
// graph by an edge of weight zero. Use Bellman-Ford for this.
wType *len = new wType [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
len [i] = 0;
// update the lenghts of the paths repeatedly (max nVertices times)
bool noNegativeLoop = false;
int_t counter = 0;
for (; counter <= nVertices; ++ counter)
{
bool modified = false;
int_t curEdge = 0;
for (int_t vertex = 0; vertex < nVertices; ++ vertex)
{
int_t maxEdge = edgeEnds [vertex];
for (; curEdge < maxEdge; ++ curEdge)
{
int_t next = edges [curEdge];
wType newlen = rounding. add_down
(len [vertex], weights [curEdge]);
if (newlen < len [next])
{
// this "if" statement is necessary
// because of a bug in GCC 3.4.2...
if (counter > nVertices)
{
std::cout << vertex;
}
modified = true;
len [next] = newlen;
}
}
}
if (!modified)
{
noNegativeLoop = true;
++ counter;
break;
}
}
if (!ignoreNegLoop && !noNegativeLoop)
throw "Negative loop found in Johnson's algorithm.";
// STEP 2: Re-weigh the edges using the computed path lengths.
wType *newWeights = new wType [edgeEnds [nVertices - 1]];
int_t edge = 0;
for (int_t vertex = 0; vertex < nVertices; ++ vertex)
{
int_t maxEdge = edgeEnds [vertex];
for (; edge < maxEdge; ++ edge)
{
wType w = weights [edge];
w = rounding. add_down (w, len [vertex]);
w = rounding. sub_down (w, len [edges [edge]]);
newWeights [edge] = (w < 0) ?
static_cast<wType> (0) : w;
}
}
// STEP 3: Run the Dijkstra algorithm for every vertex to compute
// the shortest paths to all the other vertices.
// Negative entries indicate no path existence.
for (int_t u = 0; u < nVertices; ++ u)
{
this -> Dijkstra (rounding, u, arr [u], newWeights);
}
delete [] newWeights;
// STEP 4: Make a correction to the computed path lengths.
// Compute the value for infinity if requested to.
// Otherwise compute the minimum of path lengths.
wType result = 0;
if (setInfinity)
{
wType &infinity = result;
for (int_t u = 0; u < nVertices; ++ u)
{
for (int_t v = 0; v < nVertices; ++ v)
{
wType w = arr [u] [v];
if (w < 0)
continue;
w = rounding. add_down (w, len [v]);
w = rounding. sub_down (w, len [u]);
if (w < infinity)
continue;
infinity = rounding. add_up (w, 1);
}
}
for (int_t u = 0; u < nVertices; ++ u)
{
for (int_t v = 0; v < nVertices; ++ v)
{
wType w = arr [u] [v];
if (w < 0)
{
arr [u] [v] = infinity;
continue;
}
w = rounding. add_down (w, len [v]);
arr [u] [v] =
rounding. sub_down (w, len [u]);
}
}
}
else
{
wType &minWeight = result;
bool firstTime = true;
for (int_t u = 0; u < nVertices; ++ u)
{
for (int_t v = 0; v < nVertices; ++ v)
{
wType w = arr [u] [v];
if (w < 0)
continue;
w = rounding. add_down (w, len [v]);
w = rounding. sub_down (w, len [u]);
if (firstTime)
{
minWeight = w;
firstTime = false;
}
else if (w < minWeight)
minWeight = w;
}
}
}
delete [] len;
// DEBUG VERIFICATION
if (false && sbug. show)
{
// chomp::homology::sbug << "[Johnson: " << result <<
// ", " << (double) stopWatch << " sec]\n";
}
return result;
} /* diGraph::Johnson */
| wType chomp::homology::diGraph< wType >::Johnson | ( | arrayType & | arr, | |
| bool | setInfinity = true, |
|||
| bool | ignoreNegLoop = false | |||
| ) | const [inline] |
The above algorithm without rounding control.
Definition at line 2263 of file digraph.h.
References chomp::homology::diGraph< wType >::Johnson().
{
const dummyRounding<wType> rounding = dummyRounding<wType> ();
return Johnson (rounding, arr, setInfinity, ignoreNegLoop);
} /* diGraph::Johnson */
| wType chomp::homology::diGraph< wType >::minMeanCycleWeight | ( | diGraph< wType > * | transposed = 0 |
) | const |
Runs the Karp algorithm for each strongly connected component of the graph and returns the minimum mean cycle weight, which can be negative.
As a byproduct, saves the transposed graph, if requested to.
Definition at line 2589 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, chomp::homology::SCC(), and chomp::homology::diGraph< wType >::weights.
{
// find the strongly connected components of the graph
multitable<int_t> compVertices, compEnds;
bool copyweights = !!transposed;
int_t countSCC = SCC (*this, compVertices, compEnds,
static_cast<diGraph<wType> *> (0), transposed, copyweights);
if (countSCC <= 0)
return 0;
// compute the maximum size of each strongly connected component
int_t maxCompSize = compEnds [0];
for (int_t comp = 1; comp < countSCC; ++ comp)
{
int_t compSize = compEnds [comp] - compEnds [comp - 1];
if (maxCompSize < compSize)
maxCompSize = compSize;
}
// allocate arrays for weights and bit fields
wType **F = new wType * [maxCompSize + 1];
BitField *finite = new BitField [maxCompSize + 1];
for (int_t i = 0; i <= maxCompSize; ++ i)
{
F [i] = new wType [maxCompSize];
finite [i]. allocate (maxCompSize);
}
// compute the numbers of vertices in each component
int_t *numbers = new int_t [nVertices];
int_t *components = new int_t [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
components [i] = -1;
int_t offset = 0;
for (int_t comp = 0; comp < countSCC; ++ comp)
{
int_t maxOffset = compEnds [comp];
int_t pos = offset;
for (; pos < maxOffset; ++ pos)
{
numbers [compVertices [pos]] = pos - offset;
components [compVertices [pos]] = comp;
}
offset = pos;
}
// compute the minimum mean cycle weight for each component
wType minWeight (0);
for (int_t comp = 0; comp < countSCC; ++ comp)
{
int_t offset = comp ? compEnds [comp - 1] :
static_cast<int_t> (0);
int_t compSize = compEnds [comp] - offset;
for (int_t i = 0; i <= compSize; ++ i)
finite [i]. clearall (compSize);
F [0] [0] = 0;
finite [0]. set (0);
// compute path progressions of given length
for (int_t len = 1; len <= compSize; ++ len)
{
// process source vertices
for (int_t i = 0; i < compSize; ++ i)
{
if (!finite [len - 1]. test (i))
continue;
wType prevWeight = F [len - 1] [i];
int_t source = compVertices [offset + i];
// process target vertices (and edges)
int_t edgeOffset = source ?
edgeEnds [source - 1] :
static_cast<int_t> (0);
int_t edgeEnd = edgeEnds [source];
for (; edgeOffset < edgeEnd; ++ edgeOffset)
{
int_t target = edges [edgeOffset];
if (components [target] != comp)
continue;
int_t j = numbers [target];
wType newWeight = prevWeight +
weights [edgeOffset];
if (!finite [len]. test (j))
{
finite [len]. set (j);
F [len] [j] = newWeight;
}
else if (newWeight < F [len] [j])
F [len] [j] = newWeight;
}
}
}
// compute the minimum mean cycle weight for this component
wType minCompWeight (0);
bool firstMin = true;
for (int_t vert = 0; vert < compSize; ++ vert)
{
if (!finite [compSize]. test (vert))
continue;
bool firstAverage = true;
wType maxAverage = 0;
for (int_t first = 0; first < compSize; ++ first)
{
if (!finite [first]. test (vert))
continue;
wType average = (F [compSize] [vert] -
F [first] [vert]) /
(compSize - first);
if (firstAverage)
{
maxAverage = average;
firstAverage = false;
}
else if (maxAverage < average)
maxAverage = average;
}
if (firstMin || (maxAverage < minCompWeight))
{
if (firstAverage)
throw "Bug in Karp's algorithm";
minCompWeight = maxAverage;
firstMin = false;
}
}
// make a correction to the total minimum if necessary
if (!comp || (minCompWeight < minWeight))
minWeight = minCompWeight;
}
// release allocated memory
delete [] components;
delete [] numbers;
for (int_t i = 0; i < maxCompSize; ++ i)
{
finite [i]. free ();
delete [] (F [i]);
}
delete [] finite;
delete [] F;
// return the computed minimum
return minWeight;
} /* diGraph::minMeanCycleWeight */
| wType chomp::homology::diGraph< wType >::minMeanCycleWeight | ( | const roundType & | rounding, | |
| diGraph< wType > * | transposed | |||
| ) | const |
A version of the above function modified for the purpose of interval arithmetic to provide the correct lower bound for the minimum mean cycle weight in a graph.
This specialization is necessary, because of the subtraction operation used in Karp's algorithm. Therefore, upper and lower bounds for the minimum path progression weights must be computed independently. The intervals are compared by comparing their lower bounds only.
Definition at line 2736 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, chomp::homology::SCC(), and chomp::homology::diGraph< wType >::weights.
{
// find the strongly connected components of the graph
multitable<int_t> compVertices, compEnds;
bool copyweights = !!transposed;
int_t countSCC = SCC (*this, compVertices, compEnds,
static_cast<diGraph<wType> *> (0), transposed, copyweights);
if (countSCC <= 0)
return 0;
// compute the maximum size of each strongly connected component
int_t maxCompSize = compEnds [0];
for (int_t comp = 1; comp < countSCC; ++ comp)
{
int_t compSize = compEnds [comp] - compEnds [comp - 1];
if (maxCompSize < compSize)
maxCompSize = compSize;
}
// allocate arrays for weights and bit fields
wType **FUpper = new wType * [maxCompSize + 1];
wType **FLower = new wType * [maxCompSize + 1];
BitField *finite = new BitField [maxCompSize + 1];
for (int_t i = 0; i <= maxCompSize; ++ i)
{
FUpper [i] = new wType [maxCompSize];
FLower [i] = new wType [maxCompSize];
finite [i]. allocate (maxCompSize);
}
// compute the numbers of vertices in each component
int_t *numbers = new int_t [nVertices];
int_t *components = new int_t [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
components [i] = -1;
int_t offset = 0;
for (int_t comp = 0; comp < countSCC; ++ comp)
{
int_t maxOffset = compEnds [comp];
int_t pos = offset;
for (; pos < maxOffset; ++ pos)
{
numbers [compVertices [pos]] = pos - offset;
components [compVertices [pos]] = comp;
}
offset = pos;
}
// compute the minimum mean cycle weight for each component
wType minWeight (0);
for (int_t comp = 0; comp < countSCC; ++ comp)
{
int_t offset = comp ? compEnds [comp - 1] :
static_cast<int_t> (0);
int_t compSize = compEnds [comp] - offset;
for (int_t i = 0; i <= compSize; ++ i)
finite [i]. clearall (compSize);
FUpper [0] [0] = 0;
FLower [0] [0] = 0;
finite [0]. set (0);
// compute path progressions of given length
for (int_t len = 1; len <= compSize; ++ len)
{
// process source vertices
for (int_t i = 0; i < compSize; ++ i)
{
if (!finite [len - 1]. test (i))
continue;
wType prevUpper = FUpper [len - 1] [i];
wType prevLower = FLower [len - 1] [i];
int_t source = compVertices [offset + i];
// process target vertices (and edges)
int_t edgeOffset = source ?
edgeEnds [source - 1] :
static_cast<int_t> (0);
int_t edgeEnd = edgeEnds [source];
for (; edgeOffset < edgeEnd; ++ edgeOffset)
{
int_t target = edges [edgeOffset];
if (components [target] != comp)
continue;
int_t j = numbers [target];
wType newUpper = rounding. add_up
(prevUpper,
weights [edgeOffset]);
wType newLower = rounding. add_down
(prevLower,
weights [edgeOffset]);
if (!finite [len]. test (j))
{
finite [len]. set (j);
FUpper [len] [j] = newUpper;
FLower [len] [j] = newLower;
}
else
{
wType &curUpper =
FUpper [len] [j];
if (newUpper < curUpper)
curUpper = newUpper;
wType &curLower =
FLower [len] [j];
if (newLower < curLower)
curLower = newLower;
}
}
}
}
// compute the minimum mean cycle weight for this component
wType minCompWeight (0);
bool firstMin = true;
for (int_t vert = 0; vert < compSize; ++ vert)
{
if (!finite [compSize]. test (vert))
continue;
bool firstAverage = true;
wType maxAverage = 0;
for (int_t first = 0; first < compSize; ++ first)
{
if (!finite [first]. test (vert))
continue;
const wType diff = rounding. sub_down
(FLower [compSize] [vert],
FUpper [first] [vert]);
wType average = rounding. div_down
(diff, compSize - first);
if (firstAverage)
{
maxAverage = average;
firstAverage = false;
}
else if (maxAverage < average)
maxAverage = average;
}
if (firstMin || (maxAverage < minCompWeight))
{
if (firstAverage)
throw "Bug in Karp's algorithm";
minCompWeight = maxAverage;
firstMin = false;
}
}
// make a correction to the total minimum if necessary
if (!comp || (minCompWeight < minWeight))
minWeight = minCompWeight;
}
// release allocated memory
delete [] components;
delete [] numbers;
for (int_t i = 0; i < maxCompSize; ++ i)
{
finite [i]. free ();
delete [] (FUpper [i]);
delete [] (FLower [i]);
}
delete [] finite;
delete [] FUpper;
delete [] FLower;
// return the computed minimum
return minWeight;
} /* diGraph::minMeanCycleWeight_intv */
| wType chomp::homology::diGraph< wType >::minMeanPathWeight | ( | const roundType & | rounding, | |
| const arrayType & | starting, | |||
| int_t | n | |||
| ) | const |
Runs an algorithm based on Karp's idea to compute the minimum mean path weight for paths starting at any of the given n vertices and of length not exceeding the number of vertices in the graph.
Returns 0 if no path starts at any of the vertices.
Definition at line 2906 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::minMeanPathWeight().
{
// allocate arrays for weights and bit fields
const int nIndices = 2;
wType **F = new wType * [nIndices];
BitField *finite = new BitField [nIndices];
for (int i = 0; i < nIndices; ++ i)
{
F [i] = new wType [nVertices];
finite [i]. allocate (nVertices);
}
// set the zero path lengths from the initial vertices
for (int_t i = 0; i < n; ++ i)
{
int_t v = starting [i];
if ((v < 0) || (v >= nVertices))
throw "Starting vertex out of range.";
F [0] [v] = 0;
finite [0]. set (v);
}
// compute path progressions of given length and average weights
wType minWeight (0);
bool firstWeight = true;
for (int_t len = 1; len <= nVertices; ++ len)
{
// determine the indices for previous and current paths
int_t prevIndex = (len - 1) & 1;
int_t curIndex = len & 1;
finite [curIndex]. clearall (nVertices);
// process source vertices
for (int_t source = 0; source < nVertices; ++ source)
{
if (!finite [prevIndex]. test (source))
continue;
wType prevWeight = F [prevIndex] [source];
// process target vertices (and edges)
int_t edgeOffset = source ?
edgeEnds [source - 1] :
static_cast<int_t> (0);
int_t edgeEnd = edgeEnds [source];
for (; edgeOffset < edgeEnd; ++ edgeOffset)
{
int_t target = edges [edgeOffset];
wType newWeight = rounding. add_down
(prevWeight, weights [edgeOffset]);
if (!finite [curIndex]. test (target))
{
finite [curIndex]. set (target);
F [curIndex] [target] = newWeight;
}
else if (newWeight < F [curIndex] [target])
F [curIndex] [target] = newWeight;
}
}
// update the minimum mean path weight
for (int_t vert = 0; vert < nVertices; ++ vert)
{
if (!finite [curIndex]. test (vert))
continue;
wType average = rounding. div_down
(F [curIndex] [vert], len);
if (firstWeight)
{
minWeight = average;
firstWeight = false;
}
else if (average < minWeight)
minWeight = average;
}
}
// release allocated memory
for (int i = 0; i < nIndices; ++ i)
{
finite [i]. free ();
delete [] (F [i]);
}
delete [] finite;
delete [] F;
// return the computed minimum
return minWeight;
} /* diGraph::minMeanPathWeight */
| wType chomp::homology::diGraph< wType >::minMeanPathWeight | ( | const arrayType & | starting, | |
| int_t | n | |||
| ) | const |
The above algorithm without rounding control.
Definition at line 2998 of file digraph.h.
References chomp::homology::diGraph< wType >::minMeanPathWeight().
{
const dummyRounding<wType> rounding = dummyRounding<wType> ();
return minMeanPathWeight (rounding, starting, n);
} /* diGraph::minMeanPathWeight */
| wType chomp::homology::diGraph< wType >::minPathWeight | ( | const roundType & | rounding, | |
| bool | ignoreNegLoop = false, |
|||
| int | sparseGraph = -1 | |||
| ) | const |
Uses the Floyd-Warshall algorithm or Johnson's algorithm, depending on the number of edges, to compute the minimum path weight between any vertices in the graph.
Throws an error message if a negative loop exists in the graph, unless "ignoreNegLoop" is set to "true". To force the use of Johnson's algorithm, set "sparseGraph" to 1, to force the use of Warshall-Floyd, set "sparseGraph" to 0, otherwise it will be determined heuristically which algorithm should be used.
Definition at line 2272 of file digraph.h.
References chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::countVertices(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::Johnson(), and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::minPathWeight().
{
// if the graph is empty, return 0 as the minimum path weight
if (nVertices <= 0)
return 0;
// allocate memory for an array of arrays to store min path weights
wType **arr = new wType * [nVertices];
for (int_t i = 0; i < nVertices; ++ i)
arr [i] = new wType [nVertices];
// determine whether to run the Floyd-Warshall algorithm
// or Johnson's algorithm
bool sparse = false;
if (sparseGraph == 1)
sparse = true;
else if (sparseGraph != 0)
{
double nEdgesD = this -> countEdges ();
double nVerticesD = this -> countVertices ();
if ((nVerticesD > 3000) && (nEdgesD < nVerticesD * 1000) &&
(nEdgesD < nVerticesD * nVerticesD / 50))
{
sparse = true;
}
}
// run the Johnson's or Floyd-Warshall algorithm
wType minWeight = sparse ?
this -> Johnson (rounding, arr, false, ignoreNegLoop) :
this -> FloydWarshall (rounding, arr, false, ignoreNegLoop);
/* // compute the minimum of all the paths
wType minWeight = arr [0] [0];
for (int_t i = 0; i < nVertices; ++ i)
{
for (int_t j = 0; j < nVertices; ++ j)
{
const wType &weight = arr [i] [j];
if (weight < minWeight)
minWeight = weight;
}
}
*/
// release the memory
for (int_t i = 0; i < nVertices; ++ i)
delete [] (arr [i]);
delete [] arr;
return minWeight;
} /* diGraph::minPathWeight */
| wType chomp::homology::diGraph< wType >::minPathWeight | ( | bool | ignoreNegLoop = false, |
|
| int | sparseGraph = -1 | |||
| ) | const |
The above algorithm without rounding control.
Definition at line 2326 of file digraph.h.
References chomp::homology::diGraph< wType >::minPathWeight().
{
const dummyRounding<wType> rounding = dummyRounding<wType> ();
return this -> minPathWeight (rounding, ignoreNegLoop, sparseGraph);
} /* diGraph::minPathWeight */
| void chomp::homology::diGraph< wType >::removeVertex | ( | int_t | vertex, | |
| bool | updateweights = false | |||
| ) | [inline] |
Removes the given vertex and all the edges going out from it, as well as the edges going towards it.
If requested, the weights in the graph are also updated. This function might be slow - it is done in the time O(V+E).
Definition at line 707 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
{
// make sure that the vertex number is within the scope
if ((vertex < 0) || (vertex >= nVertices))
throw "Trying to remove a vertex that is not in the graph.";
// remove edges that begin or end at the given vertex
int_t curEdge = 0;
int_t newEdge = 0;
int_t skipped = 0;
for (int_t v = 0; v < nVertices; ++ v)
{
// skip the edges that begin at the given vertex
if (!skipped && (v == vertex))
{
curEdge = edgeEnds [v];
++ skipped;
continue;
}
// skip the edges that point to the given vertex
int_t maxEdge = edgeEnds [v];
for (; curEdge < maxEdge; ++ curEdge)
{
if (edges [curEdge] == vertex)
continue;
int_t target = edges [curEdge];
edges [newEdge] = (target < vertex) ? target :
(target - 1);
if (updateweights)
weights [newEdge] = weights [curEdge];
++ newEdge;
}
edgeEnds [v - skipped] = newEdge;
}
// decrease the number of vertices
nVertices -= skipped;
return;
} /* diGraph::removeVertex */
| void chomp::homology::diGraph< wType >::removeVertex | ( | void | ) | [inline] |
Removes the last vertex and all the edges going out from it.
This is done in the time O(1).
Definition at line 698 of file digraph.h.
References chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::DFSforest().
| void chomp::homology::diGraph< wType >::setWeight | ( | int_t | vertex, | |
| int_t | i, | |||
| const wType & | weight | |||
| ) | [inline] |
Sets the weight of the given edge.
Definition at line 669 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, and chomp::homology::diGraph< wType >::weights.
| void chomp::homology::diGraph< wType >::setWeight | ( | int_t | edge, | |
| const wType & | weight | |||
| ) | [inline] |
Sets the weight of the given edge.
Definition at line 680 of file digraph.h.
References chomp::homology::diGraph< wType >::weights.
{
weights [edge] = weight;
return;
} /* diGraph::setWeight */
| void chomp::homology::diGraph< wType >::setWeights | ( | const Table & | tab | ) | [inline] |
Sets the weights of all the edges at a time.
The weights are pulled from the table with the [] operator.
Definition at line 687 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
| int_t chomp::homology::diGraph< wType >::shortestLoop | ( | int_t | origin | ) | const [inline] |
Computes the length of the shortest loop from the given vertex to itself.
The length is measured by counting edges on the way. Uses a stack version of the BFS algorithm. Returns the length of the loop or 0 if none.
Definition at line 1554 of file digraph.h.
References chomp::homology::diGraph< wType >::shortestPath().
{
return shortestPath (origin, origin);
} /* diGraph::shortestLoop */
| int_t chomp::homology::diGraph< wType >::shortestPath | ( | int_t | source, | |
| int_t | destination | |||
| ) | const [inline] |
Computes the length of the shortest nontrivial path from the given vertex to another one.
The length is measured by counting edges. Uses a stack version of the BFS algorithm. Returns the length of the path or 0 if none.
Definition at line 1474 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
Referenced by chomp::homology::diGraph< wType >::shortestLoop().
{
// make sure that the given vertex is present in the graph
if ((source < 0) || (source >= nVertices) ||
(destination < 0) || (destination >= nVertices))
{
throw "diGraph - shortest path: Wrong vertex number.";
}
// prepare an array of bits to store the information
// on whether the given vertices have been visited or not
BitField visited;
visited. allocate (nVertices);
visited. clearall (nVertices);
// prepare queues for the BFS algorithm
std::queue<int_t> q_vertex;
std::queue<int_t> q_depth;
// set the initial vertex
int_t vertex = source;
int_t depth = 0;
while (1)
{
// mark the current vertex as visited
visited. set (vertex);
// determine the depth of the vertices that will be analyzed
++ depth;
// determine the edges to be checked
int_t firstedge = vertex ? edgeEnds [vertex - 1] :
static_cast<int_t> (0);
int_t maxedge = edgeEnds [vertex];
// put all the unvisited destination vertices on the stack
for (int_t edge = firstedge; edge < maxedge; ++ edge)
{
// determine the vertex pointed to by this edge
int_t next = edges [edge];
// if this is the destination vertex then return
// the shortest path length; note: this vertex
// might be visited if checking a loop, so it is
// important to check the destination first
if (next == destination)
{
visited. free ();
return depth;
}
// if the vertex was already visited then skip it
if (visited. test (next))
continue;
// add the vertex to the queue
q_vertex. push (next);
q_depth. push (depth);
}
// if there are no vertices whose neighbors are to be
// analyzed and the destination vertex was not found
// then there is no path to that vertex
if (q_vertex. empty ())
{
visited. free ();
return 0;
}
// pick up a vertex stored in the queue
vertex = q_vertex. front ();
q_vertex. pop ();
depth = q_depth. front ();
q_depth. pop ();
}
} /* diGraph::shortestPath */
| outType & chomp::homology::diGraph< wType >::show | ( | outType & | out, | |
| bool | showWeights = false | |||
| ) | const [inline] |
Outputs the graph to a text stream in a human-readable format.
Definition at line 2334 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
Referenced by chomp::homology::diGraph< wType >::BellmanFord(), and chomp::homology::diGraph< wType >::Johnson().
{
out << "; Directed graph: " << nVertices << " vertices.\n";
int_t curEdge = 0;
for (int_t i = 0; i < nVertices; ++ i)
{
for (; curEdge < edgeEnds [i]; ++ curEdge)
{
out << i << " -> " << edges [curEdge];
if (showWeights)
out << " [" << weights [curEdge] << "]\n";
else
out << "\n";
}
}
out << "; This is the end of the graph.\n";
return out;
} /* diGraph::show */
| void chomp::homology::diGraph< wType >::subgraph | ( | diGraph< wType1 > & | result, | |
| const Table & | tab, | |||
| bool | copyweights = false | |||
| ) | const [inline] |
Computes a restriction of the graph to its subgraph.
The subgraph vertices are defined by nonzero entries in the supplied table. The result must be initially empty.
Definition at line 864 of file digraph.h.
References chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
{
// compute the new numbers of vertices that remain in the graph
int_t *numbers = new int_t [nVertices];
int_t curNumber = 0;
for (int_t i = 0; i < nVertices; ++ i)
{
if (tab [i])
numbers [i] = curNumber ++;
else
numbers [i] = -1;
}
// copy the edges from the old graph to the new one
for (int_t i = 0; i < nVertices; ++ i)
{
if (numbers [i] < 0)
continue;
g. addVertex ();
int_t firstEdge = i ? edgeEnds [i - 1] :
static_cast<int_t> (0);
int_t endEdge = edgeEnds [i];
for (int_t j = firstEdge; j < endEdge; ++ j)
{
int_t edgeEnd = edges [j];
if (numbers [edgeEnd] >= 0)
{
if (copyweights)
g. addEdge (numbers [edgeEnd],
weights [j]);
else
g. addEdge (numbers [edgeEnd]);
}
}
}
// clean up memory and exit
delete [] numbers;
return;
} /* diGraph::subgraph */
| void chomp::homology::diGraph< wType >::swap | ( | diGraph< wType > & | g | ) | [inline] |
Swaps the data with another graph.
Definition at line 615 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::my_swap(), chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
| void chomp::homology::diGraph< wType >::transpose | ( | diGraph< wType1 > & | result, | |
| bool | copyweights = false | |||
| ) | const [inline] |
Creates a transposed graph.
Definition at line 826 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, chomp::homology::diGraph< wType >::nVertices, and chomp::homology::diGraph< wType >::weights.
{
// prepare the resulting graph
result. nVertices = nVertices;
if (!nVertices)
return;
// compute the initial offsets for the edge numbers
for (int_t i = 0; i < nVertices; ++ i)
result. edgeEnds [i] = 0;
int_t nEdges = edgeEnds [nVertices - 1];
for (int_t i = 0; i < nEdges; ++ i)
{
if (edges [i] < nVertices - 1)
++ result. edgeEnds [edges [i] + 1];
}
for (int_t i = 2; i < nVertices; ++ i)
result. edgeEnds [i] += result. edgeEnds [i - 1];
// compute the reversed edges
int_t curEdge = 0;
for (int_t i = 0; i < nVertices; ++ i)
{
for (; curEdge < edgeEnds [i]; ++ curEdge)
{
int_t j = edges [curEdge];
int_t &offset = result. edgeEnds [j];
result. edges [offset] = i;
if (copyweights)
result. weights [offset] = weights [curEdge];
++ offset;
}
}
return;
} /* diGraph::transpose */
| void chomp::homology::diGraph< wType >::writeEdges | ( | Table & | tab | ) | const [inline] |
Fills out a table that represents all the edges of the graph.
The indices of a starting and ending vertex of the n-th edge are written to "tab [n] [0]" and "tab [n] [1]", respectively.
Definition at line 809 of file digraph.h.
References chomp::homology::diGraph< wType >::edgeEnds, chomp::homology::diGraph< wType >::edges, and chomp::homology::diGraph< wType >::nVertices.
| bool operator== | ( | const diGraph< wType1 > & | g1, | |
| const diGraph< wType2 > & | g2 | |||
| ) | [friend] |
Operator == for comparing digraphs.
No isomorphism check, just comparing with the same order of vertices. Ignores weights.
Definition at line 584 of file digraph.h.
{
if (g1. nVertices != g2. nVertices)
return false;
if (!g1. nVertices)
return true;
for (int_t i = 0; i < g1. nVertices; ++ i)
{
if (g1. edgeEnds [i] != g2. edgeEnds [i])
return false;
}
int_t nEdges = g1. edgeEnds [g1. nVertices - 1];
for (int_t i = 0; i < nEdges; ++ i)
{
if (g1. edges [i] != g2. edges [i])
return false;
}
return true;
} /* operator == */
multitable<int_t> chomp::homology::diGraph< wType >::edgeEnds [protected] |
A table with the offsets of the one-after-the-last edge of each vertex.
Definition at line 444 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::DFScolorRecurrent(), chomp::homology::diGraph< wType >::DFScolorStack(), chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent(), chomp::homology::diGraph< wType >::DFSfinishTimeStack(), chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getEdge(), chomp::homology::diGraph< wType >::getWeight(), chomp::homology::diGraph< wType >::getWeights(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::setWeight(), chomp::homology::diGraph< wType >::setWeights(), chomp::homology::diGraph< wType >::shortestPath(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), chomp::homology::diGraph< wType >::transpose(), and chomp::homology::diGraph< wType >::writeEdges().
multitable<int_t> chomp::homology::diGraph< wType >::edges [protected] |
A table with edge target numbers.
Definition at line 447 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::DFScolorRecurrent(), chomp::homology::diGraph< wType >::DFScolorStack(), chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent(), chomp::homology::diGraph< wType >::DFSfinishTimeStack(), chomp::homology::diGraph< wType >::DFSforestRecurrent(), chomp::homology::diGraph< wType >::DFSforestStack(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getEdge(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::shortestPath(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), chomp::homology::diGraph< wType >::transpose(), and chomp::homology::diGraph< wType >::writeEdges().
int_t chomp::homology::diGraph< wType >::nVertices [protected] |
The number of vertices.
Definition at line 440 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::addVertex(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::countEdges(), chomp::homology::diGraph< wType >::countVertices(), chomp::homology::diGraph< wType >::DFSfinishTime(), chomp::homology::diGraph< wType >::DFSforest(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getWeights(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::minPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::setWeights(), chomp::homology::diGraph< wType >::shortestPath(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), chomp::homology::diGraph< wType >::transpose(), and chomp::homology::diGraph< wType >::writeEdges().
multitable<wType> chomp::homology::diGraph< wType >::weights [protected] |
A table with edge weights.
Definition at line 450 of file digraph.h.
Referenced by chomp::homology::diGraph< wType >::addEdge(), chomp::homology::diGraph< wType >::BellmanFord(), chomp::homology::diGraph< wType >::Dijkstra(), chomp::homology::diGraph< wType >::Edmonds(), chomp::homology::diGraph< wType >::EdmondsOld(), chomp::homology::diGraph< wType >::FloydWarshall(), chomp::homology::diGraph< wType >::getWeight(), chomp::homology::diGraph< wType >::getWeights(), chomp::homology::diGraph< wType >::Johnson(), chomp::homology::diGraph< wType >::minMeanCycleWeight(), chomp::homology::diGraph< wType >::minMeanPathWeight(), chomp::homology::diGraph< wType >::removeVertex(), chomp::homology::diGraph< wType >::setWeight(), chomp::homology::diGraph< wType >::setWeights(), chomp::homology::diGraph< wType >::show(), chomp::homology::diGraph< wType >::subgraph(), chomp::homology::diGraph< wType >::swap(), and chomp::homology::diGraph< wType >::transpose().
1.7.1