RhodeCode

  ///

  /// ReverseDigraph can be used for reversing the arcs in a digraph.

  /// It conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  ///

  /// \note The \c Node and \c Arc types of this adaptor and the adapted

  /// digraph are convertible to each other.

  template<typename DGR>

#ifdef DOXYGEN

  /// shown in the subdigraph. The arcs that are incident to hidden

  /// nodes are also filtered out.

  /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  /// \tparam NF The type of the node filter map.

  /// It must be a \c bool (or convertible) node map of the

  /// adapted digraph. The default type is

  /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>".

  /// \tparam AF The type of the arc filter map.

  /// shown in the subgraph. The edges that are incident to hidden

  /// nodes are also filtered out.

  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

  ///

  /// The adapted graph can also be modified through this adaptor

  /// by adding or removing nodes or edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted graph.

  /// It must conform to the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam NF The type of the node filter map.

  /// It must be a \c bool (or convertible) node map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

  /// \tparam EF The type of the edge filter map.

  /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph

  /// "Digraph" concept or the \ref concepts::Graph "Graph" concept

  /// depending on the \c GR template parameter.

  ///

  /// The adapted (di)graph can also be modified through this adaptor

  /// by adding or removing nodes or arcs/edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted digraph or graph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept

  /// or the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam NF The type of the node filter map.

  /// It must be a \c bool (or convertible) node map of the

  /// adapted (di)graph. The default type is

  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".

  /// the arcs. Only the arcs with \c true filter value are shown in the

  /// subdigraph. This adaptor conforms to the \ref concepts::Digraph

  /// "Digraph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  /// \tparam AF The type of the arc filter map.

  /// It must be a \c bool (or convertible) arc map of the

  /// adapted digraph. The default type is

  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".

  ///

  /// the edges. Only the edges with \c true filter value are shown in the

  /// subgraph. This adaptor conforms to the \ref concepts::Graph

  /// "Graph" concept.

  ///

  /// The adapted graph can also be modified through this adaptor

  /// by adding or removing nodes or edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted graph.

  /// It must conform to the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam EF The type of the edge filter map.

  /// It must be a \c bool (or convertible) edge map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

  ///

  /// graph. All arcs of the underlying digraph are showed in the

  /// adaptor as an edge (and also as a pair of arcs, of course).

  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.

  ///

  /// The adapted digraph can also be modified through this adaptor

  /// by adding or removing nodes or edges, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It can also be specified to be \c const.

  ///

  /// \note The \c Node type of this adaptor and the adapted digraph are

  /// convertible to each other, moreover the \c Edge type of the adaptor

  /// and the \c Arc type of the adapted digraph are also convertible to

  /// each other.

  /// The arcs can be easily reversed by the \c reverseArc() member function

  /// of the adaptor.

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// The adapted graph can also be modified through this adaptor

  /// by adding or removing nodes or arcs, unless the \c GR template

  /// parameter is set to be \c const.

  ///

  /// \tparam GR The type of the adapted graph.

  /// It must conform to the \ref concepts::Graph "Graph" concept.

  /// It can also be specified to be \c const.

  /// \tparam DM The type of the direction map.

  /// It must be a \c bool (or convertible) edge map of the

  /// adapted graph. The default type is

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".

  ///

  /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so

  /// called residual digraph.

  /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,

  /// multiplicities are counted, i.e. the adaptor has exactly

  /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel

  /// arcs).

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It is implicitly \c const.

  /// \tparam CM The type of the capacity map.

  /// It must be an arc map of some numerical type, which defines

  /// the capacities in the flow problem. It is implicitly \c const.

  /// The default type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

  ///

  /// The aim of this class is running an algorithm with respect to node

  /// costs or capacities if the algorithm considers only arc costs or

  /// capacities directly.

  /// In this case you can use \c SplitNodes adaptor, and set the node

  /// costs/capacities of the original digraph to the \e bind \e arcs

  /// in the adaptor.

  ///

  /// \tparam DGR The type of the adapted digraph.

  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

  /// It is implicitly \c const.

  ///

  /// \note The \c Node type of this adaptor is converible to the \c Node

  /// type of the adapted digraph.

  template <typename DGR>

