alpar@906: /* -*- C++ -*-
ladanyi@1435: * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
alpar@906: *
alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906: *
alpar@906: * Permission to use, modify and distribute this software is granted
alpar@906: * provided that this copyright notice appears in all copies. For
alpar@906: * precise terms see the accompanying LICENSE file.
alpar@906: *
alpar@906: * This software is provided "AS IS" with no warranty of any kind,
alpar@906: * express or implied, and with no claim as to its suitability for any
alpar@906: * purpose.
alpar@906: *
alpar@906: */
alpar@906:
alpar@1401: #ifndef LEMON_GRAPH_ADAPTOR_H
alpar@1401: #define LEMON_GRAPH_ADAPTOR_H
marci@556:
alpar@1401: ///\ingroup graph_adaptors
marci@556: ///\file
alpar@1401: ///\brief Several graph adaptors.
marci@556: ///
alpar@1401: ///This file contains several useful graph adaptor functions.
marci@556: ///
marci@556: ///\author Marton Makai
marci@556:
alpar@921: #include <lemon/invalid.h>
alpar@921: #include <lemon/maps.h>
deba@1472: #include <lemon/bits/erasable_graph_extender.h>
deba@1472: #include <lemon/bits/clearable_graph_extender.h>
deba@1472: #include <lemon/bits/extendable_graph_extender.h>
deba@1307: #include <lemon/bits/iterable_graph_extender.h>
deba@1472: #include <lemon/bits/alteration_notifier.h>
deba@1472: #include <lemon/bits/default_map.h>
deba@1791: #include <lemon/bits/graph_extender.h>
alpar@774: #include <iostream>
marci@556:
alpar@921: namespace lemon {
marci@556:
alpar@1401: // Graph adaptors
marci@556:
marci@1172: /*!
alpar@1401: \addtogroup graph_adaptors
marci@1004: @{
marci@1172: */
marci@556:
marci@1172: /*!
alpar@1401: Base type for the Graph Adaptors
marci@1242:
alpar@1401: \warning Graph adaptors are in even more experimental state than the other
marci@1004: parts of the lib. Use them at you own risk.
marci@1242:
alpar@1401: This is the base type for most of LEMON graph adaptors.
alpar@1401: This class implements a trivial graph adaptor i.e. it only wraps the
marci@1004: functions and types of the graph. The purpose of this class is to
alpar@1401: make easier implementing graph adaptors. E.g. if an adaptor is
marci@1004: considered which differs from the wrapped graph only in some of its
alpar@1401: functions or types, then it can be derived from GraphAdaptor, and only the
marci@1004: differences should be implemented.
marci@1004:
marci@1004: \author Marton Makai
marci@1004: */
marci@970: template<typename _Graph>
alpar@1401: class GraphAdaptorBase {
marci@970: public:
marci@970: typedef _Graph Graph;
marci@970: typedef Graph ParentGraph;
marci@970:
marci@556: protected:
marci@556: Graph* graph;
alpar@1401: GraphAdaptorBase() : graph(0) { }
marci@556: void setGraph(Graph& _graph) { graph=&_graph; }
marci@556:
marci@556: public:
alpar@1401: GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
marci@556:
alpar@774: typedef typename Graph::Node Node;
alpar@774: typedef typename Graph::Edge Edge;
marci@556:
marci@970: void first(Node& i) const { graph->first(i); }
marci@970: void first(Edge& i) const { graph->first(i); }
marci@970: void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
marci@970: void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
marci@556:
marci@970: void next(Node& i) const { graph->next(i); }
marci@970: void next(Edge& i) const { graph->next(i); }
marci@970: void nextIn(Edge& i) const { graph->nextIn(i); }
marci@970: void nextOut(Edge& i) const { graph->nextOut(i); }
marci@970:
alpar@986: Node source(const Edge& e) const { return graph->source(e); }
alpar@986: Node target(const Edge& e) const { return graph->target(e); }
marci@556:
deba@1697: typedef NodeNumTagIndicator<Graph> NodeNumTag;
marci@556: int nodeNum() const { return graph->nodeNum(); }
deba@1697:
deba@1697: typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
marci@556: int edgeNum() const { return graph->edgeNum(); }
deba@1697:
deba@1697: typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1697: Edge findEdge(const Node& source, const Node& target,
deba@1697: const Edge& prev = INVALID) {
deba@1697: return graph->findEdge(source, target, prev);
deba@1697: }
marci@556:
deba@1697: Node addNode() const {
deba@1697: return Node(graph->addNode());
deba@1697: }
deba@1697:
alpar@986: Edge addEdge(const Node& source, const Node& target) const {
deba@1697: return Edge(graph->addEdge(source, target));
deba@1697: }
marci@556:
marci@556: void erase(const Node& i) const { graph->erase(i); }
marci@556: void erase(const Edge& i) const { graph->erase(i); }
marci@556:
marci@556: void clear() const { graph->clear(); }
marci@556:
marci@739: int id(const Node& v) const { return graph->id(v); }
marci@739: int id(const Edge& e) const { return graph->id(e); }
marci@650:
deba@1627: Edge oppositeNode(const Edge& e) const {
deba@1627: return Edge(graph->opposite(e));
deba@1627: }
marci@650:
marci@970: template <typename _Value>
marci@970: class NodeMap : public _Graph::template NodeMap<_Value> {
marci@970: public:
marci@970: typedef typename _Graph::template NodeMap<_Value> Parent;
deba@1755: explicit NodeMap(const GraphAdaptorBase<_Graph>& gw)
deba@1755: : Parent(*gw.graph) { }
alpar@1401: NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
deba@1755: : Parent(*gw.graph, value) { }
marci@970: };
marci@556:
marci@970: template <typename _Value>
marci@970: class EdgeMap : public _Graph::template EdgeMap<_Value> {
marci@970: public:
marci@970: typedef typename _Graph::template EdgeMap<_Value> Parent;
deba@1755: explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw)
deba@1755: : Parent(*gw.graph) { }
alpar@1401: EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
deba@1755: : Parent(*gw.graph, value) { }
marci@970: };
deba@877:
marci@556: };
marci@556:
marci@970: template <typename _Graph>
alpar@1401: class GraphAdaptor :
alpar@1401: public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
marci@970: public:
marci@970: typedef _Graph Graph;
alpar@1401: typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
marci@970: protected:
alpar@1401: GraphAdaptor() : Parent() { }
marci@569:
marci@970: public:
deba@1755: explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
marci@970: };
marci@569:
marci@997: template <typename _Graph>
alpar@1401: class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@997: public:
marci@997: typedef _Graph Graph;
alpar@1401: typedef GraphAdaptorBase<_Graph> Parent;
marci@997: protected:
alpar@1401: RevGraphAdaptorBase() : Parent() { }
marci@997: public:
marci@997: typedef typename Parent::Node Node;
marci@997: typedef typename Parent::Edge Edge;
marci@997:
marci@997: void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
marci@997: void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
marci@997:
marci@997: void nextIn(Edge& i) const { Parent::nextOut(i); }
marci@997: void nextOut(Edge& i) const { Parent::nextIn(i); }
marci@997:
marci@997: Node source(const Edge& e) const { return Parent::target(e); }
marci@997: Node target(const Edge& e) const { return Parent::source(e); }
marci@997: };
marci@997:
marci@997:
alpar@1401: /// A graph adaptor which reverses the orientation of the edges.
marci@556:
alpar@1401: ///\warning Graph adaptors are in even more experimental state than the other
alpar@879: ///parts of the lib. Use them at you own risk.
alpar@879: ///
marci@923: /// Let \f$G=(V, A)\f$ be a directed graph and
marci@923: /// suppose that a graph instange \c g of type
marci@923: /// \c ListGraph implements \f$G\f$.
marci@923: /// \code
marci@923: /// ListGraph g;
marci@923: /// \endcode
marci@923: /// For each directed edge
marci@923: /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
marci@923: /// reversing its orientation.
alpar@1401: /// Then RevGraphAdaptor implements the graph structure with node-set
marci@923: /// \f$V\f$ and edge-set
marci@923: /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
marci@923: /// reversing the orientation of its edges. The following code shows how
marci@923: /// such an instance can be constructed.
marci@923: /// \code
alpar@1401: /// RevGraphAdaptor<ListGraph> gw(g);
marci@923: /// \endcode
marci@556: ///\author Marton Makai
marci@997: template<typename _Graph>
alpar@1401: class RevGraphAdaptor :
alpar@1401: public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
marci@650: public:
marci@997: typedef _Graph Graph;
marci@997: typedef IterableGraphExtender<
alpar@1401: RevGraphAdaptorBase<_Graph> > Parent;
marci@556: protected:
alpar@1401: RevGraphAdaptor() { }
marci@556: public:
deba@1755: explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
marci@997: };
marci@556:
marci@992:
deba@1681: template <typename _Graph, typename NodeFilterMap,
deba@1681: typename EdgeFilterMap, bool checked = true>
alpar@1401: class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992: public:
marci@992: typedef _Graph Graph;
alpar@1401: typedef GraphAdaptorBase<_Graph> Parent;
marci@992: protected:
marci@992: NodeFilterMap* node_filter_map;
marci@992: EdgeFilterMap* edge_filter_map;
alpar@1401: SubGraphAdaptorBase() : Parent(),
marci@992: node_filter_map(0), edge_filter_map(0) { }
marci@775:
marci@992: void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@992: node_filter_map=&_node_filter_map;
marci@992: }
marci@992: void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@992: edge_filter_map=&_edge_filter_map;
marci@992: }
marci@992:
marci@992: public:
marci@992:
marci@992: typedef typename Parent::Node Node;
marci@992: typedef typename Parent::Edge Edge;
marci@992:
marci@992: void first(Node& i) const {
marci@992: Parent::first(i);
marci@992: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992: }
deba@1681:
deba@1681: void first(Edge& i) const {
deba@1681: Parent::first(i);
deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681: || !(*node_filter_map)[Parent::source(i)]
deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681: }
deba@1681:
deba@1681: void firstIn(Edge& i, const Node& n) const {
deba@1681: Parent::firstIn(i, n);
deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681: || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681: }
deba@1681:
deba@1681: void firstOut(Edge& i, const Node& n) const {
deba@1681: Parent::firstOut(i, n);
deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681: }
deba@1681:
deba@1681: void next(Node& i) const {
deba@1681: Parent::next(i);
deba@1681: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681: }
deba@1681:
deba@1681: void next(Edge& i) const {
deba@1681: Parent::next(i);
deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681: || !(*node_filter_map)[Parent::source(i)]
deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
deba@1681: }
deba@1681:
deba@1681: void nextIn(Edge& i) const {
deba@1681: Parent::nextIn(i);
deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681: || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
deba@1681: }
deba@1681:
deba@1681: void nextOut(Edge& i) const {
deba@1681: Parent::nextOut(i);
deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i]
deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
deba@1681: }
deba@1681:
deba@1681: /// This function hides \c n in the graph, i.e. the iteration
deba@1681: /// jumps over it. This is done by simply setting the value of \c n
deba@1681: /// to be false in the corresponding node-map.
deba@1681: void hide(const Node& n) const { node_filter_map->set(n, false); }
deba@1681:
deba@1681: /// This function hides \c e in the graph, i.e. the iteration
deba@1681: /// jumps over it. This is done by simply setting the value of \c e
deba@1681: /// to be false in the corresponding edge-map.
deba@1681: void hide(const Edge& e) const { edge_filter_map->set(e, false); }
deba@1681:
deba@1681: /// The value of \c n is set to be true in the node-map which stores
deba@1681: /// hide information. If \c n was hidden previuosly, then it is shown
deba@1681: /// again
deba@1681: void unHide(const Node& n) const { node_filter_map->set(n, true); }
deba@1681:
deba@1681: /// The value of \c e is set to be true in the edge-map which stores
deba@1681: /// hide information. If \c e was hidden previuosly, then it is shown
deba@1681: /// again
deba@1681: void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
deba@1681:
deba@1681: /// Returns true if \c n is hidden.
deba@1681: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1681:
deba@1681: /// Returns true if \c n is hidden.
deba@1681: bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
deba@1681:
deba@1697: typedef False NodeNumTag;
deba@1697: typedef False EdgeNumTag;
deba@1681: };
deba@1681:
deba@1681: template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1681: class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
deba@1681: : public GraphAdaptorBase<_Graph> {
deba@1681: public:
deba@1681: typedef _Graph Graph;
deba@1681: typedef GraphAdaptorBase<_Graph> Parent;
deba@1681: protected:
deba@1681: NodeFilterMap* node_filter_map;
deba@1681: EdgeFilterMap* edge_filter_map;
deba@1681: SubGraphAdaptorBase() : Parent(),
deba@1681: node_filter_map(0), edge_filter_map(0) { }
deba@1681:
deba@1681: void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
deba@1681: node_filter_map=&_node_filter_map;
deba@1681: }
deba@1681: void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
deba@1681: edge_filter_map=&_edge_filter_map;
deba@1681: }
deba@1681:
deba@1681: public:
deba@1681:
deba@1681: typedef typename Parent::Node Node;
deba@1681: typedef typename Parent::Edge Edge;
deba@1681:
deba@1681: void first(Node& i) const {
deba@1681: Parent::first(i);
deba@1681: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
deba@1681: }
deba@1681:
marci@992: void first(Edge& i) const {
marci@992: Parent::first(i);
marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992: }
deba@1681:
marci@992: void firstIn(Edge& i, const Node& n) const {
marci@992: Parent::firstIn(i, n);
marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992: }
deba@1681:
marci@992: void firstOut(Edge& i, const Node& n) const {
marci@992: Parent::firstOut(i, n);
marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992: }
marci@992:
marci@992: void next(Node& i) const {
marci@992: Parent::next(i);
marci@992: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
marci@992: }
marci@992: void next(Edge& i) const {
marci@992: Parent::next(i);
marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
marci@992: }
marci@992: void nextIn(Edge& i) const {
marci@992: Parent::nextIn(i);
marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
marci@992: }
deba@1681:
marci@992: void nextOut(Edge& i) const {
marci@992: Parent::nextOut(i);
marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
marci@992: }
marci@992:
marci@992: /// This function hides \c n in the graph, i.e. the iteration
marci@992: /// jumps over it. This is done by simply setting the value of \c n
marci@992: /// to be false in the corresponding node-map.
marci@992: void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@992:
marci@992: /// This function hides \c e in the graph, i.e. the iteration
marci@992: /// jumps over it. This is done by simply setting the value of \c e
marci@992: /// to be false in the corresponding edge-map.
marci@992: void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@992:
marci@992: /// The value of \c n is set to be true in the node-map which stores
marci@992: /// hide information. If \c n was hidden previuosly, then it is shown
marci@992: /// again
marci@992: void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@992:
marci@992: /// The value of \c e is set to be true in the edge-map which stores
marci@992: /// hide information. If \c e was hidden previuosly, then it is shown
marci@992: /// again
marci@992: void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@992:
marci@992: /// Returns true if \c n is hidden.
marci@992: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@992:
marci@992: /// Returns true if \c n is hidden.
marci@992: bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@992:
deba@1697: typedef False NodeNumTag;
deba@1697: typedef False EdgeNumTag;
marci@992: };
marci@775:
alpar@1401: /*! \brief A graph adaptor for hiding nodes and edges from a graph.
marci@1242:
alpar@1401: \warning Graph adaptors are in even more experimental state than the other
marci@930: parts of the lib. Use them at you own risk.
marci@930:
alpar@1401: SubGraphAdaptor shows the graph with filtered node-set and
deba@1697: edge-set. If the \c checked parameter is true then it filters the edgeset
deba@1697: to do not get invalid edges without source or target.
marci@1242: Let \f$G=(V, A)\f$ be a directed graph
marci@1242: and suppose that the graph instance \c g of type ListGraph implements
marci@1242: \f$G\f$.
marci@1242: Let moreover \f$b_V\f$ and
marci@1242: \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
alpar@1401: SubGraphAdaptor<...>::NodeIt iterates
marci@1242: on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
alpar@1401: SubGraphAdaptor<...>::EdgeIt iterates
marci@1242: on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
alpar@1401: SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
marci@1242: only on edges leaving and entering a specific node which have true value.
marci@1242:
deba@1697: If the \c checked template parameter is false then we have to note that
deba@1697: the node-iterator cares only the filter on the node-set, and the
deba@1697: edge-iterator cares only the filter on the edge-set. This way the edge-map
deba@1697: should filter all edges which's source or target is filtered by the
deba@1697: node-filter.
marci@930: \code
marci@1242: typedef ListGraph Graph;
marci@930: Graph g;
marci@930: typedef Graph::Node Node;
marci@930: typedef Graph::Edge Edge;
marci@930: Node u=g.addNode(); //node of id 0
marci@930: Node v=g.addNode(); //node of id 1
marci@930: Node e=g.addEdge(u, v); //edge of id 0
marci@930: Node f=g.addEdge(v, u); //edge of id 1
marci@930: Graph::NodeMap<bool> nm(g, true);
marci@930: nm.set(u, false);
marci@930: Graph::EdgeMap<bool> em(g, true);
marci@930: em.set(e, false);
alpar@1401: typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
marci@930: SubGW gw(g, nm, em);
marci@930: for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
marci@930: std::cout << ":-)" << std::endl;
marci@930: for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
marci@930: \endcode
marci@930: The output of the above code is the following.
marci@930: \code
marci@930: 1
marci@930: :-)
marci@930: 1
marci@930: \endcode
marci@930: Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
marci@930: \c Graph::Node that is why \c g.id(n) can be applied.
marci@930:
alpar@1401: For other examples see also the documentation of NodeSubGraphAdaptor and
alpar@1401: EdgeSubGraphAdaptor.
marci@930:
marci@930: \author Marton Makai
marci@930: */
marci@992: template<typename _Graph, typename NodeFilterMap,
deba@1681: typename EdgeFilterMap, bool checked = true>
alpar@1401: class SubGraphAdaptor :
marci@992: public IterableGraphExtender<
deba@1681: SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
marci@650: public:
marci@992: typedef _Graph Graph;
marci@992: typedef IterableGraphExtender<
alpar@1401: SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
marci@556: protected:
alpar@1401: SubGraphAdaptor() { }
marci@992: public:
alpar@1401: SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
marci@992: EdgeFilterMap& _edge_filter_map) {
marci@992: setGraph(_graph);
marci@992: setNodeFilterMap(_node_filter_map);
marci@992: setEdgeFilterMap(_edge_filter_map);
marci@992: }
marci@992: };
marci@556:
marci@556:
marci@569:
alpar@1401: /*! \brief An adaptor for hiding nodes from a graph.
marci@933:
alpar@1401: \warning Graph adaptors are in even more experimental state than the other
marci@933: parts of the lib. Use them at you own risk.
marci@933:
alpar@1401: An adaptor for hiding nodes from a graph.
alpar@1401: This adaptor specializes SubGraphAdaptor in the way that only the node-set
deba@1697: can be filtered. In usual case the checked parameter is true, we get the
deba@1697: induced subgraph. But if the checked parameter is false then we can only
deba@1697: filter only isolated nodes.
marci@933: \author Marton Makai
marci@933: */
deba@1681: template<typename Graph, typename NodeFilterMap, bool checked = true>
alpar@1401: class NodeSubGraphAdaptor :
alpar@1401: public SubGraphAdaptor<Graph, NodeFilterMap,
deba@1681: ConstMap<typename Graph::Edge,bool>, checked> {
marci@933: public:
alpar@1401: typedef SubGraphAdaptor<Graph, NodeFilterMap,
marci@933: ConstMap<typename Graph::Edge,bool> > Parent;
marci@933: protected:
marci@933: ConstMap<typename Graph::Edge, bool> const_true_map;
marci@933: public:
alpar@1401: NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
marci@933: Parent(), const_true_map(true) {
marci@933: Parent::setGraph(_graph);
marci@933: Parent::setNodeFilterMap(_node_filter_map);
marci@933: Parent::setEdgeFilterMap(const_true_map);
marci@933: }
marci@933: };
marci@933:
marci@933:
alpar@1401: /*! \brief An adaptor for hiding edges from a graph.
marci@932:
alpar@1401: \warning Graph adaptors are in even more experimental state than the other
marci@932: parts of the lib. Use them at you own risk.
marci@932:
alpar@1401: An adaptor for hiding edges from a graph.
alpar@1401: This adaptor specializes SubGraphAdaptor in the way that only the edge-set
alpar@1401: can be filtered. The usefulness of this adaptor is demonstrated in the
marci@933: problem of searching a maximum number of edge-disjoint shortest paths
marci@933: between
marci@933: two nodes \c s and \c t. Shortest here means being shortest w.r.t.
marci@933: non-negative edge-lengths. Note that
marci@933: the comprehension of the presented solution
marci@1252: need's some elementary knowledge from combinatorial optimization.
marci@933:
marci@933: If a single shortest path is to be
marci@1252: searched between \c s and \c t, then this can be done easily by
marci@1252: applying the Dijkstra algorithm. What happens, if a maximum number of
marci@933: edge-disjoint shortest paths is to be computed. It can be proved that an
marci@933: edge can be in a shortest path if and only if it is tight with respect to
marci@933: the potential function computed by Dijkstra. Moreover, any path containing
marci@933: only such edges is a shortest one. Thus we have to compute a maximum number
marci@933: of edge-disjoint paths between \c s and \c t in the graph which has edge-set
marci@933: all the tight edges. The computation will be demonstrated on the following
alpar@1536: graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
marci@1425: The full source code is available in \ref sub_graph_adaptor_demo.cc.
marci@1425: If you are interested in more demo programs, you can use
marci@1425: \ref dim_to_dot.cc to generate .dot files from dimacs files.
athos@1576: The .dot file of the following figure was generated by
marci@1425: the demo program \ref dim_to_dot.cc.
marci@1425:
marci@933: \dot
marci@933: digraph lemon_dot_example {
marci@933: node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933: n0 [ label="0 (s)" ];
marci@933: n1 [ label="1" ];
marci@933: n2 [ label="2" ];
marci@933: n3 [ label="3" ];
marci@933: n4 [ label="4" ];
marci@933: n5 [ label="5" ];
marci@933: n6 [ label="6 (t)" ];
marci@933: edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933: n5 -> n6 [ label="9, length:4" ];
marci@933: n4 -> n6 [ label="8, length:2" ];
marci@933: n3 -> n5 [ label="7, length:1" ];
marci@933: n2 -> n5 [ label="6, length:3" ];
marci@933: n2 -> n6 [ label="5, length:5" ];
marci@933: n2 -> n4 [ label="4, length:2" ];
marci@933: n1 -> n4 [ label="3, length:3" ];
marci@933: n0 -> n3 [ label="2, length:1" ];
marci@933: n0 -> n2 [ label="1, length:2" ];
marci@933: n0 -> n1 [ label="0, length:3" ];
marci@933: }
marci@933: \enddot
marci@933:
marci@933: \code
marci@933: Graph g;
marci@933: Node s, t;
marci@933: LengthMap length(g);
marci@933:
marci@933: readDimacs(std::cin, g, length, s, t);
marci@933:
alpar@986: cout << "edges with lengths (of form id, source--length->target): " << endl;
marci@933: for(EdgeIt e(g); e!=INVALID; ++e)
alpar@986: cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
alpar@986: << length[e] << "->" << g.id(g.target(e)) << endl;
marci@933:
marci@933: cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
marci@933: \endcode
marci@933: Next, the potential function is computed with Dijkstra.
marci@933: \code
marci@933: typedef Dijkstra<Graph, LengthMap> Dijkstra;
marci@933: Dijkstra dijkstra(g, length);
marci@933: dijkstra.run(s);
marci@933: \endcode
marci@933: Next, we consrtruct a map which filters the edge-set to the tight edges.
marci@933: \code
marci@933: typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
marci@933: TightEdgeFilter;
marci@933: TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
marci@933:
alpar@1401: typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
marci@933: SubGW gw(g, tight_edge_filter);
marci@933: \endcode
marci@933: Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
marci@933: with a max flow algorithm Preflow.
marci@933: \code
marci@933: ConstMap<Edge, int> const_1_map(1);
marci@933: Graph::EdgeMap<int> flow(g, 0);
marci@933:
marci@933: Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
marci@933: preflow(gw, s, t, const_1_map, flow);
marci@933: preflow.run();
marci@933: \endcode
marci@933: Last, the output is:
marci@933: \code
marci@933: cout << "maximum number of edge-disjoint shortest path: "
marci@933: << preflow.flowValue() << endl;
marci@933: cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
marci@933: << endl;
marci@933: for(EdgeIt e(g); e!=INVALID; ++e)
marci@933: if (flow[e])
alpar@986: cout << " " << g.id(g.source(e)) << "--"
alpar@986: << length[e] << "->" << g.id(g.target(e)) << endl;
marci@933: \endcode
marci@933: The program has the following (expected :-)) output:
marci@933: \code
alpar@986: edges with lengths (of form id, source--length->target):
marci@933: 9, 5--4->6
marci@933: 8, 4--2->6
marci@933: 7, 3--1->5
marci@933: 6, 2--3->5
marci@933: 5, 2--5->6
marci@933: 4, 2--2->4
marci@933: 3, 1--3->4
marci@933: 2, 0--1->3
marci@933: 1, 0--2->2
marci@933: 0, 0--3->1
marci@933: s: 0 t: 6
marci@933: maximum number of edge-disjoint shortest path: 2
marci@933: edges of the maximum number of edge-disjoint shortest s-t paths:
marci@933: 9, 5--4->6
marci@933: 8, 4--2->6
marci@933: 7, 3--1->5
marci@933: 4, 2--2->4
marci@933: 2, 0--1->3
marci@933: 1, 0--2->2
marci@933: \endcode
marci@933:
marci@932: \author Marton Makai
marci@932: */
marci@932: template<typename Graph, typename EdgeFilterMap>
alpar@1401: class EdgeSubGraphAdaptor :
alpar@1401: public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1681: EdgeFilterMap, false> {
marci@932: public:
alpar@1401: typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
deba@1685: EdgeFilterMap, false> Parent;
marci@932: protected:
marci@932: ConstMap<typename Graph::Node, bool> const_true_map;
marci@932: public:
alpar@1401: EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
marci@932: Parent(), const_true_map(true) {
marci@932: Parent::setGraph(_graph);
marci@932: Parent::setNodeFilterMap(const_true_map);
marci@932: Parent::setEdgeFilterMap(_edge_filter_map);
marci@932: }
marci@932: };
marci@932:
marci@1383: template <typename _Graph>
alpar@1401: class UndirGraphAdaptorBase :
alpar@1401: public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
marci@1383: public:
marci@1383: typedef _Graph Graph;
alpar@1401: typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
marci@1383: protected:
alpar@1401: UndirGraphAdaptorBase() : Parent() { }
marci@1383: public:
marci@1383: typedef typename Parent::UndirEdge UndirEdge;
marci@1383: typedef typename Parent::Edge Edge;
marci@1383:
marci@1383: template <typename T>
marci@1383: class EdgeMap {
marci@1383: protected:
alpar@1401: const UndirGraphAdaptorBase<_Graph>* g;
marci@1383: template <typename TT> friend class EdgeMap;
marci@1383: typename _Graph::template EdgeMap<T> forward_map, backward_map;
marci@1383: public:
marci@1383: typedef T Value;
marci@1383: typedef Edge Key;
marci@1383:
alpar@1401: EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
marci@1383: forward_map(*(g->graph)), backward_map(*(g->graph)) { }
marci@569:
alpar@1401: EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
marci@1383: forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
marci@1383:
marci@1383: void set(Edge e, T a) {
deba@1627: if (g->direction(e))
marci@1383: forward_map.set(e, a);
marci@1383: else
marci@1383: backward_map.set(e, a);
marci@1383: }
marci@556:
marci@1383: T operator[](Edge e) const {
deba@1627: if (g->direction(e))
marci@1383: return forward_map[e];
marci@1383: else
marci@1383: return backward_map[e];
marci@556: }
marci@556: };
marci@1383:
marci@1383: template <typename T>
marci@1383: class UndirEdgeMap {
marci@1383: template <typename TT> friend class UndirEdgeMap;
marci@1383: typename _Graph::template EdgeMap<T> map;
marci@1383: public:
marci@1383: typedef T Value;
marci@1383: typedef UndirEdge Key;
marci@1383:
alpar@1401: UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
marci@1383: map(*(g.graph)) { }
marci@556:
alpar@1401: UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
marci@1383: map(*(g.graph), a) { }
marci@1383:
marci@1383: void set(UndirEdge e, T a) {
marci@1383: map.set(e, a);
marci@1383: }
marci@556:
marci@1383: T operator[](UndirEdge e) const {
marci@1383: return map[e];
marci@1383: }
marci@1383: };
marci@1383:
marci@1383: };
marci@1383:
alpar@1401: /// \brief An undirected graph is made from a directed graph by an adaptor
marci@1383: ///
marci@1383: /// Undocumented, untested!!!
marci@1383: /// If somebody knows nice demo application, let's polulate it.
marci@1383: ///
marci@1383: /// \author Marton Makai
marci@1383: template<typename _Graph>
alpar@1401: class UndirGraphAdaptor :
marci@1383: public IterableUndirGraphExtender<
alpar@1401: UndirGraphAdaptorBase<_Graph> > {
marci@1383: public:
marci@1383: typedef _Graph Graph;
marci@1383: typedef IterableUndirGraphExtender<
alpar@1401: UndirGraphAdaptorBase<_Graph> > Parent;
marci@1383: protected:
alpar@1401: UndirGraphAdaptor() { }
marci@1383: public:
alpar@1401: UndirGraphAdaptor(_Graph& _graph) {
marci@1383: setGraph(_graph);
marci@556: }
marci@556: };
marci@556:
marci@992:
marci@992: template <typename _Graph,
marci@992: typename ForwardFilterMap, typename BackwardFilterMap>
alpar@1401: class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992: public:
marci@992: typedef _Graph Graph;
alpar@1401: typedef GraphAdaptorBase<_Graph> Parent;
marci@992: protected:
marci@992: ForwardFilterMap* forward_filter;
marci@992: BackwardFilterMap* backward_filter;
alpar@1401: SubBidirGraphAdaptorBase() : Parent(),
marci@992: forward_filter(0), backward_filter(0) { }
marci@992:
marci@992: void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
marci@992: forward_filter=&_forward_filter;
marci@992: }
marci@992: void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
marci@992: backward_filter=&_backward_filter;
marci@992: }
marci@992:
marci@992: public:
alpar@1401: // SubGraphAdaptorBase(Graph& _graph,
marci@992: // NodeFilterMap& _node_filter_map,
marci@992: // EdgeFilterMap& _edge_filter_map) :
marci@992: // Parent(&_graph),
marci@992: // node_filter_map(&node_filter_map),
marci@992: // edge_filter_map(&edge_filter_map) { }
marci@992:
marci@992: typedef typename Parent::Node Node;
marci@992: typedef typename _Graph::Edge GraphEdge;
marci@992: template <typename T> class EdgeMap;
alpar@1401: /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
marci@992: /// _Graph::Edge. It contains an extra bool flag which is true
marci@992: /// if and only if the
marci@992: /// edge is the backward version of the original edge.
marci@992: class Edge : public _Graph::Edge {
alpar@1401: friend class SubBidirGraphAdaptorBase<
marci@992: Graph, ForwardFilterMap, BackwardFilterMap>;
marci@992: template<typename T> friend class EdgeMap;
marci@992: protected:
marci@992: bool backward; //true, iff backward
marci@992: public:
marci@992: Edge() { }
marci@992: /// \todo =false is needed, or causes problems?
marci@992: /// If \c _backward is false, then we get an edge corresponding to the
marci@992: /// original one, otherwise its oppositely directed pair is obtained.
marci@992: Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
marci@992: _Graph::Edge(e), backward(_backward) { }
marci@992: Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
marci@992: bool operator==(const Edge& v) const {
marci@992: return (this->backward==v.backward &&
marci@992: static_cast<typename _Graph::Edge>(*this)==
marci@992: static_cast<typename _Graph::Edge>(v));
marci@992: }
marci@992: bool operator!=(const Edge& v) const {
marci@992: return (this->backward!=v.backward ||
marci@992: static_cast<typename _Graph::Edge>(*this)!=
marci@992: static_cast<typename _Graph::Edge>(v));
marci@992: }
marci@992: };
marci@992:
marci@992: void first(Node& i) const {
marci@992: Parent::first(i);
marci@992: }
marci@992:
marci@992: void first(Edge& i) const {
marci@992: Parent::first(i);
marci@992: i.backward=false;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*forward_filter)[i]) Parent::next(i);
marci@992: if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: Parent::first(i);
marci@992: i.backward=true;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::next(i);
marci@992: }
marci@992: }
marci@992:
marci@992: void firstIn(Edge& i, const Node& n) const {
marci@992: Parent::firstIn(i, n);
marci@992: i.backward=false;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@1269: !(*forward_filter)[i]) Parent::nextIn(i);
marci@992: if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: Parent::firstOut(i, n);
marci@992: i.backward=true;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::nextOut(i);
marci@992: }
marci@992: }
marci@992:
marci@992: void firstOut(Edge& i, const Node& n) const {
marci@992: Parent::firstOut(i, n);
marci@992: i.backward=false;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*forward_filter)[i]) Parent::nextOut(i);
marci@992: if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: Parent::firstIn(i, n);
marci@992: i.backward=true;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::nextIn(i);
marci@992: }
marci@992: }
marci@992:
marci@992: void next(Node& i) const {
marci@992: Parent::next(i);
marci@992: }
marci@992:
marci@992: void next(Edge& i) const {
marci@992: if (!(i.backward)) {
marci@992: Parent::next(i);
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*forward_filter)[i]) Parent::next(i);
marci@992: if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: Parent::first(i);
marci@992: i.backward=true;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::next(i);
marci@992: }
marci@992: } else {
marci@992: Parent::next(i);
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::next(i);
marci@992: }
marci@992: }
marci@992:
marci@992: void nextIn(Edge& i) const {
marci@992: if (!(i.backward)) {
marci@992: Node n=Parent::target(i);
marci@992: Parent::nextIn(i);
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*forward_filter)[i]) Parent::nextIn(i);
marci@992: if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: Parent::firstOut(i, n);
marci@992: i.backward=true;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::nextOut(i);
marci@992: }
marci@992: } else {
marci@992: Parent::nextOut(i);
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::nextOut(i);
marci@992: }
marci@992: }
marci@992:
marci@992: void nextOut(Edge& i) const {
marci@992: if (!(i.backward)) {
marci@992: Node n=Parent::source(i);
marci@992: Parent::nextOut(i);
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*forward_filter)[i]) Parent::nextOut(i);
marci@992: if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: Parent::firstIn(i, n);
marci@992: i.backward=true;
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::nextIn(i);
marci@992: }
marci@992: } else {
marci@992: Parent::nextIn(i);
marci@992: while (*static_cast<GraphEdge*>(&i)!=INVALID &&
marci@992: !(*backward_filter)[i]) Parent::nextIn(i);
marci@992: }
marci@992: }
marci@992:
marci@992: Node source(Edge e) const {
marci@992: return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
marci@992: Node target(Edge e) const {
marci@992: return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
marci@992:
marci@992: /// Gives back the opposite edge.
marci@992: Edge opposite(const Edge& e) const {
marci@992: Edge f=e;
marci@992: f.backward=!f.backward;
marci@992: return f;
marci@992: }
marci@992:
marci@992: /// \warning This is a linear time operation and works only if
marci@992: /// \c Graph::EdgeIt is defined.
marci@992: /// \todo hmm
marci@992: int edgeNum() const {
marci@992: int i=0;
marci@992: Edge e;
marci@992: for (first(e); e!=INVALID; next(e)) ++i;
marci@992: return i;
marci@992: }
marci@992:
marci@992: bool forward(const Edge& e) const { return !e.backward; }
marci@992: bool backward(const Edge& e) const { return e.backward; }
marci@992:
marci@992: template <typename T>
alpar@1401: /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
marci@992: /// _Graph::EdgeMap one for the forward edges and
marci@992: /// one for the backward edges.
marci@992: class EdgeMap {
marci@992: template <typename TT> friend class EdgeMap;
marci@992: typename _Graph::template EdgeMap<T> forward_map, backward_map;
marci@992: public:
marci@992: typedef T Value;
marci@992: typedef Edge Key;
marci@992:
alpar@1401: EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
marci@992: ForwardFilterMap, BackwardFilterMap>& g) :
marci@992: forward_map(*(g.graph)), backward_map(*(g.graph)) { }
marci@992:
alpar@1401: EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
marci@992: ForwardFilterMap, BackwardFilterMap>& g, T a) :
marci@992: forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
marci@992:
marci@992: void set(Edge e, T a) {
marci@992: if (!e.backward)
marci@992: forward_map.set(e, a);
marci@992: else
marci@992: backward_map.set(e, a);
marci@992: }
marci@992:
marci@992: // typename _Graph::template EdgeMap<T>::ConstReference
marci@992: // operator[](Edge e) const {
marci@992: // if (!e.backward)
marci@992: // return forward_map[e];
marci@992: // else
marci@992: // return backward_map[e];
marci@992: // }
marci@992:
marci@992: // typename _Graph::template EdgeMap<T>::Reference
marci@1016: T operator[](Edge e) const {
marci@992: if (!e.backward)
marci@992: return forward_map[e];
marci@992: else
marci@992: return backward_map[e];
marci@992: }
marci@992:
marci@992: void update() {
marci@992: forward_map.update();
marci@992: backward_map.update();
marci@992: }
marci@992: };
marci@992:
marci@992: };
marci@569:
marci@650:
alpar@1401: ///\brief An adaptor for composing a subgraph of a
marci@792: /// bidirected graph made from a directed one.
marci@612: ///
alpar@1401: /// An adaptor for composing a subgraph of a
alpar@911: /// bidirected graph made from a directed one.
alpar@911: ///
alpar@1401: ///\warning Graph adaptors are in even more experimental state than the other
alpar@879: ///parts of the lib. Use them at you own risk.
alpar@879: ///
marci@923: /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
marci@923: /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
marci@923: /// reversing its orientation. We are given moreover two bool valued
marci@923: /// maps on the edge-set,
marci@923: /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
alpar@1401: /// SubBidirGraphAdaptor implements the graph structure with node-set
marci@923: /// \f$V\f$ and edge-set
marci@923: /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
marci@792: /// The purpose of writing + instead of union is because parallel
marci@923: /// edges can arise. (Similarly, antiparallel edges also can arise).
marci@792: /// In other words, a subgraph of the bidirected graph obtained, which
marci@792: /// is given by orienting the edges of the original graph in both directions.
marci@923: /// As the oppositely directed edges are logically different,
marci@923: /// the maps are able to attach different values for them.
marci@923: ///
alpar@1401: /// An example for such a construction is \c RevGraphAdaptor where the
marci@792: /// forward_filter is everywhere false and the backward_filter is
marci@792: /// everywhere true. We note that for sake of efficiency,
alpar@1401: /// \c RevGraphAdaptor is implemented in a different way.
alpar@1401: /// But BidirGraphAdaptor is obtained from
alpar@1401: /// SubBidirGraphAdaptor by considering everywhere true
marci@910: /// valued maps both for forward_filter and backward_filter.
marci@1252: ///
alpar@1401: /// The most important application of SubBidirGraphAdaptor
alpar@1401: /// is ResGraphAdaptor, which stands for the residual graph in directed
marci@792: /// flow and circulation problems.
alpar@1401: /// As adaptors usually, the SubBidirGraphAdaptor implements the
marci@792: /// above mentioned graph structure without its physical storage,
marci@923: /// that is the whole stuff is stored in constant memory.
marci@992: template<typename _Graph,
marci@650: typename ForwardFilterMap, typename BackwardFilterMap>
alpar@1401: class SubBidirGraphAdaptor :
marci@992: public IterableGraphExtender<
alpar@1401: SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
marci@650: public:
marci@992: typedef _Graph Graph;
marci@992: typedef IterableGraphExtender<
alpar@1401: SubBidirGraphAdaptorBase<
marci@992: _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
marci@569: protected:
alpar@1401: SubBidirGraphAdaptor() { }
marci@992: public:
alpar@1401: SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
marci@992: BackwardFilterMap& _backward_filter) {
marci@992: setGraph(_graph);
marci@992: setForwardFilterMap(_forward_filter);
marci@992: setBackwardFilterMap(_backward_filter);
marci@992: }
marci@992: };
marci@650:
marci@569:
marci@650:
alpar@1401: ///\brief An adaptor for composing bidirected graph from a directed one.
marci@650: ///
alpar@1401: ///\warning Graph adaptors are in even more experimental state than the other
alpar@879: ///parts of the lib. Use them at you own risk.
alpar@879: ///
alpar@1401: /// An adaptor for composing bidirected graph from a directed one.
marci@650: /// A bidirected graph is composed over the directed one without physical
marci@650: /// storage. As the oppositely directed edges are logically different ones
marci@650: /// the maps are able to attach different values for them.
marci@650: template<typename Graph>
alpar@1401: class BidirGraphAdaptor :
alpar@1401: public SubBidirGraphAdaptor<
marci@650: Graph,
marci@650: ConstMap<typename Graph::Edge, bool>,
marci@650: ConstMap<typename Graph::Edge, bool> > {
marci@650: public:
alpar@1401: typedef SubBidirGraphAdaptor<
marci@650: Graph,
marci@650: ConstMap<typename Graph::Edge, bool>,
marci@650: ConstMap<typename Graph::Edge, bool> > Parent;
marci@650: protected:
marci@650: ConstMap<typename Graph::Edge, bool> cm;
marci@650:
alpar@1401: BidirGraphAdaptor() : Parent(), cm(true) {
marci@655: Parent::setForwardFilterMap(cm);
marci@655: Parent::setBackwardFilterMap(cm);
marci@655: }
marci@650: public:
alpar@1401: BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
marci@650: Parent::setGraph(_graph);
marci@650: Parent::setForwardFilterMap(cm);
marci@650: Parent::setBackwardFilterMap(cm);
marci@650: }
marci@738:
marci@738: int edgeNum() const {
marci@738: return 2*this->graph->edgeNum();
marci@738: }
marci@650: };
marci@650:
marci@650:
marci@650: template<typename Graph, typename Number,
marci@650: typename CapacityMap, typename FlowMap>
marci@658: class ResForwardFilter {
marci@658: // const Graph* graph;
marci@650: const CapacityMap* capacity;
marci@650: const FlowMap* flow;
marci@650: public:
marci@658: ResForwardFilter(/*const Graph& _graph, */
marci@658: const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658: /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
marci@658: ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
marci@656: void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656: void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650: bool operator[](const typename Graph::Edge& e) const {
marci@738: return (Number((*flow)[e]) < Number((*capacity)[e]));
marci@650: }
marci@650: };
marci@650:
marci@650: template<typename Graph, typename Number,
marci@650: typename CapacityMap, typename FlowMap>
marci@658: class ResBackwardFilter {
marci@650: const CapacityMap* capacity;
marci@650: const FlowMap* flow;
marci@650: public:
marci@658: ResBackwardFilter(/*const Graph& _graph,*/
marci@658: const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658: /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
marci@658: ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
marci@656: void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656: void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650: bool operator[](const typename Graph::Edge& e) const {
marci@738: return (Number(0) < Number((*flow)[e]));
marci@650: }
marci@650: };
marci@650:
marci@653:
alpar@1401: /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
marci@650:
alpar@1401: An adaptor for composing the residual graph for directed flow and circulation problems.
marci@1242: Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
marci@1242: number type. Let moreover
marci@1242: \f$f,c:A\to F\f$, be functions on the edge-set.
alpar@1401: In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
marci@1242: and \f$c\f$ for a capacity function.
marci@1242: Suppose that a graph instange \c g of type
marci@1242: \c ListGraph implements \f$G\f$.
marci@1242: \code
marci@1242: ListGraph g;
marci@1242: \endcode
alpar@1401: Then RevGraphAdaptor implements the graph structure with node-set
marci@1242: \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
marci@1242: \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
marci@1242: \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
marci@1242: i.e. the so called residual graph.
marci@1242: When we take the union \f$A_{forward}\cup A_{backward}\f$,
marci@1242: multilicities are counted, i.e. if an edge is in both
alpar@1401: \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
marci@1242: appears twice.
marci@1242: The following code shows how
marci@1242: such an instance can be constructed.
marci@1242: \code
marci@1242: typedef ListGraph Graph;
marci@1242: Graph::EdgeMap<int> f(g);
marci@1242: Graph::EdgeMap<int> c(g);
alpar@1401: ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
marci@1242: \endcode
marci@1242: \author Marton Makai
marci@1242: */
marci@650: template<typename Graph, typename Number,
marci@650: typename CapacityMap, typename FlowMap>
alpar@1401: class ResGraphAdaptor :
alpar@1401: public SubBidirGraphAdaptor<
marci@650: Graph,
marci@658: ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
marci@658: ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
marci@650: public:
alpar@1401: typedef SubBidirGraphAdaptor<
marci@650: Graph,
marci@658: ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
marci@658: ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
marci@650: protected:
marci@650: const CapacityMap* capacity;
marci@650: FlowMap* flow;
marci@658: ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
marci@658: ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
alpar@1401: ResGraphAdaptor() : Parent(),
marci@658: capacity(0), flow(0) { }
marci@658: void setCapacityMap(const CapacityMap& _capacity) {
marci@658: capacity=&_capacity;
marci@658: forward_filter.setCapacity(_capacity);
marci@658: backward_filter.setCapacity(_capacity);
marci@658: }
marci@658: void setFlowMap(FlowMap& _flow) {
marci@658: flow=&_flow;
marci@658: forward_filter.setFlow(_flow);
marci@658: backward_filter.setFlow(_flow);
marci@658: }
marci@650: public:
alpar@1401: ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
marci@650: FlowMap& _flow) :
marci@650: Parent(), capacity(&_capacity), flow(&_flow),
marci@658: forward_filter(/*_graph,*/ _capacity, _flow),
marci@658: backward_filter(/*_graph,*/ _capacity, _flow) {
marci@650: Parent::setGraph(_graph);
marci@650: Parent::setForwardFilterMap(forward_filter);
marci@650: Parent::setBackwardFilterMap(backward_filter);
marci@650: }
marci@650:
marci@660: typedef typename Parent::Edge Edge;
marci@660:
marci@660: void augment(const Edge& e, Number a) const {
marci@650: if (Parent::forward(e))
marci@650: flow->set(e, (*flow)[e]+a);
marci@650: else
marci@650: flow->set(e, (*flow)[e]-a);
marci@650: }
marci@650:
marci@660: /// \brief Residual capacity map.
marci@660: ///
marci@910: /// In generic residual graphs the residual capacity can be obtained
marci@910: /// as a map.
marci@660: class ResCap {
marci@660: protected:
alpar@1401: const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
marci@660: public:
alpar@987: typedef Number Value;
alpar@987: typedef Edge Key;
alpar@1401: ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
marci@888: _res_graph) : res_graph(&_res_graph) { }
marci@660: Number operator[](const Edge& e) const {
marci@660: if (res_graph->forward(e))
marci@660: return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
marci@660: else
marci@660: return (*(res_graph->flow))[e];
marci@660: }
marci@660: };
marci@660:
alpar@1401: // KEEP_MAPS(Parent, ResGraphAdaptor);
marci@650: };
marci@650:
marci@650:
marci@998:
marci@998: template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401: class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@998: public:
marci@998: typedef _Graph Graph;
alpar@1401: typedef GraphAdaptorBase<_Graph> Parent;
marci@998: protected:
marci@998: FirstOutEdgesMap* first_out_edges;
alpar@1401: ErasingFirstGraphAdaptorBase() : Parent(),
marci@998: first_out_edges(0) { }
marci@998:
marci@998: void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
marci@998: first_out_edges=&_first_out_edges;
marci@998: }
marci@998:
marci@998: public:
marci@998:
marci@998: typedef typename Parent::Node Node;
marci@998: typedef typename Parent::Edge Edge;
marci@998:
marci@998: void firstOut(Edge& i, const Node& n) const {
marci@998: i=(*first_out_edges)[n];
marci@998: }
marci@998:
marci@998: void erase(const Edge& e) const {
marci@998: Node n=source(e);
marci@998: Edge f=e;
marci@998: Parent::nextOut(f);
marci@998: first_out_edges->set(n, f);
marci@998: }
marci@998: };
marci@998:
marci@998:
marci@612: /// For blocking flows.
marci@556:
alpar@1401: ///\warning Graph adaptors are in even more experimental state than the other
alpar@879: ///parts of the lib. Use them at you own risk.
alpar@879: ///
alpar@1401: /// This graph adaptor is used for on-the-fly
marci@792: /// Dinits blocking flow computations.
marci@612: /// For each node, an out-edge is stored which is used when the
marci@612: /// \code
marci@612: /// OutEdgeIt& first(OutEdgeIt&, const Node&)
marci@612: /// \endcode
marci@612: /// is called.
marci@556: ///
marci@792: /// \author Marton Makai
marci@998: template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401: class ErasingFirstGraphAdaptor :
marci@998: public IterableGraphExtender<
alpar@1401: ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
marci@650: public:
marci@998: typedef _Graph Graph;
marci@998: typedef IterableGraphExtender<
alpar@1401: ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
alpar@1401: ErasingFirstGraphAdaptor(Graph& _graph,
marci@998: FirstOutEdgesMap& _first_out_edges) {
marci@998: setGraph(_graph);
marci@998: setFirstOutEdgesMap(_first_out_edges);
marci@998: }
marci@1019:
marci@998: };
marci@556:
deba@1472: template <typename _Graph>
deba@1697: class SplitGraphAdaptorBase
deba@1697: : public GraphAdaptorBase<_Graph> {
deba@1697: public:
deba@1697: typedef GraphAdaptorBase<_Graph> Parent;
deba@1697:
deba@1697: class Node;
deba@1697: class Edge;
deba@1697: template <typename T> class NodeMap;
deba@1697: template <typename T> class EdgeMap;
deba@1697:
deba@1697:
deba@1697: class Node : public Parent::Node {
deba@1697: friend class SplitGraphAdaptorBase;
deba@1697: template <typename T> friend class NodeMap;
deba@1697: typedef typename Parent::Node NodeParent;
deba@1697: private:
deba@1697:
deba@1697: bool entry;
deba@1697: Node(typename Parent::Node _node, bool _entry)
deba@1697: : Parent::Node(_node), entry(_entry) {}
deba@1697:
deba@1697: public:
deba@1697: Node() {}
deba@1697: Node(Invalid) : NodeParent(INVALID), entry(true) {}
deba@1697:
deba@1697: bool operator==(const Node& node) const {
deba@1697: return NodeParent::operator==(node) && entry == node.entry;
deba@1697: }
deba@1697:
deba@1697: bool operator!=(const Node& node) const {
deba@1697: return !(*this == node);
deba@1697: }
deba@1697:
deba@1697: bool operator<(const Node& node) const {
deba@1697: return NodeParent::operator<(node) ||
deba@1697: (NodeParent::operator==(node) && entry < node.entry);
deba@1697: }
deba@1697: };
deba@1697:
deba@1697: /// \todo May we want VARIANT/union type
deba@1697: class Edge : public Parent::Edge {
deba@1697: friend class SplitGraphAdaptorBase;
deba@1697: template <typename T> friend class EdgeMap;
deba@1697: private:
deba@1697: typedef typename Parent::Edge EdgeParent;
deba@1697: typedef typename Parent::Node NodeParent;
deba@1697: NodeParent bind;
deba@1697:
deba@1697: Edge(const EdgeParent& edge, const NodeParent& node)
deba@1697: : EdgeParent(edge), bind(node) {}
deba@1697: public:
deba@1697: Edge() {}
deba@1697: Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
deba@1697:
deba@1697: bool operator==(const Edge& edge) const {
deba@1697: return EdgeParent::operator==(edge) && bind == edge.bind;
deba@1697: }
deba@1697:
deba@1697: bool operator!=(const Edge& edge) const {
deba@1697: return !(*this == edge);
deba@1697: }
deba@1697:
deba@1697: bool operator<(const Edge& edge) const {
deba@1697: return EdgeParent::operator<(edge) ||
deba@1697: (EdgeParent::operator==(edge) && bind < edge.bind);
deba@1697: }
deba@1697: };
deba@1697:
deba@1697: void first(Node& node) const {
deba@1697: Parent::first(node);
deba@1697: node.entry = true;
deba@1697: }
deba@1697:
deba@1697: void next(Node& node) const {
deba@1697: if (node.entry) {
deba@1697: node.entry = false;
deba@1697: } else {
deba@1697: node.entry = true;
deba@1697: Parent::next(node);
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: void first(Edge& edge) const {
deba@1697: Parent::first(edge);
deba@1697: if ((typename Parent::Edge&)edge == INVALID) {
deba@1697: Parent::first(edge.bind);
deba@1697: } else {
deba@1697: edge.bind = INVALID;
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: void next(Edge& edge) const {
deba@1697: if ((typename Parent::Edge&)edge != INVALID) {
deba@1697: Parent::next(edge);
deba@1697: if ((typename Parent::Edge&)edge == INVALID) {
deba@1697: Parent::first(edge.bind);
deba@1697: }
deba@1697: } else {
deba@1697: Parent::next(edge.bind);
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: void firstIn(Edge& edge, const Node& node) const {
deba@1697: if (node.entry) {
deba@1697: Parent::firstIn(edge, node);
deba@1697: edge.bind = INVALID;
deba@1697: } else {
deba@1697: (typename Parent::Edge&)edge = INVALID;
deba@1697: edge.bind = node;
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: void nextIn(Edge& edge) const {
deba@1697: if ((typename Parent::Edge&)edge != INVALID) {
deba@1697: Parent::nextIn(edge);
deba@1697: } else {
deba@1697: edge.bind = INVALID;
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: void firstOut(Edge& edge, const Node& node) const {
deba@1697: if (!node.entry) {
deba@1697: Parent::firstOut(edge, node);
deba@1697: edge.bind = INVALID;
deba@1697: } else {
deba@1697: (typename Parent::Edge&)edge = INVALID;
deba@1697: edge.bind = node;
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: void nextOut(Edge& edge) const {
deba@1697: if ((typename Parent::Edge&)edge != INVALID) {
deba@1697: Parent::nextOut(edge);
deba@1697: } else {
deba@1697: edge.bind = INVALID;
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: Node source(const Edge& edge) const {
deba@1697: if ((typename Parent::Edge&)edge != INVALID) {
deba@1697: return Node(Parent::source(edge), false);
deba@1697: } else {
deba@1697: return Node(edge.bind, true);
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: Node target(const Edge& edge) const {
deba@1697: if ((typename Parent::Edge&)edge != INVALID) {
deba@1697: return Node(Parent::target(edge), true);
deba@1697: } else {
deba@1697: return Node(edge.bind, false);
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: static bool entryNode(const Node& node) {
deba@1697: return node.entry;
deba@1697: }
deba@1697:
deba@1697: static bool exitNode(const Node& node) {
deba@1697: return !node.entry;
deba@1697: }
deba@1697:
deba@1697: static Node getEntry(const typename Parent::Node& node) {
deba@1697: return Node(node, true);
deba@1697: }
deba@1697:
deba@1697: static Node getExit(const typename Parent::Node& node) {
deba@1697: return Node(node, false);
deba@1697: }
deba@1697:
deba@1697: static bool originalEdge(const Edge& edge) {
deba@1697: return (typename Parent::Edge&)edge != INVALID;
deba@1697: }
deba@1697:
deba@1697: static bool bindingEdge(const Edge& edge) {
deba@1697: return edge.bind != INVALID;
deba@1697: }
deba@1697:
deba@1697: static Node getBindedNode(const Edge& edge) {
deba@1697: return edge.bind;
deba@1697: }
deba@1697:
deba@1697: int nodeNum() const {
deba@1697: return Parent::nodeNum() * 2;
deba@1697: }
deba@1697:
deba@1697: typedef CompileTimeAnd<typename Parent::NodeNumTag,
deba@1697: typename Parent::EdgeNumTag> EdgeNumTag;
deba@1697:
deba@1697: int edgeNum() const {
deba@1697: return Parent::edgeNum() + Parent::nodeNum();
deba@1697: }
deba@1697:
deba@1697: Edge findEdge(const Node& source, const Node& target,
deba@1697: const Edge& prev = INVALID) const {
deba@1697: if (exitNode(source) && entryNode(target)) {
deba@1697: return Parent::findEdge(source, target, prev);
deba@1697: } else {
deba@1697: if (prev == INVALID && entryNode(source) && exitNode(target) &&
deba@1697: (typename Parent::Node&)source == (typename Parent::Node&)target) {
deba@1697: return Edge(INVALID, source);
deba@1697: } else {
deba@1697: return INVALID;
deba@1697: }
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: template <typename T>
deba@1697: class NodeMap : public MapBase<Node, T> {
deba@1697: typedef typename Parent::template NodeMap<T> NodeImpl;
deba@1697: public:
deba@1697: NodeMap(const SplitGraphAdaptorBase& _graph)
deba@1697: : entry(_graph), exit(_graph) {}
deba@1697: NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@1697: : entry(_graph, t), exit(_graph, t) {}
deba@1697:
deba@1697: void set(const Node& key, const T& val) {
deba@1697: if (key.entry) { entry.set(key, val); }
deba@1697: else {exit.set(key, val); }
deba@1697: }
deba@1697:
deba@1725: typename MapTraits<NodeImpl>::ReturnValue
deba@1697: operator[](const Node& key) {
deba@1697: if (key.entry) { return entry[key]; }
deba@1697: else { return exit[key]; }
deba@1697: }
deba@1697:
deba@1725: typename MapTraits<NodeImpl>::ConstReturnValue
deba@1725: operator[](const Node& key) const {
deba@1697: if (key.entry) { return entry[key]; }
deba@1697: else { return exit[key]; }
deba@1697: }
deba@1697:
deba@1697: private:
deba@1697: NodeImpl entry, exit;
deba@1697: };
deba@1697:
deba@1697: template <typename T>
deba@1697: class EdgeMap : public MapBase<Edge, T> {
deba@1697: typedef typename Parent::template NodeMap<T> NodeImpl;
deba@1697: typedef typename Parent::template EdgeMap<T> EdgeImpl;
deba@1697: public:
deba@1697: EdgeMap(const SplitGraphAdaptorBase& _graph)
deba@1697: : bind(_graph), orig(_graph) {}
deba@1697: EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
deba@1697: : bind(_graph, t), orig(_graph, t) {}
deba@1697:
deba@1697: void set(const Edge& key, const T& val) {
deba@1697: if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
deba@1697: else {bind.set(key.bind, val); }
deba@1697: }
deba@1697:
deba@1725: typename MapTraits<EdgeImpl>::ReturnValue
deba@1697: operator[](const Edge& key) {
deba@1697: if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
deba@1697: else {return bind[key.bind]; }
deba@1697: }
deba@1697:
deba@1725: typename MapTraits<EdgeImpl>::ConstReturnValue
deba@1725: operator[](const Edge& key) const {
deba@1697: if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
deba@1697: else {return bind[key.bind]; }
deba@1697: }
deba@1697:
deba@1697: private:
deba@1697: typename Parent::template NodeMap<T> bind;
deba@1697: typename Parent::template EdgeMap<T> orig;
deba@1697: };
deba@1697:
deba@1697: template <typename EntryMap, typename ExitMap>
deba@1697: class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
deba@1697: public:
deba@1697: typedef MapBase<Node, typename EntryMap::Value> Parent;
deba@1697:
deba@1697: typedef typename Parent::Key Key;
deba@1697: typedef typename Parent::Value Value;
deba@1697:
deba@1697: CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
deba@1697: : entryMap(_entryMap), exitMap(_exitMap) {}
deba@1697:
deba@1697: Value& operator[](const Key& key) {
deba@1697: if (key.entry) {
deba@1697: return entryMap[key];
deba@1697: } else {
deba@1697: return exitMap[key];
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: Value operator[](const Key& key) const {
deba@1697: if (key.entry) {
deba@1697: return entryMap[key];
deba@1697: } else {
deba@1697: return exitMap[key];
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: void set(const Key& key, const Value& value) {
deba@1697: if (key.entry) {
deba@1697: entryMap.set(key, value);
deba@1697: } else {
deba@1697: exitMap.set(key, value);
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: private:
deba@1697:
deba@1697: EntryMap& entryMap;
deba@1697: ExitMap& exitMap;
deba@1697:
deba@1697: };
deba@1697:
deba@1697: template <typename EdgeMap, typename NodeMap>
deba@1697: class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
deba@1697: public:
deba@1697: typedef MapBase<Edge, typename EdgeMap::Value> Parent;
deba@1697:
deba@1697: typedef typename Parent::Key Key;
deba@1697: typedef typename Parent::Value Value;
deba@1697:
deba@1697: CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
deba@1697: : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
deba@1697:
deba@1697: void set(const Edge& edge, const Value& val) {
deba@1697: if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1697: edgeMap.set(edge, val);
deba@1697: } else {
deba@1697: nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: Value operator[](const Key& edge) const {
deba@1697: if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1697: return edgeMap[edge];
deba@1697: } else {
deba@1697: return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: Value& operator[](const Key& edge) {
deba@1697: if (SplitGraphAdaptorBase::originalEdge(edge)) {
deba@1697: return edgeMap[edge];
deba@1697: } else {
deba@1697: return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
deba@1697: }
deba@1697: }
deba@1697:
deba@1697: private:
deba@1697: EdgeMap& edgeMap;
deba@1697: NodeMap& nodeMap;
deba@1697: };
deba@1697:
deba@1697: };
deba@1697:
deba@1697: template <typename _Graph>
deba@1697: class SplitGraphAdaptor
deba@1697: : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
deba@1697: public:
deba@1697: typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@1697:
deba@1697: SplitGraphAdaptor(_Graph& graph) {
deba@1697: Parent::setGraph(graph);
deba@1697: }
deba@1697:
deba@1697:
deba@1697: };
deba@1697:
marci@556: ///@}
marci@556:
alpar@921: } //namespace lemon
marci@556:
alpar@1401: #endif //LEMON_GRAPH_ADAPTOR_H
marci@556: