demo/sub_graph_adaptor_demo.cc
author deba
Wed, 09 Nov 2005 13:04:39 +0000
changeset 1783 474666e89a2a
parent 1636 260ac104190f
child 1875 98698b69a902
permissions -rw-r--r--
One more bug fix
athos@1583
     1
/* -*- C++ -*-
ladanyi@1636
     2
 * demo/sub_graph_adaptor_demo.cc - Part of LEMON, a generic C++ optimization
ladanyi@1636
     3
 * library
athos@1583
     4
 *
athos@1583
     5
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
athos@1583
     6
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
athos@1583
     7
 *
athos@1583
     8
 * Permission to use, modify and distribute this software is granted
athos@1583
     9
 * provided that this copyright notice appears in all copies. For
athos@1583
    10
 * precise terms see the accompanying LICENSE file.
athos@1583
    11
 *
athos@1583
    12
 * This software is provided "AS IS" with no warranty of any kind,
athos@1583
    13
 * express or implied, and with no claim as to its suitability for any
athos@1583
    14
 * purpose.
athos@1583
    15
 *
athos@1583
    16
 */
athos@1583
    17
athos@1583
    18
///\ingroup demos
athos@1583
    19
///\file
athos@1583
    20
///\brief Computing maximum number of edge-disjoint shortest paths
athos@1583
    21
///
athos@1583
    22
/// This program computes a maximum number of edge-disjoint shortest paths
athos@1583
    23
/// between nodes \c s and \c t.
alpar@1641
    24
///
alpar@1641
    25
/// \include sub_graph_adaptor_demo.cc
marci@866
    26
athos@1560
    27
// Use a DIMACS max flow file as input.
alpar@1401
    28
// sub_graph_adaptor_demo < dimacs_max_flow_file
athos@1583
    29
// Modified to eat lemon graph format! 
athos@1583
    30
marci@866
    31
marci@866
    32
#include <iostream>
marci@866
    33
#include <fstream>
marci@866
    34
alpar@921
    35
#include <lemon/smart_graph.h>
alpar@921
    36
#include <lemon/dijkstra.h>
alpar@921
    37
#include <lemon/maps.h>
alpar@1401
    38
#include <lemon/graph_adaptor.h>
alpar@921
    39
#include <lemon/dimacs.h>
alpar@921
    40
#include <lemon/preflow.h>
marci@931
    41
#include <tight_edge_filter_map.h>
marci@866
    42
athos@1583
    43
#include <lemon/graph_reader.h>
athos@1577
    44
athos@1577
    45
alpar@921
    46
using namespace lemon;
marci@866
    47
marci@866
    48
using std::cout;
marci@866
    49
using std::endl;
marci@866
    50
athos@1560
    51
int main(int argc, char *argv[]) 
athos@1560
    52
{
athos@1560
    53
  if(argc<2)
athos@1560
    54
  {
athos@1583
    55
      std::cerr << "USAGE: sub_graph_adaptor_demo input_file.lgf" << std::endl;
athos@1583
    56
      std::cerr << "The file 'input_file.lgf' has to contain a max flow "
athos@1583
    57
		<< "instance in \n LEMON format "
athos@1583
    58
		<< "(e.g. sub_gad_input.lgf is such a file)." 
athos@1583
    59
		<< std::endl;
athos@1560
    60
      return 0;
athos@1560
    61
  }
athos@1560
    62
athos@1560
    63
athos@1560
    64
  //input stream to read the graph from
athos@1560
    65
  std::ifstream is(argv[1]);
athos@1560
    66
marci@866
    67
  typedef SmartGraph Graph;
marci@866
    68
marci@866
    69
  typedef Graph::Edge Edge;
marci@866
    70
  typedef Graph::Node Node;
marci@866
    71
  typedef Graph::EdgeIt EdgeIt;
marci@866
    72
  typedef Graph::NodeIt NodeIt;
marci@866
    73
  typedef Graph::EdgeMap<int> LengthMap;
marci@866
    74
marci@866
    75
  Graph g;
marci@866
    76
  Node s, t;
marci@866
    77
  LengthMap length(g);
marci@866
    78
athos@1583
    79
  //readDimacs(is, g, length, s, t);
marci@866
    80
athos@1577
    81
athos@1583
    82
  GraphReader<SmartGraph> reader(is,g);
athos@1583
    83
  reader.readNode("source",s).readNode("target",t)
athos@1583
    84
    .readEdgeMap("length",length).run();
athos@1577
    85
alpar@986
    86
  cout << "edges with lengths (of form id, source--length->target): " << endl;
marci@866
    87
  for(EdgeIt e(g); e!=INVALID; ++e) 
alpar@986
    88
    cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" 
alpar@986
    89
	 << length[e] << "->" << g.id(g.target(e)) << endl;
marci@866
    90
marci@866
    91
  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
marci@866
    92
marci@866
    93
  typedef Dijkstra<Graph, LengthMap> Dijkstra;
marci@866
    94
  Dijkstra dijkstra(g, length);
marci@866
    95
  dijkstra.run(s);
marci@866
    96
marci@869
    97
  // This map returns true exactly for those edges which are 
marci@869
    98
  // tight w.r.t the length funcion and the potential 
marci@869
    99
  // given by the dijkstra algorithm.
marci@866
   100
  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
marci@866
   101
    TightEdgeFilter;
marci@866
   102
  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
marci@866
   103
marci@932
   104
//  ConstMap<Node, bool> const_true_map(true);
marci@869
   105
  // This graph contains exaclty the tight edges.
alpar@1401
   106
// typedef SubGraphAdaptor<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
alpar@1401
   107
  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
marci@932
   108
  SubGW gw(g, tight_edge_filter);
marci@866
   109
marci@866
   110
  ConstMap<Edge, int> const_1_map(1);
marci@866
   111
  Graph::EdgeMap<int> flow(g, 0);
marci@869
   112
  // Max flow between s and t in the graph of tight edges.
marci@866
   113
  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
marci@866
   114
    preflow(gw, s, t, const_1_map, flow);
marci@866
   115
  preflow.run();
marci@866
   116
athos@1544
   117
  cout << "maximum number of edge-disjoint shortest paths: " 
marci@931
   118
       << preflow.flowValue() << endl;
marci@866
   119
  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
marci@866
   120
       << endl;
marci@866
   121
  for(EdgeIt e(g); e!=INVALID; ++e) 
marci@866
   122
    if (flow[e])
marci@931
   123
      cout << " " << g.id(e) << ", "
alpar@986
   124
	   << g.id(g.source(e)) << "--" 
alpar@986
   125
	   << length[e] << "->" << g.id(g.target(e)) << endl;
marci@866
   126
}