The CyMeAlg Software (Release 0.01)
digraph.h
Go to the documentation of this file.
1 /// @addtogroup cymealg
2 /// @{
3 
4 /////////////////////////////////////////////////////////////////////////////
5 ///
6 /// @file
7 ///
8 /// This header file contains the definition of a weighted directed graph.
9 ///
10 /// @author Pawel Pilarczyk
11 ///
12 /////////////////////////////////////////////////////////////////////////////
13 
14 // Copyright (C) 1997-2020 by Pawel Pilarczyk.
15 //
16 // This file is part of my research software. This is free software:
17 // you can redistribute it and/or modify it under the terms of the GNU
18 // General Public License as published by the Free Software Foundation,
19 // either version 3 of the License, or (at your option) any later version.
20 //
21 // This software is distributed in the hope that it will be useful,
22 // but WITHOUT ANY WARRANTY; without even the implied warranty of
23 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 // GNU General Public License for more details.
25 //
26 // You should have received a copy of the GNU General Public License
27 // along with this software; see the file "license.txt". If not,
28 // please, see <http://www.gnu.org/licenses/>.
29 
30 // Started in January 2006. Last revision: August 23, 2019.
31 
32 
33 #ifndef _CYMEALG_DIGRAPH_H_
34 #define _CYMEALG_DIGRAPH_H_
35 
36 // include selected standard library header files
37 #include <iostream>
38 #include <new>
39 #include <stack>
40 #include <queue>
41 #include <set>
42 #include <memory>
43 #include <vector>
44 #include <algorithm>
45 
46 // include selected CHomP header files
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"
57 
58 // include selected CyMeAlg header files
59 #include "cymealg/dummyarr.h"
60 #include "cymealg/dummyrnd.h"
61 
62 
63 namespace cymealg {
64 
65 
66 // --------------------------------------------------
67 // ----------------- DIRECTED GRAPH -----------------
68 // --------------------------------------------------
69 
70 // #define DIGRAPH_DEBUG
71 
72 /// This class defines a weighted directed graph with very limited number
73 /// of operations. The graph can be treated as non-weighted if necessary.
74 template <class wType = int>
75 class diGraph
76 {
77 public:
78  /// The type of the weight of edges.
79  typedef wType weight_type;
80 
81  /// The default constructor of an empty graph.
82  /// Note: The default copy constructor and assignment operator
83  /// generated by the compiler are good for copying graphs.
84  diGraph ();
85 
86  /// The destructor.
87  ~diGraph ();
88 
89  /// Swaps the data with another graph.
90  void swap (diGraph<wType> &g);
91 
92  /// Adds a vertex.
93  void addVertex (void);
94 
95  /// Adds an edge starting at the last vertex.
96  /// Note: The range of the target vertex number is not verified.
97  void addEdge (int_t target);
98 
99  /// Adds an edge from the last vertex to the given one
100  /// and sets the weight of this edge.
101  void addEdge (int_t target, const wType &weight);
102 
103  /// Sets the weight of the given edge.
104  void setWeight (int_t vertex, int_t i, const wType &weight);
105 
106  /// Sets the weight of the given edge.
107  void setWeight (int_t edge, const wType &weight);
108 
109  /// Removes the last vertex and all the edges going out from it.
110  /// This is done in the time O(1).
111  void removeVertex (void);
112 
113  /// Removes the given vertex and all the edges going out from it,
114  /// as well as the edges going towards it.
115  /// If requested, the weights in the graph are also updated.
116  /// This function might be slow - it is done in the time O(V+E).
117  void removeVertex (int_t vertex, bool updateweights = false);
118 
119  /// Returns the number of vertices.
120  int_t countVertices (void) const;
121 
122  /// Returns the number of edges.
123  int_t countEdges (void) const;
124 
125  /// Counts the number of edges leaving the given vertex.
126  int_t countEdges (int_t vertex) const;
127 
128  /// Retrieves the given edge that leaves the given vertex.
129  int_t getEdge (int_t vertex, int_t i) const;
130 
131  /// Retrieves the weight of the given edge.
132  const wType &getWeight (int_t vertex, int_t i) const;
133 
134  /// Retrieves the weight of the given edge.
135  const wType &getWeight (int_t edge) const;
136 
137  /// Operator == for comparing digraphs. No isomorphism check, just
138  /// comparing with the same order of vertices. Ignores weights.
139  template <class wType1, class wType2>
140  friend bool operator == (const diGraph<wType1> &g1,
141  const diGraph<wType2> &g2);
142 
143 // --------------------------------------------------
144 
145  /// Creates a transposed graph.
146  template <class wType1>
147  void transpose (diGraph<wType1> &result,
148  bool copyweights = false) const;
149 
150  /// Computes a restriction of the graph to its subgraph. The subgraph
151  /// vertices are defined by nonzero entries in the supplied table.
152  /// The result must be initially empty.
153  template <class Table, class wType1>
154  void subgraph (diGraph<wType1> &result, const Table &tab,
155  bool copyweights = false) const;
156 
157 // --------------------------------------------------
158 
159  /// The recurrent procedure for DFSfinishTime.
160  template <class Table>
161  void DFSfinishTimeRecurrent (Table &tab, int_t vertex,
162  int_t &counter) const;
163 
164  /// A stack version of the recurrent procedure for DFSfinishTime.
165  template <class Table>
166  void DFSfinishTimeStack (Table &tab, int_t vertex,
167  int_t &counter) const;
168 
169  /// Computes the DFS finishing time for each vertex.
170  /// Note: The time begins with 1, not with 0.
171  template <class Table>
172  void DFSfinishTime (Table &tab) const;
173 
174  /// The recurrent procedure for DFSforest.
175  /// Returns true iff there is a loop within the tree found.
176  template <class Table1, class Table2>
177  bool DFSforestRecurrent (Table1 &tab, Table1 &ntab, int_t vertex,
178  int_t treeNumber, int_t countTrees, Table2 &compVertices,
179  int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded)
180  const;
181 
182  /// A stack version of the recurrent procedure for DFSforest.
183  template <class Table1, class Table2>
184  bool DFSforestStack (Table1 &tab, Table1 &ntab, int_t vertex,
185  int_t treeNumber, int_t countTrees, Table2 &compVertices,
186  int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded)
187  const;
188 
189  /// Computes the DFS forest.
190  /// Considers the vertices in the given order.
191  /// Saves the numbers of vertices of each tree in 'compVertices',
192  /// and keeps the one-beyond-the-end offsets of the trees in the
193  /// table 'compEnds'. Records the connections between the trees
194  /// in 'scc' (which must be empty when this function is called).
195  /// If requested, only those single-vertex trees are counted
196  /// which have an edge that loops back to themselves.
197  /// Returns the number of trees in the computed forest.
198  template <class Table1, class Table2, class Table3>
199  int_t DFSforest (const Table1 &ordered, Table2 &compVertices,
200  Table3 &compEnds, bool nontrivial = false,
201  diGraph<wType> *sccGraph = 0) const;
202 
203  /// The recurrent procedure for DFScolor.
204  template <class Table, class Color>
205  void DFScolorRecurrent (Table &tab, const Color &color,
206  int_t vertex = 0) const;
207 
208  /// A stack version of the recurrent procedure for DFScolor.
209  template <class Table, class Color>
210  void DFScolorStack (Table &tab, const Color &color,
211  int_t vertex = 0) const;
212 
213  /// Marks each vertex visited by DFS with the given color,
214  /// starting with the given vertex. Runs for one component only.
215  /// The initial color in 'tab' must be different than the given one.
216  template <class Table, class Color>
217  void DFScolor (Table &tab, const Color &color,
218  int_t vertex = 0) const;
219 
220  /// Computes the length of the shortest nontrivial path
221  /// from the given vertex to another one.
222  /// The length is measured by counting edges.
223  /// Uses a stack version of the BFS algorithm.
224  /// Returns the length of the path or 0 if none.
225  int_t shortestPath (int_t source, int_t destination) const;
226 
227  /// Computes the length of the shortest loop from the given vertex
228  /// to itself. The length is measured by counting edges on the way.
229  /// Uses a stack version of the BFS algorithm.
230  /// Returns the length of the loop or 0 if none.
231  int_t shortestLoop (int_t origin) const;
232 
233  /// Dijkstra's algorithm for solving the single-source shortest
234  /// paths problem if all the edge weights are nonnegative.
235  /// The table 'len' is used to store the path lengths during the
236  /// computations and contains the final result. A negative value
237  /// stands for the infinity (no path to the given vertex).
238  /// This is a special version that uses the given edge weights
239  /// instead of the weights contained in the definition of the graph.
240  template <class lenTable, class weightsType, class roundType>
241  void Dijkstra (const roundType &rounding, int_t source,
242  lenTable &len, weightsType &edgeWeights) const;
243 
244  /// Dijkstra's algorithm running on the graph's own weights.
245  template <class lenTable, class roundType>
246  void Dijkstra (const roundType &rounding, int_t source,
247  lenTable &len) const;
248 
249  /// The above algorithm without rounding control.
250  template <class lenTable>
251  void Dijkstra (int_t source, lenTable &len) const;
252 
253  /// Runs the Bellman-Ford algorithm which computes the single-source
254  /// shortest paths in a weighted directed graph, where some edge
255  /// weights may be negative. Runs in O(V*E).
256  /// The table 'len' is used to store the path lengths during the
257  /// computations and contains the final result. The number for
258  /// infinity is set to indicate unreachable vertices.
259  /// The table with predecessors allows to retrieve shortest paths;
260  /// this must be a pointer to an array-like structure, e.g., int **.
261  /// To ignore this data, use an object of the 'dummyArray' class.
262  /// Returns true if successful, false if a negative cycle is found.
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;
266 
267  /// The above algorithm without rounding control.
268  template <class lenTable, class predTable>
269  bool BellmanFord (int_t source, lenTable &len, wType *infinity,
270  predTable pred) const;
271 
272  /// Runs the Bellman-Ford algorithm (see above) without storing the
273  /// distances, only returns the information about the existence
274  /// of a negative-weight cycle.
275  template <class roundType>
276  bool BellmanFord (const roundType &rounding, int_t source) const;
277 
278  /// The above algorithm without rounding control.
279  bool BellmanFord (int_t source) const;
280 
281  /// Runs the Edmonds algorithm to compute the shortest path
282  /// that runs through all the vertices of the graph.
283  /// Computation time: O (n log n). The length of the path
284  /// is measured as the sum of the weights of the edges.
285  /// The path does not contain any loops.
286  /// The graph should be strongly connected.
287  wType Edmonds () const;
288 
289  /// An old implementation of the Edmonds algorithm (less efficient).
290  wType EdmondsOld () const;
291 
292  /// Runs the Floyd-Warshall algorithm to compute the shortest
293  /// paths between all pairs of vertices in the graph.
294  /// The position [i] [j] of the array contains
295  /// the length of the shortest path from vertex i to vertex j.
296  /// Provides a rigorous lower bound in interval arithmetic,
297  /// provided that intervals are compared with "<" and "<="
298  /// by comparing their lower ends only.
299  /// If "setInfinity" is "true", then computes a value that serves
300  /// as the infinity, fills in the corresponding entries in "arr",
301  /// and returns this value.
302  /// Otherwise, returns the length of the shortest path. In this
303  /// case, arr [i] [j] is undefined if there is no path i -> j.
304  /// Throws an error message if a negative loop is found,
305  /// unless "ignoreNegLoop" is set to "true".
306  template <class arrayType, class roundType>
307  wType FloydWarshall (const roundType &rounding, arrayType &arr,
308  bool setInfinity = true, bool ignoreNegLoop = false) const;
309 
310  /// The above algorithm without rounding control.
311  template <class arrayType>
312  wType FloydWarshall (arrayType &arr, bool setInfinity = true,
313  bool ignoreNegLoop = false) const;
314 
315  /// Runs Johnson's algorithm to compute the minimum path weight
316  /// between any vertices in the graph. The time complexity of this
317  /// algorithm is essentially O (V^2 log V + VE log V),
318  /// which is better than the complexity of the Warshall-Floyd
319  /// algorithm for sparse graphs, that is, graphs in which the number
320  /// of edges E is of order smaller than V^2.
321  /// The meaning of the arguments and the returned value is the same
322  /// as in 'FloydWarshall'.
323  template <class arrayType, class roundType>
324  wType Johnson (const roundType &rounding, arrayType &arr,
325  bool setInfinity = true, bool ignoreNegLoop = false) const;
326 
327  /// The above algorithm without rounding control.
328  template <class arrayType>
329  wType Johnson (arrayType &arr, bool setInfinity = true,
330  bool ignoreNegLoop = false) const;
331 
332  /// Uses the Floyd-Warshall algorithm or Johnson's algorithm,
333  /// depending on the number of edges, to compute the minimum
334  /// path weight between any vertices in the graph.
335  /// Throws an error message if a negative loop exists in the graph,
336  /// unless "ignoreNegLoop" is set to "true".
337  /// To force the use of Johnson's algorithm, set "sparseGraph" to 1,
338  /// to force the use of Warshall-Floyd, set "sparseGraph" to 0,
339  /// otherwise it will be determined heuristically which algorithm
340  /// should be used.
341  template <class roundType>
342  wType minPathWeight (const roundType &rounding,
343  bool ignoreNegLoop = false, int sparseGraph = -1) const;
344 
345  /// The above algorithm without rounding control.
346  wType minPathWeight (bool ignoreNegLoop = false,
347  int sparseGraph = -1) const;
348 
349 protected:
350  /// The number of vertices.
351  int_t nVertices;
352 
353  /// A table with the offsets of the one-after-the-last edge
354  /// of each vertex.
355  chomp::homology::multitable<int_t> edgeEnds;
356 
357  /// A table with edge target numbers.
358  chomp::homology::multitable<int_t> edges;
359 
360  /// A table with edge weights.
361  chomp::homology::multitable<wType> weights;
362 
363 private:
364  /// An edge with a weight (used by the Edmonds algorithm).
365  struct edgeTriple
366  {
367  /// The starting and ending vertices of the edge.
368  int_t vert1;
369  int_t vert2;
370 
371  /// The weight of the edge.
372  wType weight;
373 
374  /// The < operator for comparing the weights of edges.
375  friend bool operator < (const edgeTriple &x,
376  const edgeTriple &y)
377  {
378  return (x. weight < y. weight);
379  }
380  };
381 
382  /// A class for representing a positive number with negative values
383  /// serving as the infinity (used in the Dijkstra algorithm).
384  class posWeight
385  {
386  public:
387  /// The default constructor.
389  {
390  value = 0;
391  return;
392  }
393 
394  /// An optional constructor.
395  explicit posWeight (const wType &_value)
396  {
397  if (_value < 0)
398  value = 0;
399  else
400  value = _value;
401  return;
402  }
403 
404  /// Sets the value to the infinity.
405  void setInfinity ()
406  {
407  value = -1;
408  return;
409  }
410 
411  /// Returns true iff the value corresponds to the infinity.
412  bool isInfinity () const
413  {
414  return (value < 0);
415  }
416 
417  /// Returns the value stored in this object.
418  const wType &getValue () const
419  {
420  return value;
421  }
422 
423  /// The < operator for comparing the numbers.
424  friend bool operator < (const posWeight &x,
425  const posWeight &y)
426  {
427  if (y. isInfinity ())
428  return !(x. isInfinity ());
429  else if (x. isInfinity ())
430  return false;
431  return (x. value < y. value);
432  }
433 
434  /// The operator for showing the number to the output stream.
435  friend std::ostream &operator << (std::ostream &out,
436  const posWeight &x)
437  {
438  if (x. isInfinity ())
439  out << "+oo";
440  else
441  out << x. getValue ();
442  return out;
443  }
444 
445  private:
446  /// The actual number.
447  wType value;
448  };
449 
450 }; /* class diGraph */
451 
452 // --------------------------------------------------
453 
454 template <class wType>
456  edgeEnds (1024), edges (4096), weights (4096)
457 {
458  return;
459 } /* diGraph::diGraph */
460 
461 template <class wType>
463 {
464  return;
465 } /* diGraph::~diGraph */
466 
467 // --------------------------------------------------
468 
469 template <class wType1, class wType2>
470 inline bool operator == (const diGraph<wType1> &g1,
471  const diGraph<wType2> &g2)
472 {
473  if (g1. nVertices != g2. nVertices)
474  return false;
475  if (!g1. nVertices)
476  return true;
477  for (int_t i = 0; i < g1. nVertices; ++ i)
478  {
479  if (g1. edgeEnds [i] != g2. edgeEnds [i])
480  return false;
481  }
482  int_t nEdges = g1. edgeEnds [g1. nVertices - 1];
483  for (int_t i = 0; i < nEdges; ++ i)
484  {
485  if (g1. edges [i] != g2. edges [i])
486  return false;
487  }
488  return true;
489 } /* operator == */
490 
491 template <class wType1, class wType2>
492 inline bool operator != (const diGraph<wType1> &g1,
493  const diGraph<wType2> &g2)
494 {
495  return !(g1 == g2);
496 } /* operator != */
497 
498 // --------------------------------------------------
499 
500 template <class wType>
502 {
503  std::swap (nVertices, g. nVertices);
504  edgeEnds. swap (g. edgeEnds);
505  edges. swap (g. edges);
506  weights. swap (g. weights);
507  return;
508 } /* diGraph::swap */
509 
510 template <class wType>
511 inline void diGraph<wType>::addVertex (void)
512 {
514  static_cast<int_t> (0);
515  ++ nVertices;
516  return;
517 } /* diGraph::addVertex */
518 
519 template <class wType>
520 inline void diGraph<wType>::addEdge (int_t target)
521 {
522  if (!nVertices)
523  throw "Trying to add an edge to an empty graph.";
524 // if (target >= nVertices)
525 // throw "Trying to add an edge to a nonexistent vertex.";
526  if (target < 0)
527  throw "Trying to add an edge to a negative vertex.";
528  int_t &offset = edgeEnds [nVertices - 1];
529  if (offset + 1 <= 0)
530  throw "Too many edges in a diGraph (limit = 2,147,483,647).";
531  edges [offset] = target;
532  ++ offset;
533  return;
534 } /* diGraph::addEdge */
535 
536 template <class wType>
537 inline void diGraph<wType>::addEdge (int_t target, const wType &weight)
538 {
539  if (!nVertices)
540  throw "Trying to add an edge to an empty graph.";
541 // if (target >= nVertices)
542 // throw "Trying to add an edge to a nonexistent vertex.";
543  if (target < 0)
544  throw "Trying to add an edge to a negative vertex.";
545  int_t &offset = edgeEnds [nVertices - 1];
546  if (offset + 1 <= 0)
547  throw "Too many edges in a diGraph (limit = 2,147,483,647).";
548  edges [offset] = target;
549  weights [offset] = weight;
550  ++ offset;
551  return;
552 } /* diGraph::addEdge */
553 
554 template <class wType>
555 inline void diGraph<wType>::setWeight (int_t vertex, int_t i,
556  const wType &weight)
557 {
558  if (!vertex)
559  weights [i] = weight;
560  else
561  weights [edgeEnds [vertex - 1] + i] = weight;
562  return;
563 } /* diGraph::setWeight */
564 
565 template <class wType>
566 inline void diGraph<wType>::setWeight (int_t edge, const wType &weight)
567 {
568  weights [edge] = weight;
569  return;
570 } /* diGraph::setWeight */
571 
572 template <class wType>
574 {
575  if (!nVertices)
576  throw "Trying to remove a vertex from the empty graph.";
577  -- nVertices;
578  return;
579 } /* diGraph::removeVertex */
580 
581 template <class wType>
582 inline void diGraph<wType>::removeVertex (int_t vertex, bool updateweights)
583 {
584  // make sure that the vertex number is within the scope
585  if ((vertex < 0) || (vertex >= nVertices))
586  throw "Trying to remove a vertex that is not in the graph.";
587 
588  // remove edges that begin or end at the given vertex
589  int_t curEdge = 0;
590  int_t newEdge = 0;
591  int_t skipped = 0;
592  for (int_t v = 0; v < nVertices; ++ v)
593  {
594  // skip the edges that begin at the given vertex
595  if (!skipped && (v == vertex))
596  {
597  curEdge = edgeEnds [v];
598  ++ skipped;
599  continue;
600  }
601 
602  // skip the edges that point to the given vertex
603  int_t maxEdge = edgeEnds [v];
604  for (; curEdge < maxEdge; ++ curEdge)
605  {
606  if (edges [curEdge] == vertex)
607  continue;
608  int_t target = edges [curEdge];
609  edges [newEdge] = (target < vertex) ? target :
610  (target - 1);
611  if (updateweights)
612  weights [newEdge] = weights [curEdge];
613  ++ newEdge;
614  }
615  edgeEnds [v - skipped] = newEdge;
616  }
617 
618  // decrease the number of vertices
619  nVertices -= skipped;
620 
621  return;
622 } /* diGraph::removeVertex */
623 
624 template <class wType>
625 inline int_t diGraph<wType>::countVertices (void) const
626 {
627  return nVertices;
628 } /* diGraph::countVertices */
629 
630 template <class wType>
631 inline int_t diGraph<wType>::countEdges (void) const
632 {
633  if (!nVertices)
634  return 0;
635  else
636  return edgeEnds [nVertices - 1];
637 } /* diGraph::countEdges */
638 
639 template <class wType>
640 inline int_t diGraph<wType>::countEdges (int_t vertex) const
641 {
642  if (!vertex)
643  return edgeEnds [0];
644  else
645  return edgeEnds [vertex] - edgeEnds [vertex - 1];
646 } /* diGraph::countEdges */
647 
648 template <class wType>
649 inline int_t diGraph<wType>::getEdge (int_t vertex, int_t i) const
650 {
651  if (!vertex)
652  return edges [i];
653  else
654  return edges [edgeEnds [vertex - 1] + i];
655 } /* diGraph::getEdge */
656 
657 template <class wType>
658 inline const wType &diGraph<wType>::getWeight (int_t vertex, int_t i) const
659 {
660  if (!vertex)
661  return weights [i];
662  else
663  return weights [edgeEnds [vertex - 1] + i];
664 } /* diGraph::getWeight */
665 
666 template <class wType>
667 inline const wType &diGraph<wType>::getWeight (int_t edge) const
668 {
669  return weights [edge];
670 } /* diGraph::getWeight */
671 
672 // --------------------------------------------------
673 
674 template <class wType> template <class wType1>
676  bool copyweights) const
677 {
678  // prepare the resulting graph
679  result. nVertices = nVertices;
680  if (!nVertices)
681  return;
682 
683  // compute the initial offsets for the edge numbers
684  for (int_t i = 0; i < nVertices; ++ i)
685  result. edgeEnds [i] = 0;
686  int_t nEdges = edgeEnds [nVertices - 1];
687  for (int_t i = 0; i < nEdges; ++ i)
688  {
689  if (edges [i] < nVertices - 1)
690  ++ result. edgeEnds [edges [i] + 1];
691  }
692  for (int_t i = 2; i < nVertices; ++ i)
693  result. edgeEnds [i] += result. edgeEnds [i - 1];
694 
695  // compute the reversed edges
696  int_t curEdge = 0;
697  for (int_t i = 0; i < nVertices; ++ i)
698  {
699  for (; curEdge < edgeEnds [i]; ++ curEdge)
700  {
701  int_t j = edges [curEdge];
702  int_t &offset = result. edgeEnds [j];
703  result. edges [offset] = i;
704  if (copyweights)
705  result. weights [offset] = weights [curEdge];
706  ++ offset;
707  }
708  }
709  return;
710 } /* diGraph::transpose */
711 
712 template <class wType> template <class Table, class wType1>
714  const Table &tab, bool copyweights) const
715 {
716  // compute the new numbers of vertices that remain in the graph
717  int_t *numbers = new int_t [nVertices];
718  int_t curNumber = 0;
719  for (int_t i = 0; i < nVertices; ++ i)
720  {
721  if (tab [i])
722  numbers [i] = curNumber ++;
723  else
724  numbers [i] = -1;
725  }
726 
727  // copy the edges from the old graph to the new one
728  for (int_t i = 0; i < nVertices; ++ i)
729  {
730  if (numbers [i] < 0)
731  continue;
732  g. addVertex ();
733  int_t firstEdge = i ? edgeEnds [i - 1] :
734  static_cast<int_t> (0);
735  int_t endEdge = edgeEnds [i];
736  for (int_t j = firstEdge; j < endEdge; ++ j)
737  {
738  int_t edgeEnd = edges [j];
739  if (numbers [edgeEnd] >= 0)
740  {
741  if (copyweights)
742  g. addEdge (numbers [edgeEnd],
743  weights [j]);
744  else
745  g. addEdge (numbers [edgeEnd]);
746  }
747  }
748  }
749 
750  // clean up memory and exit
751  delete [] numbers;
752  return;
753 } /* diGraph::subgraph */
754 
755 // --------------------------------------------------
756 
757 template <class wType> template <class Table, class Color>
758 inline void diGraph<wType>::DFScolorRecurrent (Table &tab,
759  const Color &color, int_t vertex) const
760 {
761  tab [vertex] = color;
762  int_t maxEdge = edgeEnds [vertex];
763  for (int_t i = vertex ? edgeEnds [vertex - 1] :
764  static_cast<int_t> (0); i < maxEdge; ++ i)
765  {
766  int_t next = edges [i];
767  if (tab [next] != color)
768  DFScolorRecurrent (tab, color, next);
769  }
770  return;
771 } /* diGraph::DFScolorRecurrent */
772 
773 template <class wType> template <class Table, class Color>
774 inline void diGraph<wType>::DFScolorStack (Table &tab, const Color &color,
775  int_t vertex) const
776 {
777  // prepare stacks for the recursion
778  std::stack<int_t> s_vertex;
779  std::stack<int_t> s_edge;
780  std::stack<int_t> s_maxedge;
781 
782  // mark the current vertex as visited
783  tab [vertex] = color;
784 
785  // determine the edges to be visited
786  int_t edge = vertex ? edgeEnds [vertex - 1] :
787  static_cast<int_t> (0);
788  int_t maxedge = edgeEnds [vertex];
789 
790  while (1)
791  {
792  // return to the previous recursion level
793  // if all the edges have been followed
794  if (edge >= maxedge)
795  {
796  // return if this is the initial recursion level
797  if (s_vertex. empty ())
798  return;
799 
800  // restore the variables from the previous level
801  vertex = s_vertex. top ();
802  s_vertex. pop ();
803  edge = s_edge. top ();
804  s_edge. pop ();
805  maxedge = s_maxedge. top ();
806  s_maxedge. pop ();
807  continue;
808  }
809 
810  // go to the deeper recursion level if possible
811  int_t next = edges [edge ++];
812  if (tab [next] != color)
813  {
814  // store the previous variables at the stacks
815  s_vertex. push (vertex);
816  s_edge. push (edge);
817  s_maxedge. push (maxedge);
818 
819  // set the new vertex
820  vertex = next;
821 
822  // mark the new vertex as visited
823  tab [vertex] = color;
824 
825  // determine the edges to be visited
826  edge = vertex ? edgeEnds [vertex - 1] :
827  static_cast<int_t> (0);
828  maxedge = edgeEnds [vertex];
829  }
830  }
831 } /* diGraph::DFScolorStack */
832 
833 template <class wType> template <class Table, class Color>
834 inline void diGraph<wType>::DFScolor (Table &tab, const Color &color,
835  int_t vertex) const
836 {
837  DFScolorStack (tab, color, vertex);
838  return;
839 } /* diGraph::DFScolor */
840 
841 // --------------------------------------------------
842 
843 template <class wType> template <class Table>
845  int_t vertex, int_t &counter) const
846 {
847  // mark the current vertex as visited
848  tab [vertex] = -1;
849 
850  // call DFS for the other vertices
851  for (int_t edge = vertex ? edgeEnds [vertex - 1] :
852  static_cast<int_t> (0);
853  edge < edgeEnds [vertex]; ++ edge)
854  {
855  int_t next = edges [edge];
856  if (!tab [next])
857  DFSfinishTimeRecurrent (tab, next, counter);
858  }
859 
860  // record the finishing time for the current vertex and return
861  tab [vertex] = ++ counter;
862  return;
863 } /* diGraph::DFSfinishTimeRecurrent */
864 
865 template <class wType> template <class Table>
866 inline void diGraph<wType>::DFSfinishTimeStack (Table &tab, int_t vertex,
867  int_t &counter) const
868 {
869  // prepare stacks for the recursion
870  std::stack<int_t> s_vertex;
871  std::stack<int_t> s_edge;
872  std::stack<int_t> s_maxedge;
873 
874  // mark the current vertex as visited
875  tab [vertex] = -1;
876 
877  // determine the edges to be visited
878  int_t edge = vertex ? edgeEnds [vertex - 1] :
879  static_cast<int_t> (0);
880  int_t maxedge = edgeEnds [vertex];
881 
882  while (1)
883  {
884  // return to the previous recursion level
885  // if all the edges have been followed
886  if (edge >= maxedge)
887  {
888  // record the finishing time
889  // for the current vertex
890  tab [vertex] = ++ counter;
891 
892  // return if this is the initial recursion level
893  if (s_vertex. empty ())
894  return;
895 
896  // restore the variables from the previous level
897  vertex = s_vertex. top ();
898  s_vertex. pop ();
899  edge = s_edge. top ();
900  s_edge. pop ();
901  maxedge = s_maxedge. top ();
902  s_maxedge. pop ();
903  continue;
904  }
905 
906  // go to the deeper recursion level if possible
907  int_t next = edges [edge ++];
908  if (!tab [next])
909  {
910  // store the previous variables at the stacks
911  s_vertex. push (vertex);
912  s_edge. push (edge);
913  s_maxedge. push (maxedge);
914 
915  // set the new vertex
916  vertex = next;
917 
918  // mark the new vertex as visited
919  tab [vertex] = -1;
920 
921  // determine the edges to be visited
922  edge = vertex ? edgeEnds [vertex - 1] :
923  static_cast<int_t> (0);
924  maxedge = edgeEnds [vertex];
925  }
926  }
927 
928  return;
929 } /* diGraph::DFSfinishTimeStack */
930 
931 template <class wType> template <class Table>
932 inline void diGraph<wType>::DFSfinishTime (Table &tab) const
933 {
934  // initialize the table and the counter
935  for (int_t i = 0; i < nVertices; ++ i)
936  tab [i] = 0;
937  int_t counter = 0;
938 
939  // compute the finishing time for each tree in the DFS forest
940  for (int_t i = 0; i < nVertices; ++ i)
941  {
942  if (!tab [i])
943  DFSfinishTimeStack (tab, i, counter);
944  }
945 
946  #ifdef DIGRAPH_DEBUG
947  int_t *tabdebug = new int_t [nVertices];
948  for (int_t i = 0; i < nVertices; ++ i)
949  tabdebug [i] = 0;
950  int_t counterdebug = 0;
951  for (int_t i = 0; i < nVertices; ++ i)
952  if (!tabdebug [i])
953  DFSfinishTimeRecurrent (tabdebug, i, counterdebug);
954  if (counter != counterdebug)
955  throw "DFSfinishTime: Wrong counter.";
956  for (int_t i = 0; i < nVertices; ++ i)
957  {
958  if (tab [i] != tabdebug [i])
959  {
960  chomp::homology::sbug <<
961  "\nDFSfinishTime error: tabRec [" << i <<
962  "] = " << tab [i] << ", tabStack [" << i <<
963  "] = " << tabdebug [i] << ".\n";
964  throw "DFSfinishTime: Wrong numbers.";
965  }
966  }
967  chomp::homology::sbug << "DEBUG: DFSfinishTime OK. ";
968  #endif // DIGRAPH_DEBUG
969  return;
970 } /* diGraph::DFSfinishTime */
971 
972 // --------------------------------------------------
973 
974 template <class wType> template <class Table1, class Table2>
975 inline bool diGraph<wType>::DFSforestRecurrent (Table1 &tab, Table1 &ntab,
976  int_t vertex, int_t treeNumber, int_t countTrees,
977  Table2 &compVertices, int_t &curVertex,
978  diGraph<wType> *sccGraph, int_t *sccEdgeAdded) const
979 {
980  // add the vertex to the tree
981  compVertices [curVertex ++] = vertex;
982 
983  // mark the vertex as belonging to the current tree
984  tab [vertex] = treeNumber;
985 // if (sccGraph)
986 // ntab [treeNumber - 1] = countTrees;
987 
988  // build the tree recursively or record connections
989  bool loop = false;
990  for (int_t edge = vertex ? edgeEnds [vertex - 1] :
991  static_cast<int_t> (0);
992  edge < edgeEnds [vertex]; ++ edge)
993  {
994  int_t next = edges [edge];
995  if (!tab [next])
996  loop |= DFSforestRecurrent (tab, ntab, next,
997  treeNumber, countTrees, compVertices,
998  curVertex, sccGraph, sccEdgeAdded);
999  else if (tab [next] == treeNumber)
1000  {
1001  if (sccGraph)
1002  {
1003  int_t target = ntab [treeNumber - 1];
1004  if (sccEdgeAdded [target] != treeNumber)
1005  {
1006  sccGraph -> addEdge (target);
1007  sccEdgeAdded [target] = treeNumber;
1008  }
1009  }
1010  loop = true;
1011  }
1012  else if (sccGraph)
1013  {
1014  int_t target = ntab [tab [next] - 1];
1015  if ((target >= 0) &&
1016  (sccEdgeAdded [target] != treeNumber))
1017  {
1018  sccGraph -> addEdge (target);
1019  sccEdgeAdded [target] = treeNumber;
1020  }
1021  }
1022  }
1023 
1024  return loop;
1025 } /* diGraph::DFSforestRecurrent */
1026 
1027 template <class wType> template <class Table1, class Table2>
1028 inline bool diGraph<wType>::DFSforestStack (Table1 &tab, Table1 &ntab,
1029  int_t vertex, int_t treeNumber, int_t /*countTrees*/,
1030  Table2 &compVertices, int_t &curVertex,
1031  diGraph<wType> *sccGraph, int_t *sccEdgeAdded) const
1032 {
1033  // prepare stacks for the recursion
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;
1038 
1039  // add the vertex to the tree
1040  compVertices [curVertex ++] = vertex;
1041 
1042  // mark the vertex as belonging to the current tree
1043  tab [vertex] = treeNumber;
1044 // if (sccGraph)
1045 // ntab [vertex] = countTrees;
1046 
1047  // build the tree recursively or record connections
1048  bool loop = false;
1049  int_t edge = vertex ? edgeEnds [vertex - 1] :
1050  static_cast<int_t> (0);
1051  int_t maxedge = edgeEnds [vertex];
1052  while (1)
1053  {
1054  // return to the previous recursion level
1055  // if all the edges have been followed
1056  if (edge >= maxedge)
1057  {
1058  // return if this is the initial recursion level
1059  if (s_vertex. empty ())
1060  return loop;
1061 
1062  // restore the variables from the previous level
1063  vertex = s_vertex. top ();
1064  s_vertex. pop ();
1065  edge = s_edge. top ();
1066  s_edge. pop ();
1067  maxedge = s_maxedge. top ();
1068  s_maxedge. pop ();
1069  loop |= s_loop. top ();
1070  s_loop. pop ();
1071  continue;
1072  }
1073 
1074  // go to the deeper recursion level if possible
1075  int_t next = edges [edge ++];
1076  if (!tab [next])
1077  {
1078  // store the previous variables at the stacks
1079  s_vertex. push (vertex);
1080  s_edge. push (edge);
1081  s_maxedge. push (maxedge);
1082  s_loop. push (loop);
1083 
1084  // set the new vertex
1085  vertex = next;
1086 
1087  // add the vertex to the tree
1088  compVertices [curVertex ++] = vertex;
1089 
1090  // mark the vertex as belonging to the current tree
1091  tab [vertex] = treeNumber;
1092 
1093  // determine the edges to be visited
1094  loop = false;
1095  edge = vertex ? edgeEnds [vertex - 1] :
1096  static_cast<int_t> (0);
1097  maxedge = edgeEnds [vertex];
1098  }
1099  else if (tab [next] == treeNumber)
1100  {
1101  if (sccGraph)
1102  {
1103  int_t target = ntab [treeNumber - 1];
1104  if (sccEdgeAdded [target] != treeNumber)
1105  {
1106  sccGraph -> addEdge (target);
1107  sccEdgeAdded [target] = treeNumber;
1108  }
1109  }
1110  loop = true;
1111  }
1112  else if (sccGraph)
1113  {
1114  int_t target = ntab [tab [next] - 1];
1115  if ((target >= 0) &&
1116  (sccEdgeAdded [target] != treeNumber))
1117  {
1118  sccGraph -> addEdge (target);
1119  sccEdgeAdded [target] = treeNumber;
1120  }
1121  }
1122  }
1123 
1124  return loop;
1125 } /* diGraph::DFSforestStack */
1126 
1127 template <class wType> template <class Table1, class Table2, class Table3>
1128 inline int_t diGraph<wType>::DFSforest (const Table1 &ordered,
1129  Table2 &compVertices, Table3 &compEnds, bool nontrivial,
1130  diGraph<wType> *sccGraph) const
1131 {
1132  // prepare a table to record the numbers of DFS trees
1133  // to which the vertices belong (the tree numbers begin with 1)
1134  int_t *tab = new int_t [nVertices];
1135  for (int_t i = 0; i < nVertices; ++ i)
1136  tab [i] = 0;
1137 
1138  // prepare a table to record the numbers of nontrivial trees
1139  // that correspond to the trees in 'tab' (these numbers begin with 0)
1140  int_t *ntab = new int_t [nVertices];
1141 
1142  // prepare a table to record the numbers of edges already in the
1143  // scc graph; "sccEdgeAdded [n] = m" indicates that the edge
1144  // m -> n has been added to the scc graph
1145  int_t *sccEdgeAdded = sccGraph ? new int_t [nVertices] :
1146  static_cast<int_t *> (0);
1147  if (sccGraph)
1148  {
1149  for (int_t n = 0; n < nVertices; ++ n)
1150  sccEdgeAdded [n] = -1;
1151  }
1152 
1153  // prepare the official DFS tree number
1154  int_t treeNumber = 0;
1155 
1156  // prepare the data for keeping the nontrivial trees information
1157  int_t countTrees = 0;
1158  int_t curVertex = 0;
1159 
1160  // compute the DFS trees and connections between them
1161  for (int_t i = 0; i < nVertices; ++ i)
1162  {
1163  // take the next vertex
1164  int_t vertex = ordered [i];
1165 
1166  // if the vertex already belongs to some tree, skip it
1167  if (tab [vertex])
1168  continue;
1169 
1170  // add a vertex corresponding to the component
1171  if (sccGraph)
1172  sccGraph -> addVertex ();
1173 
1174  // remember the previous vertex number
1175  int_t prevVertex = curVertex;
1176 
1177  // mark the entire component and record connections graph
1178  if (sccGraph)
1179  ntab [treeNumber] = countTrees;
1180  ++ treeNumber;
1181  bool loop = DFSforestStack (tab, ntab, vertex,
1182  treeNumber, countTrees, compVertices,
1183  curVertex, sccGraph, sccEdgeAdded);
1184 
1185  // update the index bound for the vertex list
1186  compEnds [countTrees ++] = curVertex;
1187 
1188  // remove the component if it is trivial
1189  if (nontrivial && !loop)
1190  {
1191  -- countTrees;
1192  curVertex = prevVertex;
1193  if (sccGraph)
1194  {
1195  ntab [treeNumber - 1] = -1;
1196  sccGraph -> removeVertex ();
1197  }
1198  }
1199  }
1200 
1201  #ifdef DIGRAPH_DEBUG
1202  diGraph<wType> *sccGraphdebug = 0;
1203  if (sccGraph)
1204  sccGraphdebug = new diGraph<wType>;
1205  // prepare a table to record the numbers of DFS trees
1206  // to which the vertices belong (the tree numbers begin with 1)
1207  int_t *tabdebug = new int_t [nVertices];
1208  for (int_t i = 0; i < nVertices; ++ i)
1209  tabdebug [i] = 0;
1210 
1211  // prepare a table to record the numbers of nontrivial trees
1212  // to which the vertices belong (the tree numbers begin with 0)
1213  int_t *ntabdebug = new int_t [nVertices];
1214 
1215  // prepare a table to record the numbers of vertices from which
1216  // edges were added to the scc graph
1217  int_t *sccEdgeAddeddebug = sccGraph ? new int_t [nVertices] :
1218  static_cast<int_t> (0);
1219  if (sccGraph)
1220  {
1221  for (int_t n = 0; n < nVertices; ++ n)
1222  sccEdgeAddeddebug [n] = -1;
1223  }
1224  // prepare the official DFS tree number
1225  int_t treeNumberdebug = 0;
1226 
1227  // prepare the data for keeping the nontrivial trees information
1228  int_t countTreesdebug = 0;
1229  int_t curVertexdebug = 0;
1230 
1231  int_t *compVerticesdebug = new int_t [nVertices];
1232  int_t *compEndsdebug = new int_t [nVertices];
1233 
1234  // compute the DFS trees and connections between them
1235  for (int_t i = 0; i < nVertices; ++ i)
1236  {
1237  // take the next vertex
1238  int_t vertex = ordered [i];
1239 
1240  // if the vertex already belongs to some tree, skip it
1241  if (tabdebug [vertex])
1242  continue;
1243 
1244  // add a vertex corresponding to the component
1245  if (sccGraphdebug)
1246  sccGraphdebug -> addVertex ();
1247 
1248  // remember the previous vertex number
1249  int_t prevVertex = curVertexdebug;
1250 
1251  // mark the entire component and record connections graph
1252  if (sccGraphdebug)
1253  ntabdebug [treeNumberdebug] = countTreesdebug;
1254  ++ treeNumberdebug;
1255  bool loop = DFSforestRecurrent (tabdebug, ntabdebug, vertex,
1256  treeNumberdebug, countTreesdebug, compVerticesdebug,
1257  curVertexdebug, sccGraphdebug, sccEdgeAddeddebug);
1258 
1259  // update the index bound for the vertex list
1260  compEndsdebug [countTreesdebug ++] = curVertexdebug;
1261 
1262  // remove the component if it is trivial
1263  if (nontrivial && !loop)
1264  {
1265  -- countTreesdebug;
1266  curVertexdebug = prevVertex;
1267  if (sccGraphdebug)
1268  {
1269  ntabdebug [treeNumberdebug - 1] = -1;
1270  sccGraphdebug -> removeVertex ();
1271  }
1272  }
1273  }
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.";
1284  for (int_t i = 0; i < nVertices; ++ i)
1285  if (tab [i] != tabdebug [i])
1286  throw "DFSforest: Wrong tab.";
1287  if (sccGraph)
1288  {
1289  for (int_t i = 0; i < nVertices; ++ i)
1290  if (ntab [i] != ntabdebug [i])
1291  throw "DFSforest: Wrong ntab.";
1292  if (*sccGraph != *sccGraphdebug)
1293  throw "DFSforest: Wrong graph.";
1294  }
1295  if (sccEdgeAdded)
1296  {
1297  for (int_t i = 0; i < nVertices; ++ i)
1298  if (sccEdgeAdded [i] != sccEdgeAddeddebug [i])
1299  throw "DFSforest: Wrong sccEdgeAdded.";
1300  }
1301  if (treeNumber != treeNumberdebug)
1302  throw "DFSforest: Wrong treeNumber.";
1303  chomp::homology::sbug << "DEBUG: DFSforest OK. ";
1304  if (!sccGraph)
1305  chomp::homology::sbug << "(Graphs not compared.) ";
1306  delete [] compVerticesdebug;
1307  delete [] compEndsdebug;
1308  if (sccGraphdebug)
1309  delete sccGraphdebug;
1310  delete [] ntabdebug;
1311  delete [] tabdebug;
1312  if (sccEdgeAddeddebug)
1313  delete [] sccEdgeAddeddebug;
1314  #endif // DIGRAPH_DEBUG
1315 
1316  if (sccEdgeAdded)
1317  delete [] sccEdgeAdded;
1318  delete [] ntab;
1319  delete [] tab;
1320  return countTrees;
1321 } /* diGraph::DFSforest */
1322 
1323 // --------------------------------------------------
1324 
1325 template <class wType>
1326 inline int_t diGraph<wType>::shortestPath (int_t source, int_t destination)
1327  const
1328 {
1329  // make sure that the given vertex is present in the graph
1330  if ((source < 0) || (source >= nVertices) ||
1331  (destination < 0) || (destination >= nVertices))
1332  {
1333  throw "diGraph - shortest path: Wrong vertex number.";
1334  }
1335 
1336  // prepare an array of bits to store the information
1337  // on whether the given vertices have been visited or not
1338  chomp::homology::BitField visited;
1339  visited. allocate (nVertices);
1340  visited. clearall (nVertices);
1341 
1342  // prepare queues for the BFS algorithm
1343  std::queue<int_t> q_vertex;
1344  std::queue<int_t> q_depth;
1345 
1346  // set the initial vertex
1347  int_t vertex = source;
1348  int_t depth = 0;
1349 
1350  while (1)
1351  {
1352  // mark the current vertex as visited
1353  visited. set (vertex);
1354 
1355  // determine the depth of the vertices that will be analyzed
1356  ++ depth;
1357 
1358  // determine the edges to be checked
1359  int_t firstedge = vertex ? edgeEnds [vertex - 1] :
1360  static_cast<int_t> (0);
1361  int_t maxedge = edgeEnds [vertex];
1362 
1363  // put all the unvisited destination vertices on the stack
1364  for (int_t edge = firstedge; edge < maxedge; ++ edge)
1365  {
1366  // determine the vertex pointed to by this edge
1367  int_t next = edges [edge];
1368 
1369  // if this is the destination vertex then return
1370  // the shortest path length; note: this vertex
1371  // might be visited if checking a loop, so it is
1372  // important to check the destination first
1373  if (next == destination)
1374  {
1375  visited. free ();
1376  return depth;
1377  }
1378 
1379  // if the vertex was already visited then skip it
1380  if (visited. test (next))
1381  continue;
1382 
1383  // add the vertex to the queue
1384  q_vertex. push (next);
1385  q_depth. push (depth);
1386  }
1387 
1388  // if there are no vertices whose neighbors are to be
1389  // analyzed and the destination vertex was not found
1390  // then there is no path to that vertex
1391  if (q_vertex. empty ())
1392  {
1393  visited. free ();
1394  return 0;
1395  }
1396 
1397  // pick up a vertex stored in the queue
1398  vertex = q_vertex. front ();
1399  q_vertex. pop ();
1400  depth = q_depth. front ();
1401  q_depth. pop ();
1402  }
1403 } /* diGraph::shortestPath */
1404 
1405 template <class wType>
1406 inline int_t diGraph<wType>::shortestLoop (int_t origin) const
1407 {
1408  return shortestPath (origin, origin);
1409 } /* diGraph::shortestLoop */
1410 
1411 template <class wType>
1412 template <class lenTable, class weightsType, class roundType>
1413 inline void diGraph<wType>::Dijkstra (const roundType &rounding,
1414  int_t source, lenTable &len, weightsType &edgeWeights) const
1415 {
1416  // use the Fibonacci heap as a priority queue
1417  chomp::homology::FibonacciHeap<posWeight> Q (nVertices);
1418 
1419  // add the vertices to the heap with the initial shortest path
1420  // lengths: 0 to the source, plus infinity to all the others
1421  for (int_t v = 0; v < nVertices; ++ v)
1422  {
1423  posWeight w (0);
1424  if (v != source)
1425  w. setInfinity ();
1426  int_t number = Q. Insert (w);
1427  if (number != v)
1428  {
1429  throw "Wrong implementation of Fibonacci heap "
1430  "for this version of Dijkstra.";
1431  }
1432  }
1433 
1434  // pick up vertices from the priority queue, record the length
1435  // of the shortest path to them, and modify the remaining paths
1436  for (int_t i = 0; i < nVertices; ++ i)
1437  {
1438  // extract the minimal vertex from the queue
1439  int_t minVertex = Q. Minimum ();
1440  posWeight minWeight = Q. ExtractMinimum ();
1441 
1442  if (minWeight. isInfinity ())
1443  {
1444  len [minVertex] = -1;
1445  continue;
1446  }
1447  wType minValue = minWeight. getValue ();
1448  len [minVertex] = minValue;
1449 
1450  // go through all the edges emanating from this vertex
1451  // and update the path lengths for the target vertices
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)
1456  {
1457  // determine the vertex at the other end of the edge
1458  int_t nextVertex = edges [edge];
1459 
1460  // if the path that runs through the extracted
1461  // vertex is shorter, then make a correction
1462  const posWeight &nextWeight = Q. Value (nextVertex);
1463  wType newWeight = rounding. add_down (minValue,
1464  edgeWeights [edge]);
1465  if (newWeight < 0)
1466  newWeight = 0;
1467  if (nextWeight. isInfinity () ||
1468  (newWeight < nextWeight. getValue ()))
1469  {
1470  Q. DecreaseKey (nextVertex,
1471  posWeight (newWeight));
1472  }
1473  }
1474  }
1475  return;
1476 } /* diGraph::Dijkstra */
1477 
1478 template <class wType>
1479 template <class lenTable, class roundType>
1480 inline void diGraph<wType>::Dijkstra (const roundType &rounding,
1481  int_t source, lenTable &len) const
1482 {
1483  this -> Dijkstra (rounding, source, len, this -> weights);
1484  return;
1485 } /* diGraph::Dijkstra */
1486 
1487 template <class wType>
1488 template <class lenTable>
1489 inline void diGraph<wType>::Dijkstra (int_t source, lenTable &len) const
1490 {
1491  const dummyRounding<wType> rounding = dummyRounding<wType> ();
1492  this -> Dijkstra (rounding, source, len);
1493  return;
1494 } /* diGraph::Dijkstra */
1495 
1496 template <class wType> template <class lenTable, class predTable,
1497  class roundType>
1498 inline bool diGraph<wType>::BellmanFord (const roundType &rounding,
1499  int_t source, lenTable &len, wType *infinity, predTable pred) const
1500 {
1501  // make sure the source vertex number is correct
1502  if ((source < 0) || (source >= nVertices))
1503  throw "Bellman-Ford: Wrong source vertex number.";
1504 
1505  // prepare marks to indicate finite values (not "infinity")
1506  chomp::homology::BitField finite;
1507  finite. allocate (nVertices);
1508  finite. clearall (nVertices);
1509  finite. set (source);
1510  len [source] = 0;
1511 
1512  // count the negative vertices
1513  int_t countNegative = 0;
1514 
1515  // set the initial predecessors
1516  for (int_t i = 0; i < nVertices; ++ i)
1517  pred [i] = -1;
1518 
1519  // update the lenghts of the paths repeatedly (max nVertices times)
1520  bool noNegativeLoop = false;
1521  int_t counter = 0;
1522  for (; counter <= nVertices; ++ counter)
1523  {
1524  bool modified = false;
1525  int_t curEdge = 0;
1526  for (int_t vertex = 0; vertex < nVertices; ++ vertex)
1527  {
1528  int_t maxEdge = edgeEnds [vertex];
1529  if (!finite. test (vertex))
1530  {
1531  curEdge = maxEdge;
1532  continue;
1533  }
1534  for (; curEdge < maxEdge; ++ curEdge)
1535  {
1536  int_t next = edges [curEdge];
1537  wType newlen = rounding. add_down
1538  (len [vertex], weights [curEdge]);
1539  if (!finite. test (next))
1540  {
1541  finite. set (next);
1542  modified = true;
1543  len [next] = newlen;
1544  pred [next] = vertex;
1545  if (newlen < 0)
1546  ++ countNegative;
1547  }
1548  else if (newlen < len [next])
1549  {
1550  modified = true;
1551  if (!(len [next] < 0) &&
1552  (newlen < 0))
1553  {
1554  ++ countNegative;
1555  }
1556  len [next] = newlen;
1557  pred [next] = vertex;
1558  }
1559  }
1560  }
1561  if (countNegative == nVertices)
1562  {
1563  noNegativeLoop = false;
1564  ++ counter;
1565  break;
1566  }
1567  if (!modified)
1568  {
1569  noNegativeLoop = true;
1570  ++ counter;
1571  break;
1572  }
1573  }
1574 
1575  // show a message on how many loops have been done
1576  if (false && chomp::homology::sbug. show)
1577  {
1578  chomp::homology::sbug << "Bellman-Ford: " <<
1579  counter << ((counter > 1) ? " loops (" : " loop (") <<
1580  nVertices << " vertices, " << countNegative <<
1581  " negative). " <<
1582  (noNegativeLoop ? "No negative loops.\n" :
1583  "A negative loop found.\n");
1584  }
1585 
1586  // compute the value for the infinity and set the undefined distances
1587  if (infinity && noNegativeLoop)
1588  {
1589  wType infty (0);
1590  bool first = true;
1591  for (int_t i = 0; i < nVertices; ++ i)
1592  {
1593  if (!finite. test (i))
1594  continue;
1595  if (first)
1596  {
1597  infty = len [i];
1598  first = false;
1599  }
1600  else if (infty < len [i])
1601  {
1602  infty = len [i];
1603  }
1604  }
1605  infty = infty + 1;
1606  for (int_t i = 0; i < nVertices; ++ i)
1607  {
1608  if (!finite. test (i))
1609  len [i] = infty;
1610  }
1611  *infinity = infty;
1612  }
1613 
1614  finite. free ();
1615  return noNegativeLoop;
1616 } /* diGraph::BellmanFord */
1617 
1618 template <class wType> template <class lenTable, class predTable>
1619 inline bool diGraph<wType>::BellmanFord (int_t source, lenTable &len,
1620  wType *infinity, predTable pred) const
1621 {
1622  const dummyRounding<wType> rounding = dummyRounding<wType> ();
1623  return this -> BellmanFord (rounding, source, len, infinity, pred);
1624 } /* diGraph::BellmanFord */
1625 
1626 template <class wType> template <class roundType>
1627 inline bool diGraph<wType>::BellmanFord (const roundType &rounding,
1628  int_t source) const
1629 {
1630  chomp::homology::auto_array<wType> len_ptr (new wType [nVertices]);
1631  wType *len = len_ptr. get ();
1632  wType *infinity = 0;
1633  dummyArray tab;
1634  return BellmanFord (rounding, source, len, infinity, tab);
1635 } /* diGraph::BellmanFord */
1636 
1637 template <class wType>
1638 inline bool diGraph<wType>::BellmanFord (int_t source) const
1639 {
1640  const dummyRounding<wType> rounding = dummyRounding<wType> ();
1641  return BellmanFord (rounding, source);
1642 } /* diGraph::BellmanFord */
1643 
1644 template <class wType>
1645 inline wType diGraph<wType>::Edmonds () const
1646 {
1647  // create a list of edges with weights and sort this list
1648  std::vector<edgeTriple> edgeTriples (countEdges ());
1649  int_t prevEdge = 0;
1650  int_t curEdge = 0;
1651  for (int_t vert = 0; vert < nVertices; ++ vert)
1652  {
1653  while (curEdge < edgeEnds [vert])
1654  {
1655  edgeTriple &e = edgeTriples [curEdge];
1656  e. vert1 = vert;
1657  e. vert2 = edges [curEdge];
1658  e. weight = weights [curEdge];
1659  ++ curEdge;
1660  }
1661  prevEdge = curEdge;
1662  }
1663  std::sort (edgeTriples. begin (), edgeTriples. end ());
1664 
1665  // create a forest which initially contains single vertices
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)
1669  {
1670  root [vert] = -1;
1671  }
1672 
1673  // go through the edges and join the trees, but avoid loops
1674  wType totalWeight = 0;
1675  int_t nEdges = countEdges ();
1676  for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
1677  {
1678  // determine the roots of both vertices of the edge
1679  // and compress the paths
1680  edgeTriple &e = edgeTriples [curEdge];
1681  int_t root1 = e. vert1;
1682  while (root [root1] >= 0)
1683  {
1684  root1 = root [root1];
1685  }
1686  int_t vert1 = e. vert1;
1687  while (root [vert1] >= 0)
1688  {
1689  int_t next = root [vert1];
1690  root [vert1] = root1;
1691  vert1 = next;
1692  }
1693  int_t root2 = e. vert2;
1694  while (root [root2] >= 0)
1695  {
1696  root2 = root [root2];
1697  }
1698  int_t vert2 = e. vert2;
1699  while (root [vert2] >= 0)
1700  {
1701  int_t next = root [vert2];
1702  root [vert2] = root2;
1703  vert2 = next;
1704  }
1705 
1706  // skip the edge if it closes a loop
1707  if (root1 == root2)
1708  continue;
1709 
1710  // add the weight
1711  totalWeight += e. weight;
1712 
1713  // join the trees
1714  root [root1] = root2;
1715  }
1716  return totalWeight;
1717 } /* diGraph::Edmonds */
1718 
1719 template <class wType>
1720 inline wType diGraph<wType>::EdmondsOld () const
1721 {
1722  // create a list of edges with weights and sort this list
1723  std::vector<edgeTriple> edgeTriples (countEdges ());
1724  int_t prevEdge = 0;
1725  int_t curEdge = 0;
1726  for (int_t vert = 0; vert < nVertices; ++ vert)
1727  {
1728  while (curEdge < edgeEnds [vert])
1729  {
1730  edgeTriple &e = edgeTriples [curEdge];
1731  e. vert1 = vert;
1732  e. vert2 = edges [curEdge];
1733  e. weight = weights [curEdge];
1734  ++ curEdge;
1735  }
1736  prevEdge = curEdge;
1737  }
1738  std::sort (edgeTriples. begin (), edgeTriples. end ());
1739 
1740  // create a forest which initially contains single vertices
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)
1751  {
1752  forest [vert] = vert;
1753  next [vert] = -1;
1754  prev [vert] = -1;
1755  }
1756 
1757  // go through the edges and join the trees, but avoid loops
1758  wType totalWeight = 0;
1759  int_t nEdges = countEdges ();
1760  for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
1761  {
1762  // check the edge and skip it if it closes a loop
1763  edgeTriple &e = edgeTriples [curEdge];
1764  if (forest [e. vert1] == forest [e. vert2])
1765  continue;
1766 
1767  // add the weight
1768  totalWeight += e. weight;
1769 
1770  // go to the end of the first tree
1771  int_t vert1 = e. vert1;
1772  while (next [vert1] >= 0)
1773  {
1774  vert1 = next [vert1];
1775  }
1776 
1777  // go to the beginning of the second tree
1778  int_t vert2 = e. vert2;
1779  while (prev [vert2] >= 0)
1780  {
1781  vert2 = prev [vert2];
1782  }
1783 
1784  // join the trees and modify the numbers
1785  next [vert1] = vert2;
1786  prev [vert2] = vert1;
1787  int_t treeNumber = forest [vert1];
1788  while (vert2 >= 0)
1789  {
1790  forest [vert2] = treeNumber;
1791  vert2 = next [vert2];
1792  }
1793  }
1794  return totalWeight;
1795 } /* diGraph::EdmondsOld */
1796 
1797 template <class wType>
1798 template <class arrayType, class roundType>
1799 inline wType diGraph<wType>::FloydWarshall (const roundType &rounding,
1800  arrayType &arr, bool setInfinity, bool ignoreNegLoop) const
1801 {
1802  // do nothing if the graph is empty
1803  if (!nVertices)
1804  return 0;
1805 
1806  // prepare marks to indicate finite values (not "infinity")
1807  chomp::homology::BitField *finite =
1808  new chomp::homology::BitField [nVertices];
1809  for (int_t i = 0; i < nVertices; ++ i)
1810  {
1811  finite [i]. allocate (nVertices);
1812  finite [i]. clearall (nVertices);
1813  }
1814 
1815  // create the initial values of the array based on the edge weights
1816  int_t curEdge = 0;
1817  for (int_t source = 0; source < nVertices; ++ source)
1818  {
1819  bool diagset = false;
1820  while (curEdge < edgeEnds [source])
1821  {
1822  int_t target = edges [curEdge];
1823  const wType &weight = weights [curEdge];
1824  if (source == target)
1825  {
1826  if (weight < 0)
1827  {
1828  arr [source] [target] = weight;
1829  diagset = true;
1830  }
1831  }
1832  else
1833  {
1834  arr [source] [target] = weight;
1835  finite [source]. set (target);
1836  }
1837  ++ curEdge;
1838  }
1839  if (!diagset)
1840  arr [source] [source] = 0;
1841  finite [source]. set (source);
1842  }
1843 
1844  // find the shortest paths between the vertices (dynamic programming)
1845  for (int_t k = 0; k < nVertices; ++ k)
1846  {
1847  for (int_t i = 0; i < nVertices; ++ i)
1848  {
1849  if (!finite [i]. test (k))
1850  continue;
1851  for (int_t j = 0; j < nVertices; ++ j)
1852  {
1853  if (!finite [k]. test (j))
1854  continue;
1855  const wType sum = rounding. add_down
1856  (arr [i] [k], arr [k] [j]);
1857  if (finite [i]. test (j))
1858  {
1859  if (sum < arr [i] [j])
1860  arr [i] [j] = sum;
1861  }
1862  else
1863  {
1864  arr [i] [j] = sum;
1865  finite [i]. set (j);
1866  }
1867  }
1868  }
1869  }
1870 
1871  // verify if a negative loop exists by checking for a negative
1872  // result in the diagonal
1873  if (!ignoreNegLoop)
1874  {
1875  for (int_t i = 0; i < nVertices; ++ i)
1876  {
1877  if (arr [i] [i] < 0)
1878  throw "Negative loop in Floyd-Warshall.";
1879  }
1880  }
1881 
1882  // prepare a variable to store the returned result
1883  wType result = 0;
1884 
1885  // compute the value for the infinity and fill in the array
1886  // if requested to do so
1887  if (setInfinity)
1888  {
1889  wType &infinity = result;
1890  for (int_t i = 0; i < nVertices; ++ i)
1891  {
1892  for (int_t j = 0; j < nVertices; ++ j)
1893  {
1894  if (finite [i]. test (j) &&
1895  (infinity <= arr [i] [j]))
1896  {
1897  infinity = rounding. add_up
1898  (arr [i] [j], 1);
1899  }
1900  }
1901  }
1902  for (int_t i = 0; i < nVertices; ++ i)
1903  {
1904  for (int_t j = 0; j < nVertices; ++ j)
1905  {
1906  if (!finite [i]. test (j))
1907  arr [i] [j] = infinity;
1908  }
1909  }
1910  }
1911 
1912  // otherwise, only compute the minimum path weight
1913  else
1914  {
1915  wType &minWeight = result;
1916  bool firstTime = true;
1917  for (int_t i = 0; i < nVertices; ++ i)
1918  {
1919  for (int_t j = 0; j < nVertices; ++ j)
1920  {
1921  if (finite [i]. test (j))
1922  {
1923  if (firstTime)
1924  {
1925  minWeight = arr [i] [j];
1926  firstTime = false;
1927  }
1928  else if (arr [i] [j] < minWeight)
1929  {
1930  minWeight = arr [i] [j];
1931  }
1932  }
1933  }
1934  }
1935  }
1936 
1937  // release the 'finite' bitfields
1938  for (int_t i = 0; i < nVertices; ++ i)
1939  finite [i]. free ();
1940  delete [] finite;
1941 
1942  return result;
1943 } /* diGraph::FloydWarshall */
1944 
1945 template <class wType>
1946 template <class arrayType>
1947 inline wType diGraph<wType>::FloydWarshall (arrayType &arr,
1948  bool setInfinity, bool ignoreNegLoop) const
1949 {
1950  const dummyRounding<wType> rounding = dummyRounding<wType> ();
1951  return FloydWarshall (rounding, arr, setInfinity, ignoreNegLoop);
1952 } /* diGraph::FloydWarshall */
1953 
1954 template <class wType>
1955 template <class arrayType, class roundType>
1956 inline wType diGraph<wType>::Johnson (const roundType &rounding,
1957  arrayType &arr, bool setInfinity, bool ignoreNegLoop) const
1958 {
1959  // DEBUG VERIFICATION
1960  if (false && chomp::homology::sbug. show)
1961  {
1962  chomp::homology::timeused stopWatch;
1963  wType res = FloydWarshall (rounding,
1964  arr, setInfinity, ignoreNegLoop);
1965  chomp::homology::sbug << "\n[Floyd-Warshall: " << res <<
1966  ", " << (double) stopWatch << " sec]\n";
1967  }
1968  // debug time measurement (see below)
1969 // chomp::homology::timeused stopWatch;
1970 
1971  // do nothing if the graph is empty
1972  if (!nVertices)
1973  return 0;
1974 
1975  // STEP 1: Compute the shortest paths to any vertex from an
1976  // artificial extra vertex connected to every other vertex in the
1977  // graph by an edge of weight zero. Use Bellman-Ford for this.
1978  wType *len = new wType [nVertices];
1979  for (int_t i = 0; i < nVertices; ++ i)
1980  len [i] = 0;
1981 
1982  // update the lenghts of the paths repeatedly (max nVertices times)
1983  bool noNegativeLoop = false;
1984  int_t counter = 0;
1985  for (; counter <= nVertices; ++ counter)
1986  {
1987  bool modified = false;
1988  int_t curEdge = 0;
1989  for (int_t vertex = 0; vertex < nVertices; ++ vertex)
1990  {
1991  int_t maxEdge = edgeEnds [vertex];
1992  for (; curEdge < maxEdge; ++ curEdge)
1993  {
1994  int_t next = edges [curEdge];
1995  wType newlen = rounding. add_down
1996  (len [vertex], weights [curEdge]);
1997  if (newlen < len [next])
1998  {
1999  // this "if" statement is necessary
2000  // because of a bug in GCC 3.4.2...
2001  if (counter > nVertices)
2002  {
2003  std::cout << vertex;
2004  }
2005  modified = true;
2006  len [next] = newlen;
2007  }
2008  }
2009  }
2010  if (!modified)
2011  {
2012  noNegativeLoop = true;
2013  ++ counter;
2014  break;
2015  }
2016  }
2017  if (!ignoreNegLoop && !noNegativeLoop)
2018  throw "Negative loop found in Johnson's algorithm.";
2019 
2020  // STEP 2: Re-weigh the edges using the computed path lengths.
2021  wType *newWeights = new wType [edgeEnds [nVertices - 1]];
2022  int_t edge = 0;
2023  for (int_t vertex = 0; vertex < nVertices; ++ vertex)
2024  {
2025  int_t maxEdge = edgeEnds [vertex];
2026  for (; edge < maxEdge; ++ edge)
2027  {
2028  wType w = weights [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;
2033  }
2034  }
2035 
2036  // STEP 3: Run the Dijkstra algorithm for every vertex to compute
2037  // the shortest paths to all the other vertices.
2038  // Negative entries indicate no path existence.
2039  for (int_t u = 0; u < nVertices; ++ u)
2040  {
2041  this -> Dijkstra (rounding, u, arr [u], newWeights);
2042  }
2043  delete [] newWeights;
2044 
2045  // STEP 4: Make a correction to the computed path lengths.
2046  // Compute the value for infinity if requested to.
2047  // Otherwise compute the minimum of path lengths.
2048  wType result = 0;
2049  if (setInfinity)
2050  {
2051  wType &infinity = result;
2052  for (int_t u = 0; u < nVertices; ++ u)
2053  {
2054  for (int_t v = 0; v < nVertices; ++ v)
2055  {
2056  wType w = arr [u] [v];
2057  if (w < 0)
2058  continue;
2059  w = rounding. add_down (w, len [v]);
2060  w = rounding. sub_down (w, len [u]);
2061  if (w < infinity)
2062  continue;
2063  infinity = rounding. add_up (w, 1);
2064  }
2065  }
2066  for (int_t u = 0; u < nVertices; ++ u)
2067  {
2068  for (int_t v = 0; v < nVertices; ++ v)
2069  {
2070  wType w = arr [u] [v];
2071  if (w < 0)
2072  {
2073  arr [u] [v] = infinity;
2074  continue;
2075  }
2076  w = rounding. add_down (w, len [v]);
2077  arr [u] [v] =
2078  rounding. sub_down (w, len [u]);
2079  }
2080  }
2081  }
2082  else
2083  {
2084  wType &minWeight = result;
2085  bool firstTime = true;
2086  for (int_t u = 0; u < nVertices; ++ u)
2087  {
2088  for (int_t v = 0; v < nVertices; ++ v)
2089  {
2090  wType w = arr [u] [v];
2091  if (w < 0)
2092  continue;
2093  w = rounding. add_down (w, len [v]);
2094  w = rounding. sub_down (w, len [u]);
2095  if (firstTime)
2096  {
2097  minWeight = w;
2098  firstTime = false;
2099  }
2100  else if (w < minWeight)
2101  minWeight = w;
2102  }
2103  }
2104  }
2105  delete [] len;
2106 
2107  // DEBUG VERIFICATION
2108  if (false && chomp::homology::sbug. show)
2109  {
2110 // chomp::homology::sbug << "[Johnson: " << result <<
2111 // ", " << (double) stopWatch << " sec]\n";
2112  }
2113 
2114  return result;
2115 } /* diGraph::Johnson */
2116 
2117 template <class wType>
2118 template <class arrayType>
2119 inline wType diGraph<wType>::Johnson (arrayType &arr,
2120  bool setInfinity, bool ignoreNegLoop) const
2121 {
2122  const dummyRounding<wType> rounding = dummyRounding<wType> ();
2123  return Johnson (rounding, arr, setInfinity, ignoreNegLoop);
2124 } /* diGraph::Johnson */
2125 
2126 template <class wType>
2127 template <class roundType>
2128 wType diGraph<wType>::minPathWeight (const roundType &rounding,
2129  bool ignoreNegLoop, int sparseGraph) const
2130 {
2131  // if the graph is empty, return 0 as the minimum path weight
2132  if (nVertices <= 0)
2133  return 0;
2134 
2135  // allocate memory for an array of arrays to store min path weights
2136  wType **arr = new wType * [nVertices];
2137  for (int_t i = 0; i < nVertices; ++ i)
2138  arr [i] = new wType [nVertices];
2139 
2140  // determine whether to run the Floyd-Warshall algorithm
2141  // or Johnson's algorithm
2142  bool sparse = false;
2143  if (sparseGraph == 1)
2144  sparse = true;
2145  else if (sparseGraph != 0)
2146  {
2147  double nEdgesD = this -> countEdges ();
2148  double nVerticesD = this -> countVertices ();
2149  if ((nVerticesD > 3000) && (nEdgesD < nVerticesD * 1000) &&
2150  (nEdgesD < nVerticesD * nVerticesD / 50))
2151  {
2152  sparse = true;
2153  }
2154  }
2155 
2156  // run the Johnson's or Floyd-Warshall algorithm
2157  wType minWeight = sparse ?
2158  this -> Johnson (rounding, arr, false, ignoreNegLoop) :
2159  this -> FloydWarshall (rounding, arr, false, ignoreNegLoop);
2160 
2161 /* // compute the minimum of all the paths
2162  wType minWeight = arr [0] [0];
2163  for (int_t i = 0; i < nVertices; ++ i)
2164  {
2165  for (int_t j = 0; j < nVertices; ++ j)
2166  {
2167  const wType &weight = arr [i] [j];
2168  if (weight < minWeight)
2169  minWeight = weight;
2170  }
2171  }
2172 */
2173  // release the memory
2174  for (int_t i = 0; i < nVertices; ++ i)
2175  delete [] (arr [i]);
2176  delete [] arr;
2177 
2178  return minWeight;
2179 } /* diGraph::minPathWeight */
2180 
2181 template <class wType>
2182 wType diGraph<wType>::minPathWeight (bool ignoreNegLoop, int sparseGraph)
2183  const
2184 {
2185  const dummyRounding<wType> rounding = dummyRounding<wType> ();
2186  return this -> minPathWeight (rounding, ignoreNegLoop, sparseGraph);
2187 } /* diGraph::minPathWeight */
2188 
2189 
2190 
2191 } // namespace cymealg
2192 
2193 #endif // _CYMEALG_DIGRAPH_H_
2194 
2195 /// @}
2196 
posWeight()
The default constructor.
Definition: digraph.h:388
void subgraph(diGraph< wType1 > &result, const Table &tab, bool copyweights=false) const
Computes a restriction of the graph to its subgraph.
Definition: digraph.h:713
wType weight_type
The type of the weight of edges.
Definition: digraph.h:79
wType weight
The weight of the edge.
Definition: digraph.h:372
std::ostream & operator<<(std::ostream &out, const diGraph< wType > &g)
Writes a graph in the text mode to an output stream.
Definition: readwrite.h:165
int_t DFSforest(const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, diGraph< wType > *sccGraph=0) const
Computes the DFS forest.
Definition: digraph.h:1128
bool operator!=(const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
Definition: digraph.h:492
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.
Definition: digraph.h:834
posWeight(const wType &_value)
An optional constructor.
Definition: digraph.h:395
int_t countVertices(void) const
Returns the number of vertices.
Definition: digraph.h:625
This class defines a weighted directed graph with very limited number of operations.
Definition: digraph.h:75
~diGraph()
The destructor.
Definition: digraph.h:462
wType minPathWeight(const roundType &rounding, bool ignoreNegLoop=false, int sparseGraph=-1) const
Uses the Floyd-Warshall algorithm or Johnson&#39;s algorithm, depending on the number of edges...
Definition: digraph.h:2128
void DFSfinishTime(Table &tab) const
Computes the DFS finishing time for each vertex.
Definition: digraph.h:932
void addVertex(void)
Adds a vertex.
Definition: digraph.h:511
void DFSfinishTimeRecurrent(Table &tab, int_t vertex, int_t &counter) const
The recurrent procedure for DFSfinishTime.
Definition: digraph.h:844
bool isInfinity() const
Returns true iff the value corresponds to the infinity.
Definition: digraph.h:412
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:1498
wType EdmondsOld() const
An old implementation of the Edmonds algorithm (less efficient).
Definition: digraph.h:1720
void swap(diGraph< wType > &g)
Swaps the data with another graph.
Definition: digraph.h:501
void DFScolorStack(Table &tab, const Color &color, int_t vertex=0) const
A stack version of the recurrent procedure for DFScolor.
Definition: digraph.h:774
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.
Definition: digraph.h:975
int_t nVertices
The number of vertices.
Definition: digraph.h:351
chomp::homology::multitable< int_t > edges
A table with edge target numbers.
Definition: digraph.h:358
friend bool operator==(const diGraph< wType1 > &g1, const diGraph< wType2 > &g2)
Operator == for comparing digraphs.
Definition: digraph.h:470
void setWeight(int_t vertex, int_t i, const wType &weight)
Sets the weight of the given edge.
Definition: digraph.h:555
int_t shortestLoop(int_t origin) const
Computes the length of the shortest loop from the given vertex to itself.
Definition: digraph.h:1406
const wType & getValue() const
Returns the value stored in this object.
Definition: digraph.h:418
int_t countEdges(void) const
Returns the number of edges.
Definition: digraph.h:631
A dummy array of integers that ignores all the assigned values.
Definition: dummyarr.h:46
diGraph()
The default constructor of an empty graph.
Definition: digraph.h:455
void DFScolorRecurrent(Table &tab, const Color &color, int_t vertex=0) const
The recurrent procedure for DFScolor.
Definition: digraph.h:758
A class for representing a positive number with negative values serving as the infinity (used in the ...
Definition: digraph.h:384
An edge with a weight (used by the Edmonds algorithm).
Definition: digraph.h:365
const wType & getWeight(int_t vertex, int_t i) const
Retrieves the weight of the given edge.
Definition: digraph.h:658
chomp::homology::multitable< wType > weights
A table with edge weights.
Definition: digraph.h:361
void removeVertex(void)
Removes the last vertex and all the edges going out from it.
Definition: digraph.h:573
void setInfinity()
Sets the value to the infinity.
Definition: digraph.h:405
void Dijkstra(const roundType &rounding, int_t source, lenTable &len, weightsType &edgeWeights) const
Dijkstra&#39;s algorithm for solving the single-source shortest paths problem if all the edge weights are...
Definition: digraph.h:1413
A dummy class for rounding operations which does not actually do any rounding.
Definition: dummyrnd.h:45
chomp::homology::multitable< int_t > edgeEnds
A table with the offsets of the one-after-the-last edge of each vertex.
Definition: digraph.h:355
int_t vert1
The starting and ending vertices of the edge.
Definition: digraph.h:368
void DFSfinishTimeStack(Table &tab, int_t vertex, int_t &counter) const
A stack version of the recurrent procedure for DFSfinishTime.
Definition: digraph.h:866
wType value
The actual number.
Definition: digraph.h:447
void addEdge(int_t target)
Adds an edge starting at the last vertex.
Definition: digraph.h:520
wType Edmonds() const
Runs the Edmonds algorithm to compute the shortest path that runs through all the vertices of the gra...
Definition: digraph.h:1645
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.
Definition: digraph.h:375
wType Johnson(const roundType &rounding, arrayType &arr, bool setInfinity=true, bool ignoreNegLoop=false) const
Runs Johnson&#39;s algorithm to compute the minimum path weight between any vertices in the graph...
Definition: digraph.h:1956
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:1799
int_t getEdge(int_t vertex, int_t i) const
Retrieves the given edge that leaves the given vertex.
Definition: digraph.h:649
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:1028
void transpose(diGraph< wType1 > &result, bool copyweights=false) const
Creates a transposed graph.
Definition: digraph.h:675
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:1326