RhodeCode

@defgroup graph_adaptors Adaptor Classes for Graphs

\brief Adaptor classes for digraphs and graphs

This group contains several useful adaptor classes for digraphs and graphs.

graph algorithms, graph concepts, which couple them, and graph

instance \c g of a directed graph type, say ListDigraph and an algorithm

to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.

The adaptor uses the original digraph structure and digraph operations when

methods of the reversed oriented graph are called.  This means that the adaptor

have minor memory usage, and do not perform sophisticated algorithmic

obtained by a usual construction like filtering the node or the arc set or

ReverseDigraph<ListDigraph> rg(g);

During running the algorithm, the original digraph \c g is untouched.

This techniques give rise to an elegant code, and based on stable

In flow, circulation and matching problems, the residual

this with shortest path algorithms or minimum mean cycle algorithms,

meaningless. This means that the concepts that they meet depend

on the graph adaptor, and the wrapped graph.

For example, if an arc of a reversed digraph is deleted, this is carried

out by deleting the corresponding arc of the original digraph, thus the

adaptor modifies the original digraph.

However in case of a residual digraph, this operation has no sense.

ReverseDigraph has constructor

This means that in a situation, when a <tt>const %ListDigraph&</tt>

<tt>Digraph=const %ListDigraph</tt>.

  ReverseDigraph<const ListDigraph> rg(g);

