Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

EdgeSubGraphWrapper Class Template Reference
[Wrapper Classes for Graphs]

#include <lemon/graph_wrapper.h>

Inheritance diagram for EdgeSubGraphWrapper:

Inheritance graph
[legend]
Collaboration diagram for EdgeSubGraphWrapper:

Collaboration graph
[legend]
List of all members.

Detailed Description

template<typename Graph, typename EdgeFilterMap>
class lemon::EdgeSubGraphWrapper< Graph, EdgeFilterMap >

Warning:
Graph wrappers are in even more experimental state than the other parts of the lib. Use them at you own risk.
A wrapper for hiding edges from a graph. This wrapper specializes SubGraphWrapper in the way that only the edge-set can be filtered. The usefulness of this wrapper is demonstrated in the problem of searching a maximum number of edge-disjoint shortest paths between two nodes s and t. Shortest here means being shortest w.r.t. non-negative edge-lengths. Note that the comprehension of the presented solution need's some knowledge from elementary combinatorial optimization.

If a single shortest path is to be searched between two nodes s and t, then this can be done easily by applying the Dijkstra algorithm class. What happens, if a maximum number of edge-disjoint shortest paths is to be computed. It can be proved that an edge can be in a shortest path if and only if it is tight with respect to the potential function computed by Dijkstra. Moreover, any path containing only such edges is a shortest one. Thus we have to compute a maximum number of edge-disjoint paths between s and t in the graph which has edge-set all the tight edges. The computation will be demonstrated on the following graph, which is read from a dimacs file.

inline_dotgraph_1

  Graph g;
  Node s, t;
  LengthMap length(g);

  readDimacs(std::cin, g, length, s, t);

  cout << "edges with lengths (of form id, source--length->target): " << endl;
  for(EdgeIt e(g); e!=INVALID; ++e) 
    cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 
         << length[e] << "->" << g.id(g.target(e)) << endl;

  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
Next, the potential function is computed with Dijkstra.
  typedef Dijkstra<Graph, LengthMap> Dijkstra;
  Dijkstra dijkstra(g, length);
  dijkstra.run(s);
Next, we consrtruct a map which filters the edge-set to the tight edges.
  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
    TightEdgeFilter;
  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
  
  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
  SubGW gw(g, tight_edge_filter);
Then, the maximum nimber of edge-disjoint s-t paths are computed with a max flow algorithm Preflow.
  ConstMap<Edge, int> const_1_map(1);
  Graph::EdgeMap<int> flow(g, 0);

  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
    preflow(gw, s, t, const_1_map, flow);
  preflow.run();
Last, the output is:
  cout << "maximum number of edge-disjoint shortest path: " 
       << preflow.flowValue() << endl;
  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
       << endl;
  for(EdgeIt e(g); e!=INVALID; ++e) 
    if (flow[e])
      cout << " " << g.id(g.source(e)) << "--" 
           << length[e] << "->" << g.id(g.target(e)) << endl;
The program has the following (expected :-)) output:
  edges with lengths (of form id, source--length->target):
   9, 5--4->6
   8, 4--2->6
   7, 3--1->5
   6, 2--3->5
   5, 2--5->6
   4, 2--2->4
   3, 1--3->4
   2, 0--1->3
   1, 0--2->2
   0, 0--3->1
  s: 0 t: 6
  maximum number of edge-disjoint shortest path: 2
  edges of the maximum number of edge-disjoint shortest s-t paths:
   9, 5--4->6
   8, 4--2->6
   7, 3--1->5
   4, 2--2->4
   2, 0--1->3
   1, 0--2->2

Author:
Marton Makai

Definition at line 593 of file graph_wrapper.h.


The documentation for this class was generated from the following file:
Generated on Sat Mar 19 10:58:51 2005 for LEMON by  doxygen 1.4.1