1.1 --- a/demo/Makefile.am Mon Sep 04 19:12:44 2006 +0000
1.2 +++ b/demo/Makefile.am Mon Sep 04 19:48:09 2006 +0000
1.3 @@ -14,6 +14,8 @@
1.4 demo/graph_orientation \
1.5 demo/min_route \
1.6 demo/hello_lemon \
1.7 + demo/hello_world \
1.8 + demo/maps_summary \
1.9 demo/sub_graph_adaptor_demo \
1.10 demo/descriptor_map_demo \
1.11 demo/coloring \
1.12 @@ -45,6 +47,8 @@
1.13
1.14 demo_coloring_SOURCES = demo/coloring.cc
1.15
1.16 +demo_maps_summary_SOURCES = demo/maps_summary.cc
1.17 +
1.18 demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
1.19
1.20 demo_grid_ugraph_demo_SOURCES = demo/grid_ugraph_demo.cc
1.21 @@ -55,6 +59,8 @@
1.22
1.23 demo_hello_lemon_SOURCES = demo/hello_lemon.cc
1.24
1.25 +demo_hello_world_SOURCES = demo/hello_world.cc
1.26 +
1.27 demo_sub_graph_adaptor_demo_SOURCES = \
1.28 demo/sub_graph_adaptor_demo.cc \
1.29 demo/tight_edge_filter_map.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/hello_world.cc Mon Sep 04 19:48:09 2006 +0000
2.3 @@ -0,0 +1,125 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2006
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +///\ingroup demos
2.23 +///\file
2.24 +///\brief LEMON style "Hello World!" program
2.25 +///
2.26 +/// This program is intended to be a "Hello World!" program that shows
2.27 +/// the very basic notions of the LEMON library: \ref graphs "graphs" and
2.28 +/// \ref maps-page "maps". Click on the links to read more about these.
2.29 +///
2.30 +/// \include hello_lemon.cc
2.31 +
2.32 +#include <iostream>
2.33 +#include <lemon/list_graph.h>
2.34 +
2.35 +using namespace lemon;
2.36 +
2.37 +typedef ListGraph::Node Node;
2.38 +typedef ListGraph::Edge Edge;
2.39 +
2.40 +
2.41 +int main( int argc, char *argv[] )
2.42 +{
2.43 + // Declare the graph itself and a NodeMap, witch will store the characters
2.44 + // assigned to the nodes
2.45 + ListGraph graph;
2.46 + ListGraph::NodeMap<char> char_map(graph);
2.47 +
2.48 + // Add nodes
2.49 + Node new_node = graph.addNode();
2.50 + char_map[new_node] = 'H';
2.51 +
2.52 + // Store the start node
2.53 + Node start_node = new_node;
2.54 +
2.55 + Node from_node = new_node;
2.56 + new_node = graph.addNode();
2.57 + char_map[new_node] = 'e';
2.58 +
2.59 + // Here we add the first edge...
2.60 + graph.addEdge( from_node, new_node );
2.61 +
2.62 + // ... and we add some more nodes and edges to the graph
2.63 + from_node = new_node;
2.64 + new_node = graph.addNode();
2.65 + char_map[new_node] = 'l';
2.66 + graph.addEdge( from_node, new_node );
2.67 +
2.68 + from_node = new_node;
2.69 + new_node = graph.addNode();
2.70 + char_map[new_node] = 'l';
2.71 + graph.addEdge( from_node, new_node );
2.72 +
2.73 + from_node = new_node;
2.74 + new_node = graph.addNode();
2.75 + char_map[new_node] = 'o';
2.76 + graph.addEdge( from_node, new_node );
2.77 +
2.78 + from_node = new_node;
2.79 + new_node = graph.addNode();
2.80 + char_map[new_node] = ' ';
2.81 + graph.addEdge( from_node, new_node );
2.82 +
2.83 + from_node = new_node;
2.84 + new_node = graph.addNode();
2.85 + char_map[new_node] = 'W';
2.86 + graph.addEdge( from_node, new_node );
2.87 +
2.88 + from_node = new_node;
2.89 + new_node = graph.addNode();
2.90 + char_map[new_node] = 'o';
2.91 + graph.addEdge( from_node, new_node );
2.92 +
2.93 + from_node = new_node;
2.94 + new_node = graph.addNode();
2.95 + char_map[new_node] = 'r';
2.96 + graph.addEdge( from_node, new_node );
2.97 +
2.98 + from_node = new_node;
2.99 + new_node = graph.addNode();
2.100 + char_map[new_node] = 'l';
2.101 + graph.addEdge( from_node, new_node );
2.102 +
2.103 + from_node = new_node;
2.104 + new_node = graph.addNode();
2.105 + char_map[new_node] = 'd';
2.106 + graph.addEdge( from_node, new_node );
2.107 +
2.108 + from_node = new_node;
2.109 + new_node = graph.addNode();
2.110 + char_map[new_node] = '\n';
2.111 + graph.addEdge( from_node, new_node );
2.112 +
2.113 +
2.114 + // iterating
2.115 + Node current_node = start_node;
2.116 + while( current_node != INVALID )
2.117 + {
2.118 + std::cout << char_map[current_node] << std::flush;
2.119 +
2.120 + ListGraph::OutEdgeIt edge(graph, current_node);
2.121 + if( edge != INVALID )
2.122 + current_node = graph.target( edge );
2.123 + else
2.124 + current_node = INVALID;
2.125 + }
2.126 +
2.127 + return 0;
2.128 +}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/demo/maps_summary.cc Mon Sep 04 19:48:09 2006 +0000
3.3 @@ -0,0 +1,53 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2006
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +///\ingroup demos
3.23 +///\file maps_summary demo program
3.24 +///\brief Introduction to LEMON maps
3.25 +///
3.26 +/// \include maps_summary.cc
3.27 +
3.28 +#include <iostream>
3.29 +#include <lemon/list_graph.h>
3.30 +
3.31 +using namespace lemon;
3.32 +
3.33 +
3.34 +template < typename GRAPH, typename MAP >
3.35 +typename MAP::Value summary( GRAPH& gr, MAP& m )
3.36 +{
3.37 + typename MAP::Value summ = typename MAP::Value();
3.38 +
3.39 + for( typename GRAPH::NodeIt n(gr); n != lemon::INVALID; ++n )
3.40 + summ += m[n];
3.41 +
3.42 + return summ;
3.43 +}
3.44 +
3.45 +
3.46 +int main( int argc, char *argv[] )
3.47 +{
3.48 + ListGraph gr;
3.49 + ListGraph::NodeMap<double> value(gr, 0.0);
3.50 +
3.51 + //TODO: build a graph
3.52 +
3.53 + std::cout << "The summary of assigned values is " << summary(gr,value) << std::endl;
3.54 +
3.55 + return 0;
3.56 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/doc/basic_concepts.dox Mon Sep 04 19:48:09 2006 +0000
4.3 @@ -0,0 +1,119 @@
4.4 +/**
4.5 +\page basic_concepts Basic concepts
4.6 +
4.7 +\section basic_graph The graph classes
4.8 +The most important classes in LEMON are the graph classes. A instance of a graph
4.9 +class is the representation of the mathematical graph. It holds the topology and
4.10 +every structural information of the graph. The structural manipulations are also
4.11 +provided by the graph object. There is no universal graph class instead we have
4.12 +different classes for different purposes. They can differ in many ways, but all
4.13 +have to satisfy one or more \ref concept "graph concepts" which are standardized
4.14 +interfaces to work whit the rest of the library. The most basic concept is the
4.15 +\ref Graph.<br>
4.16 +A good example is the \ref ListGraph which we already know from Hello World and
4.17 +will be used in our examples as well.
4.18 +
4.19 +One main advantage of the templates are, that you can write your own graph classes.
4.20 +As long as they provide the interface a concept is defining all the LEMON algorithms
4.21 +and classes will work with it properly - no representation or implementation is
4.22 +written into stone.
4.23 +
4.24 +
4.25 +\subsection basic_node Nodes
4.26 +To refer to a node of a graph we need some kind of typed variable. Graph classes
4.27 +have the Node public type for this purpose. Stacking by the last example:
4.28 +\code lemon::ListGraph::Node \endcode
4.29 +
4.30 +If the graph fits the ExtendableGraphComponent concept, then you can add new nodes
4.31 +to the graph with the addNode() member function. It returns the newly added node
4.32 +(as value). So if you need the new node to do something useful with it, for example
4.33 +create a edge, assign a value to it through \ref map1 maps.
4.34 +\code lemon::ListGraph::Node new_node = graph.addNode(); \endcode
4.35 +
4.36 +If the graph fits the ErasableGraphComponent concept you also can remove nodes
4.37 +from the graph with the erase() member function.
4.38 +\code graph.erase( new_node ); \endcode
4.39 +
4.40 +You don't have to store every node in a variable, you can access individual nodes
4.41 +with node iterators discussed in the next section. But how do you know which
4.42 +node is which?<br>
4.43 +The graph class has the id( Node n ) member function providing an unique identifier
4.44 +assigned to every node.
4.45 +
4.46 +
4.47 +\subsection basic_edge Edges
4.48 +An Edge is what you think it is. It goes from one node to another node (they can
4.49 +be identical). If the graph class is directed, the Edge is directed too. Otherwise
4.50 +the edge is considered undirected and called UEdge.
4.51 +\code lemon::ListUGraph::UEdge \endcode
4.52 +
4.53 +The addEdge() member function will create a new edge. It has two arguments, the
4.54 +source node and the target node. The graph class must be extendable.
4.55 +\code lemon::ListGraph::Edge new_edge = graph.addEdge( src_node, trg_node ); \endcode
4.56 +You can handle edge similar as nodes. The erase() member function has an edge taking
4.57 +overload too.
4.58 +
4.59 +You can ask for the source or target node of the edge by the corresponding member
4.60 +functions:
4.61 +\code
4.62 +graph.source( new_edge );
4.63 +lemon::ListGraph::Node n = graph.target( new_edge ); \endcode
4.64 +These functions are always legal even if the graph is undirected. UEdge has a
4.65 +default direction.
4.66 +
4.67 +
4.68 +\section basic_iterators Iterators
4.69 +Graphs are some kind of containers. And as you expect they have iterator types.
4.70 +One fore nodes and a couple for edges - and special classes can have additional
4.71 +iterators too. An example:
4.72 +\code lemon::ListGraph::NodeIt \endcode
4.73 +That is a node iterator. Every iterator type starts whit an name what refers to
4.74 +the iterated object, and ends whit 'It'.
4.75 +
4.76 +LEMON style iterators differs from \c stl or \c boost iterators in a very tasty
4.77 +way. A graph has no begin or end - or at least a generic graph class has none.
4.78 +If by some topology you could pick a good begin node, it would be misleading and
4.79 +incorrect. A LEMON style iterator must be initialized at construction time.
4.80 +The constructor takes the needed parameters - by a node iterator it's the graph
4.81 +object. And will be compared to the lemon::INVALID to check if it's still valid.
4.82 +Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br>
4.83 +Let's see these things working together:
4.84 +\code
4.85 +for( ListGraph::NodeIt n(graph); n != INVALID; ++n )
4.86 + do_useful_things_whit_node(n);
4.87 +\endcode
4.88 +Note that the function \c do_useful_things_with_node() expects a Node type argument
4.89 +ad we just gave him the iterator. LEMON style iterators must provide "on demand
4.90 +dereferencing". For example a NodeIt can be used everywhere a Node could. (In some
4.91 +graph classes Node is the base class of NodeIt. But in other cases this is implemented
4.92 +through typecast operator.)
4.93 +
4.94 +<b>Very important!</b> The iteration has no defined order. There is absolutely no
4.95 +guaranty that the next time the iteration will give us the nodes in the same order.
4.96 +Don't use this order to identify nodes! Use the \c id() member function of the
4.97 +graph class described above. (There is a powerful technique using maps right in
4.98 +the next page.)
4.99 +
4.100 +The \ref EdgeIt works exactly the same - nothing more to say. But there are \ref InEdgeIt
4.101 +and \ref OutEdgeIt by directed graphs and \ref IncEdgeIt by undirected graphs.
4.102 +They take two arguments. The first is a graph, the second is certain node of the
4.103 +graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it
4.104 +on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to
4.105 +the given node.
4.106 +
4.107 +\code
4.108 +for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) {
4.109 + int in = 0, out = 0;
4.110 + for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in;
4.111 + for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out;
4.112 +
4.113 + std::cout << "#" << graph.id(n) << " node has " << in << " incoming and "
4.114 + << out << "outgoing edges." << std::endl;
4.115 +}
4.116 +\endcode
4.117 +
4.118 +
4.119 +\section basic_ListGraph ListGraph - a versatile directed graph
4.120 +As you see ListGraph satisfies most of the basic concepts and ideal for general
4.121 +graph representations. It has an undirected version too: ListUGraph.
4.122 +*/
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/doc/getting_started.dox Mon Sep 04 19:48:09 2006 +0000
5.3 @@ -0,0 +1,104 @@
5.4 +/**
5.5 +\page getting_started Getting Started
5.6 +
5.7 +At the beginning we hardly suggest that you open your favorite text editor
5.8 +and enter the code simultaneously as you read it. Compiling the demos is also
5.9 +a good exercise.
5.10 +
5.11 +As the first example we show you a lemon style "Hello World" program. Now we
5.12 +explain almost every line, but later we will skip the basics and focus on new
5.13 +things.
5.14 +
5.15 +\section hello_world Hello World in LEMON
5.16 +
5.17 +In this little program we give you a taste of the LEMON programming.
5.18 +
5.19 +Let's see the code fragment to fragment!
5.20 +
5.21 +\dontinclude hello_world.cc
5.22 +\skip include
5.23 +\until iostream
5.24 +
5.25 +We want to use a \c lemon::ListGraph so the include goes like this:
5.26 +\skip include
5.27 +\until list_graph
5.28 +
5.29 +The next few lines are not necessary but useful shortcuts, if you don't
5.30 +want to type \c lemon::ListGraph::Node every time.
5.31 +\skip using
5.32 +\until Edge
5.33 +
5.34 +For this demo we need to declare a ListGraph and a special NodeMap to store the
5.35 +characters associated to the graph's nodes.
5.36 +\skip main
5.37 +\until char_map
5.38 +
5.39 +Adding nodes to the graph is very easy.
5.40 +\skip new_node
5.41 +\until addNode
5.42 +
5.43 +When a new node or edge to the graph the assigned maps are automatically resized.
5.44 +So graphs can be build dynamically. The usage of a map is very natural.
5.45 +\skip char_map
5.46 +\until char_map
5.47 +
5.48 +Notice that no reference or additional assignment needed to work with nodes.
5.49 +They won't become illegal or won't lead to throwing any exceptions.
5.50 +You can declare and handle node like every other basic type such as \c int.
5.51 +\skip Store
5.52 +\until char_map
5.53 +
5.54 +As one expects adding an Edge is similar. You need to define the \b source node
5.55 +and the \b destination node. The nodes must belong to the graph of course. The
5.56 +Edge has the direction from the source to the destination. In some case you don't
5.57 +want the edges to be directed - then you use an undirected graph. For example
5.58 +lemon::ListUGraph.
5.59 +\skip addEdge
5.60 +\until addEdge
5.61 +
5.62 +In the next few lines we add some more nodes and edges and to the graph we need.
5.63 +Those lines are not very interesting so we skip them, but you find the whole
5.64 +working program in file hello_lemon.cc in the demo section.
5.65 +
5.66 +The next statement must be familiar. But what is that INVALID in the \c while
5.67 +test statement? In LEMON we usually use the INVALID to check if an object
5.68 +contains valid information.
5.69 +\skip current_node
5.70 +\until {
5.71 +
5.72 +We take the current node and write out the character assigned to it. Is's easy
5.73 +with the \c char_map.
5.74 +\skip std
5.75 +\until std
5.76 +
5.77 +And here comes the trick. OutEdgeIt iterates on outgoing edges of a given node.
5.78 +We pass the current node as argument to it, so the \c edge iterator will stand
5.79 +on the first outgoing edge of the current node, or will be INVALID if the node
5.80 +has no outgoing edges.
5.81 +\skip edge
5.82 +\until edge
5.83 +
5.84 +The graph we built before is linear, so we know that it ends, when no more outgoing
5.85 +edges found. Otherwise the current node must be the node the edge points to.
5.86 +Basic information about an edge can be requested from the graph.
5.87 +\skip if
5.88 +\until }
5.89 +
5.90 +Finish the code, just to be precise.
5.91 +\skip return
5.92 +\until }
5.93 +
5.94 +
5.95 +\section compile_hw Compiling Hello World
5.96 +To compile this program all you have to do is type in
5.97 +\code g++ -ohw hello_world.cc \endcode
5.98 +and press \c Enter! This is the case if you installed LEMON on your system.
5.99 +(For more information see the LEMON installation instructions.)
5.100 +
5.101 +This is because LEMON is template library and most of it's code has to be available
5.102 +as source code during compilation.
5.103 +
5.104 +Most programs using LEMON will compile as easy as this one unless you want to
5.105 +use some performance measuring tools LEMON can provide. Then you need to link
5.106 +an additional library against your program.
5.107 +*/
6.1 --- a/doc/tutorial.dox Mon Sep 04 19:12:44 2006 +0000
6.2 +++ b/doc/tutorial.dox Mon Sep 04 19:48:09 2006 +0000
6.3 @@ -1,67 +1,44 @@
6.4 /**
6.5 \page Tutorial LEMON Tutorial
6.6
6.7 -\section toc Table of Contents
6.8 +<H2>Table of Contents</H2>
6.9
6.10 --# \ref intro
6.11 --# \ref get_start
6.12 - - \ref hello_world
6.13 - - \ref compile
6.14 --# \ref basic
6.15 - - \ref list_graph
6.16 - - \ref maps1
6.17 --# \ref file
6.18 --# \ref algos
6.19 - - \ref bfs_dfs
6.20 - - \ref dijkstra
6.21 - - \ref kruskal
6.22 --# \ref maps2
6.23 - - \ref custom_maps
6.24 - - \ref map_adaptors
6.25 - - \ref spec_maps
6.26 --# \ref show
6.27 --# \ref misc
6.28 - - \ref lp
6.29 - - \ref simann
6.30 +<OL style="padding-bottom: 60px">
6.31 + <LI>\ref intro
6.32 + <LI>\ref getting_started
6.33 + <UL>
6.34 + <LI>\ref hello_world
6.35 + <LI>\ref compile_hw
6.36 + </UL>
6.37 + <LI>\ref basic_concepts
6.38 + <UL>
6.39 + <LI>\ref basic_ListGraph
6.40 + <LI>\ref maps1
6.41 + </UL>
6.42 + <LI><A href="#file">Lemon Graph File Format</A>
6.43 + <LI>\ref algorithms
6.44 + <UL>
6.45 + <LI><A href="#bfs_dfs">Bfs/Dfs</A>
6.46 + <LI><A href="#dijkstra">Dijkstra</A>
6.47 + <LI><A href="#kruskal">Kruskal</A>
6.48 + </UL>
6.49 + <LI>\ref maps2
6.50 + <UL>
6.51 + <LI>\ref custom_maps
6.52 + <LI><A href="#map_adaptors">Map Adaptors</A>
6.53 + <LI><A href="#special_maps">Special Purpose Maps</a>
6.54 + </UL>
6.55 + <LI><A href="#show">Show a graph</A>
6.56 + <LI><A href="#misc">Miscellaneous Tool</A>
6.57 + <UL>
6.58 + <LI><A href="#lp">LP solver</A>
6.59 + <LI><A href="#simann">Simulated Annealing</A>
6.60 + </UL>
6.61 +</OL>
6.62
6.63 \section intro Introduction
6.64 -
6.65 -\section get_start Getting Started
6.66 -
6.67 - \subsection hello_world Hello World in LEMON
6.68 -
6.69 - \subsection compile Compiling Hello World
6.70 -
6.71 -\section basic Basic concepts
6.72 -
6.73 - \subsection list_graph ListGraph - a versatile directed graph
6.74 -
6.75 - \subsection maps1 Maps I.
6.76 -
6.77 -\section file Lemon Graph File Format
6.78 -
6.79 -\section algos Algorithms
6.80 -
6.81 - \subsection bfs_dfs Bfs/Dfs
6.82 -
6.83 - \subsection dijkstra Dijkstra
6.84 -
6.85 - \subsection kruskal Kruskal
6.86 -
6.87 -\section maps2 Maps II.
6.88 -
6.89 - \subsection custom_maps Writing Custom ReadMap
6.90 -
6.91 - \subsection map_adaptors Map Adaptors
6.92 -
6.93 - \subsection spec_maps Special Purpose Maps
6.94 -
6.95 -\section show Show a graph
6.96 -
6.97 -\section misc Miscellaneous Tool
6.98 -
6.99 - \subsection lp LP solver
6.100 -
6.101 - \subsection simann Simulated Annealing
6.102 -
6.103 +In this tutorial we try to show you as many aspects of LEMON as possible. From
6.104 +the basics to the very advanced or highly optimized tools. The given examples
6.105 +are all available in \c demo directory, so feel free to look at them after the
6.106 +sections.
6.107 */