RhodeCode

      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)

        : Parent(*adaptor._digraph) {}

      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)

        : Parent(*adaptor._digraph, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

        return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }

    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;

    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }

  protected:

    UndirectorBase() : _digraph(0) {}

    DGR* _digraph;

    void initialize(DGR& digraph) {

      _digraph = &digraph;

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Adaptor class for viewing a digraph as an undirected graph.

  ///

  /// Undirector adaptor can be used for viewing a digraph as an undirected

  /// 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

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\ingroup graph_concepts

///\file

///\brief The concept of graph components.

#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H

#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H

#include <lemon/core.h>

#include <lemon/concepts/maps.h>

#include <lemon/bits/alteration_notifier.h>

namespace lemon {

  namespace concepts {

    ///

    ///

    /// \note This class is a template class so that we can use it to

#ifndef DOXYGEN

    template <char sel = '0'>

#endif

    class GraphItem {

    public:

      /// \brief Default constructor.

      ///

      /// \warning The default constructor is not required to set

      /// the item to some well-defined value. So you should consider it

      /// as uninitialized.

      GraphItem() {}

      /// \brief Copy constructor.

      ///

      /// Copy constructor.

      ///

      /// \sa Invalid for more details.

      GraphItem(Invalid) {}

      ///

      /// \brief Equality operator.

      ///

      /// \brief Inequality operator.

      ///

      ///

      ///

      /// \note This operator only have to define some strict ordering of

      /// the items; this order has nothing to do with the iteration

      /// ordering of the items.

      template<typename _GraphItem>

      struct Constraints {

        void constraints() {

          _GraphItem i1;

          _GraphItem i2 = i1;

          _GraphItem i3 = INVALID;

          i1 = i2 = i3;

          bool b;

          b = (ia == ib) && (ia != ib);

          b = (ia == INVALID) && (ib != INVALID);

          b = (ia < ib);

        }

        const _GraphItem &ia;

        const _GraphItem &ib;

      };

    };

    ///

    class BaseDigraphComponent {

    public:

      typedef BaseDigraphComponent Digraph;

      /// \brief Node class of the digraph.

      ///

      typedef GraphItem<'n'> Node;

      /// \brief Arc class of the digraph.

      ///

      ///

      ///

      ///

      Node oppositeNode(const Node&, const Arc&) const {

        return INVALID;

      }

      template <typename _Digraph>

      struct Constraints {

        typedef typename _Digraph::Node Node;

        typedef typename _Digraph::Arc Arc;

        void constraints() {

          checkConcept<GraphItem<'n'>, Node>();

          checkConcept<GraphItem<'a'>, Arc>();

          {

            Node n;

            Arc e(INVALID);

            n = digraph.source(e);

            n = digraph.target(e);

            n = digraph.oppositeNode(n, e);

          }

        }

        const _Digraph& digraph;

      };

    };

    ///

    class BaseGraphComponent : public BaseDigraphComponent {

    public:

      typedef BaseDigraphComponent::Node Node;

      typedef BaseDigraphComponent::Arc Arc;

      ///

      public:

        /// \brief Default constructor.

        ///

        /// \warning The default constructor is not required to set

        /// the item to some well-defined value. So you should consider it

        /// as uninitialized.

        Edge() {}

        /// \brief Copy constructor.

        ///

        /// Copy constructor.

        ///

        /// \sa Invalid for more details.

        Edge(Invalid) {}

        ///

        /// Besides the core graph item functionality each arc should

        /// be convertible to the represented edge.

        Edge(const Arc&) {}

        ///

        /// Besides the core graph item functionality each arc should

        /// be convertible to the represented edge.

        Edge& operator=(const Arc&) { return *this; }

      };

      ///

      /// Returns the direction of the arc. Each arc represents an

      /// edge with a direction. It gives back the

      /// direction.

      bool direction(const Arc&) const { return true; }

      ///

      template <typename _Graph>

      struct Constraints {

        typedef typename _Graph::Node Node;

        typedef typename _Graph::Arc Arc;

        typedef typename _Graph::Edge Edge;

        void constraints() {

          checkConcept<BaseDigraphComponent, _Graph>();

          {

            Node n;

            Edge ue(INVALID);

            Arc e;

            n = graph.u(ue);

            n = graph.v(ue);

            e = graph.direct(ue, true);

            e = graph.direct(ue, n);

            e = graph.oppositeArc(e);

            ue = e;

            bool d = graph.direction(e);

            ignore_unused_variable_warning(d);

          }

        }

        const _Graph& graph;

      };

    };

    ///

    template <typename BAS = BaseDigraphComponent>

    class IDableDigraphComponent : public BAS {

    public:

      typedef BAS Base;

      typedef typename Base::Node Node;

      typedef typename Base::Arc Arc;

      ///

      ///

      ///

      ///

      ///

      ///

      template <typename _Digraph>

      struct Constraints {

        void constraints() {

          checkConcept<Base, _Digraph >();

          typename _Digraph::Node node;

          int nid = digraph.id(node);

          nid = digraph.id(node);

          node = digraph.nodeFromId(nid);

          typename _Digraph::Arc arc;

          int eid = digraph.id(arc);

          eid = digraph.id(arc);

          arc = digraph.arcFromId(eid);

          nid = digraph.maxNodeId();

          ignore_unused_variable_warning(nid);

          eid = digraph.maxArcId();

          ignore_unused_variable_warning(eid);

        }

        const _Digraph& digraph;

      };

    };

    ///

    template <typename BAS = BaseGraphComponent>

    class IDableGraphComponent : public IDableDigraphComponent<BAS> {

    public:

      typedef BAS Base;

      typedef typename Base::Edge Edge;

      using IDableDigraphComponent<Base>::id;

      ///

      ///

      ///

      template <typename _Graph>

      struct Constraints {

        void constraints() {

          checkConcept<IDableDigraphComponent<Base>, _Graph >();

          typename _Graph::Edge edge;

          int ueid = graph.id(edge);

          ueid = graph.id(edge);

          edge = graph.edgeFromId(ueid);

          ueid = graph.maxEdgeId();

          ignore_unused_variable_warning(ueid);

        }

        const _Graph& graph;

      };

    };

    ///

    template <typename GR, typename Item>

    class GraphItemIt : public Item {

    public:

      /// \brief Default constructor.

      ///

      GraphItemIt() {}

      /// \brief Copy constructor.

      ///

      /// Copy constructor.

      ///

      ///

      /// \sa Invalid for more details.

      GraphItemIt(Invalid) {}

      ///

      ///

      GraphItemIt& operator++() { return *this; }

      /// \brief Equality operator

      ///

      /// Two iterators are equal if and only if they point to the

      /// same object or both are invalid.

      bool operator==(const GraphItemIt&) const { return true;}

      /// \brief Inequality operator

      ///

      bool operator!=(const GraphItemIt&) const { return true;}

      template<typename _GraphItemIt>

      struct Constraints {

        void constraints() {

          _GraphItemIt it1(g);

          _GraphItemIt it2;

          it2 = ++it1;

          ++it2 = it1;

          ++(++it1);

          Item bi = it1;

          bi = it2;

        }

      };

    };

    ///

    template <typename GR,

              typename Item = typename GR::Arc,

              typename Base = typename GR::Node,

              char sel = '0'>

    class GraphIncIt : public Item {

    public:

      /// \brief Default constructor.

      ///

      GraphIncIt() {}

      /// \brief Copy constructor.

      ///

      /// Copy constructor.

      ///

      ///

      /// \sa Invalid for more details.

      GraphIncIt(Invalid) {}

      ///

      ///

      GraphIncIt& operator++() { return *this; }

      /// \brief Equality operator

      ///

      /// Two iterators are equal if and only if they point to the

      /// same object or both are invalid.

      bool operator==(const GraphIncIt&) const { return true;}

      /// \brief Inequality operator

      ///

      bool operator!=(const GraphIncIt&) const { return true;}

      template <typename _GraphIncIt>

      struct Constraints {

        void constraints() {

          checkConcept<GraphItem<sel>, _GraphIncIt>();

          _GraphIncIt it1(graph, node);

          _GraphIncIt it2;

          it2 = ++it1;

          ++it2 = it1;

          ++(++it1);

          Item e = it1;

          e = it2;

        }

      };

    };

    ///

    /// This concept is part of the Digraph concept.

    template <typename BAS = BaseDigraphComponent>

    class IterableDigraphComponent : public BAS {

    public:

      typedef BAS Base;

      typedef typename Base::Node Node;

      typedef typename Base::Arc Arc;

      typedef IterableDigraphComponent Digraph;

      /// \name Base iteration

      ///

      ///

      /// @{

      ///

      void first(Node&) const {}

      ///

      void next(Node&) const {}

      ///

      void first(Arc&) const {}

      ///

      void next(Arc&) const {}

      ///

      void firstIn(Arc&, const Node&) const {}

      ///

      void nextIn(Arc&) const {}

      /// given node.

      void firstOut(Arc&, const Node&) const {}

      ///

      void nextOut(Arc&) const {}

      /// @}

      /// \name Class based iteration

      ///

      ///

      /// @{

      /// \brief This iterator goes through each node.

      ///

      /// This iterator goes through each node.

      ///

      typedef GraphItemIt<Digraph, Node> NodeIt;

      ///

      ///

      typedef GraphItemIt<Digraph, Arc> ArcIt;

      /// \brief This iterator goes trough the incoming arcs of a node.

      ///

      /// of a digraph.

      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;

      /// \brief This iterator goes trough the outgoing arcs of a node.

      ///

      /// This iterator goes trough the \e outgoing arcs of a certain node

      /// of a digraph.

      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;

      /// \brief The base node of the iterator.

      ///

      Node baseNode(const InArcIt&) const { return INVALID; }

      /// \brief The running node of the iterator.

      ///

      Node runningNode(const InArcIt&) const { return INVALID; }

      /// \brief The base node of the iterator.

      ///

      Node baseNode(const OutArcIt&) const { return INVALID; }

      /// \brief The running node of the iterator.

      ///

      Node runningNode(const OutArcIt&) const { return INVALID; }

      /// @}

      template <typename _Digraph>

      struct Constraints {

        void constraints() {

          checkConcept<Base, _Digraph>();

          {

            typename _Digraph::Node node(INVALID);

            typename _Digraph::Arc arc(INVALID);

            {

              digraph.first(node);

              digraph.next(node);

            }

            {

              digraph.first(arc);

              digraph.next(arc);

            }

            {

              digraph.firstIn(arc, node);

              digraph.nextIn(arc);

            }

            {

              digraph.firstOut(arc, node);

              digraph.nextOut(arc);

            }

          }

          {

            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,

              typename _Digraph::ArcIt >();

            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,

              typename _Digraph::NodeIt >();

            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,

              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();

            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,

              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();

            typename _Digraph::Node n;

            ignore_unused_variable_warning(n);

          }

        }