demo/sub_graph_adaptor_demo.cc
author deba
Wed, 01 Mar 2006 10:25:30 +0000
changeset 1991 d7442141d9ef
parent 1875 98698b69a902
child 2013 02e70e25aac5
permissions -rw-r--r--
The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.

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