# HG changeset patch
# User deba
# Date 1147447782 0
# Node ID 94a7deb46c073b407f1b1b9e56d584c58466479d
# Parent  630a5e16dc129a44e5bb7c5ea884da05d2065730
New demo file for computing disjoint paths

Doc review
	Correcting misformatting in adaptors
	Adding header to demos

diff -r 630a5e16dc12 -r 94a7deb46c07 demo/Makefile.am
--- a/demo/Makefile.am	Fri May 12 09:57:03 2006 +0000
+++ b/demo/Makefile.am	Fri May 12 15:29:42 2006 +0000
@@ -18,7 +18,8 @@
 	coloring \
 	grid_ugraph_demo \
 	topology_demo \
-	simann_maxcut_demo
+	simann_maxcut_demo \
+	disjoint_paths_demo
 
 if HAVE_GLPK
 noinst_PROGRAMS += lp_demo lp_maxflow_demo
@@ -66,3 +67,5 @@
 topology_demo_SOURCES = topology_demo.cc
 
 simann_maxcut_demo_SOURCES = simann_maxcut_demo.cc
+
+disjoint_paths_demo_SOURCES = disjoint_paths.cc
diff -r 630a5e16dc12 -r 94a7deb46c07 demo/descriptor_map_demo.cc
--- a/demo/descriptor_map_demo.cc	Fri May 12 09:57:03 2006 +0000
+++ b/demo/descriptor_map_demo.cc	Fri May 12 15:29:42 2006 +0000
@@ -16,6 +16,16 @@
  *
  */
 
+/// \ingroup demos
+/// \file
+/// \brief Using descriptor map and own special map types.
+///
+/// This demo shows how can be used the DescriptorMap class
+/// which helps to use unique label for each node or edge.
+/// And it gives an example how easy is creating own map types.
+///
+/// \include descriptor_map_demo.cc
+
 #include <lemon/list_graph.h>
 #include <lemon/graph_utils.h>
 #include <lemon/graph_writer.h>
@@ -30,12 +40,13 @@
 
 using namespace lemon;
 
-// Special map type
-// It gives back a position for each node. The position of the nodes 
+// Special xy<double> map type 
+//
+// It gives back a position for each node. The position of the nodes
 // are on the circle with the given center and radius.
 //
