chomp/struct/digraph.h

Go to the documentation of this file.

/// @addtogroup struct
/// @{

/////////////////////////////////////////////////////////////////////////////
///
/// @file digraph.h
///
/// This header file contains the definition of a weighted directed graph
/// class and several algorithms on this graph, including some minimal path
/// algorithms with rounding control to compute rigorous results.
///
/// @author Pawel Pilarczyk
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 1997-2013 by Pawel Pilarczyk.
//
// This file is part of the Homology Library.  This library is free software;
// you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation;
// either version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this software; see the file "license.txt".  If not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// Started in January 2006. Last revision: May 29, 2010.


#ifndef _CHOMP_STRUCT_DIGRAPH_H_
#define _CHOMP_STRUCT_DIGRAPH_H_

#include <iostream>
#include <new>
#include <stack>
#include <queue>
#include <set>
#include <memory>
#include <vector>
#include <algorithm>

#include "chomp/struct/multitab.h"
#include "chomp/struct/hashsets.h"
#include "chomp/struct/flatmatr.h"
#include "chomp/struct/bitfield.h"
#include "chomp/struct/bitsets.h"
#include "chomp/struct/fibheap.h"
#include "chomp/struct/autoarray.h"
#include "chomp/system/textfile.h"
#include "chomp/system/timeused.h"

namespace chomp {
namespace homology {


// --------------------------------------------------
// ----------------- DUMMY ROUNDING -----------------
// --------------------------------------------------

/// A dummy class for rounding operations which does not actually do
/// any rounding. Please, use it as a template for your own rounding classes.
template <class numType>
class dummyRounding
{
public:
        /// Adds two numbers with the result rounded downwards.
        static inline numType add_down (const numType &x, const numType &y)
        { return x + y; }

        /// Adds two numbers with the result rounded upwards.
        static inline numType add_up (const numType &x, const numType &y)
        { return x + y; }

        /// Subtracts two numbers with the result rounded downwards.
        static inline numType sub_down (const numType &x, const numType &y)
        { return x - y; }

        /// Subtracts two numbers with the result rounded upwards.
        static inline numType sub_up (const numType &x, const numType &y)
        { return x - y; }

        /// Multiplies two numbers with the result rounded downwards.
        static inline numType mul_down (const numType &x, const numType &y)
        { return x * y; }

        /// Multiplies two numbers with the result rounded upwards.
        static inline numType mul_up (const numType &x, const numType &y)
        { return x * y; }

        /// Divides two numbers with the result rounded downwards.
        static inline numType div_down (const numType &x, const numType &y)
        { return x / y; }

        /// Divides a number by an integer with the result rounded downwards.
        static inline numType div_down (const numType &x, int_t y)
        { return x / y; }

        /// Divides two numbers with the result rounded upwards.
        static inline numType div_up (const numType &x, const numType &y)
        { return x / y; }

private:
}; /* class dummyRounding */


// --------------------------------------------------
// ------------------ DUMMY ARRAY -------------------
// --------------------------------------------------

/// A dummy array of integers that ignores all the assigned values.
class dummyArray
{
public:
        /// The constructor of a dummy array.
        dummyArray () {n = 0;}

        /// Operator [] which returns a reference to a dummy value.
        int_t &operator [] (int_t) {return n;}

private:
        /// A dummy number used as a dump box for assigning values.
        int_t n;

}; /* class dummyArray */


// --------------------------------------------------
// ----------------- DIRECTED GRAPH -----------------
// --------------------------------------------------

// #define DIGRAPH_DEBUG

/// This class defines a directed graph with very limited number of
/// operations, and a few specific algorithms implemented on it, like DFS.
/// The graph can be treated as weighted if necessary.
template <class wType = int>
class diGraph
{
public:
        /// The type of the weight of edges.
        typedef wType weight_type;
        
        /// The default constructor of an empty graph.
        /// Note: The default copy constructor and assignment operator
        /// generated by the compiler are good for copying graphs.
        diGraph ();

        /// The destructor.
        ~diGraph ();

        /// Swaps the data with another graph.
        void swap (diGraph<wType> &g);

        /// Adds a vertex.
        void addVertex (void);

        /// Adds an edge starting at the last vertex.
        /// Note: The range of the target vertex number is not verified.
        void addEdge (int_t target);

        /// Adds an edge from the last vertex to the given one
        /// and sets the weight of this edge.
        void addEdge (int_t target, const wType &weight);

        /// Sets the weight of the given edge.
        void setWeight (int_t vertex, int_t i, const wType &weight);

        /// Sets the weight of the given edge.
        void setWeight (int_t edge, const wType &weight);
        
        /// Sets the weights of all the edges at a time.
        /// The weights are pulled from the table with the [] operator.
        template <class Table>
        void setWeights (const Table &tab);

        /// Removes the last vertex and all the edges going out from it.
        /// This is done in the time O(1).
        void removeVertex (void);

        /// Removes the given vertex and all the edges going out from it,
        /// as well as the edges going towards it.
        /// If requested, the weights in the graph are also updated.
        /// This function might be slow - it is done in the time O(V+E).
        void removeVertex (int_t vertex, bool updateweights = false);

        /// Returns the number of vertices.
        int_t countVertices (void) const;

        /// Returns the number of edges.
        int_t countEdges (void) const;

        /// Counts the number of edges leaving the given vertex.
        int_t countEdges (int_t vertex) const;
        
        /// Retrieves the given edge that leaves the given vertex.
        int_t getEdge (int_t vertex, int_t i) const;

        /// Retrieves the weight of the given edge.
        const wType &getWeight (int_t vertex, int_t i) const;

        /// Retrieves the weight of the given edge.
        const wType &getWeight (int_t edge) const;

        /// Gets the weights of all the edges at a time.
        /// The weights are put into the table with the [] operator.
        template <class Table>
        void getWeights (Table &tab) const;

        /// Fills out a table that represents all the edges of the graph.
        /// The indices of a starting and ending vertex of the n-th edge
        /// are written to "tab [n] [0]" and "tab [n] [1]", respectively.
        template <class Table>
        void writeEdges (Table &tab) const;

        /// Creates a transposed graph.
        template <class wType1>
        void transpose (diGraph<wType1> &result,
                bool copyweights = false) const;

        /// Computes a restriction of the graph to its subgraph. The subgraph
        /// vertices are defined by nonzero entries in the supplied table.
        /// The result must be initially empty.
        template <class Table, class wType1>
        void subgraph (diGraph<wType1> &result, const Table &tab,
                bool copyweights = false) const;

        /// Marks each vertex visited by DFS with the given color,
        /// starting with the given vertex. Runs for one component only.
        /// The initial color in 'tab' must be different than the given one.
        template <class Table, class Color>
        void DFScolor (Table &tab, const Color &color,
                int_t vertex = 0) const;

        /// The recurrent procedure for DFScolor.
        template <class Table, class Color>
        void DFScolorRecurrent (Table &tab, const Color &color,
                int_t vertex = 0) const;

        /// A stack version of the recurrent procedure for DFScolor.
        template <class Table, class Color>
        void DFScolorStack (Table &tab, const Color &color,
                int_t vertex = 0) const;

        /// Computes the DFS finishing time for each vertex.
        /// Note: The time begins with 1, not with 0.
        template <class Table>
        void DFSfinishTime (Table &tab) const;

        /// Computes the DFS forest.
        /// Considers the vertices in the given order.
        /// Saves the numbers of vertices of each tree in 'compVertices',
        /// and keeps the one-beyond-the-end offsets of the trees in the
        /// table 'compEnds'. Records the connections between the trees
        /// in 'scc' (which must be empty when this function is called).
        /// If requested, only those single-vertex trees are counted
        /// which have an edge that loops back to themselves.
        /// Returns the number of trees in the computed forest.
        template <class Table1, class Table2, class Table3>
        int_t DFSforest (const Table1 &ordered, Table2 &compVertices,
                Table3 &compEnds, bool nontrivial = false,
                diGraph<wType> *sccGraph = 0) const;

        /// Computes the length of the shortest nontrivial path
        /// from the given vertex to another one.
        /// The length is measured by counting edges.
        /// Uses a stack version of the BFS algorithm.
        /// Returns the length of the path or 0 if none.
        int_t shortestPath (int_t source, int_t destination) const;

        /// Computes the length of the shortest loop from the given vertex
        /// to itself. The length is measured by counting edges on the way.
        /// Uses a stack version of the BFS algorithm.
        /// Returns the length of the loop or 0 if none.
        int_t shortestLoop (int_t origin) const;

        /// Dijkstra's algorithm for solving the single-source shortest
        /// paths problem if all the edge weights are nonnegative.
        /// The table 'len' is used to store the path lengths during the
        /// computations and contains the final result. A negative value
        /// stands for the infinity (no path to the given vertex).
        /// This is a special version that uses the given edge weights
        /// instead of the weights contained in the definition of the graph.
        template <class lenTable, class weightsType, class roundType>
        void Dijkstra (const roundType &rounding, int_t source,
                lenTable &len, weightsType &edgeWeights) const;

        /// Dijkstra's algorithm running on the graph's own weights.
        template <class lenTable, class roundType>
        void Dijkstra (const roundType &rounding, int_t source,
                lenTable &len) const;

        /// The above algorithm without rounding control.
        template <class lenTable>
        void Dijkstra (int_t source, lenTable &len) const;

        /// Runs the Bellman-Ford algorithm which computes the single-source
        /// shortest paths in a weighted directed graph, where some edge
        /// weights may be negative. Runs in O(V*E).
        /// The table 'len' is used to store the path lengths during the
        /// computations and contains the final result. The number for
        /// infinity is set to indicate unreachable vertices.
        /// The table with predecessors allows to retrieve shortest paths;
        /// this must be a pointer to an array-like structure, e.g., int **.
        /// To ignore this data, use an object of the 'dummyArray' class.
        /// Returns true if successful, false if a negative cycle is found.
        template <class lenTable, class predTable, class roundType>
        bool BellmanFord (const roundType &rounding, int_t source,
                lenTable &len, wType *infinity, predTable pred) const;

        /// The above algorithm without rounding control.
        template <class lenTable, class predTable>
        bool BellmanFord (int_t source, lenTable &len, wType *infinity,
                predTable pred) const;

        /// Runs the Bellman-Ford algorithm (see above) without storing the
        /// distances, only returns the information about the existence
        /// of a negative-weight cycle.
        template <class roundType>
        bool BellmanFord (const roundType &rounding, int_t source) const;

        /// The above algorithm without rounding control.
        bool BellmanFord (int_t source) const;

        /// Runs the Edmonds algorithm to compute the shortest path
        /// that runs through all the vertices of the graph.
        /// Computation time: O (n log n). The length of the path
        /// is measured as the sum of the weights of the edges.
        /// The path does not contain any loops.
        /// The graph should be strongly connected.
        wType Edmonds () const;

        /// An old implementation of the Edmonds algorithm (less efficient).
        wType EdmondsOld () const;

        /// Runs the Floyd-Warshall algorithm to compute the shortest
        /// paths between all pairs of vertices in the graph.
        /// The position [i] [j] of the array contains
        /// the length of the shortest path from vertex i to vertex j.
        /// Provides a rigorous lower bound in interval arithmetic,
        /// provided that intervals are compared with "<" and "<="
        /// by comparing their lower ends only.
        /// If "setInfinity" is "true", then computes a value that serves
        /// as the infinity, fills in the corresponding entries in "arr",
        /// and returns this value.
        /// Otherwise, returns the length of the shortest path. In this
        /// case, arr [i] [j] is undefined if there is no path i -> j.
        /// Throws an error message if a negative loop is found,
        /// unless "ignoreNegLoop" is set to "true".
        template <class arrayType, class roundType>
        wType FloydWarshall (const roundType &rounding, arrayType &arr,
                bool setInfinity = true, bool ignoreNegLoop = false) const;

