The Original CHomP Software
Classes | Public Types | Public Member Functions | Protected Attributes | Private Member Functions | Friends | List of all members
chomp::homology::diGraph< wType > Class Template Reference

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. More...
 

Public Member Functions

 diGraph ()
 The default constructor of an empty graph. More...
 
 ~diGraph ()
 The destructor. More...
 
void swap (diGraph< wType > &g)
 Swaps the data with another graph. More...
 
void addVertex (void)
 Adds a vertex. More...
 
void addEdge (int_t target)
 Adds an edge starting at the last vertex. More...
 
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. More...
 
void setWeight (int_t vertex, int_t i, const wType &weight)
 Sets the weight of the given edge. More...
 
void setWeight (int_t edge, const wType &weight)
 Sets the weight of the given edge. More...
 
template<class Table >
void setWeights (const Table &tab)
 Sets the weights of all the edges at a time. More...
 
void removeVertex (void)
 Removes the last vertex and all the edges going out from it. More...
 
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. More...
 
int_t countVertices (void) const
 Returns the number of vertices. More...
 
int_t countEdges (void) const
 Returns the number of edges. More...
 
int_t countEdges (int_t vertex) const
 Counts the number of edges leaving the given vertex. More...
 
int_t getEdge (int_t vertex, int_t i) const
 Retrieves the given edge that leaves the given vertex. More...
 
const wType & getWeight (int_t vertex, int_t i) const
 Retrieves the weight of the given edge. More...
 
const wType & getWeight (int_t edge) const
 Retrieves the weight of the given edge. More...
 
template<class Table >
void getWeights (Table &tab) const
 Gets the weights of all the edges at a time. More...
 
template<class Table >
void writeEdges (Table &tab) const
 Fills out a table that represents all the edges of the graph. More...
 
template<class wType1 >
void transpose (diGraph< wType1 > &result, bool copyweights=false) const
 Creates a transposed graph. More...
 
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. More...
 
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. More...
 
template<class Table , class Color >
void DFScolorRecurrent (Table &tab, const Color &color, int_t vertex=0) const
 The recurrent procedure for DFScolor. More...
 
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. More...
 
template<class Table >
void DFSfinishTime (Table &tab) const
 Computes the DFS finishing time for each vertex. More...
 
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. More...
 
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. More...
 
int_t shortestLoop (int_t origin) const
 Computes the length of the shortest loop from the given vertex to itself. More...
 
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. More...
 
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. More...
 
template<class lenTable >
void Dijkstra (int_t source, lenTable &len) const
 The above algorithm without rounding control. More...
 
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. More...
 
template<class lenTable , class predTable >
bool BellmanFord (int_t source, lenTable &len, wType *infinity, predTable pred) const
 The above algorithm without rounding control. More...
 
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. More...
 
bool BellmanFord (int_t source) const
 The above algorithm without rounding control. More...
 
wType Edmonds () const
 Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the graph. More...
 
wType EdmondsOld () const
 An old implementation of the Edmonds algorithm (less efficient). More...
 
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. More...
 
