SplitGraphAdaptor< _Graph > Class Template Reference
[Adaptor Classes for Graphs]

---

Detailed Description

template<typename _Graph>
class lemon::SplitGraphAdaptor< _Graph >

This is an graph adaptor which splits all node into an in-node and an out-node. Formaly, the adaptor replaces each node in the graph with two node, node and node. If there is an edge in the original graph the new target of the edge will be and similarly the source of the original edge will be . The adaptor will add for each node in the original graph an additional edge which will connect .

The aim of this class is to run algorithm with node costs if the algorithm can use directly just edge costs. In this case we should use a SplitGraphAdaptor and set the node cost of the graph to the bind edge in the adapted graph.

By example a maximum flow algoritm can compute how many edge disjoint paths are in the graph. But we would like to know how many node disjoint paths are in the graph. First we have to adapt the graph with the SplitGraphAdaptor. Then run the flow algorithm on the adapted graph. The bottleneck of the flow will be the bind edges which bounds the flow with the count of the node disjoint paths.

      typedef SplitGraphAdaptor<SmartGraph> SGraph;
     
      SGraph sgraph(graph);
     
      typedef ConstMap<SGraph::Edge, int> SCapacity;
      SCapacity scapacity(1);
     
      SGraph::EdgeMap<int> sflow(sgraph);
     
      Preflow<SGraph, SCapacity> 
        spreflow(sgraph, scapacity, 
                 SGraph::outNode(source), SGraph::inNode(target));
                                                 
      spreflow.run();

The result of the mamixum flow on the original graph shows the next figure:

And the maximum flow on the adapted graph:

The second solution contains just 3 disjoint paths while the first 4. The full code can be found in the disjoint_paths_demo.cc demo file.

This graph adaptor is fully conform to the Graph concept and contains some additional member functions and types. The documentation of some member functions may be found just in the SplitGraphAdaptorBase class.

See also:

SplitGraphAdaptorBase

#include <lemon/graph_adaptor.h>

Inherits lemon::AlterableSplitGraphAdaptor<_Graph>.

List of all members.

Classes
class	CombinedEdgeMap
	EdgeMap combined from an original EdgeMap and NodeMap. More...
class	CombinedNodeMap
	NodeMap combined from two original NodeMap. More...
Public Member Functions
	SplitGraphAdaptor (_Graph &g)
Static Public Member Functions
template<typename InNodeMap , typename OutNodeMap >
static CombinedNodeMap < InNodeMap, OutNodeMap >	combinedNodeMap (InNodeMap &in_map, OutNodeMap &out_map)
template<typename GraphEdgeMap , typename GraphNodeMap >
static CombinedEdgeMap < GraphEdgeMap, GraphNodeMap >	combinedEdgeMap (GraphEdgeMap &edge_map, GraphNodeMap &node_map)

---

Constructor & Destructor Documentation

SplitGraphAdaptor

(

_Graph &

g

)

[inline]

Constructor of the adaptor.

---

Member Function Documentation

static CombinedNodeMap<InNodeMap, OutNodeMap> combinedNodeMap	(	InNodeMap &	in_map,
		OutNodeMap &	out_map
	)			[inline, static]

Just gives back a combined node map.

static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap> combinedEdgeMap	(	GraphEdgeMap &	edge_map,
		GraphNodeMap &	node_map
	)			[inline, static]

Just gives back a combined edge map.