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]
+*/
+}