# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1266796019 -3600
# Node ID 58557724a13975fa09aeb06d1b7b17311f553be2
# Parent  725c60c7492dcdbe886a813416a6c002debfcc2b
Add new sekeleton pages and complete the TOC

diff -r 725c60c7492d -r 58557724a139 algorithms.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algorithms.dox	Mon Feb 22 00:46:59 2010 +0100
@@ -0,0 +1,46 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * 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.
+ *
+ */
+
+namespace lemon {
+/**
+[PAGE]sec_algorithms[PAGE] Algorithms
+
+\todo This page is under construction.
+
+In addition to the graph structures, the most important parts of LEMON are
+the various algorithm implementations, which can be used quite flexibly and
+efficiently.
+
+In this section, we present only some of the most fundamental algorithms.
+For a complete overview, see the \ref algs module of the reference manual.
+
+[SEC]sec_graph_search[SEC] Graph Search
+
+See \ref Bfs, \ref Dfs and \ref graph_properties.
+
+[SEC]sec_shortest_paths[SEC] Shortest Paths
+
+See \ref Dijkstra and \ref BellmanFord.
+
+[SEC]sec_max_flow[SEC] Maximum Flows
+
+See \ref Preflow.
+
+[TRAILER]
+*/
+}
diff -r 725c60c7492d -r 58557724a139 glemon.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/glemon.dox	Mon Feb 22 00:46:59 2010 +0100
@@ -0,0 +1,31 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * 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.
+ *
+ */
+
+namespace lemon {
+/**
+[PAGE]sec_glemon[PAGE] gLemon
+
+\todo This page is under construction.
+
+gLemon is a graph editor for LEMON. 
+
+\image html glemon.png
+
+[TRAILER]
+*/
+}
diff -r 725c60c7492d -r 58557724a139 graph_utils.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graph_utils.dox	Mon Feb 22 00:46:59 2010 +0100
@@ -0,0 +1,48 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * 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.
+ *
+ */
+
+namespace lemon {
+/**
+[PAGE]sec_graph_utilities[PAGE] Basic Graph Utilities
+
+\todo This page is under construction.
+
+
+[SEC]sec_util_item_count[SEC] Count Graph Items
+
+See countNodes(), countArcs(), countEdges(),
+countOutArcs(), countInArcs(), countIncEdges().
+
+
+[SEC]sec_util_graph_copy[SEC] Copying a Graph
+
+See DigraphCopy and GraphCopy.
+
+
+[SEC]sec_util_typedefs[SEC] Type Definitions
+
+See DIGRAPH_TYPEDEFS, GRAPH_TYPEDEFS and their TEMPLATE_* variants.
+
+
+[SEC]sec_util_graph_maps[SEC] Special Graph Maps
+
+See \ref graph_maps in the reference manual.
+
+[TRAILER]
+*/
+}
diff -r 725c60c7492d -r 58557724a139 graphs.dox
--- a/graphs.dox	Mon Feb 22 00:43:23 2010 +0100
+++ b/graphs.dox	Mon Feb 22 00:46:59 2010 +0100
@@ -23,8 +23,8 @@
 The implementation of combinatorial algorithms heavily relies on
 efficient graph structures. Diverse applications require the
 usage of different physical graph storages.
-In \ref sec_basics, we have introduced a general digraph structure,
-\ref ListDigraph. Apart from this class, LEMON provides several
+Until now, we used two general graph structures, \ref ListDigraph
+and \ref ListGraph. Apart from these types, LEMON also provides several
 other classes for handling directed and undirected graphs to meet the
 diverging requirements of the possible users. In order to save on running
 time or on memory usage, some structures may fail to support some graph
@@ -61,7 +61,7 @@
 all the LEMON algorithms and classes will work with them properly.
 
 
-[SEC]sec_digraph_types[SEC] Digraph Structures
+[SEC]sec_digraph_types[SEC] Directed Graph Structures
 
 The already used \ref ListDigraph class is the most versatile directed
 graph structure. As its name suggests, it is based on linked lists,
@@ -90,123 +90,16 @@
 arcs or nodes, moreover, the class needs constant space in memory.
 
 