/// \brief Adaptor classes for digraphs and graphs

    typedef ArcNumTagIndicator<Digraph> ArcNumTag;

    typedef FindArcTagIndicator<Digraph> FindArcTag;

    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {

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

    void erase(const Arc& a) { _digraph->erase(a); }

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

    typedef ArcNumTagIndicator<Graph> ArcNumTag;

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

    typedef FindArcTagIndicator<Graph> FindArcTag;

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

                const Arc& prev = INVALID) const {

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

    Edge findEdge(const Node& u, const Node& v,

                  const Edge& prev = INVALID) const {

    typedef FindArcTagIndicator<Digraph> FindArcTag;

                const Arc& prev = INVALID) const {

  /// \brief Adaptor class for reversing the orientation of the arcs in

  /// a digraph.

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

#ifdef DOXYGEN

  class ReverseDigraph {

#else

    public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {

#endif

    /// The type of the adapted digraph.

    typedef GR Digraph;

    typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;

    /// Creates a reverse digraph adaptor for the given digraph.

  /// \brief Returns a read-only ReverseDigraph adaptor

  /// This function just returns a read-only \ref ReverseDigraph adaptor.

  /// \ingroup graph_adaptors

  /// \relates ReverseDigraph

  template<typename GR>

  ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {

    return ReverseDigraph<const GR>(digraph);

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

    bool status(const Node& n) const { return (*_node_filter)[n]; }

    bool status(const Arc& a) const { return (*_arc_filter)[a]; }

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> FindArcTag;

                const Arc& prev = INVALID) const {

    void status(const Node& n, bool v) const { _node_filter->set(n, v); }

    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }

    bool status(const Node& n) const { return (*_node_filter)[n]; }

    bool status(const Arc& a) const { return (*_arc_filter)[a]; }

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Digraph> FindArcTag;

                const Arc& prev = INVALID) const {

  /// \brief Adaptor class for hiding nodes and arcs in a digraph

  /// SubDigraph can be used for hiding nodes and arcs in a digraph.

  /// A \c bool node map and a \c bool arc map must be specified, which

  /// define the filters for nodes and arcs.

  /// Only the nodes and arcs with \c true filter value are

  /// 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 GR 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 "GR::NodeMap<bool>".

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

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

  /// adapted digraph. The default type is

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

  ///

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

  /// digraph are convertible to each other.

#ifdef DOXYGEN

  template<typename GR, typename NF, typename AF>

  class SubDigraph {

#else

  template<typename GR,

           typename NF = typename GR::template NodeMap<bool>,

           typename AF = typename GR::template ArcMap<bool> >

  class SubDigraph :

    public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {

#endif

    /// The type of the adapted digraph.

    typedef GR Digraph;

    /// The type of the node filter map.

    typedef NF NodeFilterMap;

    /// The type of the arc filter map.

    typedef AF ArcFilterMap;

    typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> >

      Parent;

    /// Creates a subdigraph for the given digraph with the

    /// given node and arc filter maps.

    /// \brief Sets the status of the given node

    /// This function sets the status of the given node.

    /// It is done by simply setting the assigned value of \c n

    /// to \c v in the node filter map.

    void status(const Node& n, bool v) const { Parent::status(n, v); }

    /// \brief Sets the status of the given arc

    /// This function sets the status of the given arc.

    /// It is done by simply setting the assigned value of \c a

    /// to \c v in the arc filter map.

    void status(const Arc& a, bool v) const { Parent::status(a, v); }

    /// \brief Returns the status of the given node

    /// This function returns the status of the given node.

    /// It is \c true if the given node is enabled (i.e. not hidden).

    bool status(const Node& n) const { return Parent::status(n); }

    /// \brief Returns the status of the given arc

    /// This function returns the status of the given arc.

    /// It is \c true if the given arc is enabled (i.e. not hidden).

    bool status(const Arc& a) const { return Parent::status(a); }

    /// \brief Disables the given node

    /// This function disables the given node in the subdigraph,

    /// so the iteration jumps over it.

    /// It is the same as \ref status() "status(n, false)".

    void disable(const Node& n) const { Parent::status(n, false); }

    /// \brief Disables the given arc

    /// This function disables the given arc in the subdigraph,

    /// so the iteration jumps over it.

    /// It is the same as \ref status() "status(a, false)".

    void disable(const Arc& a) const { Parent::status(a, false); }

    /// \brief Enables the given node

    /// This function enables the given node in the subdigraph.

    /// It is the same as \ref status() "status(n, true)".

    void enable(const Node& n) const { Parent::status(n, true); }

    /// \brief Enables the given arc

    /// This function enables the given arc in the subdigraph.

    /// It is the same as \ref status() "status(a, true)".

    void enable(const Arc& a) const { Parent::status(a, true); }

  /// \brief Returns a read-only SubDigraph adaptor

  /// This function just returns a read-only \ref SubDigraph adaptor.

  /// \ingroup graph_adaptors

  /// \relates SubDigraph

  template<typename GR, typename NF, typename AF>

  SubDigraph<const GR, NF, AF>

  subDigraph(const GR& digraph,

             NF& node_filter_map, AF& arc_filter_map) {

    return SubDigraph<const GR, NF, AF>

      (digraph, node_filter_map, arc_filter_map);

  template<typename GR, typename NF, typename AF>

  SubDigraph<const GR, const NF, AF>

  subDigraph(const GR& digraph,

             const NF& node_filter_map, AF& arc_filter_map) {

    return SubDigraph<const GR, const NF, AF>

      (digraph, node_filter_map, arc_filter_map);

  template<typename GR, typename NF, typename AF>

  SubDigraph<const GR, NF, const AF>

  subDigraph(const GR& digraph,

             NF& node_filter_map, const AF& arc_filter_map) {

    return SubDigraph<const GR, NF, const AF>

      (digraph, node_filter_map, arc_filter_map);

  template<typename GR, typename NF, typename AF>

  SubDigraph<const GR, const NF, const AF>

  subDigraph(const GR& digraph,

             const NF& node_filter_map, const AF& arc_filter_map) {

    return SubDigraph<const GR, const NF, const AF>

      (digraph, node_filter_map, arc_filter_map);

  template <typename _Graph, typename _NodeFilterMap,

            typename _EdgeFilterMap, bool _checked = true>

    typedef _NodeFilterMap NodeFilterMap;

    typedef _EdgeFilterMap EdgeFilterMap;

    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }

    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }

    bool status(const Node& n) const { return (*_node_filter_map)[n]; }

    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Graph> FindArcTag;

                const Arc& prev = INVALID) const {

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

                  const Edge& prev = INVALID) const {

  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>

  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>

    typedef _NodeFilterMap NodeFilterMap;

    typedef _EdgeFilterMap EdgeFilterMap;

    void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }

    void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }

    bool status(const Node& n) const { return (*_node_filter_map)[n]; }

    bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }

    typedef False ArcNumTag;

    typedef FindArcTagIndicator<Graph> FindArcTag;

                const Arc& prev = INVALID) const {

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

                  const Edge& prev = INVALID) const {

  /// \brief Adaptor class for hiding nodes and edges in an undirected

  /// graph.

  /// SubGraph can be used for hiding nodes and edges in a graph.

  /// A \c bool node map and a \c bool edge map must be specified, which

  /// define the filters for nodes and edges.

  /// Only the nodes and edges with \c true filter value are

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

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

  ///

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

  /// adapted graph are convertible to each other.

#ifdef DOXYGEN

  template<typename GR, typename NF, typename EF>

  class SubGraph {

#else

  template<typename GR,

           typename NF = typename GR::template NodeMap<bool>,

           typename EF = typename GR::template EdgeMap<bool> >

  class SubGraph :

    public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > {

#endif

    /// The type of the adapted graph.

    typedef GR Graph;

    /// The type of the node filter map.

    typedef NF NodeFilterMap;

    /// The type of the edge filter map.

    typedef EF EdgeFilterMap;

    typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> >

      Parent;

    /// Creates a subgraph for the given graph with the given node

    /// and edge filter maps.

    SubGraph(Graph& graph, NodeFilterMap& node_filter_map,

      setGraph(graph);

    /// \brief Sets the status of the given node

    /// This function sets the status of the given node.

    /// It is done by simply setting the assigned value of \c n

    /// to \c v in the node filter map.

    void status(const Node& n, bool v) const { Parent::status(n, v); }

    /// \brief Sets the status of the given edge

    /// This function sets the status of the given edge.

    /// It is done by simply setting the assigned value of \c e

    /// to \c v in the edge filter map.

    void status(const Edge& e, bool v) const { Parent::status(e, v); }

    /// \brief Returns the status of the given node

    /// This function returns the status of the given node.

    /// It is \c true if the given node is enabled (i.e. not hidden).

    bool status(const Node& n) const { return Parent::status(n); }

    /// \brief Returns the status of the given edge

    /// This function returns the status of the given edge.

    /// It is \c true if the given edge is enabled (i.e. not hidden).

    bool status(const Edge& e) const { return Parent::status(e); }

    /// \brief Disables the given node

    /// This function disables the given node in the subdigraph,

    /// so the iteration jumps over it.

    /// It is the same as \ref status() "status(n, false)".

    void disable(const Node& n) const { Parent::status(n, false); }

    /// \brief Disables the given edge

    /// This function disables the given edge in the subgraph,

    /// so the iteration jumps over it.

    /// It is the same as \ref status() "status(e, false)".

    void disable(const Edge& e) const { Parent::status(e, false); }

    /// \brief Enables the given node

    /// This function enables the given node in the subdigraph.

    /// It is the same as \ref status() "status(n, true)".

    void enable(const Node& n) const { Parent::status(n, true); }

    /// \brief Enables the given edge

    /// This function enables the given edge in the subgraph.

    /// It is the same as \ref status() "status(e, true)".

    void enable(const Edge& e) const { Parent::status(e, true); }

  /// \brief Returns a read-only SubGraph adaptor

  /// This function just returns a read-only \ref SubGraph adaptor.

  /// \ingroup graph_adaptors

  /// \relates SubGraph

  template<typename GR, typename NF, typename EF>

  SubGraph<const GR, NF, EF>

  subGraph(const GR& graph,

           NF& node_filter_map, EF& edge_filter_map) {

    return SubGraph<const GR, NF, EF>

      (graph, node_filter_map, edge_filter_map);

  template<typename GR, typename NF, typename EF>

  SubGraph<const GR, const NF, EF>

  subGraph(const GR& graph,

           const NF& node_filter_map, EF& edge_filter_map) {

    return SubGraph<const GR, const NF, EF>

      (graph, node_filter_map, edge_filter_map);

  template<typename GR, typename NF, typename EF>

  SubGraph<const GR, NF, const EF>

  subGraph(const GR& graph,

           NF& node_filter_map, const EF& edge_filter_map) {

    return SubGraph<const GR, NF, const EF>

      (graph, node_filter_map, edge_filter_map);

  template<typename GR, typename NF, typename EF>

  SubGraph<const GR, const NF, const EF>

  subGraph(const GR& graph,

           const NF& node_filter_map, const EF& edge_filter_map) {

    return SubGraph<const GR, const NF, const EF>

      (graph, node_filter_map, edge_filter_map);

  /// \brief Adaptor class for hiding nodes in a digraph or a graph.

  /// FilterNodes adaptor can be used for hiding nodes in a digraph or a

  /// graph. A \c bool node map must be specified, which defines the filter

  /// for the nodes. Only the nodes with \c true filter value and the

  /// arcs/edges incident to nodes both with \c true filter value are shown

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

  ///

  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the

  /// adapted (di)graph are convertible to each other.

  template<typename GR, typename NF>

  class FilterNodes {

  template<typename GR,

           typename NF = typename GR::template NodeMap<bool>,

  class FilterNodes :

    public DigraphAdaptorExtender<

      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {

    typedef GR Digraph;

    typedef NF NodeFilterMap;

    typedef DigraphAdaptorExtender<

      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >

      Parent;

    /// Creates a subgraph for the given digraph or graph with the

    FilterNodes(GR& graph, NodeFilterMap& node_filter) :

      Parent(), const_true_map(true)

    {

      Parent::setDigraph(graph);

    /// \brief Sets the status of the given node

    /// This function sets the status of the given node.

    /// It is done by simply setting the assigned value of \c n

    /// to \c v in the node filter map.

    void status(const Node& n, bool v) const { Parent::status(n, v); }

    /// \brief Returns the status of the given node

    /// This function returns the status of the given node.

    /// It is \c true if the given node is enabled (i.e. not hidden).

    bool status(const Node& n) const { return Parent::status(n); }

    /// \brief Disables the given node

    /// This function disables the given node, so the iteration

    /// jumps over it.

    /// It is the same as \ref status() "status(n, false)".

    void disable(const Node& n) const { Parent::status(n, false); }

    /// \brief Enables the given node

    /// This function enables the given node.

    /// It is the same as \ref status() "status(n, true)".

    void enable(const Node& n) const { Parent::status(n, true); }

  template<typename GR, typename NF>

  class FilterNodes<GR, NF,

                    typename enable_if<UndirectedTagIndicator<GR> >::type> :

    public GraphAdaptorExtender<

      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {

    typedef GR Graph;

    typedef NF NodeFilterMap;

    typedef GraphAdaptorExtender<

      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >

      Parent;

    void status(const Node& n, bool v) const { Parent::status(n, v); }

    bool status(const Node& n) const { return Parent::status(n); }