RhodeCode

  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

  subDigraph(const Digraph& digraph,

             const NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

  subDigraph(const Digraph& digraph,

             NodeFilterMap& nfm, const ArcFilterMap& afm) {

    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>

  subDigraph(const Digraph& digraph,

             const NodeFilterMap& nfm, const ArcFilterMap& afm) {

    return SubDigraph<const Digraph, const NodeFilterMap,

      const ArcFilterMap>(digraph, nfm, afm);

  }

  class SubGraphBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase()

      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

      _node_filter_map=&node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

      _edge_filter_map=&edge_filter_map;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    void first(Node& i) const {

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, typename Parent::

                             template EdgeMap<Value> > MapParent;

      EdgeMap(const Adaptor& adaptor)

        : MapParent(adaptor) {}

      EdgeMap(const Adaptor& adaptor, const Value& value)

        : MapParent(adaptor, value) {}

    private:

      EdgeMap& operator=(const EdgeMap& cmap) {

        return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        MapParent::operator=(cmap);

        return *this;

      }

    };

  };

    : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

    SubGraphBase() : Parent(),

                     _node_filter_map(0), _edge_filter_map(0) { }

    void setNodeFilterMap(NodeFilterMap& node_filter_map) {

      _node_filter_map=&node_filter_map;

    }

    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {

      _edge_filter_map=&edge_filter_map;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    void first(Node& i) const {

      Parent::first(i);

      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);

    }

    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }

    int id(const Node &n) const { return _digraph->id(n); }

    int id(const Arc &a) const {

      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);

    }

    int id(const Edge &e) const { return _digraph->id(e); }

    int maxNodeId() const { return _digraph->maxNodeId(); }

    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }

    int maxEdgeId() const { return _digraph->maxArcId(); }

    Node addNode() { return _digraph->addNode(); }

    Edge addEdge(const Node& u, const Node& v) {

      return _digraph->addArc(u, v);

    }

    void erase(const Node& i) { _digraph->erase(i); }

    void erase(const Edge& i) { _digraph->erase(i); }

    void clear() { _digraph->clear(); }

    typedef NodeNumTagIndicator<Digraph> NodeNumTag;

    typedef ArcNumTagIndicator<Digraph> ArcNumTag;

    int arcNum() const { return 2 * _digraph->arcNum(); }

    typedef ArcNumTag EdgeNumTag;

    int edgeNum() const { return _digraph->arcNum(); }

    typedef FindArcTagIndicator<Digraph> FindArcTag;

    Arc findArc(Node s, Node t, Arc p = INVALID) const {

      if (p == INVALID) {

        Edge arc = _digraph->findArc(s, t);

        if (arc != INVALID) return direct(arc, true);

        arc = _digraph->findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else if (direction(p)) {

        Edge arc = _digraph->findArc(s, t, p);

        if (arc != INVALID) return direct(arc, true);

        arc = _digraph->findArc(t, s);

        if (arc != INVALID) return direct(arc, false);

      } else {

        Edge arc = _digraph->findArc(t, s, p);

        if (arc != INVALID) return direct(arc, false);

      }

      return INVALID;

    }

    typedef FindArcTag FindEdgeTag;

    Edge findEdge(Node s, Node t, Edge p = INVALID) const {

      if (s != t) {

        if (p == INVALID) {

          Edge arc = _digraph->findArc(s, t);

          if (arc != INVALID) return arc;

          arc = _digraph->findArc(t, s);

          if (arc != INVALID) return arc;

          Edge arc = _digraph->findArc(s, t, p);

          if (arc != INVALID) return arc;

          arc = _digraph->findArc(t, s);

          if (arc != INVALID) return arc;

        } else {

          Edge arc = _digraph->findArc(t, s, p);

          if (arc != INVALID) return arc;

        }

      } else {

        return _digraph->findArc(s, t, p);

      }

      return INVALID;

    }

  private:

    template <typename _Value>

    class ArcMapBase {

    private:

      typedef typename Digraph::template ArcMap<_Value> MapImpl;

    public:

      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;

      typedef _Value Value;

      typedef Arc Key;

      ArcMapBase(const Adaptor& adaptor) :

        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}

      ArcMapBase(const Adaptor& adaptor, const Value& v)

        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}

      void set(const Arc& a, const Value& v) {

        if (direction(a)) {

          _forward.set(a, v);

        } else {

          _backward.set(a, v);

        }

      }

        if (direction(a)) {

          return _forward[a];

        } else {

          return _backward[a];

        }

      }

        if (direction(a)) {

          return _forward[a];

        } else {

          return _backward[a];

        }

      }

    protected:

      MapImpl _forward, _backward;

    };

  public:

    template <typename _Value>

    class NodeMap : public Digraph::template NodeMap<_Value> {

    public:

      typedef _Value Value;

      typedef typename Digraph::template NodeMap<Value> Parent;

      explicit NodeMap(const Adaptor& adaptor)

        : Parent(*adaptor._digraph) {}

      NodeMap(const Adaptor& adaptor, const _Value& value)

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

    private:

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class ArcMap

      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >

    {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;

        : Parent(adaptor) {}

      ArcMap(const Adaptor& adaptor, const Value& value)

        : Parent(adaptor, value) {}

    private:

      ArcMap& operator=(const ArcMap& cmap) {

        return operator=<ArcMap>(cmap);

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename _Value>

    class EdgeMap : public Digraph::template ArcMap<_Value> {

    public:

      typedef _Value Value;

      typedef typename Digraph::template ArcMap<Value> Parent;

      explicit EdgeMap(const Adaptor& adaptor)

        : Parent(*adaptor._digraph) {}

      EdgeMap(const Adaptor& adaptor, const Value& 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<Digraph, Node>::ItemNotifier NodeNotifier;

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

  protected:

    UndirectorBase() : _digraph(0) {}

    Digraph* _digraph;

    void setDigraph(Digraph& digraph) {

      _digraph = &digraph;

    }

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief Undirect the graph

  ///

  /// This adaptor makes an undirected graph from a directed

  /// graph. All arcs of the underlying digraph will be showed in the

  /// adaptor as an edge. The Orienter adaptor is conform to the \ref

  /// concepts::Graph "Graph concept".

  ///

  /// \tparam _Digraph It must be conform to the \ref

  /// concepts::Digraph "Digraph concept". The type can be specified

  /// to const.

    /// \brief Constructor

    ///

    /// Creates a undirected graph from the given digraph

    Undirector(_Digraph& digraph) {

      setDigraph(digraph);

    }

    /// \brief ArcMap combined from two original ArcMap

    ///

    /// This class adapts two original digraph ArcMap to

    /// get an arc map on the undirected graph.

    template <typename _ForwardMap, typename _BackwardMap>

    class CombinedArcMap {

    public:

      typedef _ForwardMap ForwardMap;

      typedef _BackwardMap BackwardMap;

      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;

      typedef typename ForwardMap::Value Value;

      typedef typename Parent::Arc Key;

      /// \brief Constructor

      ///

      /// Constructor

      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)

        : _forward(&forward), _backward(&backward) {}

      /// \brief Sets the value associated with a key.

      ///

      /// Sets the value associated with a key.

      void set(const Key& e, const Value& a) {

        if (Parent::direction(e)) {

          _forward->set(e, a);

        } else {

          _backward->set(e, a);

        }

      }

      /// \brief Returns the value associated with a key.

      ///

      /// Returns the value associated with a key.

        if (Parent::direction(e)) {

          return (*_forward)[e];

        } else {

          return (*_backward)[e];

        }

      }

      /// \brief Returns the value associated with a key.

      ///

      /// Returns the value associated with a key.

        if (Parent::direction(e)) {

          return (*_forward)[e];

        } else {

          return (*_backward)[e];

        }

      }

    protected:

      ForwardMap* _forward;

      BackwardMap* _backward;

    };

    /// \brief Just gives back a combined arc map

    ///

    /// Just gives back a combined arc map

    template <typename ForwardMap, typename BackwardMap>

    static CombinedArcMap<ForwardMap, BackwardMap>

    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {

      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);

    }

    template <typename ForwardMap, typename BackwardMap>

      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);

    }

    void nextOut(Arc& i) const {

      bool d = (*_direction)[i];

      _graph->nextInc(i, d);

      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);

    }

    Node source(const Arc& e) const {

      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);

    }

    Node target(const Arc& e) const {

      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);

    }

    typedef NodeNumTagIndicator<Graph> NodeNumTag;

    int nodeNum() const { return _graph->nodeNum(); }

    typedef EdgeNumTagIndicator<Graph> ArcNumTag;

    int arcNum() const { return _graph->edgeNum(); }

    typedef FindEdgeTagIndicator<Graph> FindArcTag;

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) const {

        arc = _graph->findEdge(u, v, arc);

      }

      return arc;

    }

    Node addNode() {

      return Node(_graph->addNode());

    }

    Arc addArc(const Node& u, const Node& v) {

      return arc;

    }

    void erase(const Node& i) { _graph->erase(i); }

    void erase(const Arc& i) { _graph->erase(i); }

    void clear() { _graph->clear(); }

    int id(const Node& v) const { return _graph->id(v); }

    int id(const Arc& e) const { return _graph->id(e); }

    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }

    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }

    int maxNodeId() const { return _graph->maxNodeId(); }

    int maxArcId() const { return _graph->maxEdgeId(); }

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

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

    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }

    template <typename _Value>

      return Node(n, false);

    }

    static Arc arc(const DigraphNode& n) {

      return Arc(n);

    }

    static Arc arc(const DigraphArc& e) {

      return Arc(e);

    }

    typedef True NodeNumTag;

    int nodeNum() const {

      return  2 * countNodes(*_digraph);

    }

    typedef True ArcNumTag;

    int arcNum() const {

      return countArcs(*_digraph) + countNodes(*_digraph);

    }

    typedef True FindArcTag;

    Arc findArc(const Node& u, const Node& v,

                const Arc& prev = INVALID) const {

        }

      }

      return INVALID;

    }

  private:

    template <typename _Value>

    class NodeMapBase

      : public MapTraits<typename Parent::template NodeMap<_Value> > {

      typedef typename Parent::template NodeMap<_Value> NodeImpl;

    public:

      typedef Node Key;

      typedef _Value Value;

      NodeMapBase(const Adaptor& adaptor)

        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}

      NodeMapBase(const Adaptor& adaptor, const Value& value)

        : _in_map(*adaptor._digraph, value),

          _out_map(*adaptor._digraph, value) {}

      void set(const Node& key, const Value& val) {

        if (Adaptor::inNode(key)) { _in_map.set(key, val); }

        else {_out_map.set(key, val); }

      }

        if (Adaptor::inNode(key)) { return _in_map[key]; }

        else { return _out_map[key]; }

      }

        if (Adaptor::inNode(key)) { return _in_map[key]; }

        else { return _out_map[key]; }

      }

    private:

      NodeImpl _in_map, _out_map;

    };

    template <typename _Value>

    class ArcMapBase

      : public MapTraits<typename Parent::template ArcMap<_Value> > {

      typedef typename Parent::template ArcMap<_Value> ArcImpl;

      typedef typename Parent::template NodeMap<_Value> NodeImpl;

    public:

      typedef Arc Key;

      typedef _Value Value;

      ArcMapBase(const Adaptor& adaptor)

        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}

      ArcMapBase(const Adaptor& adaptor, const Value& value)

        : _arc_map(*adaptor._digraph, value),

          _node_map(*adaptor._digraph, value) {}

      void set(const Arc& key, const Value& val) {

        if (Adaptor::origArc(key)) {

          _arc_map.set(key._item.first(), val);

        } else {

          _node_map.set(key._item.second(), val);

        }

      }

        if (Adaptor::origArc(key)) {

          return _arc_map[key._item.first()];

        } else {

          return _node_map[key._item.second()];

        }

      }

        if (Adaptor::origArc(key)) {

          return _arc_map[key._item.first()];

        } else {

          return _node_map[key._item.second()];

        }

      }

    private:

      ArcImpl _arc_map;

      NodeImpl _node_map;

    };

  public:

    template <typename _Value>

    class NodeMap

      : public SubMapExtender<Adaptor, NodeMapBase<_Value> >

    {

    public:

      typedef _Value Value;

      typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;

      NodeMap(const Adaptor& adaptor)

        : Parent(adaptor) {}

    ///

    /// Gives back the arc binds the two part of the node.

    static Arc arc(const DigraphNode& n) {

      return Parent::arc(n);

    }

    /// \brief Gives back the arc of the original arc.

    ///

    /// Gives back the arc of the original arc.

    static Arc arc(const DigraphArc& a) {

      return Parent::arc(a);

    }

    /// \brief NodeMap combined from two original NodeMap

    ///

    /// This class adapt two of the original digraph NodeMap to

    /// get a node map on the adapted digraph.

    template <typename InNodeMap, typename OutNodeMap>

    class CombinedNodeMap {

    public:

      typedef Node Key;

      typedef typename InNodeMap::Value Value;

      /// \brief Constructor

      ///

      /// Constructor.

      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)

        : _in_map(in_map), _out_map(out_map) {}

      /// \brief The subscript operator.

      ///

      /// The subscript operator.

      Value& operator[](const Key& key) {

        if (Parent::inNode(key)) {

          return _in_map[key];

        } else {

          return _out_map[key];

        }

      }

      /// \brief The const subscript operator.

      ///

      /// The const subscript operator.

      Value operator[](const Key& key) const {

        if (Parent::inNode(key)) {

          return _in_map[key];

        } else {

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<InNodeMap, const OutNodeMap>

    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {

      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);

    }

    template <typename InNodeMap, typename OutNodeMap>

    static CombinedNodeMap<const InNodeMap, const OutNodeMap>

    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {

      return CombinedNodeMap<const InNodeMap,

        const OutNodeMap>(in_map, out_map);

    }

    /// \brief ArcMap combined from an original ArcMap and a NodeMap

    ///

    /// This class adapt an original ArcMap and a NodeMap to get an

    /// arc map on the adapted digraph

    template <typename DigraphArcMap, typename DigraphNodeMap>

    class CombinedArcMap {

    public:

      typedef Arc Key;

      typedef typename DigraphArcMap::Value Value;

      /// \brief Constructor

      ///

      /// Constructor.

      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)

        : _arc_map(arc_map), _node_map(node_map) {}

      /// \brief The subscript operator.

      ///

      /// The subscript operator.

      void set(const Arc& arc, const Value& val) {

        if (Parent::origArc(arc)) {

          _arc_map.set(arc, val);

        } else {

          _node_map.set(arc, val);

        }

      }

      /// \brief The const subscript operator.

      ///

      /// The const subscript operator.

      Value operator[](const Key& arc) const {

        if (Parent::origArc(arc)) {

          return _arc_map[arc];

        } else {