COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/graph_orientation.cc @ 1862:d47ebd34e581

Last change on this file since 1862:d47ebd34e581 was 1687:7dc3abbb7636, checked in by Alpar Juttner, 19 years ago
  • silly mistake fixed
  • output is graph_orientation.eps
  • sample input file added
File size: 3.5 KB
Line 
1/* -*- C++ -*-
2 * demo/graph_orientation.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17
18#include <lemon/list_graph.h>
19#include <lemon/graph_reader.h>
20#include <lemon/iterable_maps.h>
21#include <lemon/xy.h>
22#include <lemon/graph_to_eps.h>
23
24
25using namespace lemon;
26 
27
28typedef ListGraph::Node Node;
29typedef ListGraph::NodeIt NodeIt;
30typedef ListGraph::Edge Edge;
31typedef ListGraph::EdgeIt EdgeIt;
32typedef ListGraph::OutEdgeIt OutEdgeIt;
33typedef ListGraph::InEdgeIt InEdgeIt;
34
35int main(int argc, char** argv)
36{
37  if(argc!=2) {
38    std::cerr << "\n  USAGE: " << argv[0]
39              << " input_file.lgf" << std::endl << std::endl;
40    std::cerr << "  The file 'input_file.lgf' has to contain "
41              << "at least three node maps called \n  'f', 'coordinates_x' "
42              << "and 'coordinates_y'.\n"
43              << "  The in-degree requirement is given by 'f', while the two "
44              << "others is used\n  to create to output drawing."
45              << std::endl;
46    return 1;
47  }
48 
49  ListGraph g;
50
51  ListGraph::NodeMap<int> f(g); //in-deg requirement;
52  ListGraph::NodeMap<int> id(g);
53  ListGraph::NodeMap<xy<double> > coords(g);
54 
55  try {
56    GraphReader<ListGraph> reader(argv[1],g);
57    reader.readNodeMap("f",f);
58    reader.readNodeMap("id",id);
59    reader.readNodeMap("coordinates_x",xMap(coords));
60    reader.readNodeMap("coordinates_y",yMap(coords));
61    reader.run();
62  } catch (DataFormatError& error) {
63    std::cerr << error.what() << std::endl;
64    return 1;
65  }
66
67 
68  ListGraph::NodeMap<int> level(g,0);
69 
70  ListGraph::NodeMap<int> def(g); //deficiency of the nodes
71  def = subMap(f,InDegMap<ListGraph>(g));
72 
73  IterableBoolNodeMap<ListGraph> active(g,false);
74  for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
75 
76  ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be
77                                         //                  reversed
78
79  int nodeNum=countNodes(g);
80 
81  Node act;
82  while((act=IterableBoolNodeMap<ListGraph>::TrueIt(active))!=INVALID) {
83    std::cout << "Process node " << id[act]
84              << " (def=" << def[act]
85              << " lev=" << level[act] << "): ";
86    OutEdgeIt e(g,act);
87    while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
88    if(e!=INVALID) {
89      std::cout << " REVERT EDGE " << g.id(e)
90                << " (" << id[g.source(e)] << "---"
91                << id[g.target(e)] << ")"
92                << std::endl;
93      if(--def[act]==0) active[act]=false;
94      if(++def[g.target(e)]>0) active[g.target(e)]=true;
95      g.reverseEdge(e);
96      rev[e]=!rev[e];
97    }
98    else {
99      std::cout << " LIFT" << std::endl;
100      if(++level[act]>nodeNum) {
101        std::cout << "NINCS ILYEN\n";
102        return 1;
103      }
104    }
105  }
106 
107  //Show the graph
108
109  graphToEps(g,"graph_orientation.eps").scaleToA4().
110    title("Sample .eps figure (fits to A4)").
111    copyright("(C) 2005 LEMON Project").
112    nodeScale(15).
113    coords(coords).
114    negateY().
115    edgeColors(composeMap(ColorSet(),rev)).
116    edgeWidthScale(1).
117    nodeTexts(f).nodeTextSize(20).
118    drawArrows().arrowWidth(10).arrowLength(10).
119    run();
120
121 
122} //end of main()
123
124
Note: See TracBrowser for help on using the repository browser.