COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/graph_orientation.cc @ 2071:00c4ce4f4170

Last change on this file since 2071:00c4ce4f4170 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 3.5 KB
Line 
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#include <lemon/list_graph.h>
20#include <lemon/graph_reader.h>
21#include <lemon/iterable_maps.h>
22#include <lemon/xy.h>
23#include <lemon/graph_to_eps.h>
24
25
26using namespace lemon;
27 
28
29typedef ListGraph::Node Node;
30typedef ListGraph::NodeIt NodeIt;
31typedef ListGraph::Edge Edge;
32typedef ListGraph::EdgeIt EdgeIt;
33typedef ListGraph::OutEdgeIt OutEdgeIt;
34typedef ListGraph::InEdgeIt InEdgeIt;
35
36int main(int argc, char** argv)
37{
38  if(argc!=2) {
39    std::cerr << "\n  USAGE: " << argv[0]
40              << " input_file.lgf" << std::endl << std::endl;
41    std::cerr << "  The file 'input_file.lgf' has to contain "
42              << "at least three node maps called \n  'f', 'coordinates_x' "
43              << "and 'coordinates_y'.\n"
44              << "  The in-degree requirement is given by 'f', while the two "
45              << "others is used\n  to create to output drawing."
46              << std::endl;
47    return 1;
48  }
49 
50  ListGraph g;
51
52  ListGraph::NodeMap<int> f(g); //in-deg requirement;
53  ListGraph::NodeMap<int> label(g);
54  ListGraph::NodeMap<xy<double> > coords(g);
55 
56  try {
57    GraphReader<ListGraph> reader(argv[1],g);
58    reader.readNodeMap("f",f);
59    reader.readNodeMap("label",label);
60    reader.readNodeMap("coordinates_x",xMap(coords));
61    reader.readNodeMap("coordinates_y",yMap(coords));
62    reader.run();
63  } catch (DataFormatError& error) {
64    std::cerr << error.what() << std::endl;
65    return 1;
66  }
67
68 
69  ListGraph::NodeMap<int> level(g,0);
70 
71  ListGraph::NodeMap<int> def(g); //deficiency of the nodes
72  def = subMap(f,InDegMap<ListGraph>(g));
73 
74  IterableBoolMap<ListGraph, Node> active(g,false);
75  for(NodeIt n(g);n!=INVALID;++n) active[n]=(def[n]>0);
76 
77  ListGraph::EdgeMap<bool> rev(g,false); // rev[e]==true <=> e is be
78                                         //                  reversed
79
80  int nodeNum=countNodes(g);
81 
82  Node act;
83  while((act=IterableBoolMap<ListGraph, Node>::TrueIt(active))!=INVALID) {
84    std::cout << "Process node " << label[act]
85              << " (def=" << def[act]
86              << " lev=" << level[act] << "): ";
87    OutEdgeIt e(g,act);
88    while(e!=INVALID && level[g.target(e)]>=level[act]) ++e;
89    if(e!=INVALID) {
90      std::cout << " REVERT EDGE " << g.id(e)
91                << " (" << label[g.source(e)] << "---"
92                << label[g.target(e)] << ")"
93                << std::endl;
94      if(--def[act]==0) active[act]=false;
95      if(++def[g.target(e)]>0) active[g.target(e)]=true;
96      g.reverseEdge(e);
97      rev[e]=!rev[e];
98    }
99    else {
100      std::cout << " LIFT" << std::endl;
101      if(++level[act]>nodeNum) {
102        std::cout << "NINCS ILYEN\n";
103        return 1;
104      }
105    }
106  }
107 
108  //Show the graph
109
110  graphToEps(g,"graph_orientation.eps").scaleToA4().
111    title("Sample .eps figure (fits to A4)").
112    copyright("(C) 2006 LEMON Project").
113    nodeScale(15).
114    coords(coords).
115    negateY().
116    edgeColors(composeMap(ColorSet(),rev)).
117    edgeWidthScale(1).
118    nodeTexts(f).nodeTextSize(20).
119    drawArrows().arrowWidth(10).arrowLength(10).
120    run();
121
122 
123} //end of main()
124
125
Note: See TracBrowser for help on using the repository browser.