33 #ifndef _CYMEALG_DIGRAPH_H_ 34 #define _CYMEALG_DIGRAPH_H_ 47 #include "chomp/system/config.h" 48 #include "chomp/struct/multitab.h" 49 #include "chomp/struct/hashsets.h" 50 #include "chomp/struct/flatmatr.h" 51 #include "chomp/struct/bitfield.h" 52 #include "chomp/struct/bitsets.h" 53 #include "chomp/struct/fibheap.h" 54 #include "chomp/struct/autoarray.h" 55 #include "chomp/system/textfile.h" 56 #include "chomp/system/timeused.h" 74 template <
class wType =
int>
101 void addEdge (int_t target,
const wType &weight);
104 void setWeight (int_t vertex, int_t i,
const wType &weight);
107 void setWeight (int_t edge,
const wType &weight);
117 void removeVertex (int_t vertex,
bool updateweights =
false);
129 int_t
getEdge (int_t vertex, int_t i)
const;
132 const wType &
getWeight (int_t vertex, int_t i)
const;
135 const wType &
getWeight (int_t edge)
const;
139 template <
class wType1,
class wType2>
146 template <
class wType1>
148 bool copyweights =
false)
const;
153 template <
class Table,
class wType1>
155 bool copyweights =
false)
const;
160 template <
class Table>
162 int_t &counter)
const;
165 template <
class Table>
167 int_t &counter)
const;
171 template <
class Table>
176 template <
class Table1,
class Table2>
178 int_t treeNumber, int_t countTrees, Table2 &compVertices,
179 int_t &curVertex,
diGraph *sccGraph, int_t *sccEdgeAdded)
183 template <
class Table1,
class Table2>
185 int_t treeNumber, int_t countTrees, Table2 &compVertices,
186 int_t &curVertex,
diGraph *sccGraph, int_t *sccEdgeAdded)
198 template <
class Table1,
class Table2,
class Table3>
199 int_t
DFSforest (
const Table1 &ordered, Table2 &compVertices,
200 Table3 &compEnds,
bool nontrivial =
false,
204 template <
class Table,
class Color>
206 int_t vertex = 0)
const;
209 template <
class Table,
class Color>
211 int_t vertex = 0)
const;
216 template <
class Table,
class Color>
217 void DFScolor (Table &tab,
const Color &color,
218 int_t vertex = 0)
const;
225 int_t
shortestPath (int_t source, int_t destination)
const;
240 template <
class lenTable,
class weightsType,
class roundType>
241 void Dijkstra (
const roundType &rounding, int_t source,
242 lenTable &len, weightsType &edgeWeights)
const;
245 template <
class lenTable,
class roundType>
246 void Dijkstra (
const roundType &rounding, int_t source,
247 lenTable &len)
const;
250 template <
class lenTable>
251 void Dijkstra (int_t source, lenTable &len)
const;
263 template <
class lenTable,
class predTable,
class roundType>
264 bool BellmanFord (
const roundType &rounding, int_t source,
265 lenTable &len, wType *infinity, predTable pred)
const;
268 template <
class lenTable,
class predTable>
269 bool BellmanFord (int_t source, lenTable &len, wType *infinity,
270 predTable pred)
const;
275 template <
class roundType>
276 bool BellmanFord (
const roundType &rounding, int_t source)
const;
306 template <
class arrayType,
class roundType>
307 wType
FloydWarshall (
const roundType &rounding, arrayType &arr,
308 bool setInfinity =
true,
bool ignoreNegLoop =
false)
const;
311 template <
class arrayType>
312 wType
FloydWarshall (arrayType &arr,
bool setInfinity =
true,
313 bool ignoreNegLoop =
false)
const;
323 template <
class arrayType,
class roundType>
324 wType
Johnson (
const roundType &rounding, arrayType &arr,
325 bool setInfinity =
true,
bool ignoreNegLoop =
false)
const;
328 template <
class arrayType>
329 wType
Johnson (arrayType &arr,
bool setInfinity =
true,
330 bool ignoreNegLoop =
false)
const;
341 template <
class roundType>
343 bool ignoreNegLoop =
false,
int sparseGraph = -1)
const;
347 int sparseGraph = -1)
const;
358 chomp::homology::multitable<int_t>
edges;
378 return (x. weight < y. weight);
427 if (y. isInfinity ())
428 return !(x. isInfinity ());
429 else if (x. isInfinity ())
431 return (x. value < y. value);
438 if (x. isInfinity ())
441 out << x. getValue ();
454 template <
class wType>
461 template <
class wType>
469 template <
class wType1,
class wType2>
477 for (int_t i = 0; i < g1.
nVertices; ++ i)
483 for (int_t i = 0; i < nEdges; ++ i)
491 template <
class wType1,
class wType2>
500 template <
class wType>
510 template <
class wType>
514 static_cast<int_t
> (0);
519 template <
class wType>
523 throw "Trying to add an edge to an empty graph.";
527 throw "Trying to add an edge to a negative vertex.";
530 throw "Too many edges in a diGraph (limit = 2,147,483,647).";
531 edges [offset] = target;
536 template <
class wType>
540 throw "Trying to add an edge to an empty graph.";
544 throw "Trying to add an edge to a negative vertex.";
547 throw "Too many edges in a diGraph (limit = 2,147,483,647).";
548 edges [offset] = target;
554 template <
class wType>
565 template <
class wType>
572 template <
class wType>
576 throw "Trying to remove a vertex from the empty graph.";
581 template <
class wType>
585 if ((vertex < 0) || (vertex >=
nVertices))
586 throw "Trying to remove a vertex that is not in the graph.";
595 if (!skipped && (v == vertex))
604 for (; curEdge < maxEdge; ++ curEdge)
606 if (
edges [curEdge] == vertex)
608 int_t target =
edges [curEdge];
609 edges [newEdge] = (target < vertex) ? target :
619 nVertices -= skipped;
624 template <
class wType>
630 template <
class wType>
639 template <
class wType>
648 template <
class wType>
657 template <
class wType>
666 template <
class wType>
674 template <
class wType>
template <
class wType1>
676 bool copyweights)
const 686 int_t nEdges =
edgeEnds [nVertices - 1];
687 for (int_t i = 0; i < nEdges; ++ i)
689 if (
edges [i] < nVertices - 1)
699 for (; curEdge <
edgeEnds [i]; ++ curEdge)
701 int_t j =
edges [curEdge];
702 int_t &offset = result. edgeEnds [j];
703 result.
edges [offset] = i;
712 template <
class wType>
template <
class Table,
class wType1>
714 const Table &tab,
bool copyweights)
const 722 numbers [i] = curNumber ++;
733 int_t firstEdge = i ?
edgeEnds [i - 1] :
734 static_cast<int_t
> (0);
736 for (int_t j = firstEdge; j < endEdge; ++ j)
738 int_t edgeEnd =
edges [j];
739 if (numbers [edgeEnd] >= 0)
745 g.
addEdge (numbers [edgeEnd]);
757 template <
class wType>
template <
class Table,
class Color>
759 const Color &color, int_t vertex)
const 761 tab [vertex] = color;
763 for (int_t i = vertex ?
edgeEnds [vertex - 1] :
764 static_cast<int_t> (0); i < maxEdge; ++ i)
766 int_t next =
edges [i];
767 if (tab [next] != color)
773 template <
class wType>
template <
class Table,
class Color>
778 std::stack<int_t> s_vertex;
779 std::stack<int_t> s_edge;
780 std::stack<int_t> s_maxedge;
783 tab [vertex] = color;
786 int_t edge = vertex ?
edgeEnds [vertex - 1] :
787 static_cast<int_t
> (0);
797 if (s_vertex. empty ())
801 vertex = s_vertex. top ();
803 edge = s_edge. top ();
805 maxedge = s_maxedge. top ();
811 int_t next =
edges [edge ++];
812 if (tab [next] != color)
815 s_vertex. push (vertex);
817 s_maxedge. push (maxedge);
823 tab [vertex] = color;
826 edge = vertex ?
edgeEnds [vertex - 1] :
827 static_cast<int_t
> (0);
833 template <
class wType>
template <
class Table,
class Color>
843 template <
class wType>
template <
class Table>
845 int_t vertex, int_t &counter)
const 851 for (int_t edge = vertex ?
edgeEnds [vertex - 1] :
852 static_cast<int_t> (0);
855 int_t next =
edges [edge];
861 tab [vertex] = ++ counter;
865 template <
class wType>
template <
class Table>
867 int_t &counter)
const 870 std::stack<int_t> s_vertex;
871 std::stack<int_t> s_edge;
872 std::stack<int_t> s_maxedge;
878 int_t edge = vertex ?
edgeEnds [vertex - 1] :
879 static_cast<int_t
> (0);
890 tab [vertex] = ++ counter;
893 if (s_vertex. empty ())
897 vertex = s_vertex. top ();
899 edge = s_edge. top ();
901 maxedge = s_maxedge. top ();
907 int_t next =
edges [edge ++];
911 s_vertex. push (vertex);
913 s_maxedge. push (maxedge);
922 edge = vertex ?
edgeEnds [vertex - 1] :
923 static_cast<int_t
> (0);
931 template <
class wType>
template <
class Table>
950 int_t counterdebug = 0;
954 if (counter != counterdebug)
955 throw "DFSfinishTime: Wrong counter.";
958 if (tab [i] != tabdebug [i])
960 chomp::homology::sbug <<
961 "\nDFSfinishTime error: tabRec [" << i <<
962 "] = " << tab [i] <<
", tabStack [" << i <<
963 "] = " << tabdebug [i] <<
".\n";
964 throw "DFSfinishTime: Wrong numbers.";
967 chomp::homology::sbug <<
"DEBUG: DFSfinishTime OK. ";
968 #endif // DIGRAPH_DEBUG 974 template <
class wType>
template <
class Table1,
class Table2>
976 int_t vertex, int_t treeNumber, int_t countTrees,
977 Table2 &compVertices, int_t &curVertex,
981 compVertices [curVertex ++] = vertex;
984 tab [vertex] = treeNumber;
990 for (int_t edge = vertex ?
edgeEnds [vertex - 1] :
991 static_cast<int_t> (0);
994 int_t next =
edges [edge];
997 treeNumber, countTrees, compVertices,
998 curVertex, sccGraph, sccEdgeAdded);
999 else if (tab [next] == treeNumber)
1003 int_t target = ntab [treeNumber - 1];
1004 if (sccEdgeAdded [target] != treeNumber)
1007 sccEdgeAdded [target] = treeNumber;
1014 int_t target = ntab [tab [next] - 1];
1015 if ((target >= 0) &&
1016 (sccEdgeAdded [target] != treeNumber))
1019 sccEdgeAdded [target] = treeNumber;
1027 template <
class wType>
template <
class Table1,
class Table2>
1029 int_t vertex, int_t treeNumber, int_t ,
1030 Table2 &compVertices, int_t &curVertex,
1034 std::stack<int_t> s_vertex;
1035 std::stack<int_t> s_edge;
1036 std::stack<int_t> s_maxedge;
1037 std::stack<bool> s_loop;
1040 compVertices [curVertex ++] = vertex;
1043 tab [vertex] = treeNumber;
1049 int_t edge = vertex ?
edgeEnds [vertex - 1] :
1050 static_cast<int_t
> (0);
1056 if (edge >= maxedge)
1059 if (s_vertex. empty ())
1063 vertex = s_vertex. top ();
1065 edge = s_edge. top ();
1067 maxedge = s_maxedge. top ();
1069 loop |= s_loop. top ();
1075 int_t next =
edges [edge ++];
1079 s_vertex. push (vertex);
1080 s_edge. push (edge);
1081 s_maxedge. push (maxedge);
1082 s_loop. push (loop);
1088 compVertices [curVertex ++] = vertex;
1091 tab [vertex] = treeNumber;
1095 edge = vertex ?
edgeEnds [vertex - 1] :
1096 static_cast<int_t
> (0);
1099 else if (tab [next] == treeNumber)
1103 int_t target = ntab [treeNumber - 1];
1104 if (sccEdgeAdded [target] != treeNumber)
1107 sccEdgeAdded [target] = treeNumber;
1114 int_t target = ntab [tab [next] - 1];
1115 if ((target >= 0) &&
1116 (sccEdgeAdded [target] != treeNumber))
1119 sccEdgeAdded [target] = treeNumber;
1127 template <
class wType>
template <
class Table1,
class Table2,
class Table3>
1129 Table2 &compVertices, Table3 &compEnds,
bool nontrivial,
1145 int_t *sccEdgeAdded = sccGraph ?
new int_t [
nVertices] :
1146 static_cast<int_t *
> (0);
1150 sccEdgeAdded [n] = -1;
1154 int_t treeNumber = 0;
1157 int_t countTrees = 0;
1158 int_t curVertex = 0;
1164 int_t vertex = ordered [i];
1175 int_t prevVertex = curVertex;
1179 ntab [treeNumber] = countTrees;
1182 treeNumber, countTrees, compVertices,
1183 curVertex, sccGraph, sccEdgeAdded);
1186 compEnds [countTrees ++] = curVertex;
1189 if (nontrivial && !loop)
1192 curVertex = prevVertex;
1195 ntab [treeNumber - 1] = -1;
1201 #ifdef DIGRAPH_DEBUG 1207 int_t *tabdebug =
new int_t [
nVertices];
1213 int_t *ntabdebug =
new int_t [
nVertices];
1217 int_t *sccEdgeAddeddebug = sccGraph ?
new int_t [
nVertices] :
1218 static_cast<int_t
> (0);
1222 sccEdgeAddeddebug [n] = -1;
1225 int_t treeNumberdebug = 0;
1228 int_t countTreesdebug = 0;
1229 int_t curVertexdebug = 0;
1231 int_t *compVerticesdebug =
new int_t [
nVertices];
1232 int_t *compEndsdebug =
new int_t [
nVertices];
1238 int_t vertex = ordered [i];
1241 if (tabdebug [vertex])
1249 int_t prevVertex = curVertexdebug;
1253 ntabdebug [treeNumberdebug] = countTreesdebug;
1256 treeNumberdebug, countTreesdebug, compVerticesdebug,
1257 curVertexdebug, sccGraphdebug, sccEdgeAddeddebug);
1260 compEndsdebug [countTreesdebug ++] = curVertexdebug;
1263 if (nontrivial && !loop)
1266 curVertexdebug = prevVertex;
1269 ntabdebug [treeNumberdebug - 1] = -1;
1274 if (countTrees != countTreesdebug)
1275 throw "DFSforest: Wrong countTrees.";
1276 for (int_t i = 0; i < countTrees; ++ i)
1277 if (compEnds [i] != compEndsdebug [i])
1278 throw "DFSforest: Wrong compEnds.";
1279 for (int_t i = 0; i < compEndsdebug [countTrees - 1]; ++ i)
1280 if (compVertices [i] != compVerticesdebug [i])
1281 throw "DFSforest: Wrong vertices.";
1282 if (curVertex != curVertexdebug)
1283 throw "DFSforest: Wrong curVertex.";
1285 if (tab [i] != tabdebug [i])
1286 throw "DFSforest: Wrong tab.";
1290 if (ntab [i] != ntabdebug [i])
1291 throw "DFSforest: Wrong ntab.";
1292 if (*sccGraph != *sccGraphdebug)
1293 throw "DFSforest: Wrong graph.";
1298 if (sccEdgeAdded [i] != sccEdgeAddeddebug [i])
1299 throw "DFSforest: Wrong sccEdgeAdded.";
1301 if (treeNumber != treeNumberdebug)
1302 throw "DFSforest: Wrong treeNumber.";
1303 chomp::homology::sbug <<
"DEBUG: DFSforest OK. ";
1305 chomp::homology::sbug <<
"(Graphs not compared.) ";
1306 delete [] compVerticesdebug;
1307 delete [] compEndsdebug;
1309 delete sccGraphdebug;
1310 delete [] ntabdebug;
1312 if (sccEdgeAddeddebug)
1313 delete [] sccEdgeAddeddebug;
1314 #endif // DIGRAPH_DEBUG 1317 delete [] sccEdgeAdded;
1325 template <
class wType>
1330 if ((source < 0) || (source >=
nVertices) ||
1331 (destination < 0) || (destination >=
nVertices))
1333 throw "diGraph - shortest path: Wrong vertex number.";
1338 chomp::homology::BitField visited;
1343 std::queue<int_t> q_vertex;
1344 std::queue<int_t> q_depth;
1347 int_t vertex = source;
1353 visited.
set (vertex);
1359 int_t firstedge = vertex ?
edgeEnds [vertex - 1] :
1360 static_cast<int_t
> (0);
1364 for (int_t edge = firstedge; edge < maxedge; ++ edge)
1367 int_t next =
edges [edge];
1373 if (next == destination)
1380 if (visited. test (next))
1384 q_vertex. push (next);
1385 q_depth. push (depth);
1391 if (q_vertex. empty ())
1398 vertex = q_vertex. front ();
1400 depth = q_depth. front ();
1405 template <
class wType>
1411 template <
class wType>
1412 template <
class lenTable,
class weightsType,
class roundType>
1414 int_t source, lenTable &len, weightsType &edgeWeights)
const 1417 chomp::homology::FibonacciHeap<posWeight> Q (
nVertices);
1426 int_t number = Q. Insert (w);
1429 throw "Wrong implementation of Fibonacci heap " 1430 "for this version of Dijkstra.";
1439 int_t minVertex = Q. Minimum ();
1440 posWeight minWeight = Q. ExtractMinimum ();
1442 if (minWeight. isInfinity ())
1444 len [minVertex] = -1;
1447 wType minValue = minWeight. getValue ();
1448 len [minVertex] = minValue;
1452 int_t edge = minVertex ?
edgeEnds [minVertex - 1] :
1453 static_cast<int_t
> (0);
1454 int_t maxEdge =
edgeEnds [minVertex];
1455 for (; edge < maxEdge; ++ edge)
1458 int_t nextVertex =
edges [edge];
1462 const posWeight &nextWeight = Q. Value (nextVertex);
1463 wType newWeight = rounding. add_down (minValue,
1464 edgeWeights [edge]);
1467 if (nextWeight. isInfinity () ||
1468 (newWeight < nextWeight. getValue ()))
1470 Q. DecreaseKey (nextVertex,
1478 template <
class wType>
1479 template <
class lenTable,
class roundType>
1481 int_t source, lenTable &len)
const 1487 template <
class wType>
1488 template <
class lenTable>
1492 this ->
Dijkstra (rounding, source, len);
1496 template <
class wType>
template <
class lenTable,
class predTable,
1499 int_t source, lenTable &len, wType *infinity, predTable pred)
const 1502 if ((source < 0) || (source >=
nVertices))
1503 throw "Bellman-Ford: Wrong source vertex number.";
1506 chomp::homology::BitField finite;
1509 finite.
set (source);
1513 int_t countNegative = 0;
1520 bool noNegativeLoop =
false;
1522 for (; counter <=
nVertices; ++ counter)
1524 bool modified =
false;
1526 for (int_t vertex = 0; vertex <
nVertices; ++ vertex)
1529 if (!finite. test (vertex))
1534 for (; curEdge < maxEdge; ++ curEdge)
1536 int_t next =
edges [curEdge];
1537 wType newlen = rounding. add_down
1538 (len [vertex],
weights [curEdge]);
1539 if (!finite. test (next))
1543 len [next] = newlen;
1544 pred [next] = vertex;
1548 else if (newlen < len [next])
1551 if (!(len [next] < 0) &&
1556 len [next] = newlen;
1557 pred [next] = vertex;
1561 if (countNegative == nVertices)
1563 noNegativeLoop =
false;
1569 noNegativeLoop =
true;
1576 if (
false && chomp::homology::sbug. show)
1578 chomp::homology::sbug <<
"Bellman-Ford: " <<
1579 counter << ((counter > 1) ?
" loops (" :
" loop (") <<
1580 nVertices <<
" vertices, " << countNegative <<
1582 (noNegativeLoop ?
"No negative loops.\n" :
1583 "A negative loop found.\n");
1587 if (infinity && noNegativeLoop)
1593 if (!finite. test (i))
1600 else if (infty < len [i])
1608 if (!finite. test (i))
1615 return noNegativeLoop;
1618 template <
class wType>
template <
class lenTable,
class predTable>
1620 wType *infinity, predTable pred)
const 1623 return this ->
BellmanFord (rounding, source, len, infinity, pred);
1626 template <
class wType>
template <
class roundType>
1630 chomp::homology::auto_array<wType> len_ptr (
new wType [
nVertices]);
1631 wType *len = len_ptr.
get ();
1632 wType *infinity = 0;
1634 return BellmanFord (rounding, source, len, infinity, tab);
1637 template <
class wType>
1644 template <
class wType>
1648 std::vector<edgeTriple> edgeTriples (
countEdges ());
1651 for (int_t vert = 0; vert <
nVertices; ++ vert)
1657 e. vert2 =
edges [curEdge];
1658 e. weight =
weights [curEdge];
1663 std::sort (edgeTriples. begin (), edgeTriples. end ());
1666 chomp::homology::auto_array<int_t> root_ptr (
new int_t [nVertices]);
1667 int_t *root = root_ptr.
get ();
1668 for (int_t vert = 0; vert <
nVertices; ++ vert)
1674 wType totalWeight = 0;
1676 for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
1681 int_t root1 = e. vert1;
1682 while (root [root1] >= 0)
1684 root1 = root [root1];
1686 int_t vert1 = e. vert1;
1687 while (root [vert1] >= 0)
1689 int_t next = root [vert1];
1690 root [vert1] = root1;
1693 int_t root2 = e. vert2;
1694 while (root [root2] >= 0)
1696 root2 = root [root2];
1698 int_t vert2 = e. vert2;
1699 while (root [vert2] >= 0)
1701 int_t next = root [vert2];
1702 root [vert2] = root2;
1711 totalWeight += e. weight;
1714 root [root1] = root2;
1719 template <
class wType>
1723 std::vector<edgeTriple> edgeTriples (
countEdges ());
1726 for (int_t vert = 0; vert <
nVertices; ++ vert)
1732 e. vert2 =
edges [curEdge];
1733 e. weight =
weights [curEdge];
1738 std::sort (edgeTriples. begin (), edgeTriples. end ());
1741 chomp::homology::auto_array<int_t> forest_ptr
1742 (
new int_t [nVertices]);
1743 int_t *forest = forest_ptr.
get ();
1744 chomp::homology::auto_array<int_t> next_ptr
1745 (
new int_t [nVertices]);
1746 int_t *next = next_ptr.
get ();
1747 chomp::homology::auto_array<int_t> prev_ptr
1748 (
new int_t [nVertices]);
1749 int_t *prev = prev_ptr.
get ();
1750 for (int_t vert = 0; vert <
nVertices; ++ vert)
1752 forest [vert] = vert;
1758 wType totalWeight = 0;
1760 for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
1764 if (forest [e. vert1] == forest [e. vert2])
1768 totalWeight += e. weight;
1771 int_t vert1 = e. vert1;
1772 while (next [vert1] >= 0)
1774 vert1 = next [vert1];
1778 int_t vert2 = e. vert2;
1779 while (prev [vert2] >= 0)
1781 vert2 = prev [vert2];
1785 next [vert1] = vert2;
1786 prev [vert2] = vert1;
1787 int_t treeNumber = forest [vert1];
1790 forest [vert2] = treeNumber;
1791 vert2 = next [vert2];
1797 template <
class wType>
1798 template <
class arrayType,
class roundType>
1800 arrayType &arr,
bool setInfinity,
bool ignoreNegLoop)
const 1807 chomp::homology::BitField *finite =
1808 new chomp::homology::BitField [
nVertices];
1811 finite [i]. allocate (nVertices);
1812 finite [i]. clearall (nVertices);
1817 for (int_t source = 0; source <
nVertices; ++ source)
1819 bool diagset =
false;
1820 while (curEdge <
edgeEnds [source])
1822 int_t target =
edges [curEdge];
1823 const wType &weight =
weights [curEdge];
1824 if (source == target)
1828 arr [source] [target] = weight;
1834 arr [source] [target] = weight;
1835 finite [source].
set (target);
1840 arr [source] [source] = 0;
1841 finite [source].
set (source);
1849 if (!finite [i]. test (k))
1853 if (!finite [k]. test (j))
1855 const wType sum = rounding. add_down
1856 (arr [i] [k], arr [k] [j]);
1857 if (finite [i]. test (j))
1859 if (sum < arr [i] [j])
1865 finite [i].
set (j);
1877 if (arr [i] [i] < 0)
1878 throw "Negative loop in Floyd-Warshall.";
1889 wType &infinity = result;
1894 if (finite [i]. test (j) &&
1895 (infinity <= arr [i] [j]))
1897 infinity = rounding. add_up
1906 if (!finite [i]. test (j))
1907 arr [i] [j] = infinity;
1915 wType &minWeight = result;
1916 bool firstTime =
true;
1921 if (finite [i]. test (j))
1925 minWeight = arr [i] [j];
1928 else if (arr [i] [j] < minWeight)
1930 minWeight = arr [i] [j];
1939 finite [i]. free ();
1945 template <
class wType>
1946 template <
class arrayType>
1948 bool setInfinity,
bool ignoreNegLoop)
const 1951 return FloydWarshall (rounding, arr, setInfinity, ignoreNegLoop);
1954 template <
class wType>
1955 template <
class arrayType,
class roundType>
1957 arrayType &arr,
bool setInfinity,
bool ignoreNegLoop)
const 1960 if (
false && chomp::homology::sbug. show)
1962 chomp::homology::timeused stopWatch;
1964 arr, setInfinity, ignoreNegLoop);
1965 chomp::homology::sbug <<
"\n[Floyd-Warshall: " << res <<
1966 ", " << (double) stopWatch <<
" sec]\n";
1983 bool noNegativeLoop =
false;
1985 for (; counter <=
nVertices; ++ counter)
1987 bool modified =
false;
1989 for (int_t vertex = 0; vertex <
nVertices; ++ vertex)
1992 for (; curEdge < maxEdge; ++ curEdge)
1994 int_t next =
edges [curEdge];
1995 wType newlen = rounding. add_down
1996 (len [vertex],
weights [curEdge]);
1997 if (newlen < len [next])
2001 if (counter > nVertices)
2003 std::cout << vertex;
2006 len [next] = newlen;
2012 noNegativeLoop =
true;
2017 if (!ignoreNegLoop && !noNegativeLoop)
2018 throw "Negative loop found in Johnson's algorithm.";
2021 wType *newWeights =
new wType [
edgeEnds [nVertices - 1]];
2023 for (int_t vertex = 0; vertex <
nVertices; ++ vertex)
2025 int_t maxEdge = edgeEnds [vertex];
2026 for (; edge < maxEdge; ++ edge)
2029 w = rounding. add_down (w, len [vertex]);
2030 w = rounding. sub_down (w, len [
edges [edge]]);
2031 newWeights [edge] = (w < 0) ?
2032 static_cast<wType> (0) : w;
2041 this ->
Dijkstra (rounding, u, arr [u], newWeights);
2043 delete [] newWeights;
2051 wType &infinity = result;
2056 wType w = arr [u] [v];
2059 w = rounding. add_down (w, len [v]);
2060 w = rounding. sub_down (w, len [u]);
2063 infinity = rounding. add_up (w, 1);
2070 wType w = arr [u] [v];
2073 arr [u] [v] = infinity;
2076 w = rounding. add_down (w, len [v]);
2078 rounding. sub_down (w, len [u]);
2084 wType &minWeight = result;
2085 bool firstTime =
true;
2090 wType w = arr [u] [v];
2093 w = rounding. add_down (w, len [v]);
2094 w = rounding. sub_down (w, len [u]);
2100 else if (w < minWeight)
2108 if (
false && chomp::homology::sbug. show)
2117 template <
class wType>
2118 template <
class arrayType>
2120 bool setInfinity,
bool ignoreNegLoop)
const 2123 return Johnson (rounding, arr, setInfinity, ignoreNegLoop);
2126 template <
class wType>
2127 template <
class roundType>
2129 bool ignoreNegLoop,
int sparseGraph)
const 2138 arr [i] =
new wType [nVertices];
2142 bool sparse =
false;
2143 if (sparseGraph == 1)
2145 else if (sparseGraph != 0)
2149 if ((nVerticesD > 3000) && (nEdgesD < nVerticesD * 1000) &&
2150 (nEdgesD < nVerticesD * nVerticesD / 50))
2157 wType minWeight = sparse ?
2158 this ->
Johnson (rounding, arr,
false, ignoreNegLoop) :
2159 this ->
FloydWarshall (rounding, arr,
false, ignoreNegLoop);
2175 delete [] (arr [i]);
2181 template <
class wType>
2186 return this ->
minPathWeight (rounding, ignoreNegLoop, sparseGraph);
2193 #endif // _CYMEALG_DIGRAPH_H_ posWeight()
The default constructor.
void subgraph(diGraph< wType1 > &result, const Table &tab, bool copyweights=false) const
Computes a restriction of the graph to its subgraph.
wType weight_type
The type of the weight of edges.
wType weight
The weight of the edge.
std::ostream & operator<<(std::ostream &out, const diGraph< wType > &g)
Writes a graph in the text mode to an output stream.
int_t DFSforest(const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, diGraph< wType > *sccGraph=0) const
Computes the DFS forest.
bool operator!=(const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
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.
posWeight(const wType &_value)
An optional constructor.
int_t countVertices(void) const
Returns the number of vertices.
This class defines a weighted directed graph with very limited number of operations.
~diGraph()
The destructor.
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...
void DFSfinishTime(Table &tab) const
Computes the DFS finishing time for each vertex.
void addVertex(void)
Adds a vertex.
void DFSfinishTimeRecurrent(Table &tab, int_t vertex, int_t &counter) const
The recurrent procedure for DFSfinishTime.
bool isInfinity() const
Returns true iff the value corresponds to the infinity.
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...
wType EdmondsOld() const
An old implementation of the Edmonds algorithm (less efficient).
void swap(diGraph< wType > &g)
Swaps the data with another graph.
void DFScolorStack(Table &tab, const Color &color, int_t vertex=0) const
A stack version of the recurrent procedure for DFScolor.
This header file contains the definition of a dummy array.
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.
int_t nVertices
The number of vertices.
chomp::homology::multitable< int_t > edges
A table with edge target numbers.
friend bool operator==(const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
Operator == for comparing digraphs.
void setWeight(int_t vertex, int_t i, const wType &weight)
Sets the weight of the given edge.
int_t shortestLoop(int_t origin) const
Computes the length of the shortest loop from the given vertex to itself.
const wType & getValue() const
Returns the value stored in this object.
int_t countEdges(void) const
Returns the number of edges.
A dummy array of integers that ignores all the assigned values.
diGraph()
The default constructor of an empty graph.
void DFScolorRecurrent(Table &tab, const Color &color, int_t vertex=0) const
The recurrent procedure for DFScolor.
A class for representing a positive number with negative values serving as the infinity (used in the ...
An edge with a weight (used by the Edmonds algorithm).
const wType & getWeight(int_t vertex, int_t i) const
Retrieves the weight of the given edge.
chomp::homology::multitable< wType > weights
A table with edge weights.
void removeVertex(void)
Removes the last vertex and all the edges going out from it.
void setInfinity()
Sets the value to the infinity.
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...
A dummy class for rounding operations which does not actually do any rounding.
chomp::homology::multitable< int_t > edgeEnds
A table with the offsets of the one-after-the-last edge of each vertex.
int_t vert1
The starting and ending vertices of the edge.
void DFSfinishTimeStack(Table &tab, int_t vertex, int_t &counter) const
A stack version of the recurrent procedure for DFSfinishTime.
wType value
The actual number.
void addEdge(int_t target)
Adds an edge starting at the last vertex.
wType Edmonds() const
Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the gra...
This header file contains the definition of a dummy rounding class.
friend bool operator<(const edgeTriple &x, const edgeTriple &y)
The < operator for comparing the weights of edges.
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...
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 ...
int_t getEdge(int_t vertex, int_t i) const
Retrieves the given edge that leaves the given vertex.
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.
void transpose(diGraph< wType1 > &result, bool copyweights=false) const
Creates a transposed graph.
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...