-// Because we use the descriptor map it will hold the proprty described above
-// even if a node added or deleted. 
+// Because we use the descriptor map it will hold the proprty
+// described above even if a node added or deleted.
 template <typename Graph>
 class CircleMap {
 public:
diff -r 630a5e16dc12 -r 94a7deb46c07 demo/dim_to_dot.cc
--- a/demo/dim_to_dot.cc	Fri May 12 09:57:03 2006 +0000
+++ b/demo/dim_to_dot.cc	Fri May 12 15:29:42 2006 +0000
@@ -16,21 +16,20 @@
  *
  */
 
-// Use a DIMACS max flow file as stdin.
-// dim_to_dot < dimacs_max_flow_file > dot_output_file
-// This program makes a dot file from a dimacs max flow file. 
-// This program can be an aid in making up to date visualized documantation 
-// of demo programs.
-
-// For later documentation (if marci does not do it)
-// Az a graphviz csomag egy egyszeru formatuma, ami egy graphrajzolo csomag.
-// Az EdgeSubGraphAdaptor doksijaban szerepel egy kirajzolt graf. Azt nem
-// kezzel csinaltam, hanem a megfelelo dim file-bol ezzel a progival. A
-// doxygen ugyanis ilyet eszik, igy a juzer vizualisan is latja a grafot a
-// doksiban, es sajat maga is le tudja futtatni az algoritmust, mert ott van
-// a kezeben a dim file is. Es mivel ez egy generalt file, ezert ha vmit
-// valtoztatunk a dim-en, ezt is konnyu bemasolni. Uff.
-
+///\file
+///\brief Dim (Dimacs) to Dot (Graphviz) converter
+///
+/// This program can convert the dimacs format to graphviz dot format.
+///
+/// Use a DIMACS max flow file as stdin.
+///
+/// <tt>dim_to_dot < dimacs_max_flow_file > dot_output_file</tt>
+///
+/// This program makes a dot file from a dimacs max flow file. 
+/// This program can be an aid in making up to date visualized documantation 
+/// of demo programs.
+///
+/// \include dim_to_dot.cc
 
 #include <iostream>
 #include <fstream>
diff -r 630a5e16dc12 -r 94a7deb46c07 demo/disjoint_paths.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/disjoint_paths.cc	Fri May 12 15:29:42 2006 +0000
@@ -0,0 +1,107 @@
+/* -*- 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 Node and edge disjoint paths in directed graph.
+///
+/// This demo program calculates how many edge disjoint and node disjoint
+/// paths are in a directed graph between a source and a target node.
+/// The edge disjoint paths can be computed with a flow algorithm,
+/// in this example we use the Preflow algorithm class. To get the node
+/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
+/// and just then calculate the flow.  
+///
+/// \include disjoint_paths.cc
+
+#include <iostream>
+
+#include <lemon/smart_graph.h>
+#include <lemon/graph_adaptor.h>
+#include <lemon/graph_reader.h>
+#include <lemon/preflow.h>
+#include <lemon/graph_to_eps.h>
+
+using namespace lemon;
+using namespace std;
+
+Color color(bool b) {
+  return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
+}
+
+int main() {
+  cout << "This program calculates the number " <<
+    "of disjoint paths in a graph" << endl;
+  cout << "The graph is read from the disjoint_paths.lgf file" << endl;
+  typedef SmartGraph Graph;
+
+  Graph graph;
+
+  Graph::NodeMap<xy<double> > coords(graph);
+  Graph::Node source, target;
+  GraphReader<Graph>("disjoint_paths.lgf", graph).
+    readNodeMap("coords", coords).
+    readNode("source", source).readNode("target", target).run();
+
+  typedef ConstMap<Graph::Edge, int> Capacity;
+  Capacity capacity(1);
+
+  Graph::EdgeMap<int> flow(graph);
+
+  Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow); 
+  
+  preflow.run();
+
+  cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
+
+  graphToEps(graph, "edge_disjoint.eps").
+    title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
+    edgeColors(composeMap(functorMap(color), flow)).
+    coords(coords).autoNodeScale().run();
+
+
+  cout << "The paths are written into edge_disjoint.eps" << endl;
+
+  typedef SplitGraphAdaptor<SmartGraph> SGraph;
+
+  SGraph sgraph(graph);
+
+  typedef ConstMap<SGraph::Edge, int> SCapacity;
+  SCapacity scapacity(1);
+
+  SGraph::EdgeMap<int> sflow(sgraph);
+
+  Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source), 
+                                           SGraph::inNode(target), 
+                                           scapacity, sflow);
+
+  spreflow.run();
+
+  cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
+
+
+  graphToEps(sgraph, "node_disjoint.eps").
+    title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
+    edgeColors(composeMap(functorMap(color), sflow)).
+    coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
+    autoNodeScale().run();
+
+  cout << "The paths are written into node_disjoint.eps" << endl;
+  
+  return 0;
+}
diff -r 630a5e16dc12 -r 94a7deb46c07 demo/disjoint_paths.lgf
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/disjoint_paths.lgf	Fri May 12 15:29:42 2006 +0000
@@ -0,0 +1,46 @@
+@nodeset 
+coords	label	
+(-20,17)	15	
+(39,13) 	14	
+(39,-11)	13	
+(-12,7)	        12	
+(25,-15)        11	
+(-18,-14)	10	
+(45,3)          9	
+(28,13)         8	
+(25,-5)         7	
+(1,21)          6	
+(3,3)           5	
+(3,-9)          4	
+(-9,15)         3	
+(-13,-4)        2	
+(-27,5)         1	
+@edgeset 
+		label	
+1	15	22	
+8	14	20	
+11	13	18	
+1	12	8	
+4	11	14	
+1	10	1	
+14	9	21	
+13	9	19	
+8	9	17	
+7	9	16	
+11	9	15	
+5	8	12	
+6	8	11	
+5	7	13	
+3	6	4	
+12	5	9	
+2	5	6	
+3	5	5	
+2	4	10	
+10	4	7	
+15	3	23	
+1	3	3	
+1	2	2	
+@nodes
+source 1
+target 9
+@end
diff -r 630a5e16dc12 -r 94a7deb46c07 demo/tight_edge_filter_map.h
--- a/demo/tight_edge_filter_map.h	Fri May 12 09:57:03 2006 +0000
+++ b/demo/tight_edge_filter_map.h	Fri May 12 15:29:42 2006 +0000
@@ -16,36 +16,39 @@
  *
  */
 
-#ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H
-#define LEMON_TIGHT_EDGE_FILTER_MAP_H
+#ifndef DEMO_TIGHT_EDGE_FILTER_MAP_H
+#define DEMO_TIGHT_EDGE_FILTER_MAP_H
 
 #include <lemon/maps.h>
 
-// /// \file
-// /// \brief Maximum flow algorithms.
-// /// \ingroup galgs
+/// \file
+/// \brief Tight edge filter map.
+///
+/// Tight edge filter map is bool map on the edges of the graph
+/// which filters the edges which are not tight for a node-potential.
+/// It is used in the \ref sub_graph_adaptor_demo.cc file. 
+///
+/// \include tight_edge_filter_map.h
 
 namespace lemon {
 
-  /*! 
-    \brief A map for filtering the edge-set to those edges 
-    which are tight w.r.t. a node-potential and 
-    edge-distance.
-    
-    Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and 
-    let \f$ \mathbb{F} \f$ be a number type. 
-    Given a distance function 
-    \f$ d:E\to\mathbb{F} \f$, 
-    \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial 
-    w.r.t. \f$ d \f$ 
-    if and only if 
-    \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$ 
-    (or the reverse inequality holds for each edge). 
-    An edge is said to be tight if this inequality holds with equality, 
-    and the map returns \c true exactly for those edges. 
-    To avoid rounding errors, it is recommended to use this class with exact 
-    number types, e.g. with \c int.
-  */
+  /// \brief A map for filtering the edge-set to those edges 
+  /// which are tight w.r.t. a node-potential and 
+  /// edge-distance.
+  /// 
+  /// Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and 
+  /// let \f$ \mathbb{F} \f$ be a number type. 
+  /// Given a distance function 
+  /// \f$ d:E\to\mathbb{F} \f$, 
+  /// \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial 
+  /// w.r.t. \f$ d \f$ 
+  /// if and only if 
+  /// \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$ 
+  /// (or the reverse inequality holds for each edge). 
+  /// An edge is said to be tight if this inequality holds with equality, 
+  /// and the map returns \c true exactly for those edges. 
+  /// To avoid rounding errors, it is recommended to use this class with exact 
+  /// number types, e.g. with \c int.
   template<typename Graph, 
 	   typename NodePotentialMap, typename EdgeDistanceMap>
   class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
@@ -66,4 +69,4 @@
 
 } //namespace lemon
 
-#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
+#endif //DEMO_TIGHT_EDGE_FILTER_MAP_H
diff -r 630a5e16dc12 -r 94a7deb46c07 lemon/graph_adaptor.h
--- a/lemon/graph_adaptor.h	Fri May 12 09:57:03 2006 +0000
+++ b/lemon/graph_adaptor.h	Fri May 12 15:29:42 2006 +0000
@@ -41,7 +41,6 @@
 namespace lemon {
 
   ///\brief Base type for the Graph Adaptors
-  ///\ingroup graph_adaptors
   ///
   ///Base type for the Graph Adaptors
   ///
@@ -192,6 +191,12 @@
 
   };
 
+  ///\ingroup graph_adaptors
+  ///
+  ///\brief Trivial Graph Adaptor
+  /// 
+  /// This class is an adaptor which does not change the adapted graph.
+  /// It can be used only to test the graph adaptors.
   template <typename _Graph>
   class GraphAdaptor :
     public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > { 
@@ -245,8 +250,9 @@
   };
     
 
+  ///\ingroup graph_adaptors
+  ///
   ///\brief A graph adaptor which reverses the orientation of the edges.
-  ///\ingroup graph_adaptors
   ///
   /// If \c g is defined as
   ///\code
@@ -636,8 +642,9 @@
 
   };
 
