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
20 \page getting_started Getting Started
22 At the beginning we strongly suggest that you open your favorite text
23 editor and enter the code simultaneously as you read it. Compiling the
24 demos is also a good exercise.
26 As the first example we show you a lemon style "Hello World"
27 program. Now we explain almost every line, but later we will skip the
28 basics and focus on new things.
30 \section hello_world Hello World in LEMON
32 In this little program we give you a taste of the LEMON programming.
34 Let's see the code fragment to fragment!
36 \dontinclude hello_world.cc
40 We want to use a \c lemon::ListGraph so the include goes like this:
44 The next few lines are not necessary but useful shortcuts, if you don't
45 want to type \c lemon::ListGraph::Node every time.
49 For this demo we need to declare a ListGraph and a special NodeMap to
50 store the characters associated to the graph's nodes.
54 Adding nodes to the graph is very easy.
58 When a new node or edge is added to the graph the assigned maps are automatically resized.
59 So graphs can be built dynamically. The usage of a map is very natural.
63 Notice that no reference or additional assignment is needed to work with nodes.
64 They won't become illegal or won't lead to throwing any exceptions.
65 You can declare and handle a node like every other basic type such as \c int.
69 As one expects adding an Edge is similar. You need to define the \b source node
70 and the \b destination node. The nodes must belong to the graph of course. The
71 Edge has the direction from the source to the destination. In some cases you don't
72 want the edges to be directed - then you use an undirected graph. For example
77 In the next few lines we add some more nodes and edges and to the graph we need.
78 Those lines are not very interesting so we skip them, but you find the whole
79 working program in file hello_world.cc in the demo section.
81 The next statement must be familiar. But what is that INVALID in the \c while
82 test statement? In LEMON we usually use the INVALID to check if an object
83 contains valid information.
87 We take the current node and write out the character assigned to it. Is's easy
92 And here comes the trick. OutEdgeIt iterates on outgoing edges of a given node.
93 We pass the current node as argument to it, so the \c edge iterator will stand
94 on the first outgoing edge of the current node, or will be INVALID if the node
95 has no outgoing edges.
99 The graph we built before is linear, so we know that it ends, when no more outgoing
100 edges found. Otherwise the current node must be the node the edge points to.
101 Basic information about an edge can be requested from the graph.
105 Finish the code, just to be precise.
110 \section compile_hw Compiling Hello World
111 To compile this program all you have to do is type in
112 \code g++ -ohello_world hello_world.cc \endcode
113 and press \c Enter! This is the case if you installed LEMON on your system.
114 (For more information see the LEMON installation instructions.)
116 This is because LEMON is template library and most of it's code has to be available
117 as source code during compilation.
119 Most programs using LEMON will compile as easy as this one unless you want to
120 use some performance measuring tools LEMON can provide. Then you need to link
121 an additional library against your program.