        /// The above algorithm without rounding control.
        template <class arrayType>
        wType FloydWarshall (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. The time complexity of this
        /// algorithm is essentially O (V^2 log V + VE log V),
        /// which is better than the complexity of the Warshall-Floyd
        /// algorithm for sparse graphs, that is, graphs in which the number
        /// of edges E is of order smaller than V^2.
        /// The meaning of the arguments and the returned value is the same
        /// as in 'FloydWarshall'.
        template <class arrayType, class roundType>
        wType Johnson (const roundType &rounding, arrayType &arr,
                bool setInfinity = true, bool ignoreNegLoop = false) const;

        /// The above algorithm without rounding control.
        template <class arrayType>
        wType Johnson (arrayType &arr, bool setInfinity = true,
                bool ignoreNegLoop = false) const;

        /// Uses the Floyd-Warshall algorithm or Johnson's algorithm,
        /// depending on the number of edges, to compute the minimum
        /// path weight between any vertices in the graph.
        /// Throws an error message if a negative loop exists in the graph,
        /// unless "ignoreNegLoop" is set to "true".
        /// To force the use of Johnson's algorithm, set "sparseGraph" to 1,
        /// to force the use of Warshall-Floyd, set "sparseGraph" to 0,
        /// otherwise it will be determined heuristically which algorithm
        /// should be used.
        template <class roundType>
        wType minPathWeight (const roundType &rounding,
                bool ignoreNegLoop = false, int sparseGraph = -1) const;

        /// The above algorithm without rounding control.
        wType minPathWeight (bool ignoreNegLoop = false,
                int sparseGraph = -1) const;

        /// Runs the Karp algorithm for each strongly connected component
        /// of the graph and returns the minimum mean cycle weight,
        /// which can be negative.
        /// As a byproduct, saves the transposed graph, if requested to.
        wType minMeanCycleWeight (diGraph<wType> *transposed = 0) const;

        /// A version of the above function modified for the purpose
        /// of interval arithmetic to provide the correct lower bound
        /// for the minimum mean cycle weight in a graph.
        /// This specialization is necessary, because of the subtraction
        /// operation used in Karp's algorithm. Therefore, upper and lower
        /// bounds for the minimum path progression weights must be computed
        /// independently.
        /// The intervals are compared by comparing their lower bounds only.
        template <class roundType>
        wType minMeanCycleWeight (const roundType &rounding,
                diGraph<wType> *transposed) const;

        /// Runs an algorithm based on Karp's idea to compute the minimum
        /// mean path weight for paths starting at any of the given
        /// n vertices and of length not exceeding the number of vertices
        /// in the graph.
        /// Returns 0 if no path starts at any of the vertices.
        template <class arrayType, class roundType>
        wType minMeanPathWeight (const roundType &rounding,
                const arrayType &starting, int_t n) const;

        /// The above algorithm without rounding control.
        template <class arrayType>
        wType minMeanPathWeight (const arrayType &starting, int_t n) const;

        /// Operator == for comparing digraphs. No isomorphism check, just
        /// comparing with the same order of vertices. Ignores weights.
        template <class wType1, class wType2>
        friend bool operator == (const diGraph<wType1> &g1,
                const diGraph<wType2> &g2);

        /// Outputs the graph to a text stream in a human-readable format.
        template <class outType>
        outType &show (outType &out, bool showWeights = false) const;

protected:
        /// The number of vertices.
        int_t nVertices;

        /// A table with the offsets of the one-after-the-last edge
        /// of each vertex.
        multitable<int_t> edgeEnds;

        /// A table with edge target numbers.
        multitable<int_t> edges;

        /// A table with edge weights.
        multitable<wType> weights;

private:
        /// The recurrent procedure for DFSfinishTime.
        template <class Table>
        void DFSfinishTimeRecurrent (Table &tab, int_t vertex,
                int_t &counter) const;

        /// A stack version of the recurrent procedure for DFSfinishTime.
        template <class Table>
        void DFSfinishTimeStack (Table &tab, int_t vertex,
                int_t &counter) const;

        /// The recurrent procedure for DFSforest.
        /// Returns true iff there is a loop within the tree found.
        template <class Table1, class Table2>
        bool DFSforestRecurrent (Table1 &tab, Table1 &ntab, int_t vertex,
                int_t treeNumber, int_t countTrees, Table2 &compVertices,
                int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded)
                const;

        /// A stack version of the recurrent procedure for DFSforest.
        template <class Table1, class Table2>
        bool DFSforestStack (Table1 &tab, Table1 &ntab, int_t vertex,
                int_t treeNumber, int_t countTrees, Table2 &compVertices,
                int_t &curVertex, diGraph *sccGraph, int_t *sccEdgeAdded)
                const;

        /// An edge with a weight (used by the Edmonds algorithm).
        struct edgeTriple
        {
                /// The starting and ending vertices of the edge.
                int_t vert1;
                int_t vert2;
                
                /// The weight of the edge.
                wType weight;

                /// The < operator for comparing the weights of edges.
                friend bool operator < (const edgeTriple &x,
                        const edgeTriple &y)
                {
                        return (x. weight < y. weight);
                }
        };

        /// A class for representing a positive number with negative values
        /// serving as the infinity (used in the Dijkstra algorithm).
        class posWeight
        {
        public:
                /// The default constructor.
                posWeight ()
                {
                        value = 0;
                        return;
                }

                /// An optional constructor.
                explicit posWeight (const wType &_value)
                {
                        if (_value < 0)
                                value = 0;
                        else
                                value = _value;
                        return;
                }

                /// Sets the value to the infinity.
                void setInfinity ()
                {
                        value = -1;
                        return;
                }

                /// Returns true iff the value corresponds to the infinity.
                bool isInfinity () const
                {
                        return (value < 0);
                }

                /// Returns the value stored in this object.
                const wType &getValue () const
                {
                        return value;
                }

                /// The < operator for comparing the numbers.
                friend bool operator < (const posWeight &x,
                        const posWeight &y)
                {
                        if (y. isInfinity ())
                                return !(x. isInfinity ());
                        else if (x. isInfinity ())
                                return false;
                        return (x. value < y. value);
                }

                /// The operator for showing the number to the output stream.
                friend std::ostream &operator << (std::ostream &out,
                        const posWeight &x)
                {
                        if (x. isInfinity ())
                                out << "+oo";
                        else
                                out << x. getValue ();
                        return out;
                }

        private:
                /// The actual number.
                wType value;
        };

}; /* class diGraph */

// --------------------------------------------------

template <class wType>
inline diGraph<wType>::diGraph (): nVertices (0),
        edgeEnds (1024), edges (4096), weights (4096)
{
        return;
} /* diGraph::diGraph */

template <class wType>
inline diGraph<wType>::~diGraph ()
{
        return;
} /* diGraph::~diGraph */

// --------------------------------------------------

template <class wType1, class wType2>
inline bool operator == (const diGraph<wType1> &g1,
        const diGraph<wType2> &g2)
{
        if (g1. nVertices != g2. nVertices)
                return false;
        if (!g1. nVertices)
                return true;
        for (int_t i = 0; i < g1. nVertices; ++ i)
        {
                if (g1. edgeEnds [i] != g2. edgeEnds [i])
                        return false;
        }
        int_t nEdges = g1. edgeEnds [g1. nVertices - 1];
        for (int_t i = 0; i < nEdges; ++ i)
        {
                if (g1. edges [i] != g2. edges [i])
                        return false;
        }
        return true;
} /* operator == */

template <class wType1, class wType2>
inline bool operator != (const diGraph<wType1> &g1,
        const diGraph<wType2> &g2)
{
        return !(g1 == g2);
} /* operator != */

// --------------------------------------------------

template <class wType>
inline void diGraph<wType>::swap (diGraph<wType> &g)
{
        std::swap (nVertices, g. nVertices);
        edgeEnds. swap (g. edgeEnds);
        edges. swap (g. edges);
        weights. swap (g. weights);
        return;
} /* diGraph::swap */

template <class wType>
inline void diGraph<wType>::addVertex (void)
{
        edgeEnds [nVertices] = nVertices ? edgeEnds [nVertices - 1] :
                static_cast<int_t> (0);
        ++ nVertices;
        return;
} /* diGraph::addVertex */

template <class wType>
inline void diGraph<wType>::addEdge (int_t target)
{
        if (!nVertices)
                throw "Trying to add an edge to an empty graph.";
//      if (target >= nVertices)
//              throw "Trying to add an edge to a nonexistent vertex.";
        if (target < 0)
                throw "Trying to add an edge to a negative vertex.";
        int_t &offset = edgeEnds [nVertices - 1];
        if (offset + 1 <= 0)
                throw "Too many edges in a diGraph (limit = 2,147,483,647).";
        edges [offset] = target;
        ++ offset;
        return;
} /* diGraph::addEdge */

template <class wType>
inline void diGraph<wType>::addEdge (int_t target, const wType &weight)
{
        if (!nVertices)
                throw "Trying to add an edge to an empty graph.";
//      if (target >= nVertices)
//              throw "Trying to add an edge to a nonexistent vertex.";
        if (target < 0)
                throw "Trying to add an edge to a negative vertex.";
        int_t &offset = edgeEnds [nVertices - 1];
        if (offset + 1 <= 0)
                throw "Too many edges in a diGraph (limit = 2,147,483,647).";
        edges [offset] = target;
        weights [offset] = weight;
        ++ offset;
        return;
} /* diGraph::addEdge */

template <class wType>
inline void diGraph<wType>::setWeight (int_t vertex, int_t i,
        const wType &weight)
{
        if (!vertex)
                weights [i] = weight;
        else
                weights [edgeEnds [vertex - 1] + i] = weight;
        return;
} /* diGraph::setWeight */

template <class wType>
inline void diGraph<wType>::setWeight (int_t edge, const wType &weight)
{
        weights [edge] = weight;
        return;
} /* diGraph::setWeight */

template <class wType> template <class Table>
inline void diGraph<wType>::setWeights (const Table &tab)
{
        if (!nVertices)
                return;
        int_t nEdges = edgeEnds [nVertices - 1];
        for (int_t i = 0; i < nEdges; ++ i)
                weights [i] = tab [i];
        return;
} /* diGraph::setWeights */

template <class wType>
inline void diGraph<wType>::removeVertex (void)
{
        if (!nVertices)
                throw "Trying to remove a vertex from the empty graph.";
        -- nVertices;
        return;
} /* diGraph::removeVertex */

template <class wType>
inline void diGraph<wType>::removeVertex (int_t vertex, bool updateweights)
{
        // make sure that the vertex number is within the scope
        if ((vertex < 0) || (vertex >= nVertices))
                throw "Trying to remove a vertex that is not in the graph.";

        // remove edges that begin or end at the given vertex
        int_t curEdge = 0;
        int_t newEdge = 0;
        int_t skipped = 0;
        for (int_t v = 0; v < nVertices; ++ v)
        {
                // skip the edges that begin at the given vertex
                if (!skipped && (v == vertex))
                {
                        curEdge = edgeEnds [v];
                        ++ skipped;
                        continue;
                }

                // skip the edges that point to the given vertex
                int_t maxEdge = edgeEnds [v];
                for (; curEdge < maxEdge; ++ curEdge)
                {
                        if (edges [curEdge] == vertex)
                                continue;
                        int_t target = edges [curEdge];
                        edges [newEdge] = (target < vertex) ? target :
                                (target - 1);
                        if (updateweights)
                                weights [newEdge] = weights [curEdge];
                        ++ newEdge;
                }
                edgeEnds [v - skipped] = newEdge;
        }

        // decrease the number of vertices
        nVertices -= skipped;

        return;
} /* diGraph::removeVertex */

template <class wType>
inline int_t diGraph<wType>::countVertices (void) const
{
        return nVertices;
} /* diGraph::countVertices */

template <class wType>
inline int_t diGraph<wType>::countEdges (void) const
{
        if (!nVertices)
                return 0;
        else
                return edgeEnds [nVertices - 1];
} /* diGraph::countEdges */

template <class wType>
inline int_t diGraph<wType>::countEdges (int_t vertex) const
{
        if (!vertex)
                return edgeEnds [0];
        else
                return edgeEnds [vertex] - edgeEnds [vertex - 1];
} /* diGraph::countEdges */

template <class wType>
inline int_t diGraph<wType>::getEdge (int_t vertex, int_t i) const
{
        if (!vertex)
                return edges [i];
        else
                return edges [edgeEnds [vertex - 1] + i];
} /* diGraph::getEdge */

template <class wType>
inline const wType &diGraph<wType>::getWeight (int_t vertex, int_t i) const
{
        if (!vertex)
                return weights [i];
        else
                return weights [edgeEnds [vertex - 1] + i];
} /* diGraph::getWeight */

template <class wType>
inline const wType &diGraph<wType>::getWeight (int_t edge) const
{
        return weights [edge];
} /* diGraph::getWeight */

template <class wType> template <class Table>
inline void diGraph<wType>::getWeights (Table &tab) const
{
        if (!nVertices)
                return;
        int_t nEdges = edgeEnds [nVertices - 1];
        for (int_t i = 0; i < nEdges; ++ i)
                tab [i] = weights [i];
        return;
} /* diGraph::getWeights */

template <class wType> template <class Table>
inline void diGraph<wType>::writeEdges (Table &tab) const
{
        int_t curEdge = 0;
        for (int_t curVertex = 0; curVertex < nVertices; ++ curVertex)
        {
                int_t maxEdge = edgeEnds [curVertex];
                while (curEdge < maxEdge)
                {
                        tab [curEdge] [0] = curVertex;
                        tab [curEdge] [1] = edges [curEdge];
                        ++ curEdge;
                }
        }
        return;
} /* diGraph::writeEdges */

template <class wType> template <class wType1>
inline void diGraph<wType>::transpose (diGraph<wType1> &result,
        bool copyweights) const
{
        // prepare the resulting graph
        result. nVertices = nVertices;
        if (!nVertices)
                return;

        // compute the initial offsets for the edge numbers
        for (int_t i = 0; i < nVertices; ++ i)
                result. edgeEnds [i] = 0;
        int_t nEdges = edgeEnds [nVertices - 1];
        for (int_t i = 0; i < nEdges; ++ i)
        {
                if (edges [i] < nVertices - 1)
                        ++ result. edgeEnds [edges [i] + 1];
        }
        for (int_t i = 2; i < nVertices; ++ i)
                result. edgeEnds [i] += result. edgeEnds [i - 1];

        // compute the reversed edges
        int_t curEdge = 0;
        for (int_t i = 0; i < nVertices; ++ i)
        {
                for (; curEdge < edgeEnds [i]; ++ curEdge)
                {
                        int_t j = edges [curEdge];
                        int_t &offset = result. edgeEnds [j];
                        result. edges [offset] = i;
                        if (copyweights)
                                result. weights [offset] = weights [curEdge];
                        ++ offset;
                }
        }
        return;
} /* diGraph::transpose */

template <class wType> template <class Table, class wType1>
inline void diGraph<wType>::subgraph (diGraph<wType1> &g,
        const Table &tab, bool copyweights) const
{
        // compute the new numbers of vertices that remain in the graph
        int_t *numbers = new int_t [nVertices];
        int_t curNumber = 0;
        for (int_t i = 0; i < nVertices; ++ i)
        {
                if (tab [i])
                        numbers [i] = curNumber ++;
                else
                        numbers [i] = -1;
        }

        // copy the edges from the old graph to the new one
        for (int_t i = 0; i < nVertices; ++ i)
        {
                if (numbers [i] < 0)
                        continue;
                g. addVertex ();
                int_t firstEdge = i ? edgeEnds [i - 1] :
                        static_cast<int_t> (0);
                int_t endEdge = edgeEnds [i];
                for (int_t j = firstEdge; j < endEdge; ++ j)
                {
                        int_t edgeEnd = edges [j];
                        if (numbers [edgeEnd] >= 0)
                        {
                                if (copyweights)
                                        g. addEdge (numbers [edgeEnd],
                                                weights [j]);
                                else
                                        g. addEdge (numbers [edgeEnd]);
                        }
                }
        }

        // clean up memory and exit
        delete [] numbers;
        return;
} /* diGraph::subgraph */

// --------------------------------------------------

template <class wType> template <class Table, class Color>
inline void diGraph<wType>::DFScolorRecurrent (Table &tab,
        const Color &color, int_t vertex) const
{
        tab [vertex] = color;
        int_t maxEdge = edgeEnds [vertex];
        for (int_t i = vertex ? edgeEnds [vertex - 1] :
                static_cast<int_t> (0); i < maxEdge; ++ i)
        {
                int_t next = edges [i];
                if (tab [next] != color)
                        DFScolorRecurrent (tab, color, next);
        }
        return;
} /* diGraph::DFScolorRecurrent */

template <class wType> template <class Table, class Color>
inline void diGraph<wType>::DFScolorStack (Table &tab, const Color &color,
        int_t vertex) const
{
        // prepare stacks for the recursion
        std::stack<int_t> s_vertex;
        std::stack<int_t> s_edge;
        std::stack<int_t> s_maxedge;

        // mark the current vertex as visited
        tab [vertex] = color;

        // determine the edges to be visited
        int_t edge = vertex ? edgeEnds [vertex - 1] :
                static_cast<int_t> (0);
        int_t maxedge = edgeEnds [vertex];

        while (1)
        {
                // return to the previous recursion level
                // if all the edges have been followed
                if (edge >= maxedge)
                {
                        // return if this is the initial recursion level
                        if (s_vertex. empty ())
                                return;

                        // restore the variables from the previous level
                        vertex = s_vertex. top ();
                        s_vertex. pop ();
                        edge = s_edge. top ();
                        s_edge. pop ();
                        maxedge = s_maxedge. top ();
                        s_maxedge. pop ();
                        continue;
                }

                // go to the deeper recursion level if possible
                int_t next = edges [edge ++];
                if (tab [next] != color)
                {
                        // store the previous variables at the stacks
                        s_vertex. push (vertex);
                        s_edge. push (edge);
                        s_maxedge. push (maxedge);

                        // set the new vertex
                        vertex = next;
                        
                        // mark the new vertex as visited
                        tab [vertex] = color;
                        
                        // determine the edges to be visited
                        edge = vertex ? edgeEnds [vertex - 1] :
                                static_cast<int_t> (0);
                        maxedge = edgeEnds [vertex];
                }
        }
} /* diGraph::DFScolorStack */

template <class wType> template <class Table, class Color>
inline void diGraph<wType>::DFScolor (Table &tab, const Color &color,
        int_t vertex) const
{
        DFScolorStack (tab, color, vertex);
        return;
} /* diGraph::DFScolor */

// --------------------------------------------------

template <class wType> template <class Table>
inline void diGraph<wType>::DFSfinishTimeRecurrent (Table &tab,
        int_t vertex, int_t &counter) const
{
        // mark the current vertex as visited
        tab [vertex] = -1;

        // call DFS for the other vertices
        for (int_t edge = vertex ? edgeEnds [vertex - 1] :
                static_cast<int_t> (0);
                edge < edgeEnds [vertex]; ++ edge)
        {
                int_t next = edges [edge];
                if (!tab [next])
                        DFSfinishTimeRecurrent (tab, next, counter);
        }

        // record the finishing time for the current vertex and return
        tab [vertex] = ++ counter;
        return;
} /* diGraph::DFSfinishTimeRecurrent */

template <class wType> template <class Table>
inline void diGraph<wType>::DFSfinishTimeStack (Table &tab, int_t vertex,
        int_t &counter) const
{
        // prepare stacks for the recursion
        std::stack<int_t> s_vertex;
        std::stack<int_t> s_edge;
        std::stack<int_t> s_maxedge;

        // mark the current vertex as visited
        tab [vertex] = -1;

        // determine the edges to be visited
        int_t edge = vertex ? edgeEnds [vertex - 1] :
                static_cast<int_t> (0);
        int_t maxedge = edgeEnds [vertex];

        while (1)
        {
                // return to the previous recursion level
                // if all the edges have been followed
                if (edge >= maxedge)
                {
                        // record the finishing time
                        // for the current vertex
                        tab [vertex] = ++ counter;

                        // return if this is the initial recursion level
                        if (s_vertex. empty ())
                                return;

                        // restore the variables from the previous level
                        vertex = s_vertex. top ();
                        s_vertex. pop ();
                        edge = s_edge. top ();
                        s_edge. pop ();
                        maxedge = s_maxedge. top ();
                        s_maxedge. pop ();
                        continue;
                }

                // go to the deeper recursion level if possible
                int_t next = edges [edge ++];
                if (!tab [next])
                {
                        // store the previous variables at the stacks
                        s_vertex. push (vertex);
                        s_edge. push (edge);
                        s_maxedge. push (maxedge);

                        // set the new vertex
                        vertex = next;
                        
                        // mark the new vertex as visited
                        tab [vertex] = -1;
                        
                        // determine the edges to be visited
                        edge = vertex ? edgeEnds [vertex - 1] :
                                static_cast<int_t> (0);
                        maxedge = edgeEnds [vertex];
                }
        }

        return;
} /* diGraph::DFSfinishTimeStack */

template <class wType> template <class Table>
inline void diGraph<wType>::DFSfinishTime (Table &tab) const
{
        // initialize the table and the counter
        for (int_t i = 0; i < nVertices; ++ i)
                tab [i] = 0;
        int_t counter = 0;

        // compute the finishing time for each tree in the DFS forest
        for (int_t i = 0; i < nVertices; ++ i)
        {
                if (!tab [i])
                        DFSfinishTimeStack (tab, i, counter);
        }

        #ifdef DIGRAPH_DEBUG
        int_t *tabdebug = new int_t [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
                tabdebug [i] = 0;
        int_t counterdebug = 0;
        for (int_t i = 0; i < nVertices; ++ i)
                if (!tabdebug [i])
                        DFSfinishTimeRecurrent (tabdebug, i, counterdebug);
        if (counter != counterdebug)
                throw "DFSfinishTime: Wrong counter.";
        for (int_t i = 0; i < nVertices; ++ i)
        {
                if (tab [i] != tabdebug [i])
                {
                        sbug << "\nDFSfinishTime error: tabRec [" << i <<
                                "] = " << tab [i] << ", tabStack [" << i <<
                                "] = " << tabdebug [i] << ".\n";
                        throw "DFSfinishTime: Wrong numbers.";
                }
        }
        sbug << "DEBUG: DFSfinishTime OK. ";
        #endif // DIGRAPH_DEBUG
        return;
} /* diGraph::DFSfinishTime */

// --------------------------------------------------

template <class wType> template <class Table1, class Table2>
inline bool diGraph<wType>::DFSforestRecurrent (Table1 &tab, Table1 &ntab,
        int_t vertex, int_t treeNumber, int_t countTrees,
        Table2 &compVertices, int_t &curVertex,
        diGraph<wType> *sccGraph, int_t *sccEdgeAdded) const
{
        // add the vertex to the tree
        compVertices [curVertex ++] = vertex;

        // mark the vertex as belonging to the current tree
        tab [vertex] = treeNumber;
//      if (sccGraph)
//              ntab [treeNumber - 1] = countTrees;

        // build the tree recursively or record connections
        bool loop = false;
        for (int_t edge = vertex ? edgeEnds [vertex - 1] :
                static_cast<int_t> (0);
                edge < edgeEnds [vertex]; ++ edge)
        {
                int_t next = edges [edge];
                if (!tab [next])
                        loop |= DFSforestRecurrent (tab, ntab, next,
                                treeNumber, countTrees, compVertices,
                                curVertex, sccGraph, sccEdgeAdded);
                else if (tab [next] == treeNumber)
                {
                        if (sccGraph)
                        {
                                int_t target = ntab [treeNumber - 1];
                                if (sccEdgeAdded [target] != treeNumber)
                                {
                                        sccGraph -> addEdge (target);
                                        sccEdgeAdded [target] = treeNumber;
                                }
                        }
                        loop = true;
                }
                else if (sccGraph)
                {
                        int_t target = ntab [tab [next] - 1];
                        if ((target >= 0) &&
                                (sccEdgeAdded [target] != treeNumber))
                        {
                                sccGraph -> addEdge (target);
                                sccEdgeAdded [target] = treeNumber;
                        }
                }
        }

        return loop;
} /* diGraph::DFSforestRecurrent */

template <class wType> template <class Table1, class Table2>
inline bool diGraph<wType>::DFSforestStack (Table1 &tab, Table1 &ntab,
        int_t vertex, int_t treeNumber, int_t countTrees,
        Table2 &compVertices, int_t &curVertex,
        diGraph<wType> *sccGraph, int_t *sccEdgeAdded) const
{
        // prepare stacks for the recursion
        std::stack<int_t> s_vertex;
        std::stack<int_t> s_edge;
        std::stack<int_t> s_maxedge;
        std::stack<bool> s_loop;

        // add the vertex to the tree
        compVertices [curVertex ++] = vertex;

        // mark the vertex as belonging to the current tree
        tab [vertex] = treeNumber;
//      if (sccGraph)
//              ntab [vertex] = countTrees;

        // build the tree recursively or record connections
        bool loop = false;
        int_t edge = vertex ? edgeEnds [vertex - 1] :
                static_cast<int_t> (0);
        int_t maxedge = edgeEnds [vertex];
        while (1)
        {
                // return to the previous recursion level
                // if all the edges have been followed
                if (edge >= maxedge)
                {
                        // return if this is the initial recursion level
                        if (s_vertex. empty ())
                                return loop;

                        // restore the variables from the previous level
                        vertex = s_vertex. top ();
                        s_vertex. pop ();
                        edge = s_edge. top ();
                        s_edge. pop ();
                        maxedge = s_maxedge. top ();
                        s_maxedge. pop ();
                        loop |= s_loop. top ();
                        s_loop. pop ();
                        continue;
                }

                // go to the deeper recursion level if possible
                int_t next = edges [edge ++];
                if (!tab [next])
                {
                        // store the previous variables at the stacks
                        s_vertex. push (vertex);
                        s_edge. push (edge);
                        s_maxedge. push (maxedge);
                        s_loop. push (loop);

                        // set the new vertex
                        vertex = next;
                        
                        // add the vertex to the tree
                        compVertices [curVertex ++] = vertex;

                        // mark the vertex as belonging to the current tree
                        tab [vertex] = treeNumber;

                        // determine the edges to be visited
                        loop = false;
                        edge = vertex ? edgeEnds [vertex - 1] :
                                static_cast<int_t> (0);
                        maxedge = edgeEnds [vertex];
                }
                else if (tab [next] == treeNumber)
                {
                        if (sccGraph)
                        {
                                int_t target = ntab [treeNumber - 1];
                                if (sccEdgeAdded [target] != treeNumber)
                                {
                                        sccGraph -> addEdge (target);
                                        sccEdgeAdded [target] = treeNumber;
                                }
                        }
                        loop = true;
                }
                else if (sccGraph)
                {
                        int_t target = ntab [tab [next] - 1];
                        if ((target >= 0) &&
                                (sccEdgeAdded [target] != treeNumber))
                        {
                                sccGraph -> addEdge (target);
                                sccEdgeAdded [target] = treeNumber;
                        }
                }
        }

        return loop;
} /* diGraph::DFSforestStack */

template <class wType> template <class Table1, class Table2, class Table3>
inline int_t diGraph<wType>::DFSforest (const Table1 &ordered,
        Table2 &compVertices, Table3 &compEnds, bool nontrivial,
        diGraph<wType> *sccGraph) const
{
        // prepare a table to record the numbers of DFS trees
        // to which the vertices belong (the tree numbers begin with 1)
        int_t *tab = new int_t [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
                tab [i] = 0;

        // prepare a table to record the numbers of nontrivial trees
        // that correspond to the trees in 'tab' (these numbers begin with 0)
        int_t *ntab = new int_t [nVertices];

        // prepare a table to record the numbers of edges already in the
        // scc graph; "sccEdgeAdded [n] = m" indicates that the edge
        // m -> n has been added to the scc graph
        int_t *sccEdgeAdded = sccGraph ? new int_t [nVertices] :
                static_cast<int_t *> (0);
        if (sccGraph)
        {
                for (int_t n = 0; n < nVertices; ++ n)
                        sccEdgeAdded [n] = -1;
        }

        // prepare the official DFS tree number
        int_t treeNumber = 0;

        // prepare the data for keeping the nontrivial trees information
        int_t countTrees = 0;
        int_t curVertex = 0;

        // compute the DFS trees and connections between them
        for (int_t i = 0; i < nVertices; ++ i)
        {
                // take the next vertex
                int_t vertex = ordered [i];

                // if the vertex already belongs to some tree, skip it
                if (tab [vertex])
                        continue;

                // add a vertex corresponding to the component
                if (sccGraph)
                        sccGraph -> addVertex ();

                // remember the previous vertex number
                int_t prevVertex = curVertex;

                // mark the entire component and record connections graph
                if (sccGraph)
                        ntab [treeNumber] = countTrees;
                ++ treeNumber;
                bool loop = DFSforestStack (tab, ntab, vertex,
                        treeNumber, countTrees, compVertices,
                        curVertex, sccGraph, sccEdgeAdded);

                // update the index bound for the vertex list
                compEnds [countTrees ++] = curVertex;

                // remove the component if it is trivial
                if (nontrivial && !loop)
                {
                        -- countTrees;
                        curVertex = prevVertex;
                        if (sccGraph)
                        {
                                ntab [treeNumber - 1] = -1;
                                sccGraph -> removeVertex ();
                        }
                }
        }

        #ifdef DIGRAPH_DEBUG
        diGraph<wType> *sccGraphdebug = 0;
        if (sccGraph)
                sccGraphdebug = new diGraph<wType>;
        // prepare a table to record the numbers of DFS trees
        // to which the vertices belong (the tree numbers begin with 1)
        int_t *tabdebug = new int_t [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
                tabdebug [i] = 0;

        // prepare a table to record the numbers of nontrivial trees
        // to which the vertices belong (the tree numbers begin with 0)
        int_t *ntabdebug = new int_t [nVertices];

        // prepare a table to record the numbers of vertices from which
        // edges were added to the scc graph
        int_t *sccEdgeAddeddebug = sccGraph ? new int_t [nVertices] :
                static_cast<int_t> (0);
        if (sccGraph)
        {
                for (int_t n = 0; n < nVertices; ++ n)
                        sccEdgeAddeddebug [n] = -1;
        }
        // prepare the official DFS tree number
        int_t treeNumberdebug = 0;

        // prepare the data for keeping the nontrivial trees information
        int_t countTreesdebug = 0;
        int_t curVertexdebug = 0;

        int_t *compVerticesdebug = new int_t [nVertices];
        int_t *compEndsdebug = new int_t [nVertices];
        
        // compute the DFS trees and connections between them
        for (int_t i = 0; i < nVertices; ++ i)
        {
                // take the next vertex
                int_t vertex = ordered [i];

                // if the vertex already belongs to some tree, skip it
                if (tabdebug [vertex])
                        continue;

                // add a vertex corresponding to the component
                if (sccGraphdebug)
                        sccGraphdebug -> addVertex ();

                // remember the previous vertex number
                int_t prevVertex = curVertexdebug;

                // mark the entire component and record connections graph
                if (sccGraphdebug)
                        ntabdebug [treeNumberdebug] = countTreesdebug;
                ++ treeNumberdebug;
                bool loop = DFSforestRecurrent (tabdebug, ntabdebug, vertex,
                        treeNumberdebug, countTreesdebug, compVerticesdebug,
                        curVertexdebug, sccGraphdebug, sccEdgeAddeddebug);

                // update the index bound for the vertex list
                compEndsdebug [countTreesdebug ++] = curVertexdebug;

                // remove the component if it is trivial
                if (nontrivial && !loop)
                {
                        -- countTreesdebug;
                        curVertexdebug = prevVertex;
                        if (sccGraphdebug)
                        {
                                ntabdebug [treeNumberdebug - 1] = -1;
                                sccGraphdebug -> removeVertex ();
                        }
                }
        }
        if (countTrees != countTreesdebug)
                throw "DFSforest: Wrong countTrees.";
        for (int_t i = 0; i < countTrees; ++ i)
                if (compEnds [i] != compEndsdebug [i])
                        throw "DFSforest: Wrong compEnds.";
        for (int_t i = 0; i < compEndsdebug [countTrees - 1]; ++ i)
                if (compVertices [i] != compVerticesdebug [i])
                        throw "DFSforest: Wrong vertices.";
        if (curVertex != curVertexdebug)
                throw "DFSforest: Wrong curVertex.";
        for (int_t i = 0; i < nVertices; ++ i)
                if (tab [i] != tabdebug [i])
                        throw "DFSforest: Wrong tab.";
        if (sccGraph)
        {
                for (int_t i = 0; i < nVertices; ++ i)
                        if (ntab [i] != ntabdebug [i])
                                throw "DFSforest: Wrong ntab.";
                if (*sccGraph != *sccGraphdebug)
                        throw "DFSforest: Wrong graph.";
        }
        if (sccEdgeAdded)
        {
                for (int_t i = 0; i < nVertices; ++ i)
                        if (sccEdgeAdded [i] != sccEdgeAddeddebug [i])
                                throw "DFSforest: Wrong sccEdgeAdded.";
        }
        if (treeNumber != treeNumberdebug)
                throw "DFSforest: Wrong treeNumber.";
        sbug << "DEBUG: DFSforest OK. ";
        if (!sccGraph)
                sbug << "(Graphs not compared.) ";
        delete [] compVerticesdebug;
        delete [] compEndsdebug;
        if (sccGraphdebug)
                delete sccGraphdebug;
        delete [] ntabdebug;
        delete [] tabdebug;
        if (sccEdgeAddeddebug)
                delete [] sccEdgeAddeddebug;
        #endif // DIGRAPH_DEBUG

        if (sccEdgeAdded)
                delete [] sccEdgeAdded;
        delete [] ntab;
        delete [] tab;
        return countTrees;
} /* diGraph::DFSforest */

template <class wType>
inline int_t diGraph<wType>::shortestPath (int_t source, int_t destination)
        const
{
        // make sure that the given vertex is present in the graph
        if ((source < 0) || (source >= nVertices) ||
                (destination < 0) || (destination >= nVertices))
        {
                throw "diGraph - shortest path: Wrong vertex number.";
        }

        // prepare an array of bits to store the information
        // on whether the given vertices have been visited or not
        BitField visited;
        visited. allocate (nVertices);
        visited. clearall (nVertices);

        // prepare queues for the BFS algorithm
        std::queue<int_t> q_vertex;
        std::queue<int_t> q_depth;

        // set the initial vertex
        int_t vertex = source;
        int_t depth = 0;

        while (1)
        {
                // mark the current vertex as visited
                visited. set (vertex);

                // determine the depth of the vertices that will be analyzed
                ++ depth;

                // determine the edges to be checked
                int_t firstedge = vertex ? edgeEnds [vertex - 1] :
                        static_cast<int_t> (0);
                int_t maxedge = edgeEnds [vertex];

                // put all the unvisited destination vertices on the stack
                for (int_t edge = firstedge; edge < maxedge; ++ edge)
                {
                        // determine the vertex pointed to by this edge
                        int_t next = edges [edge];

                        // if this is the destination vertex then return
                        // the shortest path length; note: this vertex
                        // might be visited if checking a loop, so it is
                        // important to check the destination first
                        if (next == destination)
                        {
                                visited. free ();
                                return depth;
                        }

                        // if the vertex was already visited then skip it
                        if (visited. test (next))
                                continue;

                        // add the vertex to the queue
                        q_vertex. push (next);
                        q_depth. push (depth);
                }

                // if there are no vertices whose neighbors are to be
                // analyzed and the destination vertex was not found
                // then there is no path to that vertex
                if (q_vertex. empty ())
                {
                        visited. free ();
                        return 0;
                }

                // pick up a vertex stored in the queue
                vertex = q_vertex. front ();
                q_vertex. pop ();
                depth = q_depth. front ();
                q_depth. pop ();
        }
} /* diGraph::shortestPath */

template <class wType>
inline int_t diGraph<wType>::shortestLoop (int_t origin) const
{
        return shortestPath (origin, origin);
} /* diGraph::shortestLoop */

template <class wType>
template <class lenTable, class weightsType, class roundType>
inline void diGraph<wType>::Dijkstra (const roundType &rounding,
        int_t source, lenTable &len, weightsType &edgeWeights) const
{
        // use the Fibonacci heap as a priority queue
        FibonacciHeap<posWeight> Q (nVertices);

        // add the vertices to the heap with the initial shortest path
        // lengths: 0 to the source, plus infinity to all the others
        for (int_t v = 0; v < nVertices; ++ v)
        {
                posWeight w (0);
                if (v != source)
                        w. setInfinity ();
                int_t number = Q. Insert (w);
                if (number != v)
                {
                        throw "Wrong implementation of Fibonacci heap "
                                "for this version of Dijkstra.";
                }
        }

        // pick up vertices from the priority queue, record the length
        // of the shortest path to them, and modify the remaining paths
        for (int_t i = 0; i < nVertices; ++ i)
        {
                // extract the minimal vertex from the queue
                int_t minVertex = Q. Minimum ();
                posWeight minWeight = Q. ExtractMinimum ();

                if (minWeight. isInfinity ())
                {
                        len [minVertex] = -1;
                        continue;
                }
                wType minValue = minWeight. getValue ();
                len [minVertex] = minValue;

                // go through all the edges emanating from this vertex
                // and update the path lengths for the target vertices
                int_t edge = minVertex ? edgeEnds [minVertex - 1] :
                        static_cast<int_t> (0);
                int_t maxEdge = edgeEnds [minVertex];
                for (; edge < maxEdge; ++ edge)
                {
                        // determine the vertex at the other end of the edge
                        int_t nextVertex = edges [edge];

                        // if the path that runs through the extracted
                        // vertex is shorter, then make a correction
                        const posWeight &nextWeight = Q. Value (nextVertex);
                        wType newWeight = rounding. add_down (minValue,
                                edgeWeights [edge]);
                        if (newWeight < 0)
                                newWeight = 0;
                        if (nextWeight. isInfinity () ||
                                (newWeight < nextWeight. getValue ()))
                        {
                                Q. DecreaseKey (nextVertex,
                                        posWeight (newWeight));
                        }
                }
        }
        return;
} /* diGraph::Dijkstra */

template <class wType>
template <class lenTable, class roundType>
inline void diGraph<wType>::Dijkstra (const roundType &rounding,
        int_t source, lenTable &len) const
{
        this -> Dijkstra (rounding, source, len, this -> weights);
        return;
} /* diGraph::Dijkstra */

template <class wType>
template <class lenTable>
inline void diGraph<wType>::Dijkstra (int_t source, lenTable &len) const
{
        const dummyRounding<wType> rounding = dummyRounding<wType> ();
        this -> Dijkstra (rounding, source, len);
        return;
} /* diGraph::Dijkstra */

template <class wType> template <class lenTable, class predTable,
        class roundType>
inline bool diGraph<wType>::BellmanFord (const roundType &rounding,
        int_t source, lenTable &len, wType *infinity, predTable pred) const
{
        // make sure the source vertex number is correct
        if ((source < 0) || (source >= nVertices))
                throw "Bellman-Ford: Wrong source vertex number.";

        // prepare marks to indicate finite values (not "infinity")
        BitField finite;
        finite. allocate (nVertices);
        finite. clearall (nVertices);
        finite. set (source);
        len [source] = 0;

        // count the negative vertices
        int_t countNegative = 0;

        // set the initial predecessors
        for (int_t i = 0; i < nVertices; ++ i)
                pred [i] = -1;

        // update the lenghts of the paths repeatedly (max nVertices times)
        bool noNegativeLoop = false;
        int_t counter = 0;
        for (; counter <= nVertices; ++ counter)
        {
                bool modified = false;
                int_t curEdge = 0;
                for (int_t vertex = 0; vertex < nVertices; ++ vertex)
                {
                        int_t maxEdge = edgeEnds [vertex];
                        if (!finite. test (vertex))
                        {
                                curEdge = maxEdge;
                                continue;
                        }
                        for (; curEdge < maxEdge; ++ curEdge)
                        {
                                int_t next = edges [curEdge];
                                wType newlen = rounding. add_down
                                        (len [vertex], weights [curEdge]);
                                if (!finite. test (next))
                                {
                                        finite. set (next);
                                        modified = true;
                                        len [next] = newlen;
                                        pred [next] = vertex;
                                        if (newlen < 0)
                                                ++ countNegative;
                                }
                                else if (newlen < len [next])
                                {
                                        modified = true;
                                        if (!(len [next] < 0) &&
                                                (newlen < 0))
                                        {
                                                ++ countNegative;
                                        }
                                        len [next] = newlen;
                                        pred [next] = vertex;
                                }
                        }
                }
                if (countNegative == nVertices)
                {
                        noNegativeLoop = false;
                        ++ counter;
                        break;
                }
                if (!modified)
                {
                        noNegativeLoop = true;
                        ++ counter;
                        break;
                }
        }

        // show a message on how many loops have been done
        if (false && chomp::homology::sbug. show)
        {
                chomp::homology::sbug << "Bellman-Ford: " <<
                        counter << ((counter > 1) ? " loops (" : " loop (") <<
                        nVertices << " vertices, " << countNegative <<
                        " negative). " <<
                        (noNegativeLoop ? "No negative loops.\n" :
                        "A negative loop found.\n");
        }

        // compute the value for the infinity and set the undefined distances
        if (infinity && noNegativeLoop)
        {
                wType infty (0);
                bool first = true;
                for (int_t i = 0; i < nVertices; ++ i)
                {
                        if (!finite. test (i))
                                continue;
                        if (first)
                        {
                                infty = len [i];
                                first = false;
                        }
                        else if (infty < len [i])
                        {
                                infty = len [i];
                        }
                }
                infty = infty + 1;
                for (int_t i = 0; i < nVertices; ++ i)
                {
                        if (!finite. test (i))
                                len [i] = infty;
                }
                *infinity = infty;
        }

        finite. free ();
        return noNegativeLoop;
} /* diGraph::BellmanFord */

template <class wType> template <class lenTable, class predTable>
inline bool diGraph<wType>::BellmanFord (int_t source, lenTable &len,
        wType *infinity, predTable pred) const
{
        const dummyRounding<wType> rounding = dummyRounding<wType> ();
        return this -> BellmanFord (rounding, source, len, infinity, pred);
} /* diGraph::BellmanFord */

template <class wType> template <class roundType>
inline bool diGraph<wType>::BellmanFord (const roundType &rounding,
        int_t source) const
{
        chomp::homology::auto_array<wType> len_ptr (new wType [nVertices]);
        wType *len = len_ptr. get ();
        wType *infinity = 0;
        dummyArray tab;
        return BellmanFord (rounding, source, len, infinity, tab);
} /* diGraph::BellmanFord */

template <class wType>
inline bool diGraph<wType>::BellmanFord (int_t source) const
{
        const dummyRounding<wType> rounding = dummyRounding<wType> ();
        return BellmanFord (rounding, source);
} /* diGraph::BellmanFord */

template <class wType>
inline wType diGraph<wType>::Edmonds () const
{
        // create a list of edges with weights and sort this list
        std::vector<edgeTriple> edgeTriples (countEdges ());
        int_t prevEdge = 0;
        int_t curEdge = 0;
        for (int_t vert = 0; vert < nVertices; ++ vert)
        {
                while (curEdge < edgeEnds [vert])
                {
                        edgeTriple &e = edgeTriples [curEdge];
                        e. vert1 = vert;
                        e. vert2 = edges [curEdge];
                        e. weight = weights [curEdge];
                        ++ curEdge;
                }
                prevEdge = curEdge;
        }
        std::sort (edgeTriples. begin (), edgeTriples. end ());

        // create a forest which initially contains single vertices
        chomp::homology::auto_array<int_t> root_ptr (new int_t [nVertices]);
        int_t *root = root_ptr. get ();
        for (int_t vert = 0; vert < nVertices; ++ vert)
        {
                root [vert] = -1;
        }

        // go through the edges and join the trees, but avoid loops
        wType totalWeight = 0;
        int_t nEdges = countEdges ();
        for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
        {
                // determine the roots of both vertices of the edge
                // and compress the paths
                edgeTriple &e = edgeTriples [curEdge];
                int_t root1 = e. vert1;
                while (root [root1] >= 0)
                {
                        root1 = root [root1];
                }
                int_t vert1 = e. vert1;
                while (root [vert1] >= 0)
                {
                        int_t next = root [vert1];
                        root [vert1] = root1;
                        vert1 = next;
                }
                int_t root2 = e. vert2;
                while (root [root2] >= 0)
                {
                        root2 = root [root2];
                }
                int_t vert2 = e. vert2;
                while (root [vert2] >= 0)
                {
                        int_t next = root [vert2];
                        root [vert2] = root2;
                        vert2 = next;
                }

                // skip the edge if it closes a loop
                if (root1 == root2)
                        continue;

                // add the weight
                totalWeight += e. weight;

                // join the trees
                root [root1] = root2;
        }
        return totalWeight;
} /* diGraph::Edmonds */

template <class wType>
inline wType diGraph<wType>::EdmondsOld () const
{
        // create a list of edges with weights and sort this list
        std::vector<edgeTriple> edgeTriples (countEdges ());
        int_t prevEdge = 0;
        int_t curEdge = 0;
        for (int_t vert = 0; vert < nVertices; ++ vert)
        {
                while (curEdge < edgeEnds [vert])
                {
                        edgeTriple &e = edgeTriples [curEdge];
                        e. vert1 = vert;
                        e. vert2 = edges [curEdge];
                        e. weight = weights [curEdge];
                        ++ curEdge;
                }
                prevEdge = curEdge;
        }
        std::sort (edgeTriples. begin (), edgeTriples. end ());

        // create a forest which initially contains single vertices
        chomp::homology::auto_array<int_t> forest_ptr
                (new int_t [nVertices]);
        int_t *forest = forest_ptr. get ();
        chomp::homology::auto_array<int_t> next_ptr
                (new int_t [nVertices]);
        int_t *next = next_ptr. get ();
        chomp::homology::auto_array<int_t> prev_ptr
                (new int_t [nVertices]);
        int_t *prev = prev_ptr. get ();
        for (int_t vert = 0; vert < nVertices; ++ vert)
        {
                forest [vert] = vert;
                next [vert] = -1;
                prev [vert] = -1;
        }

        // go through the edges and join the trees, but avoid loops
        wType totalWeight = 0;
        int_t nEdges = countEdges ();
        for (int_t curEdge = 0; curEdge < nEdges; ++ curEdge)
        {
                // check the edge and skip it if it closes a loop
                edgeTriple &e = edgeTriples [curEdge];
                if (forest [e. vert1] == forest [e. vert2])
                        continue;

                // add the weight
                totalWeight += e. weight;

                // go to the end of the first tree
                int_t vert1 = e. vert1;
                while (next [vert1] >= 0)
                {
                        vert1 = next [vert1];
                }
                
                // go to the beginning of the second tree
                int_t vert2 = e. vert2;
                while (prev [vert2] >= 0)
                {
                        vert2 = prev [vert2];
                }

                // join the trees and modify the numbers
                next [vert1] = vert2;
                prev [vert2] = vert1;
                int_t treeNumber = forest [vert1];
                while (vert2 >= 0)
                {
                        forest [vert2] = treeNumber;
                        vert2 = next [vert2];
                }
        }
        return totalWeight;
} /* diGraph::EdmondsOld */

template <class wType>
template <class arrayType, class roundType>
inline wType diGraph<wType>::FloydWarshall (const roundType &rounding,
        arrayType &arr, bool setInfinity, bool ignoreNegLoop) const
{
        // do nothing if the graph is empty
        if (!nVertices)
                return 0;

        // prepare marks to indicate finite values (not "infinity")
        BitField *finite = new BitField [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
        {
                finite [i]. allocate (nVertices);
                finite [i]. clearall (nVertices);
        }

        // create the initial values of the array based on the edge weights
        int_t curEdge = 0;
        for (int_t source = 0; source < nVertices; ++ source)
        {
                bool diagset = false;
                while (curEdge < edgeEnds [source])
                {
                        int_t target = edges [curEdge];
                        const wType &weight = weights [curEdge];
                        if (source == target)
                        {
                                if (weight < 0)
                                {
                                        arr [source] [target] = weight;
                                        diagset = true;
                                }
                        }
                        else
                        {
                                arr [source] [target] = weight;
                                finite [source]. set (target);
                        }
                        ++ curEdge;
                }
                if (!diagset)
                        arr [source] [source] = 0;
                finite [source]. set (source);
        }

        // find the shortest paths between the vertices (dynamic programming)
        for (int_t k = 0; k < nVertices; ++ k)
        {
                for (int_t i = 0; i < nVertices; ++ i)
                {
                        if (!finite [i]. test (k))
                                continue;
                        for (int_t j = 0; j < nVertices; ++ j)
                        {
                                if (!finite [k]. test (j))
                                        continue;
                                const wType sum = rounding. add_down
                                        (arr [i] [k], arr [k] [j]);
                                if (finite [i]. test (j))
                                {
                                        if (sum < arr [i] [j])
                                                arr [i] [j] = sum;
                                }
                                else
                                {
                                        arr [i] [j] = sum;
                                        finite [i]. set (j);
                                }
                        }
                }
        }

        // verify if a negative loop exists by checking for a negative
        // result in the diagonal
        if (!ignoreNegLoop)
        {
                for (int_t i = 0; i < nVertices; ++ i)
                {
                        if (arr [i] [i] < 0)
                                throw "Negative loop in Floyd-Warshall.";
                }
        }

        // prepare a variable to store the returned result
        wType result = 0;

        // compute the value for the infinity and fill in the array
        // if requested to do so
        if (setInfinity)
        {
                wType &infinity = result;
                for (int_t i = 0; i < nVertices; ++ i)
                {
                        for (int_t j = 0; j < nVertices; ++ j)
                        {
                                if (finite [i]. test (j) &&
                                        (infinity <= arr [i] [j]))
                                {
                                        infinity = rounding. add_up
                                                (arr [i] [j], 1);
                                }
                        }
                }
                for (int_t i = 0; i < nVertices; ++ i)
                {
                        for (int_t j = 0; j < nVertices; ++ j)
                        {
                                if (!finite [i]. test (j))
                                        arr [i] [j] = infinity;
                        }
                }
        }

        // otherwise, only compute the minimum path weight
        else
        {
                wType &minWeight = result;
                bool firstTime = true;
                for (int_t i = 0; i < nVertices; ++ i)
                {
                        for (int_t j = 0; j < nVertices; ++ j)
                        {
                                if (finite [i]. test (j))
                                {
                                        if (firstTime)
                                        {
                                                minWeight = arr [i] [j];
                                                firstTime = false;
                                        }
                                        else if (arr [i] [j] < minWeight)
                                        {
                                                minWeight = arr [i] [j];
                                        }
                                }
                        }
                }
        }

        // release the 'finite' bitfields
        for (int_t i = 0; i < nVertices; ++ i)
                finite [i]. free ();
        delete [] finite;

        return result;
} /* diGraph::FloydWarshall */

template <class wType>
template <class arrayType>
inline wType diGraph<wType>::FloydWarshall (arrayType &arr,
        bool setInfinity, bool ignoreNegLoop) const
{
        const dummyRounding<wType> rounding = dummyRounding<wType> ();
        return FloydWarshall (rounding, arr, setInfinity, ignoreNegLoop);
} /* diGraph::FloydWarshall */

template <class wType>
template <class arrayType, class roundType>
inline wType diGraph<wType>::Johnson (const roundType &rounding,
        arrayType &arr, bool setInfinity, bool ignoreNegLoop) const
{
        // DEBUG VERIFICATION
        if (false && sbug. show)
        {
                timeused stopWatch;
                wType res = FloydWarshall (rounding,
                        arr, setInfinity, ignoreNegLoop);
                chomp::homology::sbug << "\n[Floyd-Warshall: " << res <<
                        ", " << (double) stopWatch << " sec]\n";
        }
        // debug time measurement (see below)
//      timeused stopWatch;

        // do nothing if the graph is empty
        if (!nVertices)
                return 0;

        // STEP 1: Compute the shortest paths to any vertex from an
        // artificial extra vertex connected to every other vertex in the
        // graph by an edge of weight zero. Use Bellman-Ford for this.
        wType *len = new wType [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
                len [i] = 0;

        // update the lenghts of the paths repeatedly (max nVertices times)
        bool noNegativeLoop = false;
        int_t counter = 0;
        for (; counter <= nVertices; ++ counter)
        {
                bool modified = false;
                int_t curEdge = 0;
                for (int_t vertex = 0; vertex < nVertices; ++ vertex)
                {
                        int_t maxEdge = edgeEnds [vertex];
                        for (; curEdge < maxEdge; ++ curEdge)
                        {
                                int_t next = edges [curEdge];
                                wType newlen = rounding. add_down
                                        (len [vertex], weights [curEdge]);
                                if (newlen < len [next])
                                {
                                        // this "if" statement is necessary
                                        // because of a bug in GCC 3.4.2...
                                        if (counter > nVertices)
                                        {
                                                std::cout << vertex;
                                        }
                                        modified = true;
                                        len [next] = newlen;
                                }
                        }
                }
                if (!modified)
                {
                        noNegativeLoop = true;
                        ++ counter;
                        break;
                }
        }
        if (!ignoreNegLoop && !noNegativeLoop)
                throw "Negative loop found in Johnson's algorithm.";

        // STEP 2: Re-weigh the edges using the computed path lengths.
        wType *newWeights = new wType [edgeEnds [nVertices - 1]];
        int_t edge = 0;
        for (int_t vertex = 0; vertex < nVertices; ++ vertex)
        {
                int_t maxEdge = edgeEnds [vertex];
                for (; edge < maxEdge; ++ edge)
                {
                        wType w = weights [edge];
                        w = rounding. add_down (w, len [vertex]);
                        w = rounding. sub_down (w, len [edges [edge]]);
                        newWeights [edge] = (w < 0) ?
                                static_cast<wType> (0) : w;
                }
        }

        // STEP 3: Run the Dijkstra algorithm for every vertex to compute
        // the shortest paths to all the other vertices.
        // Negative entries indicate no path existence.
        for (int_t u = 0; u < nVertices; ++ u)
        {
                this -> Dijkstra (rounding, u, arr [u], newWeights);
        }
        delete [] newWeights;

        // STEP 4: Make a correction to the computed path lengths.
        // Compute the value for infinity if requested to.
        // Otherwise compute the minimum of path lengths.
        wType result = 0;
        if (setInfinity)
        {
                wType &infinity = result;
                for (int_t u = 0; u < nVertices; ++ u)
                {
                        for (int_t v = 0; v < nVertices; ++ v)
                        {
                                wType w = arr [u] [v];
                                if (w < 0)
                                        continue;
                                w = rounding. add_down (w, len [v]);
                                w = rounding. sub_down (w, len [u]);
                                if (w < infinity)
                                        continue;
                                infinity = rounding. add_up (w, 1);
                        }
                }
                for (int_t u = 0; u < nVertices; ++ u)
                {
                        for (int_t v = 0; v < nVertices; ++ v)
                        {
                                wType w = arr [u] [v];
                                if (w < 0)
                                {
                                        arr [u] [v] = infinity;
                                        continue;
                                }
                                w = rounding. add_down (w, len [v]);
                                arr [u] [v] =
                                        rounding. sub_down (w, len [u]);
                        }
                }
        }
        else
        {
                wType &minWeight = result;
                bool firstTime = true;
                for (int_t u = 0; u < nVertices; ++ u)
                {
                        for (int_t v = 0; v < nVertices; ++ v)
                        {
                                wType w = arr [u] [v];
                                if (w < 0)
                                        continue;
                                w = rounding. add_down (w, len [v]);
                                w = rounding. sub_down (w, len [u]);
                                if (firstTime)
                                {
                                        minWeight = w;
                                        firstTime = false;
                                }
                                else if (w < minWeight)
                                        minWeight = w;
                        }
                }
        }
        delete [] len;

        // DEBUG VERIFICATION
        if (false && sbug. show)
        {
//              chomp::homology::sbug << "[Johnson: " << result <<
//                      ", " << (double) stopWatch << " sec]\n";
        }

        return result;
} /* diGraph::Johnson */

template <class wType>
template <class arrayType>
inline wType diGraph<wType>::Johnson (arrayType &arr,
        bool setInfinity, bool ignoreNegLoop) const
{
        const dummyRounding<wType> rounding = dummyRounding<wType> ();
        return Johnson (rounding, arr, setInfinity, ignoreNegLoop);
} /* diGraph::Johnson */

template <class wType>
template <class roundType>
wType diGraph<wType>::minPathWeight (const roundType &rounding,
        bool ignoreNegLoop, int sparseGraph) const
{
        // if the graph is empty, return 0 as the minimum path weight
        if (nVertices <= 0)
                return 0;

        // allocate memory for an array of arrays to store min path weights
        wType **arr = new wType * [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
                arr [i] = new wType [nVertices];

        // determine whether to run the Floyd-Warshall algorithm
        // or Johnson's algorithm
        bool sparse = false;
        if (sparseGraph == 1)
                sparse = true;
        else if (sparseGraph != 0)
        {
                double nEdgesD = this -> countEdges ();
                double nVerticesD = this -> countVertices ();
                if ((nVerticesD > 3000) && (nEdgesD < nVerticesD * 1000) &&
                        (nEdgesD < nVerticesD * nVerticesD / 50))
                {
                        sparse = true;
                }
        }

        // run the Johnson's or Floyd-Warshall algorithm
        wType minWeight = sparse ?
                this -> Johnson (rounding, arr, false, ignoreNegLoop) :
                this -> FloydWarshall (rounding, arr, false, ignoreNegLoop);

/*      // compute the minimum of all the paths
        wType minWeight = arr [0] [0];
        for (int_t i = 0; i < nVertices; ++ i)
        {
                for (int_t j = 0; j < nVertices; ++ j)
                {
                        const wType &weight = arr [i] [j];
                        if (weight < minWeight)
                                minWeight = weight;
                }
        }
*/
        // release the memory
        for (int_t i = 0; i < nVertices; ++ i)
                delete [] (arr [i]);
        delete [] arr;

        return minWeight;
} /* diGraph::minPathWeight */

template <class wType>
wType diGraph<wType>::minPathWeight (bool ignoreNegLoop, int sparseGraph)
        const
{
        const dummyRounding<wType> rounding = dummyRounding<wType> ();
        return this -> minPathWeight (rounding, ignoreNegLoop, sparseGraph);
} /* diGraph::minPathWeight */

template <class wType> template <class outType>
inline outType &diGraph<wType>::show (outType &out, bool showWeights) const
{
        out << "; Directed graph: " << nVertices << " vertices.\n";
        int_t curEdge = 0;
        for (int_t i = 0; i < nVertices; ++ i)
        {
                for (; curEdge < edgeEnds [i]; ++ curEdge)
                {
                        out << i << " -> " << edges [curEdge];
                        if (showWeights)
                                out << " [" << weights [curEdge] << "]\n";
                        else
                                out << "\n";
                }
        }
        out << "; This is the end of the graph.\n";
        return out;
} /* diGraph::show */

        
// --------------------------------------------------

/// Writes a graph in the text mode to an output stream.
template <class wType>
inline std::ostream &operator << (std::ostream &out, const diGraph<wType> &g)
{
        return g. show (out, false);
} /* operator << */

// --------------------------------------------------

/// Computes strongly connected components of the graph 'g'. Creates
/// the graph 'scc' in which each vertex corresponds to one component.
/// The graph 'scc' given as an argument must be initially empty.
/// The table 'compVertices' is filled with the numbers of vertices in 'g'
/// which form the components, and the indices that end the listing
/// for each component are stored in the table 'compEnds'.
/// Returns the number of strongly connected components found.
template <class wType, class Table1, class Table2>
inline int_t SCC (const diGraph<wType> &g, Table1 &compVertices,
        Table2 &compEnds, diGraph<wType> *scc = 0,
        diGraph<wType> *transposed = 0, bool copyweights = false)
{
        // prepare two tables
        int_t nVert = g. countVertices ();
        int_t *ordered = new int_t [nVert];
        int_t *tab = new int_t [nVert];

        // compute the list of vertices in the descending finishing time
        g. DFSfinishTime (tab);
        for (int_t i = 0; i < nVert; ++ i)
                ordered [nVert - tab [i]] = i;
        delete [] tab;

        // create the transposed graph
        diGraph<wType> gT;
        if (!transposed)
                transposed = &gT;
        g. transpose (*transposed, copyweights);

        // extract the DFS forest of gT in the given order of vertices
        int_t n = transposed -> DFSforest (ordered, compVertices, compEnds,
                true, scc);

        // cleanup memory and return the number of components
        delete [] ordered;
        return n;
} /* SCC */

// --------------------------------------------------

/// Computes strongly connected components of the graph 'g'
/// using Tarjan's algorithm (as described in the Wikipedia).
/// Tha advantage of this approach over the one described in Cormen's
/// textbook is that the transposed graph need not be computed.
/// However, this algorithm might be slightly slower than the other one.
/// The table 'compVertices' is filled with the numbers of vertices in 'g'
/// which form the components, and the indices that end the listing
/// for each component are stored in the table 'compEnds'.
/// Returns the number of strongly connected components found.
template <class wType, class Table1, class Table2>
inline int_t SCC_Tarjan (const diGraph<wType> &g, Table1 &compVertices,
        Table2 &compEnds)
{
        // return the obvious result if the graph is empty
        int_t nVertices = g. countVertices ();
        if (!nVertices)
                return 0;

        // prepare an array of discovery times for all the vertices
        // (zero == not yet discovered)
        std::vector<int_t> dfsIndex (nVertices, 0);

        // prepare an array of the minimal index of a node reachable
        // from each of the vertices
        std::vector<int_t> lowLink (nVertices, 0);

        // prepare an empty stack of nodes
        std::stack<int_t> s_nodes;

        // prepare an array of bits indicating whether the vertices are
        // in the stack of nodes or not
        BitField inTheStack;
        inTheStack. allocate (nVertices);
        inTheStack. clearall (nVertices);

        // prepare the number of strongly connected components
        int_t nComponents = 0;

        // prepare the current position in the array 'compVertices'
        int_t posVertices = 0;

        // remember the next vertex number in the graph to scan
        // whether this vertex has already been visited or not
        int_t vertexToScan = 0;

        // prepare a variable for storing the discovery time in the DFS
        int_t discoveryTime = 0;

        // prepare stacks for the DFS recursion
        std::stack<int_t> s_vertex;
        std::stack<int_t> s_edge;
        std::stack<int_t> s_maxedge;

        // initialize the number of the currently processed vertex
        int_t vertex = -1;

        // initialize the range of edges to be visited
        int_t edge = 0;
        int_t maxedge = 0;

        while (1)
        {
                // return to the previous recursion level
                // if all the edges have been checked
                if (edge >= maxedge)
                {
                        // extract a strongly connected component
                        if ((vertex >= 0) && (lowLink [vertex] ==
                                dfsIndex [vertex]))
                        {
                                int_t v = 0;
                                do
                                {
                                        v = s_nodes. top ();
                                        s_nodes. pop ();
                                        inTheStack. clear (v);
                                        compVertices [posVertices ++] = v;
                                } while (v != vertex);
                                compEnds [nComponents ++] = posVertices;
                        }

                        // if this is the top level of the recursion
                        // then find another unvisited vertex or return
                        if (s_vertex. empty ())
                        {
                                // find an unvisited vertex in the graph
                                while ((vertexToScan < nVertices) &&
                                        (dfsIndex [vertexToScan] != 0))
                                {
                                        ++ vertexToScan;
                                }

                                // return the result if all visited
                                if (vertexToScan == nVertices)
                                {
                                        inTheStack. free ();
                                        return nComponents;
                                }

                                // set the new vertex
                                vertex = vertexToScan ++;

                                // mark the current vertex as visited
                                // and initialize its low link
                                dfsIndex [vertex] = ++ discoveryTime;
                                lowLink [vertex] = discoveryTime;

                                // push this vertex on the stack
                                s_nodes. push (vertex);
                                inTheStack. set (vertex);

                                // determine the edges to be visited
                                edge = 0;
                                maxedge = g. countEdges (vertex);
                        }

                        // otherwise trace back to the previous level
                        else
                        {
                                // remember the current low link index
                                int_t lowLink2 = lowLink [vertex];

                                // restore the variables
                                vertex = s_vertex. top ();
                                s_vertex. pop ();
                                edge = s_edge. top ();
                                s_edge. pop ();
                                maxedge = s_maxedge. top ();
                                s_maxedge. pop ();

                                // update the current low link index
                                if (lowLink [vertex] > lowLink2)
                                        lowLink [vertex] = lowLink2;
                        }
                }

                // analyse the next edge coming out from the current vertex
                else
                {
                        // determine the next vertex
                        int_t next = g. getEdge (vertex, edge ++);

                        // go to a deeper recursion level if unvisited
                        if (dfsIndex [next] == 0)
                        {
                                // store the variables at the stacks
                                s_vertex. push (vertex);
                                s_edge. push (edge);
                                s_maxedge. push (maxedge);

                                // set the new vertex
                                vertex = next;
                        
                                // mark the new vertex as visited
                                dfsIndex [vertex] = ++ discoveryTime;
                                lowLink [vertex] = discoveryTime;
                        
                                // push this vertex on the stack
                                s_nodes. push (vertex);
                                inTheStack. set (vertex);

                                // determine the edges to be visited
                                edge = 0;
                                maxedge = g. countEdges (vertex);
                        }

                        // update the low link index if the vertex has been
                        // visited and is currently in the stack of nodes
                        else if (inTheStack. test (next))
                        {
                                if (lowLink [vertex] > dfsIndex [next])
                                        lowLink [vertex] = dfsIndex [next];
                        }
                }
        }

        // finalize and return the number of strongly connected components
        inTheStack. free ();
        return nComponents;
} /* SCC_Tarjan */

// --------------------------------------------------

template <class wType>
wType diGraph<wType>::minMeanCycleWeight (diGraph<wType> *transposed) const
{
        // find the strongly connected components of the graph
        multitable<int_t> compVertices, compEnds;
        bool copyweights = !!transposed;
        int_t countSCC = SCC (*this, compVertices, compEnds,
                static_cast<diGraph<wType> *> (0), transposed, copyweights);
        if (countSCC <= 0)
                return 0;

        // compute the maximum size of each strongly connected component
        int_t maxCompSize = compEnds [0];
        for (int_t comp = 1; comp < countSCC; ++ comp)
        {
                int_t compSize = compEnds [comp] - compEnds [comp - 1];
                if (maxCompSize < compSize)
                        maxCompSize = compSize;
        }

        // allocate arrays for weights and bit fields
        wType **F = new wType * [maxCompSize + 1];
        BitField *finite = new BitField [maxCompSize + 1];
        for (int_t i = 0; i <= maxCompSize; ++ i)
        {
                F [i] = new wType [maxCompSize];
                finite [i]. allocate (maxCompSize);
        }

        // compute the numbers of vertices in each component
        int_t *numbers = new int_t [nVertices];
        int_t *components = new int_t [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
                components [i] = -1;
        int_t offset = 0;
        for (int_t comp = 0; comp < countSCC; ++ comp)
        {
                int_t maxOffset = compEnds [comp];
                int_t pos = offset;
                for (; pos < maxOffset; ++ pos)
                {
                        numbers [compVertices [pos]] = pos - offset;
                        components [compVertices [pos]] = comp;
                }
                offset = pos;
        }

        // compute the minimum mean cycle weight for each component
        wType minWeight (0);
        for (int_t comp = 0; comp < countSCC; ++ comp)
        {
                int_t offset = comp ? compEnds [comp - 1] :
                        static_cast<int_t> (0);
                int_t compSize = compEnds [comp] - offset;
                for (int_t i = 0; i <= compSize; ++ i)
                        finite [i]. clearall (compSize);
                F [0] [0] = 0;
                finite [0]. set (0);
                // compute path progressions of given length
                for (int_t len = 1; len <= compSize; ++ len)
                {
                        // process source vertices
                        for (int_t i = 0; i < compSize; ++ i)
                        {
                                if (!finite [len - 1]. test (i))
                                        continue;
                                wType prevWeight = F [len - 1] [i];
                                int_t source = compVertices [offset + i];

                                // process target vertices (and edges)
                                int_t edgeOffset = source ?
                                        edgeEnds [source - 1] :
                                        static_cast<int_t> (0);
                                int_t edgeEnd = edgeEnds [source];
                                for (; edgeOffset < edgeEnd; ++ edgeOffset)
                                {
                                        int_t target = edges [edgeOffset];
                                        if (components [target] != comp)
                                                continue;
                                        int_t j = numbers [target];
                                        wType newWeight = prevWeight +
                                                weights [edgeOffset];
                                        if (!finite [len]. test (j))
                                        {
                                                finite [len]. set (j);
                                                F [len] [j] = newWeight;
                                        }
                                        else if (newWeight < F [len] [j])
                                                F [len] [j] = newWeight;
                                }
                        }
                }

                // compute the minimum mean cycle weight for this component
                wType minCompWeight (0);
                bool firstMin = true;
                for (int_t vert = 0; vert < compSize; ++ vert)
                {
                        if (!finite [compSize]. test (vert))
                                continue;
                        bool firstAverage = true;
                        wType maxAverage = 0;
                        for (int_t first = 0; first < compSize; ++ first)
                        {
                                if (!finite [first]. test (vert))
                                        continue;
                                wType average = (F [compSize] [vert] -
                                        F [first] [vert]) /
                                        (compSize - first);
                                if (firstAverage)
                                {
                                        maxAverage = average;
                                        firstAverage = false;
                                }
                                else if (maxAverage < average)
                                        maxAverage = average;
                        }
                        if (firstMin || (maxAverage < minCompWeight))
                        {
                                if (firstAverage)
                                        throw "Bug in Karp's algorithm";
                                minCompWeight = maxAverage;
                                firstMin = false;
                        }
                }

                // make a correction to the total minimum if necessary
                if (!comp || (minCompWeight < minWeight))
                        minWeight = minCompWeight;
        }

        // release allocated memory
        delete [] components;
        delete [] numbers;
        for (int_t i = 0; i < maxCompSize; ++ i)
        {
                finite [i]. free ();
                delete [] (F [i]);
        }
        delete [] finite;
        delete [] F;

        // return the computed minimum
        return minWeight;
} /* diGraph::minMeanCycleWeight */

template <class wType>
template <class roundType>
wType diGraph<wType>::minMeanCycleWeight (const roundType &rounding,
        diGraph<wType> *transposed) const
{
        // find the strongly connected components of the graph
        multitable<int_t> compVertices, compEnds;
        bool copyweights = !!transposed;
        int_t countSCC = SCC (*this, compVertices, compEnds,
                static_cast<diGraph<wType> *> (0), transposed, copyweights);
        if (countSCC <= 0)
                return 0;

        // compute the maximum size of each strongly connected component
        int_t maxCompSize = compEnds [0];
        for (int_t comp = 1; comp < countSCC; ++ comp)
        {
                int_t compSize = compEnds [comp] - compEnds [comp - 1];
                if (maxCompSize < compSize)
                        maxCompSize = compSize;
        }

        // allocate arrays for weights and bit fields
        wType **FUpper = new wType * [maxCompSize + 1];
        wType **FLower = new wType * [maxCompSize + 1];
        BitField *finite = new BitField [maxCompSize + 1];
        for (int_t i = 0; i <= maxCompSize; ++ i)
        {
                FUpper [i] = new wType [maxCompSize];
                FLower [i] = new wType [maxCompSize];
                finite [i]. allocate (maxCompSize);
        }

        // compute the numbers of vertices in each component
        int_t *numbers = new int_t [nVertices];
        int_t *components = new int_t [nVertices];
        for (int_t i = 0; i < nVertices; ++ i)
                components [i] = -1;
        int_t offset = 0;
        for (int_t comp = 0; comp < countSCC; ++ comp)
        {
                int_t maxOffset = compEnds [comp];
                int_t pos = offset;
                for (; pos < maxOffset; ++ pos)
                {
                        numbers [compVertices [pos]] = pos - offset;
                        components [compVertices [pos]] = comp;
                }
                offset = pos;
        }

        // compute the minimum mean cycle weight for each component
        wType minWeight (0);
        for (int_t comp = 0; comp < countSCC; ++ comp)
        {
                int_t offset = comp ? compEnds [comp - 1] :
                        static_cast<int_t> (0);
                int_t compSize = compEnds [comp] - offset;
                for (int_t i = 0; i <= compSize; ++ i)
                        finite [i]. clearall (compSize);
                FUpper [0] [0] = 0;
                FLower [0] [0] = 0;
                finite [0]. set (0);
                // compute path progressions of given length
                for (int_t len = 1; len <= compSize; ++ len)
                {
                        // process source vertices
                        for (int_t i = 0; i < compSize; ++ i)
                        {
                                if (!finite [len - 1]. test (i))
                                        continue;
                                wType prevUpper = FUpper [len - 1] [i];
                                wType prevLower = FLower [len - 1] [i];
                                int_t source = compVertices [offset + i];

                                // process target vertices (and edges)
                                int_t edgeOffset = source ?
                                        edgeEnds [source - 1] :
                                        static_cast<int_t> (0);
                                int_t edgeEnd = edgeEnds [source];
                                for (; edgeOffset < edgeEnd; ++ edgeOffset)
                                {
                                        int_t target = edges [edgeOffset];
                                        if (components [target] != comp)
                                                continue;
                                        int_t j = numbers [target];
                                        wType newUpper = rounding. add_up
                                                (prevUpper,
                                                weights [edgeOffset]);
                                        wType newLower = rounding. add_down
                                                (prevLower,
                                                weights [edgeOffset]);
                                        if (!finite [len]. test (j))
                                        {
                                                finite [len]. set (j);
                                                FUpper [len] [j] = newUpper;
                                                FLower [len] [j] = newLower;
                                        }
                                        else
                                        {
                                                wType &curUpper =
                                                        FUpper [len] [j];
                                                if (newUpper < curUpper)
                                                        curUpper = newUpper;
                                                wType &curLower =
                                                        FLower [len] [j];
                                                if (newLower < curLower)
                                                        curLower = newLower;
                                        }
                                }
                        }
                }

                // compute the minimum mean cycle weight for this component
                wType minCompWeight (0);
                bool firstMin = true;
                for (int_t vert = 0; vert < compSize; ++ vert)
                {
                        if (!finite [compSize]. test (vert))
                                continue;
                        bool firstAverage = true;
                        wType maxAverage = 0;
                        for (int_t first = 0; first < compSize; ++ first)
                        {
                                if (!finite [first]. test (vert))
                                        continue;
                                const wType diff = rounding. sub_down
                                        (FLower [compSize] [vert],
                                        FUpper [first] [vert]);
                                wType average = rounding. div_down
                                        (diff, compSize - first);
                                if (firstAverage)
                                {
                                        maxAverage = average;
                                        firstAverage = false;
                                }
                                else if (maxAverage < average)
                                        maxAverage = average;
                        }
                        if (firstMin || (maxAverage < minCompWeight))
                        {
                                if (firstAverage)
                                        throw "Bug in Karp's algorithm";
                                minCompWeight = maxAverage;
                                firstMin = false;
                        }
                }

                // make a correction to the total minimum if necessary
                if (!comp || (minCompWeight < minWeight))
                        minWeight = minCompWeight;
        }

        // release allocated memory
        delete [] components;
        delete [] numbers;
        for (int_t i = 0; i < maxCompSize; ++ i)
        {
                finite [i]. free ();
                delete [] (FUpper [i]);
                delete [] (FLower [i]);
        }
        delete [] finite;
        delete [] FUpper;
        delete [] FLower;

        // return the computed minimum
        return minWeight;
} /* diGraph::minMeanCycleWeight_intv */

template <class wType>
template <class arrayType, class roundType>
wType diGraph<wType>::minMeanPathWeight (const roundType &rounding,
        const arrayType &starting, int_t n) const
{
        // allocate arrays for weights and bit fields
        const int nIndices = 2;
        wType **F = new wType * [nIndices];
        BitField *finite = new BitField [nIndices];
        for (int i = 0; i < nIndices; ++ i)
        {
                F [i] = new wType [nVertices];
                finite [i]. allocate (nVertices);
        }

        // set the zero path lengths from the initial vertices
        for (int_t i = 0; i < n; ++ i)
        {
                int_t v = starting [i];
                if ((v < 0) || (v >= nVertices))
                        throw "Starting vertex out of range.";
                F [0] [v] = 0;
                finite [0]. set (v);
        }

        // compute path progressions of given length and average weights
        wType minWeight (0);
        bool firstWeight = true;
        for (int_t len = 1; len <= nVertices; ++ len)
        {
                // determine the indices for previous and current paths
                int_t prevIndex = (len - 1) & 1;
                int_t curIndex = len & 1;
                finite [curIndex]. clearall (nVertices);

                // process source vertices
                for (int_t source = 0; source < nVertices; ++ source)
                {
                        if (!finite [prevIndex]. test (source))
                                continue;
                        wType prevWeight = F [prevIndex] [source];

                        // process target vertices (and edges)
                        int_t edgeOffset = source ?
                                edgeEnds [source - 1] :
                                static_cast<int_t> (0);
                        int_t edgeEnd = edgeEnds [source];
                        for (; edgeOffset < edgeEnd; ++ edgeOffset)
                        {
                                int_t target = edges [edgeOffset];
                                wType newWeight = rounding. add_down
                                        (prevWeight, weights [edgeOffset]);
                                if (!finite [curIndex]. test (target))
                                {
                                        finite [curIndex]. set (target);
                                        F [curIndex] [target] = newWeight;
                                }
                                else if (newWeight < F [curIndex] [target])
                                        F [curIndex] [target] = newWeight;
                        }
                }

                // update the minimum mean path weight
                for (int_t vert = 0; vert < nVertices; ++ vert)
                {
                        if (!finite [curIndex]. test (vert))
                                continue;
                        wType average = rounding. div_down
                                (F [curIndex] [vert], len);
                        if (firstWeight)
                        {
                                minWeight = average;
                                firstWeight = false;
                        }
                        else if (average < minWeight)
                                minWeight = average;
                }
        }

        // release allocated memory
        for (int i = 0; i < nIndices; ++ i)
        {
                finite [i]. free ();
                delete [] (F [i]);
        }
        delete [] finite;
        delete [] F;

        // return the computed minimum
        return minWeight;
} /* diGraph::minMeanPathWeight */

template <class wType>
template <class arrayType>
wType diGraph<wType>::minMeanPathWeight (const arrayType &starting, int_t n)
        const
{
        const dummyRounding<wType> rounding = dummyRounding<wType> ();
        return minMeanPathWeight (rounding, starting, n);
} /* diGraph::minMeanPathWeight */


// --------------------------------------------------
// ------------- OTHER GRAPH ALGORITHMS -------------
// --------------------------------------------------

/// A helper function for "collapseVertices".
template <class wType>
inline int_t addRenumEdges (const diGraph<wType> &g, int_t vertex,
        const int_t *newNum, int_t cur, int_t *srcVert,
        diGraph<wType> &result)
{
        int_t nEdges = g. countEdges (vertex);
        // add all the edges that start at the component
        for (int_t edge = 0; edge < nEdges; ++ edge)
        {
                // determine the dest. vertex of the edge
                int_t dest = newNum [g. getEdge (vertex, edge)];
                // if this is an edge to self, then ignore it
                if (dest == cur)
                        continue;
                // if the edge has already been added,
                // then skip it
                if (srcVert [dest] == cur)
                        continue;
                // remember that the dest. vertex has an edge
                // pointing out from the current vertex
                srcVert [dest] = cur;
                // add the edge to the result graph
                result. addEdge (dest);
        }
        return 0;
} /* addRenumEdges */

/// Collapses disjoint subsets of vertices to single vertices and creates
/// a corresponding graph in which the first vertices come from
/// the collapsed ones. The result graph must be initially empty.
/// Saves translation table from old to new vertex numbers.
/// The table must have sufficient length.
template <class wType, class Table1, class Table2>
inline int_t collapseVertices (const diGraph<wType> &g,
        int_t compNum, Table1 &compVertices, Table2 &compEnds,
        diGraph<wType> &result, int_t *newNumbers = 0)
{
        // do nothing if the input graph is empty
        int_t nVert = g. countVertices ();
        if (!nVert)
                return 0;

        // compute the new numbers of vertices: newNum [i] is the
        // number of vertex 'i' from 'g' in the resulting graph
        int_t *newNum = newNumbers ? newNumbers : new int_t [nVert];
        for (int_t i = 0; i < nVert; ++ i)
                newNum [i] = -1;
        int_t cur = 0; // current vertex number in the new graph
        int_t pos = 0; // position in compVertices
        while (cur < compNum)
        {
                int_t posEnd = compEnds [cur];
                while (pos < posEnd)
                        newNum [compVertices [pos ++]] = cur;
                ++ cur;
        }
        for (int_t i = 0; i < nVert; ++ i)
        {
                if (newNum [i] < 0)
                        newNum [i] = cur ++;
        }

        // prepare a table to mark the most recent source vertex for edges:
        // srcVert [j] contains i if the edge i -> j has just been added
        int_t newVert = nVert - (compNum ? compEnds [compNum - 1] :
                static_cast<int_t> (0)) + compNum;
        // debug:
        if (cur != newVert)
                throw "DEBUG: Wrong numbers.";
        int_t *srcVert = new int_t [newVert];
        for (int_t i = 0; i < newVert; ++ i)
                srcVert [i] = -1;

        // scan the input graph and create the resulting graph: begin with
        // the vertices in the collapsed groups
        cur = 0, pos = 0;
        while (cur < compNum)
        {
                // add a new vertex to the result graph
                result. addVertex ();
                // for all the vertices in this component...
                int_t posEnd = compEnds [cur];
                while (pos < posEnd)
                {
                        // take the next vertex from the component
                        int_t vertex = compVertices [pos ++];
                        // add the appropriate edges to the result graph
                        addRenumEdges (g, vertex, newNum, cur,
                                srcVert, result);
                }
                ++ cur;
        }
        // process the remaining vertices of the graph
        for (int_t vertex = 0; vertex < nVert; ++ vertex)
        {
                // debug
                if (newNum [vertex] > cur)
                        throw "DEBUG: Wrong order.";
                // if the vertex has already been processed, skip it
                if (newNum [vertex] != cur)
                        continue;
                // add the appropriate edges to the result graph
                result. addVertex ();
                addRenumEdges (g, vertex, newNum, cur, srcVert, result);
                ++ cur;
        }

        // free memory and exit
        delete [] srcVert;
        if (!newNumbers)
                delete [] newNum;
        return 0;
} /* collapseVertices */

/// A helper function for "collapseVertices2".
template <class wType, class TabSets>
inline int_t addRenumEdges2 (const diGraph<wType> &g, int_t vertex,
        const int_t *newNum, TabSets &numSets,
        int_t cur, int_t *srcVert, diGraph<wType> &result)
{
        int_t nEdges = g. countEdges (vertex);

        // add all the edges that start at this vertex
        for (int_t edge = 0; edge < nEdges; ++ edge)
        {
                // determine the dest. vertex of the edge
                int_t destNumber = newNum [g. getEdge (vertex, edge)];

                // consider all the destination vertices
                int_t destSize = (destNumber < 0) ?
                        numSets [-destNumber]. size () :
                        static_cast<int_t> (1);
                for (int_t i = 0; i < destSize; ++ i)
                {
                        // determine the consecutive destination vertex
                        int_t dest = (destNumber < 0) ?
                                numSets [-destNumber] [i] : destNumber;

                        // if this is an edge to self, then ignore it
                        if (dest == cur)
                                continue;

                        // if the edge has already been added,
                        // then skip it
                        if (srcVert [dest] == cur)
                                continue;

                        // add the edge to the result graph
                        result. addEdge (dest);
                }
        }
        return 0;
} /* addRenumEdges2 */

/// Collapses (possibly non-disjoint) subsets of vertices
/// to single vertices and creates a corresponding graph
/// in which the first vertices come from the collapsed ones.
/// The result graph must be initially empty.
template <class wType, class Table1, class Table2>
inline int_t collapseVertices2 (const diGraph<wType> &g,
        int_t compNum, Table1 &compVertices, Table2 &compEnds,
        diGraph<wType> &result)
{
        // do nothing if the input graph is empty
        int_t nVert = g. countVertices ();
        if (!nVert)
                return 0;

        // compute the new numbers of vertices: newNum [i] is the
        // number of vertex 'i' from 'g' in the resulting graph,
        // unless negative; then it points to a set of numbers,
        // with -1 meaning "not defined, yet"
        int_t *newNum = new int_t [nVert];
        for (int_t i = 0; i < nVert; ++ i)
                newNum [i] = -1;

        // sets of numbers of vertices; the numbers refering to the sets
        // begin with 2, thus the first two sets are skipped
        multitable<hashedset<int_t> > numSets;
        // the number of the set waiting to be used next
        int_t numSetCur = 2;

        int_t cur = 0; // current vertex number in the new graph
        int_t pos = 0; // position in compVertices
        while (cur < compNum)
        {
                int_t posEnd = compEnds [cur];
                while (pos < posEnd)
                {
                        int_t number = compVertices [pos ++];
                        if (newNum [number] == -1)
                                newNum [number] = cur;
                        else if (newNum [number] < 0)
                                numSets [-newNum [number]]. add (cur);
                        else
                        {
                                numSets [numSetCur]. add (newNum [number]);
                                numSets [numSetCur]. add (cur);
                                newNum [number] = -(numSetCur ++);
                        }
                }
                ++ cur;
        }
        for (int_t i = 0; i < nVert; ++ i)
        {
                if (newNum [i] == -1)
                        newNum [i] = cur ++;
        }

        // prepare a table to mark the most recent source vertex for edges:
        // srcVert [j] contains i if the edge i -> j has just been added
        int_t newVert = cur;
        int_t *srcVert = new int_t [newVert];
        for (int_t i = 0; i < newVert; ++ i)
                srcVert [i] = -1;

        // scan the input graph and create the resulting graph: begin with
        // the vertices in the collapsed groups
        cur = 0;
        pos = 0;
        while (cur < compNum)
        {
                // add a new vertex to the result graph
                result. addVertex ();

                // for all the vertices in this component...
                int_t posEnd = compEnds [cur];
                while (pos < posEnd)
                {
                        // take the next vertex from the component
                        int_t vertex = compVertices [pos ++];

                        // add the appropriate edges to the result graph
                        addRenumEdges2 (g, vertex, newNum, numSets, cur,
                                srcVert, result);
                }
                ++ cur;
        }

        // process the remaining vertices of the graph
        for (int_t vertex = 0; vertex < nVert; ++ vertex)
        {
                // debug
                if (newNum [vertex] > cur)
                        throw "DEBUG: Wrong order 2.";

                // if the vertex has already been processed, skip it
                if (newNum [vertex] != cur)
                        continue;

                // add the appropriate edges to the result graph
                result. addVertex ();
                addRenumEdges2 (g, vertex, newNum, numSets, cur,
                        srcVert, result);
                ++ cur;
        }

        // free memory and exit
        delete [] srcVert;
        delete [] newNum;
        return 0;
} /* collapseVertices2 */

/// Computes the graph that represents connections between a number
/// of the first vertices in the given graph.
/// The vertices of the result graph are the first "nVert" vertices
/// from the source graph. An edge is added to the new graph
/// iff there exists a path from one vertex to another,
/// without going through any other vertex in that set.
/// Runs DFS starting from each of the first "nVert" vertices,
/// and thus may be a little inefficient in some cases.
template <class wType>
inline int_t connectionGraph (const diGraph<wType> &g, int_t nVert,
        diGraph<wType> &result)
{
        // remember the number of vertices in the input graph
        int_t nVertG = g. countVertices ();
        if (!nVertG)
                return 0;

        // prepare a bitfield in which visited vertices will be marked
        BitField visited;
        visited. allocate (nVertG);
        visited. clearall (nVertG);

        // run DFS for each of the starting vertices
        for (int_t startVertex = 0; startVertex < nVert; ++ startVertex)
        {
                // add this vertex to the resulting graph
                result. addVertex ();

                // prepare a counter and a stack of visited vertices
                int_t nVisited = 0;
                std::stack<int_t> s_visited;

                // prepare stacks for the DFS algorithm
                std::stack<int_t> s_vertex;
                std::stack<int_t> s_edge;

                // mark the starting vertex as visited
                visited. set (startVertex);
                s_visited. push (startVertex);
                ++ nVisited;

                // use DFS to visit vertices reachable from that vertex
                int_t vertex = startVertex;
                int_t edge = 0;
                while (1)
                {
                        // go back with the recursion
                        // if all the edges have been processed
                        if (edge >= g. countEdges (vertex))
                        {
                                // if this was the top recursion level
                                // then quit
                                if (s_vertex. empty ())
                                        break;

                                // return from the recursion
                                vertex = s_vertex. top ();
                                s_vertex. pop ();
                                edge = s_edge. top ();
                                s_edge. pop ();
                                continue;
                        }

                        // take the next vertex
                        int_t next = g. getEdge (vertex, edge ++);

                        // go to the deeper recursion level if not visited
                        if (!visited. test (next))
                        {
                                // add an edge to the result if necessary
                                if (next < nVert)
                                        result. addEdge (next);

                                // store the previous variables at the stacks
                                s_vertex. push (vertex);
                                s_edge. push (edge);

                                // take the new vertex
                                vertex = next;
                                edge = 0;

                                // mark the new vertex as visited
                                visited. set (vertex);
                                s_visited. push (vertex);
                                ++ nVisited;
                        }
                }

                // if this was the last vertex then skip the rest
                if (startVertex == nVert - 1)
                        break;

                // mark each vertex as non-visited
                if (nVisited > (nVertG >> 6))
                {
                        visited. clearall (nVertG);
                }
                else
                {
                        while (!s_visited. empty ())
                        {
                                int_t vertex = s_visited. top ();
                                s_visited. pop ();
                                visited. clear (vertex);
                        }
                }
        }

        // free memory and exit
        visited. free ();
        return 0;
} /* connectionGraph */

/// Computes the period of a strongly connected graph.
/// The period of a graph is defined as the greatest common divisor
/// of the lengths of all the cycles in the graph.
/// Period 1 means that the graph is aperiodic.
/// The complexity of this operation is linear (one DFS).
template <class GraphType>
inline int_t computePeriod (const GraphType &g)
{
        // remember the number of vertices in the input graph
        int_t nVertG = g. countVertices ();
        if (!nVertG)
                return 0;

        // prepare an array to record the depth of each visited vertex
        std::vector<int_t> visited (nVertG, 0);

        // run DFS starting at the first vertex
        // prepare stacks for the DFS algorithm
        std::stack<int_t> s_vertex;
        std::stack<int_t> s_edge;

        // mark the starting vertex as visited
        visited [0] = 1;

        // use DFS to visit vertices reachable from that vertex
        int_t vertex = 0;
        int_t edge = 0;
        int_t level = 1;
        int_t period = 0;
        while (1)
        {
                // go back with the recursion
                // if all the edges have been processed
                if (edge >= g. countEdges (vertex))
                {
                        // if this was the top recursion level then quit
                        if (s_vertex. empty ())
                                break;

                        // return from the recursion
                        vertex = s_vertex. top ();
                        s_vertex. pop ();
                        edge = s_edge. top ();
                        s_edge. pop ();
                        -- level;
                        continue;
                }

                // take the next vertex
                int_t next = g. getEdge (vertex, edge ++);

                // update the GCD of the cycle lengths
                if (visited [next])
                {
                        // determine the period provided by the cycle
                        int_t newPeriod = visited [next] - level - 1;
                        if (newPeriod < 0)
                                newPeriod = -newPeriod;

                        // compute the GCD of the old and new periods
                        int_t a = newPeriod;
                        int_t b = period;
                        while (b)
                        {
                                int_t t = b;
                                b = a % b;
                                a = t;
                        }
                        period = a;

                        // if the graph turns out to be aperiodic
                        // then immediately return the result
                        if (period == 1)
                                return period;
                }

                // go to the deeper recursion level if not visited
                else
                {
                        // store the previous variables at the stacks
                        s_vertex. push (vertex);
                        s_edge. push (edge);

                        // take the new vertex
                        vertex = next;
                        edge = 0;
                        ++ level;

                        // mark the new vertex as visited
                        visited [vertex] = level;
                }
        }

        // return the computed peirod and exit
        return period;
} /* computePeriod */

/// Computes the graph that represents flow-induced relations on Morse sets.
/// The vertices of the result graph are the first "nVert" vertices
/// from the source graph. An edge is added to the new graph
/// iff there exists a path from one vertex to another.
/// Edges that come from the transitive closure are not added.
template <class wType>
inline int_t inclusionGraph (const diGraph<wType> &g, int_t nVert,
        diGraph<wType> &result)
{
        // remember the number of vertices in the input graph
        int_t nVertG = g. countVertices ();
        if (!nVertG)
                return 0;

        // mark each vertex as non-visited
        BitField visited;
        visited. allocate (nVertG);
        visited. clearall (nVertG);

        // create the sets of vertices reachable from each vertex
        BitSets lists (nVertG, nVert);

        // prepare stacks for the DFS algorithm
        std::stack<int_t> s_vertex;
        std::stack<int_t> s_edge;

        // use DFS to propagate the reachable sets
        int_t startVertex = 0;
        int_t vertex = 0;
        int_t edge = 0;
        visited. set (vertex);
        while (1)
        {
                // go back with the recursion
                // if all the edges have been processed
                if (edge >= g. countEdges (vertex))
                {
                        // if this was the top recursion level,
                        // then find another starting point or quit
                        if (s_vertex. empty ())
                        {
                                while ((startVertex < nVertG) &&
                                        (visited. test (startVertex)))
                                        ++ startVertex;
                                if (startVertex >= nVertG)
                                        break;
                                vertex = startVertex;
                                edge = 0;
                                visited. set (vertex);
                                continue;
                        }

                        // determine the previous vertex (to trace back to)
                        int_t prev = s_vertex. top ();

                        // add the list of the current vertex
                        // to the list of the previous vertex
                        // unless that was one of the first 'nVert' vertices
                        if (vertex >= nVert)
                                lists. addset (prev, vertex);

                        // return from the recursion
                        vertex = prev;
                        s_vertex. pop ();
                        edge = s_edge. top ();
                        s_edge. pop ();
                        continue;
                }

                // take the next vertex
                int_t next = g. getEdge (vertex, edge ++);

                // add the number to the list if appropriate
                if (next < nVert)
                        lists. add (vertex, next);

                // go to the deeper recursion level if vertex not visited
                if (!visited. test (next))
                {
                        // store the previous variables at the stacks
                        s_vertex. push (vertex);
                        s_edge. push (edge);

                        // take the new vertex and mark as visited
                        vertex = next;
                        edge = 0;
                        visited. set (vertex);
                }

                // add the list of the next vertex to the current one
                // if the vertex has already been visited before
                // and the vertex is not one of the first 'nVert' ones
                else if (next >= nVert)
                {
                        lists. addset (vertex, next);
                }
        }

        // create the result graph based on the lists of edges
        for (int_t vertex = 0; vertex < nVert; ++ vertex)
        {
                result. addVertex ();
                int_t edge = lists. get (vertex);
                while (edge >= 0)
                {
                        result. addEdge (edge);
                        edge = lists. get (vertex, edge + 1);
                }
        }

        // free memory and exit
        visited. free ();
        return 0;
} /* inclusionGraph */

// --------------------------------------------------

/// A more complicated version of the 'inclusionGraph' function.
/// Computes the graph that represents flow-induced relations on Morse sets.
/// The vertices of the result graph are the first "nVert" vertices
/// from the source graph. An edge is added to the new graph
/// iff there exists a path from one vertex to another.
/// Edges that come from the transitive closure are not added.
/// Records vertices along connecting orbits using operator () with the
/// following arguments: source, target, vertex.
template<class wType, class TConn>
inline int_t inclusionGraph (const diGraph<wType> &g, int_t nVert,
        diGraph<wType> &result, TConn &connections)
{
        // remember the number of vertices in the input graph
        int_t nVertG = g. countVertices ();
        if (!nVertG)
                return 0;

        // mark each vertex as non-visited
        BitField visited;
        visited. allocate (nVertG);
        visited. clearall (nVertG);

        // create the sets of vertices reachable from each vertex
        BitSets forwardlists (nVertG, nVert);

        // prepare stacks for the DFS algorithm
        std::stack<int_t> s_vertex;
        std::stack<int_t> s_edge;

        // use DFS to propagate the reachable sets
        int_t startVertex = 0;
        int_t vertex = 0;
        int_t edge = 0;
        visited. set (vertex);
        while (1)
        {
                // go back with the recursion
                // if all the edges have been processed
                if (edge >= g. countEdges (vertex))
                {
                        // if this was the top recursion level,
                        // then find another starting point or quit
                        if (s_vertex. empty ())
                        {
                                while ((startVertex < nVertG) &&
                                        (visited. test (startVertex)))
                                        ++ startVertex;
                                if (startVertex >= nVertG)
                                        break;
                                vertex = startVertex;
                                edge = 0;
                                visited. set (vertex);
                                continue;
                        }

                        // determine the previous vertex (to trace back to)
                        int_t prev = s_vertex. top ();

                        // add the list of the current vertex
                        // to the list of the previous vertex
                        // unless that was one of the first 'nVert' vertices
                        if (vertex >= nVert)
                                forwardlists. addset (prev, vertex);

                        // return from the recursion
                        vertex = prev;
                        s_vertex. pop ();
                        edge = s_edge. top ();
                        s_edge. pop ();
                        continue;
                }

                // take the next vertex
                int_t next = g. getEdge (vertex, edge ++);

                // add the number to the list if appropriate
                if (next < nVert)
                        forwardlists. add (vertex, next);

                // go to the deeper recursion level if vertex not visited
                if (!visited. test (next))
                {
                        // store the previous variables at the stacks
                        s_vertex. push (vertex);
                        s_edge. push (edge);

                        // take the new vertex and mark as visited
                        vertex = next;
                        edge = 0;
                        visited. set (vertex);
                }

                // add the list of the next vertex to the current one
                // if the vertex has already been visited before
                // and the vertex is not one of the first 'nVert' ones
                else if (next >= nVert)
                {
                        forwardlists. addset (vertex, next);
                }
        }

        // ------------------------------------------

        // create the sets of vertices that can reach each vertex
        BitSets backlists (nVertG, nVert);

        diGraph<wType> gT;
        g. transpose (gT);

        // do a simple test for debugging purposes
        if (!s_vertex. empty () || !s_edge. empty ())
                throw "DEBUG: Nonempty stacks in 'inclusionGraph'.";

        // mark all the vertices as unvisited for the backward run
        visited. clearall (nVertG);

        // use DFS to propagate the reachable sets
        startVertex = 0;
        vertex = 0;
        edge = 0;
        visited. set (vertex);
        while (1)
        {
                // go back with the recursion
                // if all the edges have been processed
                if (edge >= gT. countEdges (vertex))
                {
                        // if this was the top recursion level,
                        // then find another starting point or quit
                        if (s_vertex. empty ())
                        {
                                while ((startVertex < nVertG) &&
                                        (visited. test (startVertex)))
                                        ++ startVertex;
                                if (startVertex >= nVertG)
                                        break;
                                vertex = startVertex;
                                edge = 0;
                                visited. set (vertex);
                                continue;
                        }

                        // determine the previous vertex (to trace back to)
                        int_t prev = s_vertex. top ();

                        // add the list of the current vertex
                        // to the list of the previous vertex
                        // unless that was one of the first 'nVert' vertices
                        if (vertex >= nVert)
                                backlists. addset (prev, vertex);

                        // return from the recursion
                        vertex = prev;
                        s_vertex. pop ();
                        edge = s_edge. top ();
                        s_edge. pop ();
                        continue;
                }

                // take the next vertex
                int_t next = gT. getEdge (vertex, edge ++);

                // add the number to the list if appropriate
                if (next < nVert)
                        backlists. add (vertex, next);

                // go to the deeper recursion level if vertex not visited
                if (!visited. test (next))
                {
                        // store the previous variables at the stacks
                        s_vertex. push (vertex);
                        s_edge. push (edge);

                        // take the new vertex and mark as visited
                        vertex = next;
                        edge = 0;
                        visited. set (vertex);
                }

                // add the list of the next vertex to the current one
                // if the vertex has already been visited before
                // and the vertex is not one of the first 'nVert' ones
                else if (next >= nVert)
                {
                        backlists. addset (vertex, next);
                }
        }

        // ------------------------------------------

        // record the connections to the obtained data structure
        for (int_t v = nVert; v < nVertG; ++ v)
        {
                int_t bvertex = backlists. get (v);
                while (bvertex >= 0)
                {
                        int_t fvertex = forwardlists. get (v);
                        while (fvertex >= 0)
                        {
                                connections (bvertex, fvertex, v);
                                fvertex = forwardlists. get (v, fvertex + 1);
                        }
                        bvertex = backlists. get (v, bvertex + 1);
                }
        }

        // ------------------------------------------
        
        // create the result graph based on the lists of edges
        for (int_t vertex = 0; vertex < nVert; ++ vertex)
        {
                result. addVertex ();
                int_t edge = forwardlists. get (vertex);
                while (edge >= 0)
                {
                        result. addEdge (edge);
                        edge = forwardlists. get (vertex, edge + 1);
                }
        }

        // free memory and exit
        visited. free ();
        return 0;
} /* inclusionGraph */

// --------------------------------------------------

/// Creates the adjacency matrix of the given graph.
/// m [i] [j] is set to 1 if the graph g contains the edge i -> j,
/// using the assignment operator.
template <class wType, class matrix>
inline void graph2matrix (const diGraph<wType> &g, matrix &m)
{
        int_t nVert = g. countVertices ();
        for (int_t v = 0; v < nVert; ++ v)
        {
                int_t nEdges = g. countEdges (v);
                for (int_t e = 0; e < nEdges; ++ e)
                {
                        int_t w = g. getEdge (v, e);
                        m [v] [w] = 1;
                }
        }
        return;
} /* graph2matrix */

/// Creates a graph based on the given adjacency matrix.
/// If m [i] [j] is nonzero, then the edge i -> j is added to the graph.
/// It is assumed that the graph g is initially empty.
/// The size of the matrix (the number of vertices), n, must be given.
template <class wType, class matrix>
inline void matrix2graph (const matrix &m, int_t n, diGraph<wType> &g)
{
        for (int_t v = 0; v < n; ++ v)
        {
                g. addVertex ();
                for (int_t w = 0; w < n; ++ w)
                        if (m [v] [w])
                                g. addEdge (w);
        }
        return;
} /* matrix2graph */

// --------------------------------------------------

/// Computes the transitive closure of an acyclic graph
/// defined by its adjacency matrix, using the Warshall's algorithm:
/// S. Warshall, A theorem on Boolean matrices, J. ACM 9 (1962) 11-12.
template <class matrix>
inline void transitiveClosure (matrix &m, int_t n)
{
        for (int_t k = 0; k < n; ++ k)
        {
                for (int_t i = 0; i < n; ++ i)
                {
                        for (int_t j = 0; j < n; ++ j)
                        {
                                if (m [i] [k] && m [k] [j])
                                        m [i] [j] = 1;
                        }
                }
        }
        return;
} /* transitiveClosure */

/// Computes the transitive reduction of a CLOSED acyclic graph
/// defined by its adjacency matrix, using the algorithm by D. Gries,
/// A.J. Martin, J.L.A. van de Snepscheut and J.T. Udding, An algorithm
/// for transitive reduction of an acyclic graph, Science of Computer
/// Programming 12 (1989), 151-155.
/// WARNING: The input graph MUST BE CLOSED, use the "transitiveClosure"
/// algorithm first if this is not the case.
template <class matrix>
inline void transitiveReduction (matrix &m, int_t n)
{
        for (int_t k = n - 1; k >= 0; -- k)
        {
                for (int_t i = 0; i < n; ++ i)
                {
                        for (int_t j = 0; j < n; ++ j)
                        {
                                if (m [i] [k] && m [k] [j])
                                        m [i] [j] = 0;
                        }
                }
        }
        return;
} /* transitiveReduction */

/// Computes the transitive reduction of an arbitrary acyclic graph.
/// The output graph must be initially empty.
template <class wType>
inline void transitiveReduction (const diGraph<wType> &g,
        diGraph<wType> &gRed)
{
        int_t nVert = g. countVertices ();
        if (nVert <= 0)
                return;
        flatMatrix<char> m (nVert);
        m. clear (0);
        graph2matrix (g, m);
        transitiveClosure (m, nVert);
        transitiveReduction (m, nVert);
        matrix2graph (m, nVert, gRed);
        return;
} /* transitiveReduction */


} // namespace homology
} // namespace chomp

#endif // _CHOMP_STRUCT_DIGRAPH_H_

/// @}