+  /// \ingroup graph_adaptors
+  ///
   /// \brief A graph adaptor for hiding nodes and edges from a graph.
-  /// \ingroup graph_adaptors
   /// 
   /// SubGraphAdaptor shows the graph with filtered node-set and 
   /// edge-set. If the \c checked parameter is true then it filters the edgeset
@@ -755,8 +762,9 @@
 
 
 
+  ///\ingroup graph_adaptors
+  ///
   ///\brief An adaptor for hiding nodes from a graph.
-  ///\ingroup graph_adaptors
   ///
   ///An adaptor for hiding nodes from a graph.
   ///This adaptor specializes SubGraphAdaptor in the way that only
@@ -809,6 +817,8 @@
     return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
   }
 
+  ///\ingroup graph_adaptors
+  ///
   ///\brief An adaptor for hiding edges from a graph.
   ///
   ///An adaptor for hiding edges from a graph.
@@ -1227,8 +1237,9 @@
   };
 
 
+  ///\ingroup graph_adaptors
+  ///
   /// \brief An undirected graph is made from a directed graph by an adaptor
-  /// \ingroup graph_adaptors
   ///
   /// Undocumented, untested!!!
   /// If somebody knows nice demo application, let's polulate it.
@@ -1365,11 +1376,11 @@
   };
 
   
+  ///\ingroup graph_adaptors
+  ///
   ///\brief An adaptor for composing the residual
   ///graph for directed flow and circulation problems.
   ///
-  ///\ingroup graph_adaptors
-  ///
   ///An adaptor for composing the residual graph for directed flow and
   ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
   ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
@@ -1574,8 +1585,9 @@
   };
 
 
+  ///\ingroup graph_adaptors
+  ///
   ///\brief For blocking flows.
-  ///\ingroup graph_adaptors
   ///
   ///This graph adaptor is used for on-the-fly 
   ///Dinits blocking flow computations.
@@ -2319,7 +2331,7 @@
 
   /// \ingroup graph_adaptors
   ///
-  /// \brief SplitGraphAdaptor class
+  /// \brief Split graph adaptor class
   /// 
   /// This is an graph adaptor which splits all node into an in-node
   /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
@@ -2375,6 +2387,7 @@
   /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
   ///
   /// The second solution contains just 3 disjoint paths while the first 4.
+  /// The full code can be found in the \ref disjoint_paths.cc demo file.
   ///
   /// This graph adaptor is fully conform to the 
   /// \ref concept::StaticGraph "StaticGraph" concept and