Major improvements in NetworkSimplex.
Main changes:
- Use -potenital[] instead of potential[] to conform to the usual
terminology.
- Use function parameter instead of #define commands to select pivot rule.
- Use much faster implementation for the candidate list pivot rule.
It is about 5-20 times faster now.
- Add a new pivot rule called "Limited Search" that is a modified
version of "Block Search". It is about 25 percent faster on rather
sparse graphs.
- By default "Limited Search" is used for sparse graphs and
"Block Search" is used otherwise. This combined method is the most
efficient on every input class.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Many doc improvements.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
21 /// \brief Demo of the graph grawing function \ref graphToEps()
23 /// This demo program shows examples how to use the function \ref
24 /// graphToEps(). It takes no input but simply creates six
25 /// <tt>.eps</tt> files demonstrating the capability of \ref
26 /// graphToEps(), and showing how to draw directed/undirected graphs,
27 /// how to handle parallel egdes, how to change the properties (like
28 /// color, shape, size, title etc.) of nodes and edges individually
29 /// using appropriate \ref maps-page "graph maps".
31 /// \include graph_to_eps_demo.cc
33 #include <lemon/math.h>
35 #include<lemon/graph_to_eps.h>
36 #include<lemon/list_graph.h>
37 #include<lemon/graph_utils.h>
40 using namespace lemon;
45 Palette paletteW(true);
48 typedef ListGraph::Node Node;
49 typedef ListGraph::NodeIt NodeIt;
50 typedef ListGraph::Edge Edge;
51 typedef dim2::Point<int> Point;
59 ListGraph::NodeMap<Point> coords(g);
60 ListGraph::NodeMap<double> sizes(g);
61 ListGraph::NodeMap<int> colors(g);
62 ListGraph::NodeMap<int> shapes(g);
63 ListGraph::EdgeMap<int> ecolors(g);
64 ListGraph::EdgeMap<int> widths(g);
66 coords[n1]=Point(50,50); sizes[n1]=1; colors[n1]=1; shapes[n1]=0;
67 coords[n2]=Point(50,70); sizes[n2]=2; colors[n2]=2; shapes[n2]=2;
68 coords[n3]=Point(70,70); sizes[n3]=1; colors[n3]=3; shapes[n3]=0;
69 coords[n4]=Point(70,50); sizes[n4]=2; colors[n4]=4; shapes[n4]=1;
70 coords[n5]=Point(85,60); sizes[n5]=3; colors[n5]=5; shapes[n5]=2;
74 e=g.addEdge(n1,n2); ecolors[e]=0; widths[e]=1;
75 e=g.addEdge(n2,n3); ecolors[e]=0; widths[e]=1;
76 e=g.addEdge(n3,n5); ecolors[e]=0; widths[e]=3;
77 e=g.addEdge(n5,n4); ecolors[e]=0; widths[e]=1;
78 e=g.addEdge(n4,n1); ecolors[e]=0; widths[e]=1;
79 e=g.addEdge(n2,n4); ecolors[e]=1; widths[e]=2;
80 e=g.addEdge(n3,n4); ecolors[e]=2; widths[e]=1;
82 IdMap<ListGraph,Node> id(g);
84 cout << "Create 'graph_to_eps_demo_out_pure.eps'" << endl;
85 graphToEps(g,"graph_to_eps_demo_out_pure.eps").
88 title("Sample .eps figure").
89 copyright("(C) 2003-2007 LEMON Project").
92 cout << "Create 'graph_to_eps_demo_out.eps'" << endl;
93 graphToEps(g,"graph_to_eps_demo_out.eps").
96 title("Sample .eps figure").
97 copyright("(C) 2003-2007 LEMON Project").
98 absoluteNodeSizes().absoluteEdgeWidths().
99 nodeScale(2).nodeSizes(sizes).
101 nodeColors(composeMap(palette,colors)).
102 edgeColors(composeMap(palette,ecolors)).
103 edgeWidthScale(.4).edgeWidths(widths).
104 nodeTexts(id).nodeTextSize(3).
108 cout << "Create 'graph_to_eps_demo_out_arr.eps'" << endl;
109 graphToEps(g,"graph_to_eps_demo_out_arr.eps").
111 title("Sample .eps figure (with arrowheads)").
112 copyright("(C) 2003-2007 LEMON Project").
113 absoluteNodeSizes().absoluteEdgeWidths().
114 nodeColors(composeMap(palette,colors)).
116 nodeScale(2).nodeSizes(sizes).
118 edgeColors(composeMap(palette,ecolors)).
119 edgeWidthScale(.4).edgeWidths(widths).
120 nodeTexts(id).nodeTextSize(3).
121 drawArrows().arrowWidth(1).arrowLength(1).
124 e=g.addEdge(n1,n4); ecolors[e]=2; widths[e]=1;
125 e=g.addEdge(n4,n1); ecolors[e]=1; widths[e]=2;
127 e=g.addEdge(n1,n2); ecolors[e]=1; widths[e]=1;
128 e=g.addEdge(n1,n2); ecolors[e]=2; widths[e]=1;
129 e=g.addEdge(n1,n2); ecolors[e]=3; widths[e]=1;
130 e=g.addEdge(n1,n2); ecolors[e]=4; widths[e]=1;
131 e=g.addEdge(n1,n2); ecolors[e]=5; widths[e]=1;
132 e=g.addEdge(n1,n2); ecolors[e]=6; widths[e]=1;
133 e=g.addEdge(n1,n2); ecolors[e]=7; widths[e]=1;
135 cout << "Create 'graph_to_eps_demo_out_par.eps'" << endl;
136 graphToEps(g,"graph_to_eps_demo_out_par.eps").
138 title("Sample .eps figure (parallel edges)").
139 copyright("(C) 2003-2007 LEMON Project").
140 absoluteNodeSizes().absoluteEdgeWidths().
143 nodeScale(2).nodeSizes(sizes).
144 nodeColors(composeMap(palette,colors)).
145 edgeColors(composeMap(palette,ecolors)).
146 edgeWidthScale(.4).edgeWidths(widths).
147 nodeTexts(id).nodeTextSize(3).
148 enableParallel().parEdgeDist(1.5).
151 cout << "Create 'graph_to_eps_demo_out_par_arr.eps'" << endl;
152 graphToEps(g,"graph_to_eps_demo_out_par_arr.eps").
154 title("Sample .eps figure (parallel edges and arrowheads)").
155 copyright("(C) 2003-2007 LEMON Project").
156 absoluteNodeSizes().absoluteEdgeWidths().
157 nodeScale(2).nodeSizes(sizes).
160 nodeColors(composeMap(palette,colors)).
161 edgeColors(composeMap(palette,ecolors)).
162 edgeWidthScale(.3).edgeWidths(widths).
163 nodeTexts(id).nodeTextSize(3).
164 enableParallel().parEdgeDist(1).
165 drawArrows().arrowWidth(1).arrowLength(1).
168 cout << "Create 'graph_to_eps_demo_out_a4.eps'" << endl;
169 graphToEps(g,"graph_to_eps_demo_out_a4.eps").scaleToA4().
170 title("Sample .eps figure (fits to A4)").
171 copyright("(C) 2003-2007 LEMON Project").
172 absoluteNodeSizes().absoluteEdgeWidths().
173 nodeScale(2).nodeSizes(sizes).
176 nodeColors(composeMap(palette,colors)).
177 edgeColors(composeMap(palette,ecolors)).
178 edgeWidthScale(.3).edgeWidths(widths).
179 nodeTexts(id).nodeTextSize(3).
180 enableParallel().parEdgeDist(1).
181 drawArrows().arrowWidth(1).arrowLength(1).
185 ListGraph::NodeMap<int> hcolors(h);
186 ListGraph::NodeMap<Point> hcoords(h);
188 int cols=int(sqrt(double(palette.size())));
189 for(int i=0;i<int(paletteW.size());i++) {
191 hcoords[n]=Point(i%cols,i/cols);
195 cout << "Create 'graph_to_eps_demo_out_colors.eps'" << endl;
196 graphToEps(h,"graph_to_eps_demo_out_colors.eps").
198 title("Sample .eps figure (Palette demo)").
199 copyright("(C) 2003-2007 LEMON Project").
201 absoluteNodeSizes().absoluteEdgeWidths().
203 distantColorNodeTexts().
204 // distantBWNodeTexts().
205 nodeTexts(hcolors).nodeTextSize(.6).
206 nodeColors(composeMap(paletteW,hcolors)).