SplitGraphAdaptor Class Template Reference
[Adaptor Classes for Graphs]

#include <lemon/graph_adaptor.h>

List of all members.


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 $ u $ node in the graph with two node, $ u_{in} $ node and $ u_{out} $ node. If there is an $ (v, u) $ edge in the original graph the new target of the edge will be $ u_{in} $ and similarly the source of the original $ (u, v) $ edge will be $ u_{out} $. The adaptor will add for each node in the original graph an additional edge which will connect $ (u_{in}, u_{out}) $.

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, int, SCapacity> 
        spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),  
                 scapacity, sflow);
                                                 
      spreflow.run();

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

edge_disjoint.png

And the maximum flow on the adapted graph:

node_disjoint.png

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


Public Member Functions

 SplitGraphAdaptor (_Graph &graph)
 Constructor of the adaptor.

Static Public Member Functions

template<typename InNodeMap, typename OutNodeMap>
static CombinedNodeMap< InNodeMap,
OutNodeMap > 
combinedNodeMap (InNodeMap &in_map, OutNodeMap &out_map)
 Just gives back a combined node map.
template<typename GraphEdgeMap, typename GraphNodeMap>
static CombinedEdgeMap< GraphEdgeMap,
GraphNodeMap > 
combinedEdgeMap (GraphEdgeMap &edge_map, GraphNodeMap &node_map)
 Just gives back a combined edge map.

Classes

class  CombinedEdgeMap
 EdgeMap combined from an original EdgeMap and NodeMap. More...
class  CombinedNodeMap
 NodeMap combined from two original NodeMap. More...


Constructor & Destructor Documentation

SplitGraphAdaptor ( _Graph &  graph  )  [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.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:50:26 2006 for LEMON by  doxygen 1.5.1