-[SEC]sec_undir_graphs[SEC] Undirected Graphs
+[SEC]sec_graph_types[SEC] Undirected Graph Structures
 
-LEMON also provides undirected graph structures. For example,
-\ref ListGraph and \ref SmartGraph are the undirected versions of
-\ref ListDigraph and \ref SmartDigraph, respectively.
-They provide similar features to the digraph structures.
+The general undirected graph classes, \ref ListGraph and \ref SmartGraph
+have similar implementations as their directed variants.
+Therefore, \ref SmartDigraph is more efficient, but \ref ListGraph provides
+more functionality.
 
-The \ref concepts::Graph "undirected graphs" also fulfill the concept of
-\ref concepts::Digraph "directed graphs", in such a way that each
-undirected \e edge of a graph can also be regarded as two oppositely
-directed \e arcs. As a result, all directed graph algorithms automatically
-run on undirected graphs, as well.
-
-Undirected graphs provide an \c Edge type for the \e undirected \e edges
-and an \c Arc type for the \e directed \e arcs. The \c Arc type is
-convertible to \c Edge (or inherited from it), thus the corresponding
-edge can always be obtained from an arc.
-
-Only nodes and edges can be added to or removed from an undirected
-graph and the corresponding arcs are added or removed automatically
-(there are twice as many arcs as edges)
-
-For example,
-\code
-  ListGraph g;
-
-  ListGraph::Node a = g.addNode();
-  ListGraph::Node b = g.addNode();
-  ListGraph::Node c = g.addNode();
-
-  ListGraph::Edge e = g.addEdge(a,b);
-  g.addEdge(b,c);
-  g.addEdge(c,a);
-\endcode
-
-Each edge has an inherent orientation, thus it can be defined whether an
-arc is forward or backward oriented in an undirected graph with respect
-to this default oriantation of the represented edge.
-The direction of an arc can be obtained and set using the functions
-\ref concepts::Graph::direction() "direction()" and
-\ref concepts::Graph::direct() "direct()", respectively.
-
-For example,
-\code
-  ListGraph::Arc a1 = g.direct(e, true);    // a1 is the forward arc
-  ListGraph::Arc a2 = g.direct(e, false);   // a2 is the backward arc
-
-  if (a2 == g.oppositeArc(a1))
-    std::cout << "a2 is the opposite of a1" << std::endl;
-\endcode
-
-The end nodes of an edge can be obtained using the functions
-\ref concepts::Graph::source() "u()" and
-\ref concepts::Graph::target() "v()", while the
-\ref concepts::Graph::source() "source()" and
-\ref concepts::Graph::target() "target()" can be used for arcs.
-
-\code
-  std::cout << "Edge " << g.id(e) << " connects node "
-    << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
-
-  std::cout << "Arc " << g.id(a2) << " goes from node "
-    << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
-\endcode
-
-
-Similarly to the digraphs, the undirected graphs also provide iterators
-\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
-\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
-"InArcIt", which can be used the same way.
-However, they also have iterator classes for edges.
-\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
-\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
-certain node.
-
-For example, the degree of each node can be computed and stored in a node map
-like this:
-
-\code
-  ListGraph::NodeMap<int> deg(g, 0);
-  for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
-    for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
-      deg[n]++;
-    }
-  }
-\endcode
-
-In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
-and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
-but with opposite direction. They are convertible to both \c Arc and
-\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
-on these edges, but it is not convertible to \c Arc, only to \c Edge.
-
-Apart from the node and arc maps, an undirected graph also defines
-a template member class for constructing edge maps. These maps can be
-used in conjunction with both edges and arcs.
-
-For example,
-\code
-  ListGraph::EdgeMap cost(g);
-  cost[e] = 10;
-  std::cout << cost[e] << std::endl;
-  std::cout << cost[a1] << ", " << cost[a2] << std::endl;
-
-  ListGraph::ArcMap arc_cost(g);
-  arc_cost[a1] = cost[a1];
-  arc_cost[a2] = 2 * cost[a2];
-  // std::cout << arc_cost[e] << std::endl;   // this is not valid
-  std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
-\endcode
-
-[SEC]sec_special_graphs[SEC] Special Graph Structures
-
-In addition to the general undirected classes \ref ListGraph and
-\ref SmartGraph, LEMON also provides special purpose graph types for
-handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and
-\ref HypercubeGraph "hypercube graphs".
+In addition to these general structures, LEMON also provides special purpose
+undirected graph types for handling \ref FullGraph "full graphs",
+\ref GridGraph "grid graphs" and \ref HypercubeGraph "hypercube graphs".
 They all static structures, i.e. they do not allow distinct item additions
 or deletions, the graph has to be built at once.
 
