src/demo/sub_graph_wrapper_demo.cc
author marci
Fri, 01 Oct 2004 10:08:43 +0000
changeset 932 ade3cdb9b45d
parent 931 9227ecd7b0bc
child 986 e997802b855c
permissions -rw-r--r--
New EdgeSubGraphWrapper class specializing SubGraphWrapper in the way that only the edge-set can be filtered.
marci@866
     1
// -*- c++ -*-
marci@866
     2
marci@866
     3
// Use a DIMACS max flow file as stdin.
marci@866
     4
// sub_graph_wrapper_demo < dimacs_max_flow_file
marci@871
     5
// This program computes a maximum number of edge-disjoint shortest paths
marci@869
     6
// between s and t.
marci@866
     7
marci@866
     8
#include <iostream>
marci@866
     9
#include <fstream>
marci@866
    10
alpar@921
    11
#include <lemon/smart_graph.h>
alpar@921
    12
#include <lemon/dijkstra.h>
alpar@921
    13
#include <lemon/maps.h>
alpar@921
    14
#include <lemon/graph_wrapper.h>
alpar@921
    15
#include <lemon/dimacs.h>
alpar@921
    16
#include <lemon/preflow.h>
marci@931
    17
#include <tight_edge_filter_map.h>
marci@866
    18
alpar@921
    19
using namespace lemon;
marci@866
    20
marci@866
    21
using std::cout;
marci@866
    22
using std::endl;
marci@866
    23
marci@866
    24
int main()
marci@866
    25
{    
marci@866
    26
  typedef SmartGraph Graph;
marci@866
    27
marci@866
    28
  typedef Graph::Edge Edge;
marci@866
    29
  typedef Graph::Node Node;
marci@866
    30
  typedef Graph::EdgeIt EdgeIt;
marci@866
    31
  typedef Graph::NodeIt NodeIt;
marci@866
    32
  typedef Graph::EdgeMap<int> LengthMap;
marci@866
    33
marci@866
    34
  Graph g;
marci@866
    35
  Node s, t;
marci@866
    36
  LengthMap length(g);
marci@866
    37
marci@866
    38
  readDimacs(std::cin, g, length, s, t);
marci@866
    39
marci@931
    40
  cout << "edges with lengths (of form id, tail--length->head): " << endl;
marci@866
    41
  for(EdgeIt e(g); e!=INVALID; ++e) 
marci@931
    42
    cout << " " << g.id(e) << ", " << g.id(g.tail(e)) << "--" 
marci@866
    43
	 << length[e] << "->" << g.id(g.head(e)) << endl;
marci@866
    44
marci@866
    45
  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
marci@866
    46
marci@866
    47
  typedef Dijkstra<Graph, LengthMap> Dijkstra;
marci@866
    48
  Dijkstra dijkstra(g, length);
marci@866
    49
  dijkstra.run(s);
marci@866
    50
marci@869
    51
  // This map returns true exactly for those edges which are 
marci@869
    52
  // tight w.r.t the length funcion and the potential 
marci@869
    53
  // given by the dijkstra algorithm.
marci@866
    54
  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
marci@866
    55
    TightEdgeFilter;
marci@866
    56
  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
marci@866
    57
marci@932
    58
//  ConstMap<Node, bool> const_true_map(true);
marci@869
    59
  // This graph contains exaclty the tight edges.
marci@932
    60
// typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
marci@932
    61
  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
marci@932
    62
  SubGW gw(g, tight_edge_filter);
marci@866
    63
marci@866
    64
  ConstMap<Edge, int> const_1_map(1);
marci@866
    65
  Graph::EdgeMap<int> flow(g, 0);
marci@869
    66
  // Max flow between s and t in the graph of tight edges.
marci@866
    67
  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
marci@866
    68
    preflow(gw, s, t, const_1_map, flow);
marci@866
    69
  preflow.run();
marci@866
    70
marci@931
    71
  cout << "maximum number of edge-disjoint shortest path: " 
marci@931
    72
       << preflow.flowValue() << endl;
marci@866
    73
  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
marci@866
    74
       << endl;
marci@866
    75
  for(EdgeIt e(g); e!=INVALID; ++e) 
marci@866
    76
    if (flow[e])
marci@931
    77
      cout << " " << g.id(e) << ", "
marci@931
    78
	   << g.id(g.tail(e)) << "--" 
marci@866
    79
	   << length[e] << "->" << g.id(g.head(e)) << endl;
marci@866
    80
}