template<class arrayType >
wType FloydWarshall (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const
 The above algorithm without rounding control. More...
 
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. More...
 
template<class arrayType >
wType Johnson (arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const
 The above algorithm without rounding control. More...
 
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. More...
 
wType minPathWeight (bool ignoreNegLoop=false, int sparseGraph=-1) const
 The above algorithm without rounding control. More...
 
wType minMeanCycleWeight (diGraph< wType > *transposed=0) const
 Runs Karp's algorithm for each strongly connected component of the graph and returns the minimum mean cycle weight, which can be negative. More...
 
template<class roundType >
wType minMeanCycleWeight (const roundType &rounding, diGraph< wType > *transposed) const
 A version of Karp's algorithm modified for the purpose of interval arithmetic to provide the correct lower bound for the minimum mean cycle weight in a graph. More...
 
template<class roundType , class predType >
wType minMeanCycleWeightMem (const roundType &rounding, diGraph< wType > *transposed, predType &predecessors) const
 A rigorous numerics version of Karp's algorithm modified in such a way that the memory usage is minimized, at the cost of slower execution (up to twice slower). More...
 
template<class roundType >
wType minMeanCycleWeightMem (const roundType &rounding, diGraph< wType > *transposed) const
 A version of the above which does not record predecessors. More...
 
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. More...
 
template<class arrayType >
wType minMeanPathWeight (const arrayType &starting, int_t n) const
 The above algorithm without rounding control. More...
 
template<class outType >
outType & show (outType &out, bool showWeights=false) const
 Outputs the graph to a text stream in a human-readable format. More...
 

Protected Attributes

int_t nVertices
 The number of vertices. More...
 
multitable< int_t > edgeEnds
 A table with the offsets of the one-after-the-last edge of each vertex. More...
 
multitable< int_t > edges
 A table with edge target numbers. More...
 
multitable< wType > weights
 A table with edge weights. More...
 

Private Member Functions

template<class Table >
void DFSfinishTimeRecurrent (Table &tab, int_t vertex, int_t &counter) const
 The recurrent procedure for DFSfinishTime. More...
 
template<class Table >
void DFSfinishTimeStack (Table &tab, int_t vertex, int_t &counter) const
 A stack version of the recurrent procedure for DFSfinishTime. More...
 
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. More...
 
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. More...
 

Friends

template<class wType1 , class wType2 >
bool operator== (const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
 Operator == for comparing digraphs. More...
 

Detailed Description

template<class wType = int>
class chomp::homology::diGraph< wType >

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.

Member Typedef Documentation

◆ weight_type

template<class wType = int>
typedef wType chomp::homology::diGraph< wType >::weight_type

The type of the weight of edges.

Definition at line 146 of file digraph.h.

Constructor & Destructor Documentation

◆ diGraph()

template<class wType >
chomp::homology::diGraph< wType >::diGraph
inline

The default constructor of an empty graph.

Note: The default copy constructor and assignment operator generated by the compiler are good for copying graphs.

Definition at line 585 of file digraph.h.

585 : nVertices (0),
586 edgeEnds (1024), edges (4096), weights (4096)
587{
588 return;
589} /* diGraph::diGraph */
chomp::homology::diGraph::edges
multitable< int_t > edges
A table with edge target numbers.
Definition: digraph.h:463
chomp::homology::diGraph::nVertices
int_t nVertices
The number of vertices.
Definition: digraph.h:456
chomp::homology::diGraph::edgeEnds
multitable< int_t > edgeEnds
A table with the offsets of the one-after-the-last edge of each vertex.
Definition: digraph.h:460
chomp::homology::diGraph::weights
multitable< wType > weights
A table with edge weights.
Definition: digraph.h:466

◆ ~diGraph()

template<class wType >
chomp::homology::diGraph< wType >::~diGraph
inline

The destructor.

Definition at line 592 of file digraph.h.

593{
594 return;
595} /* diGraph::~diGraph */

Member Function Documentation

◆ addEdge() [1/2]

template<class wType >
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 650 of file digraph.h.

651{
652 if (!nVertices)
653 throw "Trying to add an edge to an empty graph.";
654// if (target >= nVertices)
655// throw "Trying to add an edge to a nonexistent vertex.";
656 if (target < 0)
657 throw "Trying to add an edge to a negative vertex.";
658 int_t &offset = edgeEnds [nVertices - 1];
659 if (offset + 1 <= 0)
660 throw "Too many edges in a diGraph (limit = 2,147,483,647).";
661 edges [offset] = target;
662 ++ offset;
663 return;
664} /* diGraph::addEdge */
int_t
int int_t
Index type for indexing arrays, counting cubes, etc.
Definition: config.h:115

◆ addEdge() [2/2]

template<class wType >
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 667 of file digraph.h.

668{
669 if (!nVertices)
670 throw "Trying to add an edge to an empty graph.";
671// if (target >= nVertices)
672// throw "Trying to add an edge to a nonexistent vertex.";
673 if (target < 0)
674 throw "Trying to add an edge to a negative vertex.";
675 int_t &offset = edgeEnds [nVertices - 1];
676 if (offset + 1 <= 0)
677 throw "Too many edges in a diGraph (limit = 2,147,483,647).";
678 edges [offset] = target;
679 weights [offset] = weight;
680 ++ offset;
681 return;
682} /* diGraph::addEdge */

◆ addVertex()

template<class wType >
void chomp::homology::diGraph< wType >::addVertex ( void  )
inline

Adds a vertex.

Definition at line 641 of file digraph.h.

642{
643 edgeEnds [nVertices] = nVertices ? edgeEnds [nVertices - 1] :
644 static_cast<int_t> (0);
645 ++ nVertices;
646 return;
647} /* diGraph::addVertex */

◆ BellmanFord() [1/4]

template<class wType >
template<class roundType >
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 1791 of file digraph.h.

1793{
1794 chomp::homology::auto_array<wType> len_ptr (new wType [nVertices]);
1795 wType *len = len_ptr. get ();
1796 wType *infinity = 0;
1797 dummyArray tab;
1798 return BellmanFord (rounding, source, len, infinity, tab);
1799} /* diGraph::BellmanFord */
chomp::homology::auto_array
An auto_array template that mimics selected behaviors of the std::auto_ptr template,...
Definition: autoarray.h:54
chomp::homology::diGraph::BellmanFord
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 directe...
Definition: digraph.h:1662

◆ BellmanFord() [2/4]

template<class wType >
template<class lenTable , class predTable , class roundType >
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 1662 of file digraph.h.

1664{
1665 // make sure the source vertex number is correct
1666 if ((source < 0) || (source >= nVertices))
1667 throw "Bellman-Ford: Wrong source vertex number.";
1668
1669 // prepare marks to indicate finite values (not "infinity")
1670 BitField finite;
1671 finite. allocate (nVertices);
1672 finite. clearall (nVertices);
1673 finite. set (source);
1674 len [source] = 0;
1675
1676 // count the negative vertices
1677 int_t countNegative = 0;
1678
1679 // set the initial predecessors
1680 for (int_t i = 0; i < nVertices; ++ i)
1681 pred [i] = -1;
1682
1683 // update the lenghts of the paths repeatedly (max nVertices times)
1684 bool noNegativeLoop = false;
1685 int_t counter = 0;
1686 for (; counter <= nVertices; ++ counter)
1687 {
1688 bool modified = false;
1689 int_t curEdge = 0;
1690 for (int_t vertex = 0; vertex < nVertices; ++ vertex)
1691 {
1692 int_t maxEdge = edgeEnds [vertex];
1693 if (!finite. test (vertex))
1694 {
1695 curEdge = maxEdge;
1696 continue;
1697 }
1698 for (; curEdge < maxEdge; ++ curEdge)
1699 {
1700 int_t next = edges [curEdge];
1701 wType newlen = rounding. add_down
1702 (len [vertex], weights [curEdge]);
1703 if (!finite. test (next))
1704 {
1705 finite. set (next);
1706 modified = true;
1707 len [next] = newlen;
1708 pred [next] = vertex;
1709 if (newlen < 0)
1710 ++ countNegative;
1711 }
1712 else if (newlen < len [next])
1713 {
1714 modified = true;
1715 if (!(len [next] < 0) &&
1716 (newlen < 0))
1717 {
1718 ++ countNegative;
1719 }
1720 len [next] = newlen;
1721 pred [next] = vertex;
1722 }
1723 }
1724 }
1725 if (countNegative == nVertices)
1726 {
1727 noNegativeLoop = false;
1728 ++ counter;
1729 break;
1730 }
1731 if (!modified)
1732 {
1733 noNegativeLoop = true;
1734 ++ counter;
1735 break;
1736 }
1737 }
1738
1739 // show a message on how many loops have been done
1740 if (false && chomp::homology::sbug. show)
1741 {
1742 chomp::homology::sbug << "Bellman-Ford: " <<
1743 counter << ((counter > 1) ? " loops (" : " loop (") <<
1744 nVertices << " vertices, " << countNegative <<
1745 " negative). " <<
1746 (noNegativeLoop ? "No negative loops.\n" :
1747 "A negative loop found.\n");
1748 }
1749
1750 // compute the value for the infinity and set the undefined distances
1751 if (infinity && noNegativeLoop)
1752 {
1753 wType infty (0);
1754 bool first = true;
1755 for (int_t i = 0; i < nVertices; ++ i)
1756 {
1757 if (!finite. test (i))
1758 continue;
1759 if (first)
1760 {
1761 infty = len [i];
1762 first = false;
1763 }
1764 else if (infty < len [i])
1765 {
1766 infty = len [i];
1767 }
1768 }
1769 infty = infty + 1;
1770 for (int_t i = 0; i < nVertices; ++ i)
1771 {
1772 if (!finite. test (i))
1773 len [i] = infty;
1774 }
1775 *infinity = infty;
1776 }
1777
1778 finite. free ();
1779 return noNegativeLoop;
1780} /* diGraph::BellmanFord */
chomp::homology::diGraph::show
outType & show(outType &out, bool showWeights=false) const
Outputs the graph to a text stream in a human-readable format.
Definition: digraph.h:2353
chomp::homology::sbug
outputstream sbug
An output stream for writing additional debug messages.

References chomp::homology::sbug.

◆ BellmanFord() [3/4]

template<class wType >
bool chomp::homology::diGraph< wType >::BellmanFord ( int_t  source) const
inline

The above algorithm without rounding control.

Definition at line 1802 of file digraph.h.

1803{
1804 const dummyRounding<wType> rounding = dummyRounding<wType> ();
1805 return BellmanFord (rounding, source);
1806} /* diGraph::BellmanFord */

◆ BellmanFord() [4/4]

template<class wType >
template<class lenTable , class predTable >
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 1783 of file digraph.h.

1785{
1786 const dummyRounding<wType> rounding = dummyRounding<wType> ();
1787 return this -> BellmanFord (rounding, source, len, infinity, pred);
1788} /* diGraph::BellmanFord */

◆ countEdges() [1/2]

template<class wType >
int_t chomp::homology::diGraph< wType >::countEdges ( int_t  vertex) const
inline

Counts the number of edges leaving the given vertex.

Definition at line 781 of file digraph.h.

782{
783 if (!vertex)
784 return edgeEnds [0];
785 else
786 return edgeEnds [vertex] - edgeEnds [vertex - 1];
787} /* diGraph::countEdges */

◆ countEdges() [2/2]

template<class wType >
int_t chomp::homology::diGraph< wType >::countEdges ( void  ) const
inline

Returns the number of edges.

Definition at line 772 of file digraph.h.

773{
774 if (!nVertices)
775 return 0;
776 else
777 return edgeEnds [nVertices - 1];
778} /* diGraph::countEdges */

◆ countVertices()

template<class wType >
int_t chomp::homology::diGraph< wType >::countVertices ( void  ) const
inline

Returns the number of vertices.

Definition at line 766 of file digraph.h.

767{
768 return nVertices;
769} /* diGraph::countVertices */

◆ DFScolor()

template<class wType >
template<class Table , class Color >
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 1001 of file digraph.h.

1003{
1004 DFScolorStack (tab, color, vertex);
1005 return;
1006} /* diGraph::DFScolor */
chomp::homology::diGraph::DFScolorStack
void DFScolorStack(Table &tab, const Color &color, int_t vertex=0) const
A stack version of the recurrent procedure for DFScolor.
Definition: digraph.h:941

◆ DFScolorRecurrent()

template<class wType >
template<class Table , class Color >
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 925 of file digraph.h.

927{
928 tab [vertex] = color;
929 int_t maxEdge = edgeEnds [vertex];
930 for (int_t i = vertex ? edgeEnds [vertex - 1] :
931 static_cast<int_t> (0); i < maxEdge; ++ i)
932 {
933 int_t next = edges [i];
934 if (tab [next] != color)
935 DFScolorRecurrent (tab, color, next);
936 }
937 return;
938} /* diGraph::DFScolorRecurrent */
chomp::homology::diGraph::DFScolorRecurrent
void DFScolorRecurrent(Table &tab, const Color &color, int_t vertex=0) const
The recurrent procedure for DFScolor.
Definition: digraph.h:925

◆ DFScolorStack()

template<class wType >
template<class Table , class Color >
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 941 of file digraph.h.

943{
944 // prepare stacks for the recursion
945 std::stack<int_t> s_vertex;
946 std::stack<int_t> s_edge;
947 std::stack<int_t> s_maxedge;
948
949 // mark the current vertex as visited
950 tab [vertex] = color;
951
952 // determine the edges to be visited
953 int_t edge = vertex ? edgeEnds [vertex - 1] :
954 static_cast<int_t> (0);
955 int_t maxedge = edgeEnds [vertex];
956
957 while (1)
958 {
959 // return to the previous recursion level
960 // if all the edges have been followed
961 if (edge >= maxedge)
962 {
963 // return if this is the initial recursion level
964 if (s_vertex. empty ())
965 return;
966
967 // restore the variables from the previous level
968 vertex = s_vertex. top ();
969 s_vertex. pop ();
970 edge = s_edge. top ();
971 s_edge. pop ();
972 maxedge = s_maxedge. top ();
973 s_maxedge. pop ();
974 continue;
975 }
976
977 // go to the deeper recursion level if possible
978 int_t next = edges [edge ++];
979 if (tab [next] != color)
980 {
981 // store the previous variables at the stacks
982 s_vertex. push (vertex);
983 s_edge. push (edge);
984 s_maxedge. push (maxedge);
985
986 // set the new vertex
987 vertex = next;
988
989 // mark the new vertex as visited
990 tab [vertex] = color;
991
992 // determine the edges to be visited
993 edge = vertex ? edgeEnds [vertex - 1] :
994 static_cast<int_t> (0);
995 maxedge = edgeEnds [vertex];
996 }
997 }
998} /* diGraph::DFScolorStack */

◆ DFSfinishTime()

template<class wType >
template<class Table >
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 1099 of file digraph.h.

1100{
1101 // initialize the table and the counter
1102 for (int_t i = 0; i < nVertices; ++ i)
1103 tab [i] = 0;
1104 int_t counter = 0;
1105
1106 // compute the finishing time for each tree in the DFS forest
1107 for (int_t i = 0; i < nVertices; ++ i)
1108 {
1109 if (!tab [i])
1110 DFSfinishTimeStack (tab, i, counter);
1111 }
1112
1113 #ifdef DIGRAPH_DEBUG
1114 int_t *tabdebug = new int_t [nVertices];
1115 for (int_t i = 0; i < nVertices; ++ i)
1116 tabdebug [i] = 0;
1117 int_t counterdebug = 0;
1118 for (int_t i = 0; i < nVertices; ++ i)
1119 if (!tabdebug [i])
1120 DFSfinishTimeRecurrent (tabdebug, i, counterdebug);
1121 if (counter != counterdebug)
1122 throw "DFSfinishTime: Wrong counter.";
1123 for (int_t i = 0; i < nVertices; ++ i)
1124 {
1125 if (tab [i] != tabdebug [i])
1126 {
1127 sbug << "\nDFSfinishTime error: tabRec [" << i <<
1128 "] = " << tab [i] << ", tabStack [" << i <<
1129 "] = " << tabdebug [i] << ".\n";
1130 throw "DFSfinishTime: Wrong numbers.";
1131 }
1132 }
1133 sbug << "DEBUG: DFSfinishTime OK. ";
1134 #endif // DIGRAPH_DEBUG
1135 return;
1136} /* diGraph::DFSfinishTime */
chomp::homology::diGraph::DFSfinishTimeStack
void DFSfinishTimeStack(Table &tab, int_t vertex, int_t &counter) const
A stack version of the recurrent procedure for DFSfinishTime.
Definition: digraph.h:1033
chomp::homology::diGraph::DFSfinishTimeRecurrent
void DFSfinishTimeRecurrent(Table &tab, int_t vertex, int_t &counter) const
The recurrent procedure for DFSfinishTime.
Definition: digraph.h:1011

References chomp::homology::sbug.

◆ DFSfinishTimeRecurrent()

template<class wType >
template<class Table >
void chomp::homology::diGraph< wType >::DFSfinishTimeRecurrent ( Table &  tab,
int_t  vertex,
int_t &  counter 
) const
inlineprivate

The recurrent procedure for DFSfinishTime.

Definition at line 1011 of file digraph.h.

1013{
1014 // mark the current vertex as visited
1015 tab [vertex] = -1;
1016
1017 // call DFS for the other vertices
1018 for (int_t edge = vertex ? edgeEnds [vertex - 1] :
1019 static_cast<int_t> (0);
1020 edge < edgeEnds [vertex]; ++ edge)
1021 {
1022 int_t next = edges [edge];
1023 if (!tab [next])
1024 DFSfinishTimeRecurrent (tab, next, counter);
1025 }
1026
1027 // record the finishing time for the current vertex and return
1028 tab [vertex] = ++ counter;
1029 return;
1030} /* diGraph::DFSfinishTimeRecurrent */

◆ DFSfinishTimeStack()

template<class wType >
template<class Table >
void chomp::homology::diGraph< wType >::DFSfinishTimeStack ( Table &  tab,
int_t  vertex,
int_t &  counter 
) const
inlineprivate

A stack version of the recurrent procedure for DFSfinishTime.

Definition at line 1033 of file digraph.h.

1035{
1036 // prepare stacks for the recursion
1037 std::stack<int_t> s_vertex;
1038 std::stack<int_t> s_edge;
1039 std::stack<int_t> s_maxedge;
1040
1041 // mark the current vertex as visited
1042 tab [vertex] = -1;
1043
1044 // determine the edges to be visited
1045 int_t edge = vertex ? edgeEnds [vertex - 1] :
1046 static_cast<int_t> (0);
1047 int_t maxedge = edgeEnds [vertex];
1048
1049 while (1)
1050 {
1051 // return to the previous recursion level
1052 // if all the edges have been followed
1053 if (edge >= maxedge)
1054 {
1055 // record the finishing time
1056 // for the current vertex
1057 tab [vertex] = ++ counter;
1058
1059 // return if this is the initial recursion level
1060 if (s_vertex. empty ())
1061 return;
1062
1063 // restore the variables from the previous level
1064 vertex = s_vertex. top ();
1065 s_vertex. pop ();
1066 edge = s_edge. top ();
1067 s_edge. pop ();
1068 maxedge = s_maxedge. top ();
1069 s_maxedge. pop ();
1070 continue;
1071 }
1072
1073 // go to the deeper recursion level if possible
1074 int_t next = edges [edge ++];
1075 if (!tab [next])
1076 {
1077 // store the previous variables at the stacks
1078 s_vertex. push (vertex);
1079 s_edge. push (edge);
1080 s_maxedge. push (maxedge);
1081
1082 // set the new vertex
1083 vertex = next;
1084
1085 // mark the new vertex as visited
1086 tab [vertex] = -1;
1087
1088 // determine the edges to be visited
1089 edge = vertex ? edgeEnds [vertex - 1] :
1090 static_cast<int_t> (0);
1091 maxedge = edgeEnds [vertex];
1092 }
1093 }
1094
1095 return;
1096} /* diGraph::DFSfinishTimeStack */

◆ DFSforest()

template<class wType >
template<class Table1 , class Table2 , class Table3 >
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 1294 of file digraph.h.

1297{
1298 // prepare a table to record the numbers of DFS trees
1299 // to which the vertices belong (the tree numbers begin with 1)
1300 int_t *tab = new int_t [nVertices];
1301 for (int_t i = 0; i < nVertices; ++ i)
1302 tab [i] = 0;
1303
1304 // prepare a table to record the numbers of nontrivial trees
1305 // that correspond to the trees in 'tab' (these numbers begin with 0)
1306 int_t *ntab = new int_t [nVertices];
1307
1308 // prepare a table to record the numbers of edges already in the
1309 // scc graph; "sccEdgeAdded [n] = m" indicates that the edge
1310 // m -> n has been added to the scc graph
1311 int_t *sccEdgeAdded = sccGraph ? new int_t [nVertices] :
1312 static_cast<int_t *> (0);
1313 if (sccGraph)
1314 {
1315 for (int_t n = 0; n < nVertices; ++ n)
1316 sccEdgeAdded [n] = -1;
1317 }
1318
1319 // prepare the official DFS tree number
1320 int_t treeNumber = 0;
1321
1322 // prepare the data for keeping the nontrivial trees information
1323 int_t countTrees = 0;
1324 int_t curVertex = 0;
1325
1326 // compute the DFS trees and connections between them
1327 for (int_t i = 0; i < nVertices; ++ i)
1328 {
1329 // take the next vertex
1330 int_t vertex = ordered [i];
1331
1332 // if the vertex already belongs to some tree, skip it
1333 if (tab [vertex])
1334 continue;
1335
1336 // add a vertex corresponding to the component
1337 if (sccGraph)
1338 sccGraph -> addVertex ();
1339
1340 // remember the previous vertex number
1341 int_t prevVertex = curVertex;
1342
1343 // mark the entire component and record connections graph
1344 if (sccGraph)
1345 ntab [treeNumber] = countTrees;
1346 ++ treeNumber;
1347 bool loop = DFSforestStack (tab, ntab, vertex,
1348 treeNumber, countTrees, compVertices,
1349 curVertex, sccGraph, sccEdgeAdded);
1350
1351 // update the index bound for the vertex list
1352 compEnds [countTrees ++] = curVertex;
1353
1354 // remove the component if it is trivial
1355 if (nontrivial && !loop)
1356 {
1357 -- countTrees;
1358 curVertex = prevVertex;
1359 if (sccGraph)
1360 {
1361 ntab [treeNumber - 1] = -1;
1362 sccGraph -> removeVertex ();
1363 }
1364 }
1365 }
1366
1367 #ifdef DIGRAPH_DEBUG
1368 diGraph<wType> *sccGraphdebug = 0;
1369 if (sccGraph)
1370 sccGraphdebug = new diGraph<wType>;
1371 // prepare a table to record the numbers of DFS trees
1372 // to which the vertices belong (the tree numbers begin with 1)
1373 int_t *tabdebug = new int_t [nVertices];
1374 for (int_t i = 0; i < nVertices; ++ i)
1375 tabdebug [i] = 0;
1376
1377 // prepare a table to record the numbers of nontrivial trees
1378 // to which the vertices belong (the tree numbers begin with 0)
1379 int_t *ntabdebug = new int_t [nVertices];
1380
1381 // prepare a table to record the numbers of vertices from which
1382 // edges were added to the scc graph
1383 int_t *sccEdgeAddeddebug = sccGraph ? new int_t [nVertices] :
1384 static_cast<int_t> (0);
1385 if (sccGraph)
1386 {
1387 for (int_t n = 0; n < nVertices; ++ n)
1388 sccEdgeAddeddebug [n] = -1;
1389 }
1390 // prepare the official DFS tree number
1391 int_t treeNumberdebug = 0;
1392
1393 // prepare the data for keeping the nontrivial trees information
1394 int_t countTreesdebug = 0;
1395 int_t curVertexdebug = 0;
1396
1397 int_t *compVerticesdebug = new int_t [nVertices];
1398 int_t *compEndsdebug = new int_t [nVertices];
1399
1400 // compute the DFS trees and connections between them
1401 for (int_t i = 0; i < nVertices; ++ i)
1402 {
1403 // take the next vertex
1404 int_t vertex = ordered [i];
1405
1406 // if the vertex already belongs to some tree, skip it
1407 if (tabdebug [vertex])
1408 continue;
1409
1410 // add a vertex corresponding to the component
1411 if (sccGraphdebug)
1412 sccGraphdebug -> addVertex ();
1413
1414 // remember the previous vertex number
1415 int_t prevVertex = curVertexdebug;
1416
1417 // mark the entire component and record connections graph
1418 if (sccGraphdebug)
1419 ntabdebug [treeNumberdebug] = countTreesdebug;
1420 ++ treeNumberdebug;
1421 bool loop = DFSforestRecurrent (tabdebug, ntabdebug, vertex,
1422 treeNumberdebug, countTreesdebug, compVerticesdebug,
1423 curVertexdebug, sccGraphdebug, sccEdgeAddeddebug);
1424
1425 // update the index bound for the vertex list
1426 compEndsdebug [countTreesdebug ++] = curVertexdebug;
1427
1428 // remove the component if it is trivial
1429 if (nontrivial && !loop)
1430 {
1431 -- countTreesdebug;
1432 curVertexdebug = prevVertex;
1433 if (sccGraphdebug)
1434 {
1435 ntabdebug [treeNumberdebug - 1] = -1;
1436 sccGraphdebug -> removeVertex ();
1437 }
1438 }
1439 }
1440 if (countTrees != countTreesdebug)
1441 throw "DFSforest: Wrong countTrees.";
1442 for (int_t i = 0; i < countTrees; ++ i)
1443 if (compEnds [i] != compEndsdebug [i])
1444 throw "DFSforest: Wrong compEnds.";
1445 for (int_t i = 0; i < compEndsdebug [countTrees - 1]; ++ i)
1446 if (compVertices [i] != compVerticesdebug [i])
1447 throw "DFSforest: Wrong vertices.";
1448 if (curVertex != curVertexdebug)
1449 throw "DFSforest: Wrong curVertex.";
1450 for (int_t i = 0; i < nVertices; ++ i)
1451 if (tab [i] != tabdebug [i])
1452 throw "DFSforest: Wrong tab.";
1453 if (sccGraph)
1454 {
1455 for (int_t i = 0; i < nVertices; ++ i)
1456 if (ntab [i] != ntabdebug [i])
1457 throw "DFSforest: Wrong ntab.";
1458 if (*sccGraph != *sccGraphdebug)
1459 throw "DFSforest: Wrong graph.";
1460 }
1461 if (sccEdgeAdded)
1462 {
1463 for (int_t i = 0; i < nVertices; ++ i)
1464 if (sccEdgeAdded [i] != sccEdgeAddeddebug [i])
1465 throw "DFSforest: Wrong sccEdgeAdded.";
1466 }
1467 if (treeNumber != treeNumberdebug)
1468 throw "DFSforest: Wrong treeNumber.";
1469 sbug << "DEBUG: DFSforest OK. ";
1470 if (!sccGraph)
1471 sbug << "(Graphs not compared.) ";
1472 delete [] compVerticesdebug;
1473 delete [] compEndsdebug;
1474 if (sccGraphdebug)
1475 delete sccGraphdebug;
1476 delete [] ntabdebug;
1477 delete [] tabdebug;
1478 if (sccEdgeAddeddebug)
1479 delete [] sccEdgeAddeddebug;
1480 #endif // DIGRAPH_DEBUG
1481
1482 if (sccEdgeAdded)
1483 delete [] sccEdgeAdded;
1484 delete [] ntab;
1485 delete [] tab;
1486 return countTrees;
1487} /* diGraph::DFSforest */
chomp::homology::diGraph::DFSforestStack
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.
Definition: digraph.h:1194
chomp::homology::diGraph::DFSforestRecurrent
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.
Definition: digraph.h:1141
chomp::homology::diGraph::removeVertex
void removeVertex(void)
Removes the last vertex and all the edges going out from it.
Definition: digraph.h:714
chomp::homology::diGraph::addVertex
void addVertex(void)
Adds a vertex.
Definition: digraph.h:641

References chomp::homology::sbug.

◆ DFSforestRecurrent()

template<class wType >
template<class Table1 , class Table2 >
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
inlineprivate

The recurrent procedure for DFSforest.

Returns true iff there is a loop within the tree found.

Definition at line 1141 of file digraph.h.

1145{
1146 // add the vertex to the tree
1147 compVertices [curVertex ++] = vertex;
1148
1149 // mark the vertex as belonging to the current tree
1150 tab [vertex] = treeNumber;
1151// if (sccGraph)
1152// ntab [treeNumber - 1] = countTrees;
1153
1154 // build the tree recursively or record connections
1155 bool loop = false;
1156 for (int_t edge = vertex ? edgeEnds [vertex - 1] :
1157 static_cast<int_t> (0);
1158 edge < edgeEnds [vertex]; ++ edge)
1159 {
1160 int_t next = edges [edge];
1161 if (!tab [next])
1162 loop |= DFSforestRecurrent (tab, ntab, next,
1163 treeNumber, countTrees, compVertices,
1164 curVertex, sccGraph, sccEdgeAdded);
1165 else if (tab [next] == treeNumber)
1166 {
1167 if (sccGraph)
1168 {
1169 int_t target = ntab [treeNumber - 1];
1170 if (sccEdgeAdded [target] != treeNumber)
1171 {
1172 sccGraph -> addEdge (target);
1173 sccEdgeAdded [target] = treeNumber;
1174 }
1175 }
1176 loop = true;
1177 }
1178 else if (sccGraph)
1179 {
1180 int_t target = ntab [tab [next] - 1];
1181 if ((target >= 0) &&
1182 (sccEdgeAdded [target] != treeNumber))
1183 {
1184 sccGraph -> addEdge (target);
1185 sccEdgeAdded [target] = treeNumber;
1186 }
1187 }
1188 }
1189
1190 return loop;
1191} /* diGraph::DFSforestRecurrent */
chomp::homology::diGraph::addEdge
void addEdge(int_t target)
Adds an edge starting at the last vertex.
Definition: digraph.h:650

◆ DFSforestStack()

template<class wType >
template<class Table1 , class Table2 >
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
inlineprivate

A stack version of the recurrent procedure for DFSforest.

Definition at line 1194 of file digraph.h.

1198{
1199 // prepare stacks for the recursion
1200 std::stack<int_t> s_vertex;
1201 std::stack<int_t> s_edge;
1202 std::stack<int_t> s_maxedge;
1203 std::stack<bool> s_loop;
1204
1205 // add the vertex to the tree
1206 compVertices [curVertex ++] = vertex;
1207
1208 // mark the vertex as belonging to the current tree
1209 tab [vertex] = treeNumber;
1210// if (sccGraph)
1211// ntab [vertex] = countTrees;
1212
1213 // build the tree recursively or record connections
1214 bool loop = false;
1215 int_t edge = vertex ? edgeEnds [vertex - 1] :
1216 static_cast<int_t> (0);
1217 int_t maxedge = edgeEnds [vertex];
1218 while (1)
1219 {
1220 // return to the previous recursion level
1221 // if all the edges have been followed
1222 if (edge >= maxedge)
1223 {
1224 // return if this is the initial recursion level
1225 if (s_vertex. empty ())
1226 return loop;
1227
1228 // restore the variables from the previous level
1229 vertex = s_vertex. top ();
1230 s_vertex. pop ();
1231 edge = s_edge. top ();
1232 s_edge. pop ();
1233 maxedge = s_maxedge. top ();
1234 s_maxedge. pop ();
1235 loop |= s_loop. top ();
1236 s_loop. pop ();
1237 continue;
1238 }
1239
1240 // go to the deeper recursion level if possible
1241 int_t next = edges [edge ++];
1242 if (!tab [next])
1243 {
1244 // store the previous variables at the stacks
1245 s_vertex. push (vertex);
1246 s_edge. push (edge);
1247 s_maxedge. push (maxedge);
1248 s_loop. push (loop);
1249
1250 // set the new vertex
1251 vertex = next;
1252
1253 // add the vertex to the tree
1254 compVertices [curVertex ++] = vertex;
1255
1256 // mark the vertex as belonging to the current tree
1257 tab [vertex] = treeNumber;
1258
1259 // determine the edges to be visited
1260 loop = false;
1261 edge = vertex ? edgeEnds [vertex - 1] :
1262 static_cast<int_t> (0);
1263 maxedge = edgeEnds [vertex];
1264 }
1265 else if (tab [next] == treeNumber)
1266 {
1267 if (sccGraph)
1268 {
1269 int_t target = ntab [treeNumber - 1];
1270 if (sccEdgeAdded [target] != treeNumber)
1271 {
1272 sccGraph -> addEdge (target);
1273 sccEdgeAdded [target] = treeNumber;
1274 }
1275 }
1276 loop = true;
1277 }
1278 else if (sccGraph)
1279 {
1280 int_t target = ntab [tab [next] - 1];
1281 if ((target >= 0) &&
1282 (sccEdgeAdded [target] != treeNumber))
1283 {
1284 sccGraph -> addEdge (target);
1285 sccEdgeAdded [target] = treeNumber;
1286 }
1287 }
1288 }
1289
1290 return loop;
1291} /* diGraph::DFSforestStack */

◆ Dijkstra() [1/3]

template<class wType >
template<class lenTable , class roundType >
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 1644 of file digraph.h.

1646{
1647 this -> Dijkstra (rounding, source, len, this -> weights);
1648 return;
1649} /* diGraph::Dijkstra */
chomp::homology::diGraph::Dijkstra
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...
Definition: digraph.h:1577

◆ Dijkstra() [2/3]

template<class wType >
template<class lenTable , class weightsType , class roundType >
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 1577 of file digraph.h.

1579{
1580 // use the Fibonacci heap as a priority queue
1581 FibonacciHeap<posWeight> Q (nVertices);
1582
1583 // add the vertices to the heap with the initial shortest path
1584 // lengths: 0 to the source, plus infinity to all the others
1585 for (int_t v = 0; v < nVertices; ++ v)
1586 {
1587 posWeight w (0);
1588 if (v != source)
1589 w. setInfinity ();
1590 int_t number = Q. Insert (w);
1591 if (number != v)
1592 {
1593 throw "Wrong implementation of Fibonacci heap "
1594 "for this version of Dijkstra.";
1595 }
1596 }
1597
1598 // pick up vertices from the priority queue, record the length
1599 // of the shortest path to them, and modify the remaining paths
1600 for (int_t i = 0; i < nVertices; ++ i)
1601 {
1602 // extract the minimal vertex from the queue
1603 int_t minVertex = Q. Minimum ();
1604 posWeight minWeight = Q. ExtractMinimum ();
1605
1606 if (minWeight. isInfinity ())
1607 {
1608 len [minVertex] = -1;
1609 continue;
1610 }
1611 wType minValue = minWeight. getValue ();
1612 len [minVertex] = minValue;
1613
1614 // go through all the edges emanating from this vertex
1615 // and update the path lengths for the target vertices
1616 int_t edge = minVertex ? edgeEnds [minVertex - 1] :
1617 static_cast<int_t> (0);
1618 int_t maxEdge = edgeEnds [minVertex];
1619 for (; edge < maxEdge; ++ edge)
1620 {
1621 // determine the vertex at the other end of the edge
1622 int_t nextVertex = edges [edge];
1623
1624 // if the path that runs through the extracted
1625 // vertex is shorter, then make a correction
1626 const posWeight &nextWeight = Q. Value (nextVertex);
1627 wType newWeight = rounding. add_down (minValue,
1628 edgeWeights [edge]);
1629 if (newWeight < 0)
1630 newWeight = 0;
1631 if (nextWeight. isInfinity () ||
1632 (newWeight < nextWeight. getValue ()))
1633 {
1634 Q. DecreaseKey (nextVertex,
1635 posWeight (newWeight));
1636 }
1637 }
1638 }
1639 return;
1640} /* diGraph::Dijkstra */

◆ Dijkstra() [3/3]

template<class wType >
template<class lenTable >
void chomp::homology::diGraph< wType >::Dijkstra ( int_t  source,
lenTable &  len 
) const
inline

The above algorithm without rounding control.

Definition at line 1653 of file digraph.h.

1654{
1655 const dummyRounding<wType> rounding = dummyRounding<wType> ();
1656 this -> Dijkstra (rounding, source, len);
1657 return;
1658} /* diGraph::Dijkstra */

◆ Edmonds()

template<class wType >
wType chomp::homology::diGraph< wType >::Edmonds
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 1809 of file digraph.h.

1810{
1811 // create a list of edges with weights and sort this list
1812 std::vector<edgeTriple> edgeTriples (countEdges ());
1813 int_t prevEdge = 0;
1814 int_t curEdge = 0;
1815 for (int_t vert = 0; vert < nVertices; ++ vert)
1816 {
1817 while (curEdge < edgeEnds [vert])
1818 {
1819 edgeTriple &e = edgeTriples [curEdge];
1820 e. vert1 = vert;
1821 e. vert2 = edges [curEdge];
1822 e. weight = weights [curEdge];
1823 ++ curEdge;
1824 }
1825 prevEdge = curEdge;
1826 }
1827 std::sort (edgeTriples. begin (), edgeTriples. end ());
1828
1829 // create a forest which initially contains single vertices
1830 chomp::homology::auto_array<int_t> root_ptr (new int_t [nVertices]);
1831 int_t *root = root_ptr. get ();
1832 for (int_t vert = 0; vert < nVertices; ++ vert)
1833 {
1834 root [vert] = -1;
1835 }
1836
1837 // go through the edges and join the trees, but avoid loops
1838 wType totalWeight = 0;
1839 int_t nEdges = countEdges ();
1840 for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
1841 {
1842 // determine the roots of both vertices of the edge
1843 // and compress the paths
1844 edgeTriple &e = edgeTriples [curEdge];
1845 int_t root1 = e. vert1;
1846 while (root [root1] >= 0)
1847 {
1848 root1 = root [root1];
1849 }
1850 int_t vert1 = e. vert1;
1851 while (root [vert1] >= 0)
1852 {
1853 int_t next = root [vert1];
1854 root [vert1] = root1;
1855 vert1 = next;
1856 }
1857 int_t root2 = e. vert2;
1858 while (root [root2] >= 0)
1859 {
1860 root2 = root [root2];
1861 }
1862 int_t vert2 = e. vert2;
1863 while (root [vert2] >= 0)
1864 {
1865 int_t next = root [vert2];
1866 root [vert2] = root2;
1867 vert2 = next;
1868 }
1869
1870 // skip the edge if it closes a loop
1871 if (root1 == root2)
1872 continue;
1873
1874 // add the weight
1875 totalWeight += e. weight;
1876
1877 // join the trees
1878 root [root1] = root2;
1879 }
1880 return totalWeight;
1881} /* diGraph::Edmonds */
chomp::homology::diGraph::countEdges
int_t countEdges(void) const
Returns the number of edges.
Definition: digraph.h:772

◆ EdmondsOld()

template<class wType >
wType chomp::homology::diGraph< wType >::EdmondsOld
inline

An old implementation of the Edmonds algorithm (less efficient).

Definition at line 1884 of file digraph.h.

1885{
1886 // create a list of edges with weights and sort this list
1887 std::vector<edgeTriple> edgeTriples (countEdges ());
1888 int_t prevEdge = 0;
1889 int_t curEdge = 0;
1890 for (int_t vert = 0; vert < nVertices; ++ vert)
1891 {
1892 while (curEdge < edgeEnds [vert])
1893 {
1894 edgeTriple &e = edgeTriples [curEdge];
1895 e. vert1 = vert;
1896 e. vert2 = edges [curEdge];
1897 e. weight = weights [curEdge];
1898 ++ curEdge;
1899 }
1900 prevEdge = curEdge;
1901 }
1902 std::sort (edgeTriples. begin (), edgeTriples. end ());
1903
1904 // create a forest which initially contains single vertices
1905 chomp::homology::auto_array<int_t> forest_ptr
1906 (new int_t [nVertices]);
1907 int_t *forest = forest_ptr. get ();
1908 chomp::homology::auto_array<int_t> next_ptr
1909 (new int_t [nVertices]);
1910 int_t *next = next_ptr. get ();
1911 chomp::homology::auto_array<int_t> prev_ptr
1912 (new int_t [nVertices]);
1913 int_t *prev = prev_ptr. get ();
1914 for (int_t vert = 0; vert < nVertices; ++ vert)
1915 {
1916 forest [vert] = vert;
1917 next [vert] = -1;
1918 prev [vert] = -1;
1919 }
1920
1921 // go through the edges and join the trees, but avoid loops
1922 wType totalWeight = 0;
1923 int_t nEdges = countEdges ();
1924 for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
1925 {
1926 // check the edge and skip it if it closes a loop
1927 edgeTriple &e = edgeTriples [curEdge];
1928 if (forest [e. vert1] == forest [e. vert2])
1929 continue;
1930
1931 // add the weight
1932 totalWeight += e. weight;
1933
1934 // go to the end of the first tree
1935 int_t vert1 = e. vert1;
1936 while (next [vert1] >= 0)
1937 {
1938 vert1 = next [vert1];
1939 }
1940
1941 // go to the beginning of the second tree
1942 int_t vert2 = e. vert2;
1943 while (prev [vert2] >= 0)
1944 {
1945 vert2 = prev [vert2];
1946 }
1947
1948 // join the trees and modify the numbers
1949 next [vert1] = vert2;
1950 prev [vert2] = vert1;
1951 int_t treeNumber = forest [vert1];
1952 while (vert2 >= 0)
1953 {
1954 forest [vert2] = treeNumber;
1955 vert2 = next [vert2];
1956 }
1957 }
1958 return totalWeight;
1959} /* diGraph::EdmondsOld */

◆ FloydWarshall() [1/2]

template<class wType >
template<class arrayType >
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 2110 of file digraph.h.

2112{
2113 const dummyRounding<wType> rounding = dummyRounding<wType> ();
2114 return FloydWarshall (rounding, arr, setInfinity, ignoreNegLoop);
2115} /* diGraph::FloydWarshall */
chomp::homology::diGraph::FloydWarshall
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 ...
Definition: digraph.h:1963

◆ FloydWarshall() [2/2]

template<class wType >
template<class arrayType , class roundType >
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 1963 of file digraph.h.

1965{
1966 // do nothing if the graph is empty
1967 if (!nVertices)
1968 return 0;
1969
1970 // prepare marks to indicate finite values (not "infinity")
1971 BitField *finite = new BitField [nVertices];
1972 for (int_t i = 0; i < nVertices; ++ i)
1973 {
1974 finite [i]. allocate (nVertices);
1975 finite [i]. clearall (nVertices);
1976 }
1977
1978 // create the initial values of the array based on the edge weights
1979 int_t curEdge = 0;
1980 for (int_t source = 0; source < nVertices; ++ source)
1981 {
1982 bool diagset = false;
1983 while (curEdge < edgeEnds [source])
1984 {
1985 int_t target = edges [curEdge];
1986 const wType &weight = weights [curEdge];
1987 if (source == target)
1988 {
1989 if (weight < 0)
1990 {
1991 arr [source] [target] = weight;
1992 diagset = true;
1993 }
1994 }
1995 else
1996 {
1997 arr [source] [target] = weight;
1998 finite [source]. set (target);
1999 }
2000 ++ curEdge;
2001 }
2002 if (!diagset)
2003 arr [source] [source] = 0;
2004 finite [source]. set (source);
2005 }
2006
2007 // find the shortest paths between the vertices (dynamic programming)
2008 for (int_t k = 0; k < nVertices; ++ k)
2009 {
2010 for (int_t i = 0; i < nVertices; ++ i)
2011 {
2012 if (!finite [i]. test (k))
2013 continue;
2014 for (int_t j = 0; j < nVertices; ++ j)
2015 {
2016 if (!finite [k]. test (j))
2017 continue;
2018 const wType sum = rounding. add_down
2019 (arr [i] [k], arr [k] [j]);
2020 if (finite [i]. test (j))
2021 {
2022 if (sum < arr [i] [j])
2023 arr [i] [j] = sum;
2024 }
2025 else
2026 {
2027 arr [i] [j] = sum;
2028 finite [i]. set (j);
2029 }
2030 }
2031 }
2032 }
2033
2034 // verify if a negative loop exists by checking for a negative
2035 // result in the diagonal
2036 if (!ignoreNegLoop)
2037 {
2038 for (int_t i = 0; i < nVertices; ++ i)
2039 {
2040 if (arr [i] [i] < 0)
2041 throw "Negative loop in Floyd-Warshall.";
2042 }
2043 }
2044
2045 // prepare a variable to store the returned result
2046 wType result = 0;
2047
2048 // compute the value for the infinity and fill in the array
2049 // if requested to do so
2050 if (setInfinity)
2051 {
2052 wType &infinity = result;
2053 for (int_t i = 0; i < nVertices; ++ i)
2054 {
2055 for (int_t j = 0; j < nVertices; ++ j)
2056 {
2057 if (finite [i]. test (j) &&
2058 (infinity <= arr [i] [j]))
2059 {
2060 infinity = rounding. add_up
2061 (arr [i] [j], 1);
2062 }
2063 }
2064 }
2065 for (int_t i = 0; i < nVertices; ++ i)
2066 {
2067 for (int_t j = 0; j < nVertices; ++ j)
2068 {
2069 if (!finite [i]. test (j))
2070 arr [i] [j] = infinity;
2071 }
2072 }
2073 }
2074
2075 // otherwise, only compute the minimum path weight
2076 else
2077 {
2078 wType &minWeight = result;
2079 bool firstTime = true;
2080 for (int_t i = 0; i < nVertices; ++ i)
2081 {
2082 for (int_t j = 0; j < nVertices; ++ j)
2083 {
2084 if (finite [i]. test (j))
2085 {
2086 if (firstTime)
2087 {
2088 minWeight = arr [i] [j];
2089 firstTime = false;
2090 }
2091 else if (arr [i] [j] < minWeight)
2092 {
2093 minWeight = arr [i] [j];
2094 }
2095 }
2096 }
2097 }
2098 }
2099
2100 // release the 'finite' bitfields
2101 for (int_t i = 0; i < nVertices; ++ i)
2102 finite [i]. free ();
2103 delete [] finite;
2104
2105 return result;
2106} /* diGraph::FloydWarshall */

◆ getEdge()

template<class wType >
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 790 of file digraph.h.

791{
792 if (!vertex)
793 return edges [i];
794 else
795 return edges [edgeEnds [vertex - 1] + i];
796} /* diGraph::getEdge */

◆ getWeight() [1/2]

template<class wType >
const wType & chomp::homology::diGraph< wType >::getWeight ( int_t  edge) const
inline

Retrieves the weight of the given edge.

Definition at line 808 of file digraph.h.

809{
810 return weights [edge];
811} /* diGraph::getWeight */

◆ getWeight() [2/2]

template<class wType >
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 799 of file digraph.h.

800{
801 if (!vertex)
802 return weights [i];
803 else
804 return weights [edgeEnds [vertex - 1] + i];
805} /* diGraph::getWeight */

◆ getWeights()

template<class wType >
template<class Table >
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 814 of file digraph.h.

815{
816 if (!nVertices)
817 return;
818 int_t nEdges = edgeEnds [nVertices - 1];
819 for (int_t i = 0; i < nEdges; ++ i)
820 tab [i] = weights [i];
821 return;
822} /* diGraph::getWeights */

◆ Johnson() [1/2]

template<class wType >
template<class arrayType >
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 2282 of file digraph.h.

2284{
2285 const dummyRounding<wType> rounding = dummyRounding<wType> ();
2286 return Johnson (rounding, arr, setInfinity, ignoreNegLoop);
2287} /* diGraph::Johnson */
chomp::homology::diGraph::Johnson
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.
Definition: digraph.h:2119

◆ Johnson() [2/2]

template<class wType >
template<class arrayType , class roundType >
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 2119 of file digraph.h.

2121{
2122 // DEBUG VERIFICATION
2123 if (false && sbug. show)
2124 {
2125 timeused stopWatch;
2126 wType res = FloydWarshall (rounding,
2127 arr, setInfinity, ignoreNegLoop);
2128 chomp::homology::sbug << "\n[Floyd-Warshall: " << res <<
2129 ", " << (double) stopWatch << " sec]\n";
2130 }
2131 // debug time measurement (see below)
2132// timeused stopWatch;
2133
2134 // do nothing if the graph is empty
2135 if (!nVertices)
2136 return 0;
2137
2138 // STEP 1: Compute the shortest paths to any vertex from an
2139 // artificial extra vertex connected to every other vertex in the
2140 // graph by an edge of weight zero. Use Bellman-Ford for this.
2141 wType *len = new wType [nVertices];
2142 for (int_t i = 0; i < nVertices; ++ i)
2143 len [i] = 0;
2144
2145 // update the lenghts of the paths repeatedly (max nVertices times)
2146 bool noNegativeLoop = false;
2147 int_t counter = 0;
2148 for (; counter <= nVertices; ++ counter)
2149 {
2150 bool modified = false;
2151 int_t curEdge = 0;
2152 for (int_t vertex = 0; vertex < nVertices; ++ vertex)
2153 {
2154 int_t maxEdge = edgeEnds [vertex];
2155 for (; curEdge < maxEdge; ++ curEdge)
2156 {
2157 int_t next = edges [curEdge];
2158 wType newlen = rounding. add_down
2159 (len [vertex], weights [curEdge]);
2160 if (newlen < len [next])
2161 {
2162 // this "if" statement is necessary
2163 // because of a bug in GCC 3.4.2...
2164 if (counter > nVertices)
2165 {
2166 std::cout << vertex;
2167 }
2168 modified = true;
2169 len [next] = newlen;
2170 }
2171 }
2172 }
2173 if (!modified)
2174 {
2175 noNegativeLoop = true;
2176 ++ counter;
2177 break;
2178 }
2179 }
2180 if (!ignoreNegLoop && !noNegativeLoop)
2181 throw "Negative loop found in Johnson's algorithm.";
2182
2183 // STEP 2: Re-weigh the edges using the computed path lengths.
2184 wType *newWeights = new wType [edgeEnds [nVertices - 1]];
2185 int_t edge = 0;
2186 for (int_t vertex = 0; vertex < nVertices; ++ vertex)
2187 {
2188 int_t maxEdge = edgeEnds [vertex];
2189 for (; edge < maxEdge; ++ edge)
2190 {
2191 wType w = weights [edge];
2192 w = rounding. add_down (w, len [vertex]);
2193 w = rounding. sub_down (w, len [edges [edge]]);
2194 newWeights [edge] = (w < 0) ?
2195 static_cast<wType> (0) : w;
2196 }
2197 }
2198
2199 // STEP 3: Run the Dijkstra algorithm for every vertex to compute
2200 // the shortest paths to all the other vertices.
2201 // Negative entries indicate no path existence.
2202 for (int_t u = 0; u < nVertices; ++ u)
2203 {
2204 this -> Dijkstra (rounding, u, arr [u], newWeights);
2205 }
2206 delete [] newWeights;
2207
2208 // STEP 4: Make a correction to the computed path lengths.
2209 // Compute the value for infinity if requested to.
2210 // Otherwise compute the minimum of path lengths.
2211 wType result = 0;
2212 if (setInfinity)
2213 {
2214 wType &infinity = result;
2215 for (int_t u = 0; u < nVertices; ++ u)
2216 {
2217 for (int_t v = 0; v < nVertices; ++ v)
2218 {
2219 wType w = arr [u] [v];
2220 if (w < 0)
2221 continue;
2222 w = rounding. add_down (w, len [v]);
2223 w = rounding. sub_down (w, len [u]);
2224 if (w < infinity)
2225 continue;
2226 infinity = rounding. add_up (w, 1);
2227 }
2228 }
2229 for (int_t u = 0; u < nVertices; ++ u)
2230 {
2231 for (int_t v = 0; v < nVertices; ++ v)
2232 {
2233 wType w = arr [u] [v];
2234 if (w < 0)
2235 {
2236 arr [u] [v] = infinity;
2237 continue;
2238 }
2239 w = rounding. add_down (w, len [v]);
2240 arr [u] [v] =
2241 rounding. sub_down (w, len [u]);
2242 }
2243 }
2244 }
2245 else
2246 {
2247 wType &minWeight = result;
2248 bool firstTime = true;
2249 for (int_t u = 0; u < nVertices; ++ u)
2250 {
2251 for (int_t v = 0; v < nVertices; ++ v)
2252 {
2253 wType w = arr [u] [v];
2254 if (w < 0)
2255 continue;
2256 w = rounding. add_down (w, len [v]);
2257 w = rounding. sub_down (w, len [u]);
2258 if (firstTime)
2259 {
2260 minWeight = w;
2261 firstTime = false;
2262 }
2263 else if (w < minWeight)
2264 minWeight = w;
2265 }
2266 }
2267 }
2268 delete [] len;
2269
2270 // DEBUG VERIFICATION
2271 if (false && sbug. show)
2272 {
2273// chomp::homology::sbug << "[Johnson: " << result <<
2274// ", " << (double) stopWatch << " sec]\n";
2275 }
2276
2277 return result;
2278} /* diGraph::Johnson */

References chomp::homology::sbug.

◆ minMeanCycleWeight() [1/2]

template<class wType >
template<class roundType >
wType chomp::homology::diGraph< wType >::minMeanCycleWeight ( const roundType &  rounding,
diGraph< wType > *  transposed 
) const

A version of Karp's algorithm 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 2755 of file digraph.h.

2757{
2758 // find the strongly connected components of the graph
2759 multitable<int_t> compVertices, compEnds;
2760 bool copyweights = !!transposed;
2761 int_t countSCC = SCC (*this, compVertices, compEnds,
2762 static_cast<diGraph<wType> *> (0), transposed, copyweights);
2763 if (countSCC <= 0)
2764 return 0;
2765
2766 // compute the maximum size of each strongly connected component
2767 int_t maxCompSize = compEnds [0];
2768 for (int_t comp = 1; comp < countSCC; ++ comp)
2769 {
2770 int_t compSize = compEnds [comp] - compEnds [comp - 1];
2771 if (maxCompSize < compSize)
2772 maxCompSize = compSize;
2773 }
2774
2775 // allocate arrays for weights and bit fields
2776 wType **FUpper = new wType * [maxCompSize + 1];
2777 wType **FLower = new wType * [maxCompSize + 1];
2778 BitField *finite = new BitField [maxCompSize + 1];
2779 for (int_t i = 0; i <= maxCompSize; ++ i)
2780 {
2781 FUpper [i] = new wType [maxCompSize];
2782 FLower [i] = new wType [maxCompSize];
2783 finite [i]. allocate (maxCompSize);
2784 }
2785
2786 // compute the numbers of vertices in each component
2787 int_t *numbers = new int_t [nVertices];
2788 int_t *components = new int_t [nVertices];
2789 for (int_t i = 0; i < nVertices; ++ i)
2790 components [i] = -1;
2791 int_t offset = 0;
2792 for (int_t comp = 0; comp < countSCC; ++ comp)
2793 {
2794 int_t maxOffset = compEnds [comp];
2795 int_t pos = offset;
2796 for (; pos < maxOffset; ++ pos)
2797 {
2798 numbers [compVertices [pos]] = pos - offset;
2799 components [compVertices [pos]] = comp;
2800 }
2801 offset = pos;
2802 }
2803
2804 // compute the minimum mean cycle weight for each component
2805 wType minWeight (0);
2806 for (int_t comp = 0; comp < countSCC; ++ comp)
2807 {
2808 int_t offset = comp ? compEnds [comp - 1] :
2809 static_cast<int_t> (0);
2810 int_t compSize = compEnds [comp] - offset;
2811 for (int_t i = 0; i <= compSize; ++ i)
2812 finite [i]. clearall (compSize);
2813 FUpper [0] [0] = 0;
2814 FLower [0] [0] = 0;
2815 finite [0]. set (0);
2816 // compute path progressions of given length
2817 for (int_t len = 1; len <= compSize; ++ len)
2818 {
2819 // process source vertices
2820 for (int_t i = 0; i < compSize; ++ i)
2821 {
2822 if (!finite [len - 1]. test (i))
2823 continue;
2824 wType prevUpper = FUpper [len - 1] [i];
2825 wType prevLower = FLower [len - 1] [i];
2826 int_t source = compVertices [offset + i];
2827
2828 // process target vertices (and edges)
2829 int_t edgeOffset = source ?
2830 edgeEnds [source - 1] :
2831 static_cast<int_t> (0);
2832 int_t edgeEnd = edgeEnds [source];
2833 for (; edgeOffset < edgeEnd; ++ edgeOffset)
2834 {
2835 int_t target = edges [edgeOffset];
2836 if (components [target] != comp)
2837 continue;
2838 int_t j = numbers [target];
2839 wType newUpper = rounding. add_up
2840 (prevUpper,
2841 weights [edgeOffset]);
2842 wType newLower = rounding. add_down
2843 (prevLower,
2844 weights [edgeOffset]);
2845 if (!finite [len]. test (j))
2846 {
2847 finite [len]. set (j);
2848 FUpper [len] [j] = newUpper;
2849 FLower [len] [j] = newLower;
2850 }
2851 else
2852 {
2853 wType &curUpper =
2854 FUpper [len] [j];
2855 if (newUpper < curUpper)
2856 curUpper = newUpper;
2857 wType &curLower =
2858 FLower [len] [j];
2859 if (newLower < curLower)
2860 curLower = newLower;
2861 }
2862 }
2863 }
2864 }
2865
2866 // compute the minimum mean cycle weight for this component
2867 wType minCompWeight (0);
2868 bool firstMin = true;
2869 for (int_t vert = 0; vert < compSize; ++ vert)
2870 {
2871 if (!finite [compSize]. test (vert))
2872 continue;
2873 bool firstAverage = true;
2874 wType maxAverage = 0;
2875 for (int_t first = 0; first < compSize; ++ first)
2876 {
2877 if (!finite [first]. test (vert))
2878 continue;
2879 const wType diff = rounding. sub_down
2880 (FLower [compSize] [vert],
2881 FUpper [first] [vert]);
2882 wType average = rounding. div_down
2883 (diff, compSize - first);
2884 if (firstAverage)
2885 {
2886 maxAverage = average;
2887 firstAverage = false;
2888 }
2889 else if (maxAverage < average)
2890 maxAverage = average;
2891 }
2892 if (firstMin || (maxAverage < minCompWeight))
2893 {
2894 if (firstAverage)
2895 throw "Bug in Karp's algorithm";
2896 minCompWeight = maxAverage;
2897 firstMin = false;
2898 }
2899 }
2900
2901 // make a correction to the total minimum if necessary
2902 if (!comp || (minCompWeight < minWeight))
2903 minWeight = minCompWeight;
2904 }
2905
2906 // release allocated memory
2907 delete [] components;
2908 delete [] numbers;
2909 for (int_t i = 0; i <= maxCompSize; ++ i)
2910 {
2911 finite [i]. free ();
2912 delete [] (FUpper [i]);
2913 delete [] (FLower [i]);
2914 }
2915 delete [] finite;
2916 delete [] FUpper;
2917 delete [] FLower;
2918
2919 // return the computed minimum
2920 return minWeight;
2921} /* diGraph::minMeanCycleWeight */
chomp::homology::SCC
int_t SCC(const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds, diGraph< wType > *scc=0, diGraph< wType > *transposed=0, bool copyweights=false)
Computes strongly connected components of the graph 'g'.
Definition: digraph.h:2392

References chomp::homology::SCC().

◆ minMeanCycleWeight() [2/2]

template<class wType >
wType chomp::homology::diGraph< wType >::minMeanCycleWeight ( diGraph< wType > *  transposed = 0) const

Runs Karp's 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 2608 of file digraph.h.

2609{
2610 // find the strongly connected components of the graph
2611 multitable<int_t> compVertices, compEnds;
2612 bool copyweights = !!transposed;
2613 int_t countSCC = SCC (*this, compVertices, compEnds,
2614 static_cast<diGraph<wType> *> (0), transposed, copyweights);
2615 if (countSCC <= 0)
2616 return 0;
2617
2618 // compute the maximum size of each strongly connected component
2619 int_t maxCompSize = compEnds [0];
2620 for (int_t comp = 1; comp < countSCC; ++ comp)
2621 {
2622 int_t compSize = compEnds [comp] - compEnds [comp - 1];
2623 if (maxCompSize < compSize)
2624 maxCompSize = compSize;
2625 }
2626
2627 // allocate arrays for weights and bit fields
2628 wType **F = new wType * [maxCompSize + 1];
2629 BitField *finite = new BitField [maxCompSize + 1];
2630 for (int_t i = 0; i <= maxCompSize; ++ i)
2631 {
2632 F [i] = new wType [maxCompSize];
2633 finite [i]. allocate (maxCompSize);
2634 }
2635
2636 // compute the numbers of vertices in each component
2637 int_t *numbers = new int_t [nVertices];
2638 int_t *components = new int_t [nVertices];
2639 for (int_t i = 0; i < nVertices; ++ i)
2640 components [i] = -1;
2641 int_t offset = 0;
2642 for (int_t comp = 0; comp < countSCC; ++ comp)
2643 {
2644 int_t maxOffset = compEnds [comp];
2645 int_t pos = offset;
2646 for (; pos < maxOffset; ++ pos)
2647 {
2648 numbers [compVertices [pos]] = pos - offset;
2649 components [compVertices [pos]] = comp;
2650 }
2651 offset = pos;
2652 }
2653
2654 // compute the minimum mean cycle weight for each component
2655 wType minWeight (0);
2656 for (int_t comp = 0; comp < countSCC; ++ comp)
2657 {
2658 int_t offset = comp ? compEnds [comp - 1] :
2659 static_cast<int_t> (0);
2660 int_t compSize = compEnds [comp] - offset;
2661 for (int_t i = 0; i <= compSize; ++ i)
2662 finite [i]. clearall (compSize);
2663 F [0] [0] = 0;
2664 finite [0]. set (0);
2665 // compute path progressions of given length
2666 for (int_t len = 1; len <= compSize; ++ len)
2667 {
2668 // process source vertices
2669 for (int_t i = 0; i < compSize; ++ i)
2670 {
2671 if (!finite [len - 1]. test (i))
2672 continue;
2673 wType prevWeight = F [len - 1] [i];
2674 int_t source = compVertices [offset + i];
2675
2676 // process target vertices (and edges)
2677 int_t edgeOffset = source ?
2678 edgeEnds [source - 1] :
2679 static_cast<int_t> (0);
2680 int_t edgeEnd = edgeEnds [source];
2681 for (; edgeOffset < edgeEnd; ++ edgeOffset)
2682 {
2683 int_t target = edges [edgeOffset];
2684 if (components [target] != comp)
2685 continue;
2686 int_t j = numbers [target];
2687 wType newWeight = prevWeight +
2688 weights [edgeOffset];
2689 if (!finite [len]. test (j))
2690 {
2691 finite [len]. set (j);
2692 F [len] [j] = newWeight;
2693 }
2694 else if (newWeight < F [len] [j])
2695 F [len] [j] = newWeight;
2696 }
2697 }
2698 }
2699
2700 // compute the minimum mean cycle weight for this component
2701 wType minCompWeight (0);
2702 bool firstMin = true;
2703 for (int_t vert = 0; vert < compSize; ++ vert)
2704 {
2705 if (!finite [compSize]. test (vert))
2706 continue;
2707 bool firstAverage = true;
2708 wType maxAverage = 0;
2709 for (int_t first = 0; first < compSize; ++ first)
2710 {
2711 if (!finite [first]. test (vert))
2712 continue;
2713 wType average = (F [compSize] [vert] -
2714 F [first] [vert]) /
2715 (compSize - first);
2716 if (firstAverage)
2717 {
2718 maxAverage = average;
2719 firstAverage = false;
2720 }
2721 else if (maxAverage < average)
2722 maxAverage = average;
2723 }
2724 if (firstMin || (maxAverage < minCompWeight))
2725 {
2726 if (firstAverage)
2727 throw "Bug in Karp's algorithm";
2728 minCompWeight = maxAverage;
2729 firstMin = false;
2730 }
2731 }
2732
2733 // make a correction to the total minimum if necessary
2734 if (!comp || (minCompWeight < minWeight))
2735 minWeight = minCompWeight;
2736 }
2737
2738 // release allocated memory
2739 delete [] components;
2740 delete [] numbers;
2741 for (int_t i = 0; i <= maxCompSize; ++ i)
2742 {
2743 finite [i]. free ();
2744 delete [] (F [i]);
2745 }
2746 delete [] finite;
2747 delete [] F;
2748
2749 // return the computed minimum
2750 return minWeight;
2751} /* diGraph::minMeanCycleWeight */

References chomp::homology::SCC().

◆ minMeanCycleWeightMem() [1/2]

template<class wType >
template<class roundType >
wType chomp::homology::diGraph< wType >::minMeanCycleWeightMem ( const roundType &  rounding,
diGraph< wType > *  transposed 
) const
inline

A version of the above which does not record predecessors.

Definition at line 3381 of file digraph.h.

3383{
3384 PredecessorsIgnore predecessorsIgnore;
3385 return this -> minMeanCycleWeightMem (rounding, transposed,
3386 predecessorsIgnore);
3387} /* diGraph::minMeanCycleWeightMem */
chomp::homology::diGraph::minMeanCycleWeightMem
wType minMeanCycleWeightMem(const roundType &rounding, diGraph< wType > *transposed, predType &predecessors) const
A rigorous numerics version of Karp's algorithm modified in such a way that the memory usage is minim...
Definition: digraph.h:2925

◆ minMeanCycleWeightMem() [2/2]

template<class wType >
template<class roundType , class predType >
wType chomp::homology::diGraph< wType >::minMeanCycleWeightMem ( const roundType &  rounding,
diGraph< wType > *  transposed,
predType &  predecessors 
) const

A rigorous numerics version of Karp's algorithm modified in such a way that the memory usage is minimized, at the cost of slower execution (up to twice slower).

Additionally saves predecessors when computing the minima, as suggested by Hartmann and Orlin to retrieve the cycyle. Note that a memory conservative version of the algorithm that uses non-rigorous numerics is not programmed yet.

Definition at line 2925 of file digraph.h.

2927{
2928// NOTE: Support for CHECK_ROUNDING_WIDTH is currently in preparation.
2929
2930 // find the strongly connected components of the graph
2931 multitable<int_t> compVertices, compEnds;
2932 bool copyweights = !!transposed;
2933 int_t countSCC = SCC (*this, compVertices, compEnds,
2934 static_cast<diGraph<wType> *> (0), transposed, copyweights);
2935 if (countSCC <= 0)
2936 return 0;
2937
2938 // compute the maximum size of each strongly connected component
2939 int_t maxCompSize = compEnds [0];
2940 for (int_t comp = 1; comp < countSCC; ++ comp)
2941 {
2942 int_t compSize = compEnds [comp] - compEnds [comp - 1];
2943 if (maxCompSize < compSize)
2944 maxCompSize = compSize;
2945 }
2946
2947 // allocate arrays for weights and bit fields;
2948 // table 0 for F [0], tables 1 and 2 for F [k - 1] and F [k],
2949 // table 3 for F [n], table 4 for max of the quotients
2950 const int nTables (5);
2951 wType **FUpper = new wType * [nTables];
2952 wType **FLower = new wType * [nTables];
2953#ifdef CHECK_ROUNDING_WIDTH
2954 wType **FUpperE = new wType * [nTables];
2955 wType **FLowerE = new wType * [nTables];
2956#endif
2957 BitField *finite = new BitField [nTables];
2958 int_t *maxLength = new int_t [maxCompSize];
2959 for (int_t i = 0; i < nTables; ++ i)
2960 {
2961 FUpper [i] = new wType [maxCompSize];
2962 FLower [i] = new wType [maxCompSize];
2963#ifdef CHECK_ROUNDING_WIDTH
2964 FUpperE [i] = new wType [maxCompSize];
2965 FLowerE [i] = new wType [maxCompSize];
2966#endif
2967 finite [i]. allocate (maxCompSize);
2968 }
2969
2970 // compute the numbers of vertices in each component
2971 int_t *numbers = new int_t [nVertices];
2972 int_t *components = new int_t [nVertices];
2973 for (int_t i = 0; i < nVertices; ++ i)
2974 components [i] = -1;
2975 int_t offset = 0;
2976 for (int_t comp = 0; comp < countSCC; ++ comp)
2977 {
2978 int_t maxOffset = compEnds [comp];
2979 int_t pos = offset;
2980 for (; pos < maxOffset; ++ pos)
2981 {
2982 numbers [compVertices [pos]] = pos - offset;
2983 components [compVertices [pos]] = comp;
2984 }
2985 offset = pos;
2986 }
2987
2988 // compute the minimum mean cycle weight for each component
2989 wType minWeight (0);
2990#ifdef CHECK_ROUNDING_WIDTH
2991 wType minWeightE (0);
2992#endif
2993 // and remember the minimizing vertex in the formula for min max ...
2994 // as well as the size of that component
2995 int_t minVert (0);
2996 int_t minCompsize (0);
2997 for (int_t comp = 0; comp < countSCC; ++ comp)
2998 {
2999 int_t offset = comp ? compEnds [comp - 1] :
3000 static_cast<int_t> (0);
3001 int_t compSize = compEnds [comp] - offset;
3002 finite [0]. clearall (compSize);
3003 finite [4]. clearall (compSize);
3004 for (int_t i = 0; i < compSize; ++ i)
3005 maxLength [i] = -1;
3006 FUpper [0] [0] = 0;
3007 FLower [0] [0] = 0;
3008#ifdef CHECK_ROUNDING_WIDTH
3009 FUpperE [0] [0] = 0;
3010 FLowerE [0] [0] = 0;
3011#endif
3012 finite [0]. set (0);
3013
3014 // Pass 1: compute path progressions of maximal length
3015 const int_t maxLength1 (compSize + 1);
3016 for (int_t len = 1; len < maxLength1; ++ len)
3017 {
3018 // determine tables to use and clear the current one
3019 int_t prevIndex ((len == 1) ?
3020 0 : (((len - 1) & 1) + 1));
3021 int_t curIndex ((len == compSize) ?
3022 3 : ((len & 1) + 1));
3023 finite [curIndex]. clearall (compSize);
3024
3025 // process all the edges starting at vertices
3026 // to which finite paths are already known
3027 for (int_t i = finite [prevIndex].
3028 find (0, compSize);
3029 (i >= 0) && (i < compSize);
3030 i = finite [prevIndex]. find
3031 (i + 1, compSize))
3032 // for (int_t i = 0; i < compSize; ++ i)
3033 {
3034 // if (!finite [prevIndex]. test (i))
3035 // throw "Programming bug: infinite.";
3036 int_t source = compVertices [offset + i];
3037
3038 // process target vertices (and edges)
3039 int_t edgeEnd = edgeEnds [source];
3040 for (int_t edgeOffset = source ?
3041 edgeEnds [source - 1] :
3042 static_cast<int_t> (0);
3043 edgeOffset < edgeEnd; ++ edgeOffset)
3044 {
3045 int_t target = edges [edgeOffset];
3046 if (components [target] != comp)
3047 continue;
3048 int_t j = numbers [target];
3049 wType newLower = rounding. add_down
3050 (FLower [prevIndex] [i],
3051 weights [edgeOffset]);
3052#ifdef CHECK_ROUNDING_WIDTH
3053 wType newLowerE = rounding. add_up
3054 (FLowerE [prevIndex] [i],
3055 weights [edgeOffset]);
3056#endif
3057
3058 // if this is the first time that
3059 // a path of this length
3060 // to the vertex was encountered
3061 if (!finite [curIndex]. test (j))
3062 {
3063 finite [curIndex]. set (j);
3064 FLower [curIndex] [j] =
3065 newLower;
3066#ifdef CHECK_ROUNDING_WIDTH
3067 FLowerE [curIndex] [j] =
3068 newLowerE;
3069#endif
3070 predecessors. add (target,
3071 source, len);
3072 maxLength [j] = len;
3073 }
3074 // if a better path of this length
3075 // to the vertex was found
3076 else if (newLower <
3077 FLower [curIndex] [j])
3078 {
3079 FLower [curIndex] [j] =
3080 newLower;
3081#ifdef CHECK_ROUNDING_WIDTH
3082 FLowerE [curIndex] [j] =
3083 newLowerE;
3084#endif
3085 predecessors. add (target,
3086 source, len);
3087 maxLength [j] = len;
3088 }
3089 }
3090 }
3091 }
3092
3093 // set up the mean average at level 0
3094 finite [4]. set (0);
3095 FLower [4] [0] = rounding. div_down (FLower [3] [0],
3096 compSize);
3097#ifdef CHECK_ROUNDING_WIDTH
3098 FLowerE [4] [0] = rounding. div_up (FLowerE [3] [0],
3099 compSize);
3100#endif
3101
3102 // Pass 2: compute path progressions of all the lengths and
3103 // update the max values of the quotients for each vertex
3104 const int_t maxLength2 (compSize);
3105 for (int_t len = 1; len < maxLength2; ++ len)
3106 {
3107 // determine tables to use and clear the current one
3108 int_t prevIndex ((len == 1) ?
3109 0 : (((len - 1) & 1) + 1));
3110 int_t curIndex ((len & 1) + 1);
3111 finite [curIndex]. clearall (compSize);
3112
3113 // process all the edges starting at vertices
3114 // to which finite paths are already known
3115 for (int_t i = finite [prevIndex].
3116 find (0, compSize);
3117 (i >= 0) && (i < compSize);
3118 i = finite [prevIndex]. find
3119 (i + 1, compSize))
3120 // for (int_t i = 0; i < compSize; ++ i)
3121 {
3122 // if (!finite [prevIndex]. test (i))
3123 // throw "Programming bug: infinite.";
3124 int_t source = compVertices [offset + i];
3125
3126 // process target vertices (and edges)
3127 int_t edgeEnd = edgeEnds [source];
3128 for (int_t edgeOffset = source ?
3129 edgeEnds [source - 1] :
3130 static_cast<int_t> (0);
3131 edgeOffset < edgeEnd; ++ edgeOffset)
3132 {
3133 int_t target = edges [edgeOffset];
3134 if (components [target] != comp)
3135 continue;
3136 int_t j = numbers [target];
3137 wType newUpper = rounding. add_up
3138 (FUpper [prevIndex] [i],
3139 weights [edgeOffset]);
3140#ifdef CHECK_ROUNDING_WIDTH
3141 wType newUpperE = rounding. add_down
3142 (FUpperE [prevIndex] [i],
3143 weights [edgeOffset]);
3144#endif
3145 // if this is the first time that
3146 // a path of this length
3147 // to the vertex was encountered
3148 if (!finite [curIndex]. test (j))
3149 {
3150 finite [curIndex]. set (j);
3151 FUpper [curIndex] [j] =
3152 newUpper;
3153#ifdef CHECK_ROUNDING_WIDTH
3154 FUpperE [curIndex] [j] =
3155 newUpperE;
3156#endif
3157 }
3158 // if a better path of this length
3159 // to the vertex was found
3160 else if (newUpper <
3161 FUpper [curIndex] [j])
3162 {
3163 FUpper [curIndex] [j] =
3164 newUpper;
3165#ifdef CHECK_ROUNDING_WIDTH
3166 FUpperE [curIndex] [j] =
3167 newUpperE;
3168#endif
3169 }
3170 // otherwise, it is not necessary
3171 // to update the max average weight
3172 else
3173 {
3174 continue;
3175 }
3176
3177 // update the max average weight
3178 if (!finite [3]. test (j))
3179 continue;
3180 const wType diff = rounding. sub_down
3181 (FLower [3] [j],
3182 FUpper [curIndex] [j]);
3183#ifdef CHECK_ROUNDING_WIDTH
3184 const wType diffE = rounding. sub_up
3185 (FLowerE [3] [j],
3186 FUpperE [curIndex] [j]);
3187#endif
3188 const wType average = rounding.
3189 div_down (diff,
3190 compSize - len);
3191#ifdef CHECK_ROUNDING_WIDTH
3192 const wType averageE = rounding.
3193 div_up (diffE,
3194 compSize - len);
3195#endif
3196 if (!finite [4]. test (j))
3197 {
3198 finite [4]. set (j);
3199 FLower [4] [j] = average;
3200#ifdef CHECK_ROUNDING_WIDTH
3201 FLowerE [4] [j] = averageE;
3202#endif
3203 }
3204 else if (FLower [4] [j] < average)
3205 {
3206 FLower [4] [j] = average;
3207#ifdef CHECK_ROUNDING_WIDTH
3208 FLowerE [4] [j] = averageE;
3209#endif
3210 }
3211 }
3212 }
3213 }
3214
3215 // compute the minimum mean cycle weight for this component
3216 wType minCompWeight (0);
3217#ifdef CHECK_ROUNDING_WIDTH
3218 wType minCompWeightE (0);
3219#endif
3220 // and remember the minimizing vertex for the component
3221 int_t minCompVert (0);
3222 int_t maxCompLength (0);
3223 for (int_t vert = 0; vert < compSize; ++ vert)
3224 {
3225 if (!finite [4]. test (vert))
3226 continue;
3227 if (!vert || (FLower [4] [vert] < minCompWeight))
3228 {
3229 minCompWeight = FLower [4] [vert];
3230#ifdef CHECK_ROUNDING_WIDTH
3231 minCompWeightE = FLowerE [4] [vert];
3232#endif
3233 minCompVert = compVertices [offset + vert];
3234 maxCompLength = maxLength [vert];
3235 }
3236 }
3237
3238 // make a correction to the total minimum if necessary
3239 if (!comp || (minCompWeight < minWeight))
3240 {
3241 minWeight = minCompWeight;
3242#ifdef CHECK_ROUNDING_WIDTH
3243 minWeightE = minCompWeightE;
3244#endif
3245 minVert = minCompVert;
3246 minCompsize = maxCompLength;
3247 }
3248 }
3249
3250 // mark the minimizing vertex in the predecessors structure
3251 predecessors. add (minVert, minVert, -minCompsize);
3252
3253 // release allocated memory
3254 delete [] components;
3255 delete [] numbers;
3256 for (int_t i = 0; i < nTables; ++ i)
3257 {
3258 finite [i]. free ();
3259 delete [] (FUpper [i]);
3260 delete [] (FLower [i]);
3261#ifdef CHECK_ROUNDING_WIDTH
3262 delete [] (FUpperE [i]);
3263 delete [] (FLowerE [i]);
3264#endif
3265 }
3266 delete [] finite;
3267 delete [] maxLength;
3268 delete [] FUpper;
3269 delete [] FLower;
3270#ifdef CHECK_ROUNDING_WIDTH
3271 delete [] FUpperE;
3272 delete [] FLowerE;
3273#endif
3274
3275#ifdef CHECK_ROUNDING_WIDTH
3276 // show the loss of precision caused by rounding
3277 chomp::homology::sbug << "\nLoss of precision info: [" <<
3278 minWeight << ", " << minWeightE <<
3279 "], width: " << (minWeightE - minWeight) << ".\n";
3280#endif
3281
3282 // return the computed minimum
3283 return minWeight;
3284} /* diGraph::minMeanCycleWeightMem */

References chomp::homology::sbug, and chomp::homology::SCC().

◆ minMeanPathWeight() [1/2]

template<class wType >
template<class arrayType >
wType chomp::homology::diGraph< wType >::minMeanPathWeight ( const arrayType &  starting,
int_t  n 
) const

The above algorithm without rounding control.

Definition at line 3484 of file digraph.h.

3486{
3487 const dummyRounding<wType> rounding = dummyRounding<wType> ();
3488 return minMeanPathWeight (rounding, starting, n);
3489} /* diGraph::minMeanPathWeight */
chomp::homology::diGraph::minMeanPathWeight
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 ...
Definition: digraph.h:3391

◆ minMeanPathWeight() [2/2]

template<class wType >
template<class arrayType , class roundType >
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 3391 of file digraph.h.

3393{
3394 // allocate arrays for weights and bit fields
3395 const int nIndices = 2;
3396 wType **F = new wType * [nIndices];
3397 BitField *finite = new BitField [nIndices];
3398 for (int i = 0; i < nIndices; ++ i)
3399 {
3400 F [i] = new wType [nVertices];
3401 finite [i]. allocate (nVertices);
3402 }
3403
3404 // set the zero path lengths from the initial vertices
3405 for (int_t i = 0; i < n; ++ i)
3406 {
3407 int_t v = starting [i];
3408 if ((v < 0) || (v >= nVertices))
3409 throw "Starting vertex out of range.";
3410 F [0] [v] = 0;
3411 finite [0]. set (v);
3412 }
3413
3414 // compute path progressions of given length and average weights
3415 wType minWeight (0);
3416 bool firstWeight = true;
3417 int_t maxLength (nVertices + 1);
3418 for (int_t len = 1; len < maxLength; ++ len)
3419 {
3420 // determine the indices for previous and current paths
3421 int_t prevIndex = (len - 1) & 1;
3422 int_t curIndex = len & 1;
3423 finite [curIndex]. clearall (nVertices);
3424
3425 // process source vertices
3426 for (int_t source = 0; source < nVertices; ++ source)
3427 {
3428 if (!finite [prevIndex]. test (source))
3429 continue;
3430 wType prevWeight = F [prevIndex] [source];
3431
3432 // process target vertices (and edges)
3433 int_t edgeOffset = source ?
3434 edgeEnds [source - 1] :
3435 static_cast<int_t> (0);
3436 int_t edgeEnd = edgeEnds [source];
3437 for (; edgeOffset < edgeEnd; ++ edgeOffset)
3438 {
3439 int_t target = edges [edgeOffset];
3440 wType newWeight = rounding. add_down
3441 (prevWeight, weights [edgeOffset]);
3442 if (!finite [curIndex]. test (target))
3443 {
3444 finite [curIndex]. set (target);
3445 F [curIndex] [target] = newWeight;
3446 }
3447 else if (newWeight < F [curIndex] [target])
3448 F [curIndex] [target] = newWeight;
3449 }
3450 }
3451
3452 // update the minimum mean path weight
3453 for (int_t vert = 0; vert < nVertices; ++ vert)
3454 {
3455 if (!finite [curIndex]. test (vert))
3456 continue;
3457 wType average = rounding. div_down
3458 (F [curIndex] [vert], len);
3459 if (firstWeight)
3460 {
3461 minWeight = average;
3462 firstWeight = false;
3463 }
3464 else if (average < minWeight)
3465 minWeight = average;
3466 }
3467 }
3468
3469 // release allocated memory
3470 for (int i = 0; i < nIndices; ++ i)
3471 {
3472 finite [i]. free ();
3473 delete [] (F [i]);
3474 }
3475 delete [] finite;
3476 delete [] F;
3477
3478 // return the computed minimum
3479 return minWeight;
3480} /* diGraph::minMeanPathWeight */

◆ minPathWeight() [1/2]

template<class wType >
wType chomp::homology::diGraph< wType >::minPathWeight ( bool  ignoreNegLoop = false,
int  sparseGraph = -1 
) const

The above algorithm without rounding control.

Definition at line 2345 of file digraph.h.

2347{
2348 const dummyRounding<wType> rounding = dummyRounding<wType> ();
2349 return this -> minPathWeight (rounding, ignoreNegLoop, sparseGraph);
2350} /* diGraph::minPathWeight */
chomp::homology::diGraph::minPathWeight
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,...
Definition: digraph.h:2291

◆ minPathWeight() [2/2]

template<class wType >
template<class roundType >
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 2291 of file digraph.h.

2293{
2294 // if the graph is empty, return 0 as the minimum path weight
2295 if (nVertices <= 0)
2296 return 0;
2297
2298 // allocate memory for an array of arrays to store min path weights
2299 wType **arr = new wType * [nVertices];
2300 for (int_t i = 0; i < nVertices; ++ i)
2301 arr [i] = new wType [nVertices];
2302
2303 // determine whether to run the Floyd-Warshall algorithm
2304 // or Johnson's algorithm
2305 bool sparse = false;
2306 if (sparseGraph == 1)
2307 sparse = true;
2308 else if (sparseGraph != 0)
2309 {
2310 double nEdgesD = this -> countEdges ();
2311 double nVerticesD = this -> countVertices ();
2312 if ((nVerticesD > 3000) && (nEdgesD < nVerticesD * 1000) &&
2313 (nEdgesD < nVerticesD * nVerticesD / 50))
2314 {
2315 sparse = true;
2316 }
2317 }
2318
2319 // run the Johnson's or Floyd-Warshall algorithm
2320 wType minWeight = sparse ?
2321 this -> Johnson (rounding, arr, false, ignoreNegLoop) :
2322 this -> FloydWarshall (rounding, arr, false, ignoreNegLoop);
2323
2324/* // compute the minimum of all the paths
2325 wType minWeight = arr [0] [0];
2326 for (int_t i = 0; i < nVertices; ++ i)
2327 {
2328 for (int_t j = 0; j < nVertices; ++ j)
2329 {
2330 const wType &weight = arr [i] [j];
2331 if (weight < minWeight)
2332 minWeight = weight;
2333 }
2334 }
2335*/
2336 // release the memory
2337 for (int_t i = 0; i < nVertices; ++ i)
2338 delete [] (arr [i]);
2339 delete [] arr;
2340
2341 return minWeight;
2342} /* diGraph::minPathWeight */
chomp::homology::diGraph::countVertices
int_t countVertices(void) const
Returns the number of vertices.
Definition: digraph.h:766

◆ removeVertex() [1/2]

template<class wType >
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 723 of file digraph.h.

724{
725 // make sure that the vertex number is within the scope
726 if ((vertex < 0) || (vertex >= nVertices))
727 throw "Trying to remove a vertex that is not in the graph.";
728
729 // remove edges that begin or end at the given vertex
730 int_t curEdge = 0;
731 int_t newEdge = 0;
732 int_t skipped = 0;
733 for (int_t v = 0; v < nVertices; ++ v)
734 {
735 // skip the edges that begin at the given vertex
736 if (!skipped && (v == vertex))
737 {
738 curEdge = edgeEnds [v];
739 ++ skipped;
740 continue;
741 }
742
743 // skip the edges that point to the given vertex
744 int_t maxEdge = edgeEnds [v];
745 for (; curEdge < maxEdge; ++ curEdge)
746 {
747 if (edges [curEdge] == vertex)
748 continue;
749 int_t target = edges [curEdge];
750 edges [newEdge] = (target < vertex) ? target :
751 (target - 1);
752 if (updateweights)
753 weights [newEdge] = weights [curEdge];
754 ++ newEdge;
755 }
756 edgeEnds [v - skipped] = newEdge;
757 }
758
759 // decrease the number of vertices
760 nVertices -= skipped;
761
762 return;
763} /* diGraph::removeVertex */

◆ removeVertex() [2/2]

template<class wType >
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 714 of file digraph.h.

715{
716 if (!nVertices)
717 throw "Trying to remove a vertex from the empty graph.";
718 -- nVertices;
719 return;
720} /* diGraph::removeVertex */

◆ setWeight() [1/2]

template<class wType >
void chomp::homology::diGraph< wType >::setWeight ( int_t  edge,
const wType &  weight 
)
inline

Sets the weight of the given edge.

Definition at line 696 of file digraph.h.

697{
698 weights [edge] = weight;
699 return;
700} /* diGraph::setWeight */

◆ setWeight() [2/2]

template<class wType >
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 685 of file digraph.h.

687{
688 if (!vertex)
689 weights [i] = weight;
690 else
691 weights [edgeEnds [vertex - 1] + i] = weight;
692 return;
693} /* diGraph::setWeight */

◆ setWeights()

template<class wType >
template<class Table >
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 703 of file digraph.h.

704{
705 if (!nVertices)
706 return;
707 int_t nEdges = edgeEnds [nVertices - 1];
708 for (int_t i = 0; i < nEdges; ++ i)
709 weights [i] = tab [i];
710 return;
711} /* diGraph::setWeights */

◆ shortestLoop()

template<class wType >
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 1570 of file digraph.h.

1571{
1572 return shortestPath (origin, origin);
1573} /* diGraph::shortestLoop */
chomp::homology::diGraph::shortestPath
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.
Definition: digraph.h:1490

◆ shortestPath()

template<class wType >
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 1490 of file digraph.h.

1492{
1493 // make sure that the given vertex is present in the graph
1494 if ((source < 0) || (source >= nVertices) ||
1495 (destination < 0) || (destination >= nVertices))
1496 {
1497 throw "diGraph - shortest path: Wrong vertex number.";
1498 }
1499
1500 // prepare an array of bits to store the information
1501 // on whether the given vertices have been visited or not
1502 BitField visited;
1503 visited. allocate (nVertices);
1504 visited. clearall (nVertices);
1505
1506 // prepare queues for the BFS algorithm
1507 std::queue<int_t> q_vertex;
1508 std::queue<int_t> q_depth;
1509
1510 // set the initial vertex
1511 int_t vertex = source;
1512 int_t depth = 0;
1513
1514 while (1)
1515 {
1516 // mark the current vertex as visited
1517 visited. set (vertex);
1518
1519 // determine the depth of the vertices that will be analyzed
1520 ++ depth;
1521
1522 // determine the edges to be checked
1523 int_t firstedge = vertex ? edgeEnds [vertex - 1] :
1524 static_cast<int_t> (0);
1525 int_t maxedge = edgeEnds [vertex];
1526
1527 // put all the unvisited destination vertices on the stack
1528 for (int_t edge = firstedge; edge < maxedge; ++ edge)
1529 {
1530 // determine the vertex pointed to by this edge
1531 int_t next = edges [edge];
1532
1533 // if this is the destination vertex then return
1534 // the shortest path length; note: this vertex
1535 // might be visited if checking a loop, so it is
1536 // important to check the destination first
1537 if (next == destination)
1538 {
1539 visited. free ();
1540 return depth;
1541 }
1542
1543 // if the vertex was already visited then skip it
1544 if (visited. test (next))
1545 continue;
1546
1547 // add the vertex to the queue
1548 q_vertex. push (next);
1549 q_depth. push (depth);
1550 }
1551
1552 // if there are no vertices whose neighbors are to be
1553 // analyzed and the destination vertex was not found
1554 // then there is no path to that vertex
1555 if (q_vertex. empty ())
1556 {
1557 visited. free ();
1558 return 0;
1559 }
1560
1561 // pick up a vertex stored in the queue
1562 vertex = q_vertex. front ();
1563 q_vertex. pop ();
1564 depth = q_depth. front ();
1565 q_depth. pop ();
1566 }
1567} /* diGraph::shortestPath */

◆ show()

template<class wType >
template<class outType >
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 2353 of file digraph.h.

2354{
2355 out << "; Directed graph: " << nVertices << " vertices.\n";
2356 int_t curEdge = 0;
2357 for (int_t i = 0; i < nVertices; ++ i)
2358 {
2359 for (; curEdge < edgeEnds [i]; ++ curEdge)
2360 {
2361 out << i << " -> " << edges [curEdge];
2362 if (showWeights)
2363 out << " [" << weights [curEdge] << "]\n";
2364 else
2365 out << "\n";
2366 }
2367 }
2368 out << "; This is the end of the graph.\n";
2369 return out;
2370} /* diGraph::show */

◆ subgraph()

template<class wType >
template<class Table , class wType1 >
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 880 of file digraph.h.

882{
883 // compute the new numbers of vertices that remain in the graph
884 int_t *numbers = new int_t [nVertices];
885 int_t curNumber = 0;
886 for (int_t i = 0; i < nVertices; ++ i)
887 {
888 if (tab [i])
889 numbers [i] = curNumber ++;
890 else
891 numbers [i] = -1;
892 }
893
894 // copy the edges from the old graph to the new one
895 for (int_t i = 0; i < nVertices; ++ i)
896 {
897 if (numbers [i] < 0)
898 continue;
899 g. addVertex ();
900 int_t firstEdge = i ? edgeEnds [i - 1] :
901 static_cast<int_t> (0);
902 int_t endEdge = edgeEnds [i];
903 for (int_t j = firstEdge; j < endEdge; ++ j)
904 {
905 int_t edgeEnd = edges [j];
906 if (numbers [edgeEnd] >= 0)
907 {
908 if (copyweights)
909 g. addEdge (numbers [edgeEnd],
910 weights [j]);
911 else
912 g. addEdge (numbers [edgeEnd]);
913 }
914 }
915 }
916
917 // clean up memory and exit
918 delete [] numbers;
919 return;
920} /* diGraph::subgraph */

◆ swap()

template<class wType >
void chomp::homology::diGraph< wType >::swap ( diGraph< wType > &  g)
inline

Swaps the data with another graph.

Definition at line 631 of file digraph.h.

632{
633 std::swap (nVertices, g. nVertices);
634 edgeEnds. swap (g. edgeEnds);
635 edges. swap (g. edges);
636 weights. swap (g. weights);
637 return;
638} /* diGraph::swap */
chomp::homology::diGraph::swap
void swap(diGraph< wType > &g)
Swaps the data with another graph.
Definition: digraph.h:631
chomp::multiwork::swap
void swap(mwWorkerData &data1, mwWorkerData &data2)
Definition: mwcoord.h:108

References chomp::multiwork::swap().

◆ transpose()

template<class wType >
template<class wType1 >
void chomp::homology::diGraph< wType >::transpose ( diGraph< wType1 > &  result,
bool  copyweights = false 
) const
inline

Creates a transposed graph.

Definition at line 842 of file digraph.h.

844{
845 // prepare the resulting graph
846 result. nVertices = nVertices;
847 if (!nVertices)
848 return;
849
850 // compute the initial offsets for the edge numbers
851 for (int_t i = 0; i < nVertices; ++ i)
852 result. edgeEnds [i] = 0;
853 int_t nEdges = edgeEnds [nVertices - 1];
854 for (int_t i = 0; i < nEdges; ++ i)
855 {
856 if (edges [i] < nVertices - 1)
857 ++ result. edgeEnds [edges [i] + 1];
858 }
859 for (int_t i = 2; i < nVertices; ++ i)
860 result. edgeEnds [i] += result. edgeEnds [i - 1];
861
862 // compute the reversed edges
863 int_t curEdge = 0;
864 for (int_t i = 0; i < nVertices; ++ i)
865 {
866 for (; curEdge < edgeEnds [i]; ++ curEdge)
867 {
868 int_t j = edges [curEdge];
869 int_t &offset = result. edgeEnds [j];
870 result. edges [offset] = i;
871 if (copyweights)
872 result. weights [offset] = weights [curEdge];
873 ++ offset;
874 }
875 }
876 return;
877} /* diGraph::transpose */

◆ writeEdges()

template<class wType >
template<class Table >
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 825 of file digraph.h.

826{
827 int_t curEdge = 0;
828 for (int_t curVertex = 0; curVertex < nVertices; ++ curVertex)
829 {
830 int_t maxEdge = edgeEnds [curVertex];
831 while (curEdge < maxEdge)
832 {
833 tab [curEdge] [0] = curVertex;
834 tab [curEdge] [1] = edges [curEdge];
835 ++ curEdge;
836 }
837 }
838 return;
839} /* diGraph::writeEdges */

Friends And Related Function Documentation

◆ operator==

template<class wType = int>
template<class wType1 , class wType2 >
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 600 of file digraph.h.

602{
603 if (g1. nVertices != g2. nVertices)
604 return false;
605 if (!g1. nVertices)
606 return true;
607 for (int_t i = 0; i < g1. nVertices; ++ i)
608 {
609 if (g1. edgeEnds [i] != g2. edgeEnds [i])
610 return false;
611 }
612 int_t nEdges = g1. edgeEnds [g1. nVertices - 1];
613 for (int_t i = 0; i < nEdges; ++ i)
614 {
615 if (g1. edges [i] != g2. edges [i])
616 return false;
617 }
618 return true;
619} /* operator == */

Member Data Documentation

◆ edgeEnds

template<class wType = int>
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 460 of file digraph.h.

◆ edges

template<class wType = int>
multitable<int_t> chomp::homology::diGraph< wType >::edges
protected

A table with edge target numbers.

Definition at line 463 of file digraph.h.

◆ nVertices

template<class wType = int>
int_t chomp::homology::diGraph< wType >::nVertices
protected

The number of vertices.

Definition at line 456 of file digraph.h.

◆ weights

template<class wType = int>
multitable<wType> chomp::homology::diGraph< wType >::weights
protected

A table with edge weights.

Definition at line 466 of file digraph.h.

The documentation for this class was generated from the following file:
Generated by doxygen 1.9.4