diff -r 725c60c7492d -r 58557724a139 maps.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/maps.dox	Mon Feb 22 00:46:59 2010 +0100
@@ -0,0 +1,45 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * 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.
+ *
+ */
+
+namespace lemon {
+/**
+[PAGE]sec_maps[PAGE] Maps
+
+\todo This page is under construction.
+
+[SEC]sec_map_concepts[SEC] Map Concepts
+
+...
+
+
+[SEC]sec_own_maps[SEC] Creating Own Maps
+
+...
+
+[SEC]sec_map_adaptors[SEC] Map Adaptors
+
+See \ref map_adaptors in the reference manual.
+
+
+[SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
+
+...
+
+[TRAILER]
+*/
+}
diff -r 725c60c7492d -r 58557724a139 toc.txt
--- a/toc.txt	Mon Feb 22 00:43:23 2010 +0100
+++ b/toc.txt	Mon Feb 22 00:46:59 2010 +0100
@@ -7,20 +7,27 @@
 ** sec_digraph_it
 ** sec_digraph_maps
 ** sec_naming_conv
-*_sec_algorithms
-**_sec_alg_graph_search
-**_sec_alg_shortest_paths
-**_sec_alg_spanning_tree
-**_sec_alg_max_flow
+* sec_algorithms
+** sec_graph_search
+** sec_shortest_paths
+** sec_max_flow
+* sec_undir_graphs
+** sec_undir_graph_use
+** sec_undir_graph_algs
+* sec_graph_utilities
+** sec_util_item_count
+** sec_util_graph_copy
+** sec_util_typedefs
+** sec_util_graph_maps
+* sec_maps
+** sec_map_concepts
+** sec_own_maps
+** sec_map_adaptors
+** sec_algs_with_maps
 * sec_graph_structures
 ** sec_graph_concepts
 ** sec_digraph_types
-** sec_undir_graphs
-** sec_special_graphs
-*_sec_maps
-**_sec_map_concepts
-**_own_maps
-**_algs_with_maps
+** sec_graph_types
 * sec_graph_adaptors
 ** sec_reverse_digraph
 ** sec_subgraphs
@@ -29,8 +36,9 @@
 * sec_lgf
 * sec_tools
 ** sec_aux_structures
-**_sec_time_count
-**_sec_random
 ** sec_graph_to_eps
-**_sec_glemon
+** sec_time_count
+** sec_random
+** sec_arg_parser
+* sec_glemon
 * sec_license
diff -r 725c60c7492d -r 58557724a139 tools.dox
--- a/tools.dox	Mon Feb 22 00:43:23 2010 +0100
+++ b/tools.dox	Mon Feb 22 00:46:59 2010 +0100
@@ -67,6 +67,21 @@
 
 \image html graph_to_eps.png
 
+
+[SEC]sec_time_count[SEC] Time Measuring and Counting
+
+See \ref timecount.
+
+
+[SEC]sec_random[SEC] Random Number Generation
+
+See \ref Random.
+
+
+[SEC]sec_arg_parser[SEC] Argument Parser
+
+See \ref ArgParser.
+
 [TRAILER]
 */
 }
