1.1 --- a/demo/disjoint_paths.cc	Mon May 15 09:46:33 2006 +0000
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,107 +0,0 @@
     1.4 -/* -*- C++ -*-
     1.5 - *
     1.6 - * This file is a part of LEMON, a generic C++ optimization library
     1.7 - *
     1.8 - * Copyright (C) 2003-2006
     1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 - *
    1.12 - * Permission to use, modify and distribute this software is granted
    1.13 - * provided that this copyright notice appears in all copies. For
    1.14 - * precise terms see the accompanying LICENSE file.
    1.15 - *
    1.16 - * This software is provided "AS IS" with no warranty of any kind,
    1.17 - * express or implied, and with no claim as to its suitability for any
    1.18 - * purpose.
    1.19 - *
    1.20 - */
    1.21 -
    1.22 -/// \ingroup demos
    1.23 -/// \file
    1.24 -/// \brief Node and edge disjoint paths in directed graph.
    1.25 -///
    1.26 -/// This demo program calculates how many edge disjoint and node disjoint
    1.27 -/// paths are in a directed graph between a source and a target node.
    1.28 -/// The edge disjoint paths can be computed with a flow algorithm,
    1.29 -/// in this example we use the Preflow algorithm class. To get the node
    1.30 -/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
    1.31 -/// and just then calculate the flow.  
    1.32 -///
    1.33 -/// \include disjoint_paths.cc
    1.34 -
    1.35 -#include <iostream>
    1.36 -
    1.37 -#include <lemon/smart_graph.h>
    1.38 -#include <lemon/graph_adaptor.h>
    1.39 -#include <lemon/graph_reader.h>
    1.40 -#include <lemon/preflow.h>
    1.41 -#include <lemon/graph_to_eps.h>
    1.42 -
    1.43 -using namespace lemon;
    1.44 -using namespace std;
    1.45 -
    1.46 -Color color(bool b) {
    1.47 -  return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
    1.48 -}
    1.49 -
    1.50 -int main() {
    1.51 -  cout << "This program calculates the number " <<
    1.52 -    "of disjoint paths in a graph" << endl;
    1.53 -  cout << "The graph is read from the disjoint_paths.lgf file" << endl;
    1.54 -  typedef SmartGraph Graph;
    1.55 -
    1.56 -  Graph graph;
    1.57 -
    1.58 -  Graph::NodeMap<xy<double> > coords(graph);
    1.59 -  Graph::Node source, target;
    1.60 -  GraphReader<Graph>("disjoint_paths.lgf", graph).
    1.61 -    readNodeMap("coords", coords).
    1.62 -    readNode("source", source).readNode("target", target).run();
    1.63 -
    1.64 -  typedef ConstMap<Graph::Edge, int> Capacity;
    1.65 -  Capacity capacity(1);
    1.66 -
    1.67 -  Graph::EdgeMap<int> flow(graph);
    1.68 -
    1.69 -  Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow); 
    1.70 -  
    1.71 -  preflow.run();
    1.72 -
    1.73 -  cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
    1.74 -
    1.75 -  graphToEps(graph, "edge_disjoint.eps").
    1.76 -    title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
    1.77 -    edgeColors(composeMap(functorMap(color), flow)).
    1.78 -    coords(coords).autoNodeScale().run();
    1.79 -
    1.80 -
    1.81 -  cout << "The paths are written into edge_disjoint.eps" << endl;
    1.82 -
    1.83 -  typedef SplitGraphAdaptor<SmartGraph> SGraph;
    1.84 -
    1.85 -  SGraph sgraph(graph);
    1.86 -
    1.87 -  typedef ConstMap<SGraph::Edge, int> SCapacity;
    1.88 -  SCapacity scapacity(1);
    1.89 -
    1.90 -  SGraph::EdgeMap<int> sflow(sgraph);
    1.91 -
    1.92 -  Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source), 
    1.93 -                                           SGraph::inNode(target), 
    1.94 -                                           scapacity, sflow);
    1.95 -
    1.96 -  spreflow.run();
    1.97 -
    1.98 -  cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
    1.99 -
   1.100 -
   1.101 -  graphToEps(sgraph, "node_disjoint.eps").
   1.102 -    title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
   1.103 -    edgeColors(composeMap(functorMap(color), sflow)).
   1.104 -    coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
   1.105 -    autoNodeScale().run();
   1.106 -
   1.107 -  cout << "The paths are written into node_disjoint.eps" << endl;
   1.108 -  
   1.109 -  return 0;
   1.110 -}