#ifdef DOXYGEN

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    ///Runs the algorithm to visit all nodes in the digraph.

    ///

    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.

    ///\code

    ///  b.init();

    ///  for (NodeIt n(gr); n != INVALID; ++n) {

    ///    if (!b.reached(n)) {

    ///      b.addSource(n);

    ///      b.start();

        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);

      if (Base::_di)

        *Base::_di = alg.dist(t);

      return alg.reached(t);

    }

    ///Runs BFS algorithm to visit all nodes in the digraph.

    void run()

    {

      run(INVALID);

    }

    template<class T>

    struct SetPredMapBase : public Base {

      typedef T PredMap;

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    /// \brief Runs the algorithm to visit all nodes in the digraph.

    ///

    ///

    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.

    ///\code

    ///  b.init();

    ///  for (NodeIt n(gr); n != INVALID; ++n) {

    ///    if (!b.reached(n)) {

    ///      b.addSource(n);

    ///      b.start();

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    ///Runs the algorithm to visit all nodes in the digraph.

    ///

    ///\note <tt>d.run()</tt> is just a shortcut of the following code.

    ///\code

    ///  d.init();

    ///  for (NodeIt n(digraph); n != INVALID; ++n) {

    ///    if (!d.reached(n)) {

    ///      d.addSource(n);

    ///      d.start();

        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);

      if (Base::_di)

        *Base::_di = alg.dist(t);

      return alg.reached(t);

      }

    ///Runs DFS algorithm to visit all nodes in the digraph.

    void run()

    {

      run(INVALID);

    }

    template<class T>

    struct SetPredMapBase : public Base {

      typedef T PredMap;

      init();

      addSource(s);

      start(t);

      return reached(t);

    }

    /// \brief Runs the algorithm to visit all nodes in the digraph.

    ///

    /// \note <tt>d.run()</tt> is just a shortcut of the following code.

    ///\code

    ///   d.init();

    ///   for (NodeIt n(digraph); n != INVALID; ++n) {

    ///     if (!d.reached(n)) {

    ///       d.addSource(n);

    ///       d.start();

