# HG changeset patch
# User klao
# Date 1081187040 0
# Node ID 379e1d50089d71cf12dcc73c2e975ed4d38dfd21
# Parent  0fac67bef95a239134d0eb75a696148ad276fb6e
Working on athos' minlengthpaths algo

diff -r 0fac67bef95a -r 379e1d50089d src/work/klao/minlengthpaths.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/klao/minlengthpaths.cc	Mon Apr 05 17:44:00 2004 +0000
@@ -0,0 +1,126 @@
+// -*- c++ -*-
+//#include <iostream>
+//#include <vector>
+//#include <string>
+
+#include <list_graph.h>
+#include <minlengthpaths.h>
+
+using namespace hugo;
+
+
+int main()
+{
+
+  
+  typedef ListGraph::Node Node;
+  typedef ListGraph::Edge Edge;
+
+  ListGraph graph;
+
+  /*
+  //Marci példája
+
+
+  NodeIt s=graph.addNode();
+  NodeIt v1=graph.addNode();
+  NodeIt v2=graph.addNode();
+  NodeIt v3=graph.addNode();
+  NodeIt v4=graph.addNode();
+  NodeIt t=graph.addNode();
+  
+
+  EdgeIt s_v1=graph.addEdge(s, v1);
+  EdgeIt s_v2=graph.addEdge(s, v2);
+  EdgeIt v1_v2=graph.addEdge(v1, v2);
+  EdgeIt v2_v1=graph.addEdge(v2, v1);
+  EdgeIt v1_v3=graph.addEdge(v1, v3);
+  EdgeIt v3_v2=graph.addEdge(v3, v2);
+  EdgeIt v2_v4=graph.addEdge(v2, v4);
+  EdgeIt v4_v3=graph.addEdge(v4, v3);
+  EdgeIt v3_t=graph.addEdge(v3, t);
+  EdgeIt v4_t=graph.addEdge(v4, t);
+
+  ListGraph::EdgeMap<int> length(graph);
+
+  length.set(s_v1, 16);
+  length.set(s_v2, 13);
+  length.set(v1_v2, 10);
+  length.set(v2_v1, 4);
+  length.set(v1_v3, 12);
+  length.set(v3_v2, 9);
+  length.set(v2_v4, 14);
+  length.set(v4_v3, 7);
+  length.set(v3_t, 20);
+  length.set(v4_t, 4);
+  */
+
+
+  //Ahuja könyv példája
+
+  Node s=graph.addNode();
+  Node v2=graph.addNode();
+  Node v3=graph.addNode();
+  Node v4=graph.addNode();
+  Node v5=graph.addNode();
+  Node t=graph.addNode();
+
+  Edge s_v2=graph.addEdge(s, v2);
+  Edge s_v3=graph.addEdge(s, v3);
+  Edge v2_v4=graph.addEdge(v2, v4);
+  Edge v2_v5=graph.addEdge(v2, v5);
+  Edge v3_v5=graph.addEdge(v3, v5);
+  Edge v4_t=graph.addEdge(v4, t);
+  Edge v5_t=graph.addEdge(v5, t);
+  
+  //Kis modositas
+  //edge_iterator v2_s=graph.add_edge(v2, s);
+
+  ListGraph::EdgeMap<int> length(graph);
+
+  length.set(s_v2, 10);
+  length.set(s_v3, 10);
+  length.set(v2_v4, 5);
+  length.set(v2_v5, 8);
+  length.set(v3_v5, 5);
+  length.set(v4_t, 8);
+  length.set(v5_t, 8);
+
+  //Kis modositas
+  //length.put(v2_s, 100);
+ 
+
+
+
+  /*Egyszerű példa
+  NodeIt s=flow_test.add_node();
+  NodeIt v1=flow_test.add_node();
+  NodeIt v2=flow_test.add_node();
+  NodeIt t=flow_test.add_node();
+  
+  node_property_vector<list_graph, std::string> node_name(flow_test);
+  node_name.put(s, "s");
+  node_name.put(v1, "v1");
+  node_name.put(v2, "v2");
+  node_name.put(t, "t");
+
+  edge_iterator s_v1=flow_test.add_edge(s, v1);
+  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
+  edge_iterator v2_t=flow_test.add_edge(v2, t);
+
+  edge_property_vector<list_graph, int> length(flow_test); 
+    
+  length.put(s_v1, 16);
+  length.put(v1_v2, 10);
+  length.put(v2_t, 4);
+  */
+
+  std::cout << "Suurballe algorithm test..." << std::endl;
+
+  
+  int k=3;
+  MinLengthPaths<ListGraph, int> surb_test(graph, length);
+  std::cout << surb_test.run(s,t,k)<<std::endl;
+
+  return 0;
+}
diff -r 0fac67bef95a -r 379e1d50089d src/work/klao/minlengthpaths.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/klao/minlengthpaths.h	Mon Apr 05 17:44:00 2004 +0000
@@ -0,0 +1,164 @@
+// -*- c++ -*-
+#ifndef HUGO_MINLENGTHPATHS_H
+#define HUGO_MINLENGTHPATHS_H
+
+///\file
+///\brief An algorithm for finding k paths of minimal total length.
+
+#include <iostream>
+#include <dijkstra.h>
+#include <graph_wrapper.h>
+#include <maps.h>
+
+namespace hugo {
+
+
+///\brief Implementation of an algorithm for finding k paths between 2 nodes 
+  /// of minimal total length 
+///
+/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
+/// an algorithm which finds k edge-disjoint paths
+/// from a given source node to a given target node in an
+/// edge-weighted directed graph having minimal total weigth (length).
+/// 
+/// 
+
+  template <typename Graph, typename T, 
+    typename LengthMap=typename Graph::EdgeMap<T> >
+  class MinLengthPaths {
+
+
+//      class ConstMap {
+//      public :
+//        typedef int ValueType;
+//        typedef typename Graph::Edge KeyType;
+
+//        int operator[](typename Graph::Edge e) const { 
+//  	return 1;
+//        } 
+//      };
+
+
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::EdgeMap<int> EdgeIntMap;
+
+    typedef ConstMap<Edge,int> ConstMap;
+
+    typedef TrivGraphWrapper<const Graph> TrivGraphType;
+    typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
+      ConstMap> ResGraphType;
+
+
+    //template <typename Graph, typename T>
+    class ModLengthMap {   
+      typedef typename ResGraphType::NodeMap<T> NodeMap;
+      const ResGraphType& G;
+      const EdgeIntMap& rev; 
+      const LengthMap &ol;   
+      const NodeMap &pot;     
+    public :
+      typedef typename LengthMap::KeyType KeyType;
+      typedef typename LengthMap::ValueType ValueType;
+
+      ValueType operator[](typename ResGraphType::Edge e) const {     
+	if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
+	  ///\TODO This has to be removed
+	  std::cout<<"Negative length!!"<<std::endl;
+	}
+	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
+      }     
+
+      ModLengthMap(  const ResGraphType& _G, const EdgeIntMap& _rev, 
+		     const LengthMap &o,  const NodeMap &p) : 
+	G(_G), rev(_rev), ol(o), pot(p){}; 
+    };
+    
+
+    const Graph& G;
+    const LengthMap& length;
+
+    //auxiliary variable
+    //The value is 1 iff the edge is reversed
+    EdgeIntMap reversed; 
+
+    
+  public :
+    
+
+    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
+      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
+
+    ///Runs the algorithm
+    
+    ///Runs the algorithm
+    ///Returns k if there are at least k edge-disjoint paths from s to t.
+    ///Otherwise it returns the number of edge-disjoint paths from s to t.
+    int run(Node s, Node t, int k) {
+      ConstMap const1map(1);
+
+      ResGraphType res_graph(G, reversed, const1map);
+
+      //Initialize the copy of the Dijkstra potential to zero
+      typename ResGraphType::NodeMap<T> dijkstra_dist(G);
+      ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
+
+      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
+      
+      for (int i=0; i<k; ++i){
+	dijkstra.run(s);
+	if (!dijkstra.reached(t)){
+	  //There is no k path from s to t
+	  return ++i;
+	};
+	
+	{
+	  //We have to copy the potential
+	  typename ResGraphType::NodeIt n;
+	  for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
+	      dijkstra_dist[n] += dijkstra.distMap()[n];
+	  }
+	}
+
+
+	/*
+	{
+	  //We have to copy the potential
+	  typename ResGraphType::EdgeIt e;
+	  for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
+	    //dijkstra_dist[e] = dijkstra.distMap()[e];
+	    mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - 
+	      dijkstra.distMap()[res_graph.head(e)] +  
+	      dijkstra.distMap()[res_graph.tail(e)];
+	  }
+	}
+	*/
+
+	//Reversing the sortest path
+	Node n=t;
+	Edge e;
+	while (n!=s){
+	  e = dijkstra.pred(n);
+	  n = dijkstra.predNode(n);
+	  reversed[e] = 1-reversed[e];
+	}
+
+	  
+      }
+      return k;
+    }
+           
+      
+
+
+
+  };//class MinLengthPaths
+
+
+
+
+} //namespace hugo
+
+#endif //HUGO_MINLENGTHPATHS_H