diff -r 725c60c7492d -r 58557724a139 undir_graphs.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/undir_graphs.dox	Mon Feb 22 00:46:59 2010 +0100
@@ -0,0 +1,141 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * 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.
+ *
+ */
+
+namespace lemon {
+/**
+[PAGE]sec_undir_graphs[PAGE] Undirected Graphs
+
+In \ref sec_basics, we have introduced a general digraph structure,
+\ref ListDigraph. LEMON also contains undirected graph classes,
+for example, \ref ListGraph is the undirected versions of \ref ListDigraph.
+
+[SEC]sec_undir_graph_use[SEC] Working with Undirected Graphs
+
+The \ref concepts::Graph "undirected graphs" also fulfill the concept of
+\ref concepts::Digraph "directed graphs", in such a way that each
+undirected \e edge of a graph can also be regarded as two oppositely
+directed \e arcs. As a result, all directed graph algorithms automatically
+run on undirected graphs, as well.
+
+Undirected graphs provide an \c Edge type for the \e undirected \e edges
+and an \c Arc type for the \e directed \e arcs. The \c Arc type is
+convertible to \c Edge (or inherited from it), thus the corresponding
+edge can always be obtained from an arc.
+Of course, only nodes and edges can be added to or removed from an undirected
+graph and the corresponding arcs are added or removed automatically
+(there are twice as many arcs as edges)
+
+For example,
+\code
+  ListGraph g;
+
+  ListGraph::Node a = g.addNode();
+  ListGraph::Node b = g.addNode();
+  ListGraph::Node c = g.addNode();
+
+  ListGraph::Edge e = g.addEdge(a,b);
+  g.addEdge(b,c);
+  g.addEdge(c,a);
+\endcode
+
+Each edge has an inherent orientation, thus it can be defined whether
+an arc is forward or backward oriented in an undirected graph with respect
+to this default oriantation of the represented edge.
+The direction of an arc can be obtained and set using the functions
+\ref concepts::Graph::direction() "direction()" and
+\ref concepts::Graph::direct() "direct()", respectively.
+
+For example,
+\code
+  ListGraph::Arc a1 = g.direct(e, true);    // a1 is the forward arc
+  ListGraph::Arc a2 = g.direct(e, false);   // a2 is the backward arc
+
+  if (a2 == g.oppositeArc(a1))
+    std::cout << "a2 is the opposite of a1" << std::endl;
+\endcode
+
+The end nodes of an edge can be obtained using the functions
+\ref concepts::Graph::source() "u()" and
+\ref concepts::Graph::target() "v()", while the
+\ref concepts::Graph::source() "source()" and
+\ref concepts::Graph::target() "target()" can be used for arcs.
+
+\code
+  std::cout << "Edge " << g.id(e) << " connects node "
+    << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
+
+  std::cout << "Arc " << g.id(a2) << " goes from node "
+    << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
+\endcode
+
+Similarly to the digraphs, the undirected graphs also provide iterators
+\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
+\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
+"InArcIt", which can be used the same way.
+However, they also have iterator classes for edges.
+\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
+\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
+certain node.
+
+For example, the degree of each node can be printed out like this:
+
+\code
+  for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
+    int cnt = 0;
+    for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
+      cnt++;
+    }
+    std::cout << "deg(" << g.id(n) << ") = " << cnt << std::endl;
+  }
+\endcode
+
+In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
+and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
+but with opposite direction. They are convertible to both \c Arc and
+\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
+on these edges, but it is not convertible to \c Arc, only to \c Edge.
+
+Apart from the node and arc maps, an undirected graph also defines
+a member class for constructing edge maps. These maps can be
+used in conjunction with both edges and arcs.
+
+For example,
+\code
+  ListGraph::EdgeMap cost(g);
+  cost[e] = 10;
+  std::cout << cost[e] << std::endl;
+  std::cout << cost[a1] << ", " << cost[a2] << std::endl;
+
+  ListGraph::ArcMap arc_cost(g);
+  arc_cost[a1] = cost[a1];
+  arc_cost[a2] = 2 * cost[a2];
+  // std::cout << arc_cost[e] << std::endl;   // this is not valid
+  std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
+\endcode
+
+
+[SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms
+
+\todo This subsection is under construction.
+
+See \ref spantree for the minimum spanning tree algorithms and
+\ref matching for matching algorithms.
+
+[TRAILER]
+*/
+}