|
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 |
|
25 using namespace lemon; |
|
26 |
|
27 |
|
28 typedef ListGraph::Node Node; |
|
29 typedef ListGraph::NodeIt NodeIt; |
|
30 typedef ListGraph::Edge Edge; |
|
31 typedef ListGraph::EdgeIt EdgeIt; |
|
32 typedef ListGraph::OutEdgeIt OutEdgeIt; |
|
33 typedef ListGraph::InEdgeIt InEdgeIt; |
|
34 |
|
35 int 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,"indeg_graph_rev_out.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 |