# HG changeset patch
# User alpar
# Date 1157399289 0
# Node ID f47faf6913abc3605f6fdbb4f44c588282d5af2f
# Parent  eaf16c8f6fef5b3fa0e7728c4484823e12276929
Tutorial improvements by Mark (mqrelly)

diff -r eaf16c8f6fef -r f47faf6913ab demo/Makefile.am
--- a/demo/Makefile.am	Mon Sep 04 19:12:44 2006 +0000
+++ b/demo/Makefile.am	Mon Sep 04 19:48:09 2006 +0000
@@ -14,6 +14,8 @@
 	demo/graph_orientation \
 	demo/min_route \
 	demo/hello_lemon \
+	demo/hello_world \
+	demo/maps_summary \
 	demo/sub_graph_adaptor_demo \
 	demo/descriptor_map_demo \
 	demo/coloring \
@@ -45,6 +47,8 @@
 
 demo_coloring_SOURCES = demo/coloring.cc
 
+demo_maps_summary_SOURCES = demo/maps_summary.cc
+
 demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
 
 demo_grid_ugraph_demo_SOURCES = demo/grid_ugraph_demo.cc
@@ -55,6 +59,8 @@
 
 demo_hello_lemon_SOURCES = demo/hello_lemon.cc
 
+demo_hello_world_SOURCES = demo/hello_world.cc
+
 demo_sub_graph_adaptor_demo_SOURCES = \
 	demo/sub_graph_adaptor_demo.cc \
 	demo/tight_edge_filter_map.h
diff -r eaf16c8f6fef -r f47faf6913ab demo/hello_world.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/hello_world.cc	Mon Sep 04 19:48:09 2006 +0000
@@ -0,0 +1,125 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+///\ingroup demos
+///\file
+///\brief LEMON style "Hello World!" program
+///
+/// This program is intended to be a "Hello World!" program that shows
+/// the very basic notions of the LEMON library: \ref graphs "graphs" and
+/// \ref maps-page "maps". Click on the links to read more about these.
+///
+/// \include hello_lemon.cc
+
+#include <iostream>
+#include <lemon/list_graph.h>
+
+using namespace lemon;
+
+typedef ListGraph::Node  Node;
+typedef ListGraph::Edge  Edge;
+
+
+int  main( int argc, char *argv[] )
+{
+  // Declare the graph itself and a NodeMap, witch will store the characters
+  // assigned to the nodes
+  ListGraph  graph;
+  ListGraph::NodeMap<char>  char_map(graph);
+
+  // Add nodes
+  Node  new_node = graph.addNode();
+  char_map[new_node] = 'H';
+
+  // Store the start node
+  Node  start_node = new_node;
+
+  Node  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'e';
+
+  // Here we add the first edge...
+  graph.addEdge( from_node, new_node );
+
+  // ... and we add some more nodes and edges to the graph
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'l';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'l';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'o';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = ' ';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'W';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'o';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'r';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'l';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = 'd';
+  graph.addEdge( from_node, new_node );
+
+  from_node = new_node;
+  new_node = graph.addNode();
+  char_map[new_node] = '\n';
+  graph.addEdge( from_node, new_node );
+
+
+  // iterating
+  Node  current_node = start_node;
+  while( current_node != INVALID )
+  {
+    std::cout << char_map[current_node] << std::flush;
+
+    ListGraph::OutEdgeIt  edge(graph, current_node);
+    if( edge != INVALID )
+      current_node = graph.target( edge );
+    else
+      current_node = INVALID;
+  }
+  
+  return 0;
+}
diff -r eaf16c8f6fef -r f47faf6913ab demo/maps_summary.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/maps_summary.cc	Mon Sep 04 19:48:09 2006 +0000
@@ -0,0 +1,53 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+///\ingroup demos
+///\file maps_summary demo program
+///\brief Introduction to LEMON maps
+///
+/// \include maps_summary.cc
+
+#include <iostream>
+#include <lemon/list_graph.h>
+
+using namespace lemon;
+
+
+template < typename GRAPH, typename MAP >
+typename MAP::Value  summary( GRAPH& gr, MAP& m )
+{
+  typename MAP::Value  summ = typename MAP::Value();
+  
+  for( typename GRAPH::NodeIt  n(gr); n != lemon::INVALID; ++n )
+    summ += m[n];
+
+  return summ;
+}
+
+
+int  main( int argc, char *argv[] )
+{
+  ListGraph  gr;
+  ListGraph::NodeMap<double>  value(gr, 0.0);
+
+  //TODO: build a graph  
+  
+  std::cout << "The summary of assigned values is " << summary(gr,value) << std::endl;
+
+  return 0;
+}
diff -r eaf16c8f6fef -r f47faf6913ab doc/basic_concepts.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/basic_concepts.dox	Mon Sep 04 19:48:09 2006 +0000
@@ -0,0 +1,119 @@
+/**
+\page basic_concepts Basic concepts
+
+\section basic_graph The graph classes
+The most important classes in LEMON are the graph classes. A instance of a graph
+class is the representation of the mathematical graph. It holds the topology and
+every structural information of the graph. The structural manipulations are also
+provided by the graph object. There is no universal graph class instead we have
+different classes for different purposes. They can differ in many ways, but all
+have to satisfy one or more \ref concept "graph concepts" which are standardized
+interfaces to work whit the rest of the library. The most basic concept is the
+\ref Graph.<br>
+A good example is the \ref ListGraph which we already know from Hello World and
+will be used in our examples as well.
+
+One main advantage of the templates are, that you can write your own graph classes.
+As long as they provide the interface a concept is defining all the LEMON algorithms
+and classes will work with it properly - no representation or implementation is
+written into stone.
+
+
+\subsection basic_node Nodes
+To refer to a node of a graph we need some kind of typed variable. Graph classes
+have the Node public type for this purpose. Stacking by the last example:
+\code lemon::ListGraph::Node \endcode
+
+If the graph fits the ExtendableGraphComponent concept, then you can add new nodes
+to the graph with the addNode() member function. It returns the newly added node
+(as value). So if you need the new node to do something useful with it, for example
+create a edge, assign a value to it through \ref map1 maps.
+\code lemon::ListGraph::Node  new_node = graph.addNode(); \endcode
+
+If the graph fits the ErasableGraphComponent concept you also can remove nodes
+from the graph with the erase() member function.
+\code graph.erase( new_node ); \endcode
+
+You don't have to store every node in a variable, you can access individual nodes
+with node iterators discussed in the next section. But how do you know which
+node is which?<br>
+The graph class has the id( Node n ) member function providing an unique identifier
+assigned to every node.
+
+
+\subsection basic_edge Edges
+An Edge is what you think it is. It goes from one node to another node (they can
+be identical). If the graph class is directed, the Edge is directed too. Otherwise
+the edge is considered undirected and called UEdge.
+\code lemon::ListUGraph::UEdge \endcode
+
+The addEdge() member function will create a new edge. It has two arguments, the
+source node and the target node. The graph class must be extendable.
+\code lemon::ListGraph::Edge  new_edge = graph.addEdge( src_node, trg_node ); \endcode
+You can handle edge similar as nodes. The erase() member function has an edge taking
+overload too.
+
+You can ask for the source or target node of the edge by the corresponding member
+functions:
+\code
+graph.source( new_edge );
+lemon::ListGraph::Node  n = graph.target( new_edge ); \endcode
+These functions are always legal even if the graph is undirected. UEdge has a
+default direction.
+
+
+\section basic_iterators Iterators
+Graphs are some kind of containers. And as you expect they have iterator types.
+One fore nodes and a couple for edges - and special classes can have additional
+iterators too. An example:
+\code lemon::ListGraph::NodeIt \endcode
+That is a node iterator. Every iterator type starts whit an name what refers to
+the iterated object, and ends whit 'It'.
+
+LEMON style iterators differs from \c stl or \c boost iterators in a very tasty
+way. A graph has no begin or end - or at least a generic graph class has none.
+If by some topology you could pick a good begin node, it would be misleading and
+incorrect. A LEMON style iterator must be initialized at construction time.
+The constructor takes the needed parameters - by a node iterator it's the graph
+object. And will be compared to the lemon::INVALID to check if it's still valid.
+Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br>
+Let's see these things working together:
+\code
+for( ListGraph::NodeIt n(graph); n != INVALID; ++n )
+    do_useful_things_whit_node(n);
+\endcode
+Note that the function \c do_useful_things_with_node() expects a Node type argument
+ad we just gave him the iterator. LEMON style iterators must provide "on demand
+dereferencing". For example a NodeIt can be used everywhere a Node could. (In some
+graph classes Node is the base class of NodeIt. But in other cases this is implemented
+through typecast operator.)
+
+<b>Very important!</b> The iteration has no defined order. There is absolutely no
+guaranty that the next time the iteration will give us the nodes in the same order.
+Don't use this order to identify nodes! Use the \c id() member function of the
+graph class described above. (There is a powerful technique using maps right in
+the next page.)
+
+The \ref EdgeIt works exactly the same - nothing more to say. But there are \ref InEdgeIt
+and \ref OutEdgeIt by directed graphs and \ref IncEdgeIt by undirected graphs.
+They take two arguments. The first is a graph, the second is certain node of the
+graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it
+on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to
+the given node.
+
+\code
+for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) {
+  int in = 0, out = 0;
+  for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in;
+  for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out;
+
+  std::cout << "#" << graph.id(n) << " node has " << in << " incoming and "
+    << out << "outgoing edges." << std::endl;
+}
+\endcode
+
+
+\section basic_ListGraph ListGraph - a versatile directed graph
+As you see ListGraph satisfies most of the basic concepts and ideal for general
+graph representations. It has an undirected version too: ListUGraph.
+*/
diff -r eaf16c8f6fef -r f47faf6913ab doc/getting_started.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/getting_started.dox	Mon Sep 04 19:48:09 2006 +0000
@@ -0,0 +1,104 @@
+/**
+\page getting_started Getting Started
+
+At the beginning we hardly suggest that you open your favorite text editor
+and enter the code simultaneously as you read it. Compiling the demos is also
+a good exercise.
+
+As the first example we show you a lemon style "Hello World" program. Now we
+explain almost every line, but later we will skip the basics and focus on new
+things.
+
+\section hello_world Hello World in LEMON
+
+In this little program we give you a taste of the LEMON programming.
+
+Let's see the code fragment to fragment!
+
+\dontinclude hello_world.cc
+\skip include
+\until iostream
+
+We want to use a \c lemon::ListGraph so the include goes like this:
+\skip include
+\until list_graph
+
+The next few lines are not necessary but useful shortcuts, if you don't
+want to type \c lemon::ListGraph::Node every time.
+\skip using
+\until Edge
+
+For this demo we need to declare a ListGraph and a special NodeMap to store the
+characters associated to the graph's nodes.
+\skip main
+\until char_map
+
+Adding nodes to the graph is very easy.
+\skip new_node
+\until addNode
+
+When a new node or edge to the graph the assigned maps are automatically resized.
+So graphs can be build dynamically. The usage of a map is very natural.
+\skip char_map
+\until char_map
+
+Notice that no reference or additional assignment needed to work with nodes.
+They won't become illegal or won't lead to throwing any exceptions.
+You can declare and handle node like every other basic type such as \c int.
+\skip Store
+\until char_map
+
+As one expects adding an Edge is similar. You need to define the \b source node
+and the \b destination node. The nodes must belong to the graph of course. The
+Edge has the direction from the source to the destination. In some case you don't
+want the edges to be directed - then you use an undirected graph. For example
+lemon::ListUGraph.
+\skip addEdge
+\until addEdge
+
+In the next few lines we add some more nodes and edges and to the graph we need.
+Those lines are not very interesting so we skip them, but you find the whole
+working program in file hello_lemon.cc in the demo section.
+
+The next statement must be familiar. But what is that INVALID in the \c while
+test statement? In LEMON we usually use the INVALID to check if an object
+contains valid information.
+\skip current_node
+\until {
+
+We take the current node and write out the character assigned to it. Is's easy
+with the \c char_map.
+\skip std
+\until std
+
+And here comes the trick. OutEdgeIt iterates on outgoing edges of a given node.
+We pass the current node as argument to it, so the \c edge iterator will stand
+on the first outgoing edge of the current node, or will be INVALID if the node
+has no outgoing edges.
+\skip edge
+\until edge
+
+The graph we built before is linear, so we know that it ends, when no more outgoing
+edges found. Otherwise the current node must be the node the edge points to.
+Basic information about an edge can be requested from the graph.
+\skip if
+\until }
+
+Finish the code, just to be precise.
+\skip return
+\until }
+
+
+\section compile_hw Compiling Hello World
+To compile this program all you have to do is type in
+\code g++ -ohw hello_world.cc \endcode
+and press \c Enter! This is the case if you installed LEMON on your system.
+(For more information see the LEMON installation instructions.)
+
+This is because LEMON is template library and most of it's code has to be available
+as source code during compilation.
+ 
+Most programs using LEMON will compile as easy as this one unless you want to
+use some performance measuring tools LEMON can provide. Then you need to link
+an additional library against your program.
+*/
diff -r eaf16c8f6fef -r f47faf6913ab doc/tutorial.dox
--- a/doc/tutorial.dox	Mon Sep 04 19:12:44 2006 +0000
+++ b/doc/tutorial.dox	Mon Sep 04 19:48:09 2006 +0000
@@ -1,67 +1,44 @@
 /**
 \page Tutorial LEMON Tutorial
 
-\section toc Table of Contents
+<H2>Table of Contents</H2>
 
--# \ref intro
--# \ref get_start
-  - \ref hello_world
-  - \ref compile
--# \ref basic
-  - \ref list_graph
-  - \ref maps1
--# \ref file
--# \ref algos
-  - \ref bfs_dfs
-  - \ref dijkstra
-  - \ref kruskal
--# \ref maps2
-  - \ref custom_maps
-  - \ref map_adaptors
-  - \ref spec_maps
--# \ref show
--# \ref misc
-  - \ref lp
-  - \ref simann
+<OL style="padding-bottom: 60px">
+  <LI>\ref intro
+  <LI>\ref getting_started
+  <UL>
+    <LI>\ref hello_world
+    <LI>\ref compile_hw
+  </UL>
+  <LI>\ref basic_concepts
+  <UL>
+    <LI>\ref basic_ListGraph
+    <LI>\ref maps1
+  </UL>
+  <LI><A href="#file">Lemon Graph File Format</A>
+  <LI>\ref algorithms
+  <UL>
+    <LI><A href="#bfs_dfs">Bfs/Dfs</A>
+    <LI><A href="#dijkstra">Dijkstra</A>
+    <LI><A href="#kruskal">Kruskal</A>
+  </UL>
+  <LI>\ref maps2
+  <UL>
+    <LI>\ref custom_maps
+    <LI><A href="#map_adaptors">Map Adaptors</A>
+    <LI><A href="#special_maps">Special Purpose Maps</a>
+  </UL>
+  <LI><A href="#show">Show a graph</A>
+  <LI><A href="#misc">Miscellaneous Tool</A>
+  <UL>
+    <LI><A href="#lp">LP solver</A>
+    <LI><A href="#simann">Simulated Annealing</A>
+  </UL>
+</OL>
 
 \section intro Introduction
-
-\section get_start Getting Started
-
-  \subsection hello_world Hello World in LEMON
-
-  \subsection compile Compiling Hello World
-
-\section basic Basic concepts
-
-  \subsection list_graph ListGraph - a versatile directed graph
-
-  \subsection maps1 Maps I.
-
-\section file Lemon Graph File Format
-
-\section algos Algorithms
-
-  \subsection bfs_dfs Bfs/Dfs
-
-  \subsection dijkstra Dijkstra
-
-  \subsection kruskal Kruskal
-
-\section maps2 Maps II.
-
-  \subsection custom_maps Writing Custom ReadMap
-
-  \subsection map_adaptors Map Adaptors
-
-  \subsection spec_maps Special Purpose Maps
-
-\section show Show a graph
-
-\section misc Miscellaneous Tool
-
-  \subsection lp LP solver
-
-  \subsection simann Simulated Annealing
-
+In this tutorial we try to show you as many aspects of LEMON as possible. From
+the basics to the very advanced or highly optimized tools. The given examples
+are all available in \c demo directory, so feel free to look at them after the
+sections.
 */