#endif

  class Dijkstra {

  public:

    ///The type of the digraph the algorithm runs on.

    typedef typename TR::Digraph Digraph;

    ///The type of the arc lengths.

    ///The type of the map that stores the arc lengths.

    typedef typename TR::LengthMap LengthMap;

    ///\brief The type of the map that stores the predecessor arcs of the

    ///shortest paths.

    typedef typename TR::PredMap PredMap;

    ///The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

    ///The type of the map that indicates which nodes are processed.

  /// iterators) works equivalently as in the original graph.

  ///

  /// This implementation is based on doubly-linked lists, from each

  /// node the outgoing and the incoming arcs make up lists, therefore

  /// one arc can be erased in constant time. It also makes possible,

  /// that node can be removed from the underlying graph, in this case

  /// all arcs incident to the given node is erased from the arc set.

  ///

  /// \param GR The type of the graph which shares its node set with

  /// this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  template <typename GR>

  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {

    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  /// works equivalently as in the original graph.

  ///

  /// This implementation is based on doubly-linked lists, from each

  /// node the incident edges make up lists, therefore one edge can be

  /// erased in constant time. It also makes possible, that node can

  /// be removed from the underlying graph, in this case all edges

  /// incident to the given node is erased from the arc set.

  ///

  /// \param GR The type of the graph which shares its node set

  /// with this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  template <typename GR>

  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {

    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  ///

  /// This implementation is slightly faster than the \c ListArcSet,

  /// because it uses continuous storage for arcs and it uses just

  /// single-linked lists for enumerate outgoing and incoming

  /// arcs. Therefore the arcs cannot be erased from the arc sets.

  ///

  /// \warning If a node is erased from the underlying graph and this

  /// node is the source or target of one arc in the arc set, then

  /// the arc set is invalidated, and it cannot be used anymore. The

  /// validity can be checked with the \c valid() member function.

  template <typename GR>

  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {

    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  ///  concept.

  ///

  /// This implementation is slightly faster than the \c ListEdgeSet,

  /// because it uses continuous storage for edges and it uses just

  /// single-linked lists for enumerate incident edges. Therefore the

  /// edges cannot be erased from the edge sets.

  ///

  /// \warning If a node is erased from the underlying graph and this

  /// node is incident to one edge in the edge set, then the edge set

  /// is invalidated, and it cannot be used anymore. The validity can

  /// be checked with the \c valid() member function.

  template <typename GR>

  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {

    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

  /// This class is completely static and it needs constant memory space.

  /// Thus you can neither add nor delete nodes or arcs, however

  /// the structure can be resized using resize().

  ///

  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \note FullDigraph and FullGraph classes are very similar,

  /// but there are two differences. While this class conforms only

  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph

  /// conforms to the \ref concepts::Graph "Graph" concept,

  /// moreover FullGraph does not contain a loop for each

  /// node as this class does.

  ///

  /// \sa FullGraph

      Parent::notifier(Arc()).build();

    }

    /// \brief Returns the node with the given index.

    ///

    /// Returns the node with the given index. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// \sa index()

    Node operator()(int ix) const { return Parent::operator()(ix); }

    /// \brief Returns the index of the given node.

    ///

    /// Returns the index of the given node. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// \sa operator()()

    static int index(const Node& node) { return Parent::index(node); }

    /// \brief Returns the arc connecting the given nodes.

    ///

    /// Returns the arc connecting the given nodes.

    Arc arc(Node u, Node v) const {

      return Parent::arc(u, v);

  /// This class is completely static and it needs constant memory space.

  /// Thus you can neither add nor delete nodes or edges, however

  /// the structure can be resized using resize().

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \note FullDigraph and FullGraph classes are very similar,

  /// but there are two differences. While FullDigraph

  /// conforms only to the \ref concepts::Digraph "Digraph" concept,

  /// this class conforms to the \ref concepts::Graph "Graph" concept,

  /// moreover this class does not contain a loop for each

  /// node as FullDigraph does.

  ///

  /// \sa FullDigraph

      Parent::notifier(Arc()).build();

    }

    /// \brief Returns the node with the given index.

    ///

    /// Returns the node with the given index. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// \sa index()

    Node operator()(int ix) const { return Parent::operator()(ix); }

    /// \brief Returns the index of the given node.

    ///

    /// Returns the index of the given node. Since this structure is 

    /// completely static, the nodes can be indexed with integers from

    /// the range <tt>[0..nodeNum()-1]</tt>.

    /// \sa operator()()

    static int index(const Node& node) { return Parent::index(node); }

    /// \brief Returns the arc connecting the given nodes.

    ///

    /// Returns the arc connecting the given nodes.

    Arc arc(Node s, Node t) const {

      return Parent::arc(s, t);

  ///     val[graph(i, j)] = i + j;

  ///   }

  /// }

  ///\endcode

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  class GridGraph : public ExtendedGridGraphBase {

    typedef ExtendedGridGraphBase Parent;

  public:

    /// \brief Map to get the indices of the nodes as \ref dim2::Point

    /// "dim2::Point<int>".

    ///

  /// This class is completely static and it needs constant memory space.

  /// Thus you can neither add nor delete nodes or edges, however 

  /// the structure can be resized using resize().

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \note The type of the indices is chosen to \c int for efficiency

  /// reasons. Thus the maximum dimension of this implementation is 26

  /// (assuming that the size of \c int is 32 bit).

  class HypercubeGraph : public ExtendedHypercubeGraphBase {

    typedef ExtendedHypercubeGraphBase Parent;

  public:

  ///implementation based on linked lists that are stored in

  ///\c std::vector structures.

  ///

  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"

  ///and it also provides several useful additional functionalities.

  ///Most of its member functions and nested classes are documented

  ///only in the concept class.

  ///

  ///\sa concepts::Digraph

  ///\sa ListGraph

  class ListDigraph : public ExtendedListDigraphBase {

    typedef ExtendedListDigraphBase Parent;

  private:

    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.

    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};

    ///and target node \c t.

    ///\return The new arc.

    Arc addArc(Node s, Node t) {

      return Parent::addArc(s, t);

    }

    ///\brief Erase a node from the digraph.

    ///

    void erase(Node n) { Parent::erase(n); }

    ///\brief Erase an arc from the digraph.

    ///

    ///This function erases the given arc from the digraph.

    void erase(Arc a) { Parent::erase(a); }

    /// Node validity check

    /// This function gives back \c true if the given node is valid,

    /// i.e. it is a real node of the digraph.

    ///

    /// \warning A removed node could become valid again if new nodes are

      changeTarget(a,v);

      return v;

    }

    ///Clear the digraph.

    ///This function erases all nodes and arcs from the digraph.

    ///

    void clear() {

      Parent::clear();

    }

    /// Reserve memory for nodes.

    /// Using this function, it is possible to avoid superfluous memory

    /// allocation: if you know that the digraph you want to build will

  ///implementation based on linked lists that are stored in

  ///\c std::vector structures.

  ///

  ///This type fully conforms to the \ref concepts::Graph "Graph concept"

  ///and it also provides several useful additional functionalities.

  ///Most of its member functions and nested classes are documented

  ///only in the concept class.

  ///

  ///\sa concepts::Graph

  ///\sa ListDigraph

  class ListGraph : public ExtendedListGraphBase {

    typedef ExtendedListGraphBase Parent;

  private:

    /// Graphs are \e not copy constructible. Use GraphCopy instead.

    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};

    /// node \c v.

    /// \return The new edge.

    Edge addEdge(Node u, Node v) {

      return Parent::addEdge(u, v);

    }

    ///\brief Erase a node from the graph.

    ///

    void erase(Node n) { Parent::erase(n); }

    ///\brief Erase an edge from the graph.

    ///

    /// This function erases the given edge from the graph.

    void erase(Edge e) { Parent::erase(e); }

    /// Node validity check

    /// This function gives back \c true if the given node is valid,

    /// i.e. it is a real node of the graph.

    ///

    /// \warning A removed node could become valid again if new nodes are

    /// added to the graph.

      }

      erase(b);

    }

    ///Clear the graph.

    ///This function erases all nodes and arcs from the graph.

    ///

    void clear() {

      Parent::clear();

    }

    /// Reserve memory for nodes.

    /// Using this function, it is possible to avoid superfluous memory

    /// allocation: if you know that the graph you want to build will

  ///that it does not support node and arc deletion 

  ///(except for the Snapshot feature).

  ///

  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"

  ///and it also provides some additional functionalities.

  ///Most of its member functions and nested classes are documented

  ///only in the concept class.

  ///

  ///\sa concepts::Digraph

  ///\sa SmartGraph

  class SmartDigraph : public ExtendedSmartDigraphBase {

    typedef ExtendedSmartDigraphBase Parent;

  private:

    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.

    SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};

  /// that it does not support node and edge deletion 

  /// (except for the Snapshot feature).

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept"

  /// and it also provides some additional functionalities.

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \sa concepts::Graph

  /// \sa SmartDigraph

  class SmartGraph : public ExtendedSmartGraphBase {

    typedef ExtendedSmartGraphBase Parent;

  private:

    /// Graphs are \e not copy constructible. Use GraphCopy instead.

    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};

  /// using the corresponding \ref index() or \ref concepts::Digraph::id()

  /// "id()" function. A node or arc with a certain index can be obtained

  /// using node() or arc().

  ///

  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \sa concepts::Digraph

  class StaticDigraph : public ExtendedStaticDigraphBase {

  public:

    typedef ExtendedStaticDigraphBase Parent;

  public: