1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/klao/minlengthpaths.cc Mon Apr 05 17:44:00 2004 +0000
1.3 @@ -0,0 +1,126 @@
1.4 +// -*- c++ -*-
1.5 +//#include <iostream>
1.6 +//#include <vector>
1.7 +//#include <string>
1.8 +
1.9 +#include <list_graph.h>
1.10 +#include <minlengthpaths.h>
1.11 +
1.12 +using namespace hugo;
1.13 +
1.14 +
1.15 +int main()
1.16 +{
1.17 +
1.18 +
1.19 + typedef ListGraph::Node Node;
1.20 + typedef ListGraph::Edge Edge;
1.21 +
1.22 + ListGraph graph;
1.23 +
1.24 + /*
1.25 + //Marci példája
1.26 +
1.27 +
1.28 + NodeIt s=graph.addNode();
1.29 + NodeIt v1=graph.addNode();
1.30 + NodeIt v2=graph.addNode();
1.31 + NodeIt v3=graph.addNode();
1.32 + NodeIt v4=graph.addNode();
1.33 + NodeIt t=graph.addNode();
1.34 +
1.35 +
1.36 + EdgeIt s_v1=graph.addEdge(s, v1);
1.37 + EdgeIt s_v2=graph.addEdge(s, v2);
1.38 + EdgeIt v1_v2=graph.addEdge(v1, v2);
1.39 + EdgeIt v2_v1=graph.addEdge(v2, v1);
1.40 + EdgeIt v1_v3=graph.addEdge(v1, v3);
1.41 + EdgeIt v3_v2=graph.addEdge(v3, v2);
1.42 + EdgeIt v2_v4=graph.addEdge(v2, v4);
1.43 + EdgeIt v4_v3=graph.addEdge(v4, v3);
1.44 + EdgeIt v3_t=graph.addEdge(v3, t);
1.45 + EdgeIt v4_t=graph.addEdge(v4, t);
1.46 +
1.47 + ListGraph::EdgeMap<int> length(graph);
1.48 +
1.49 + length.set(s_v1, 16);
1.50 + length.set(s_v2, 13);
1.51 + length.set(v1_v2, 10);
1.52 + length.set(v2_v1, 4);
1.53 + length.set(v1_v3, 12);
1.54 + length.set(v3_v2, 9);
1.55 + length.set(v2_v4, 14);
1.56 + length.set(v4_v3, 7);
1.57 + length.set(v3_t, 20);
1.58 + length.set(v4_t, 4);
1.59 + */
1.60 +
1.61 +
1.62 + //Ahuja könyv példája
1.63 +
1.64 + Node s=graph.addNode();
1.65 + Node v2=graph.addNode();
1.66 + Node v3=graph.addNode();
1.67 + Node v4=graph.addNode();
1.68 + Node v5=graph.addNode();
1.69 + Node t=graph.addNode();
1.70 +
1.71 + Edge s_v2=graph.addEdge(s, v2);
1.72 + Edge s_v3=graph.addEdge(s, v3);
1.73 + Edge v2_v4=graph.addEdge(v2, v4);
1.74 + Edge v2_v5=graph.addEdge(v2, v5);
1.75 + Edge v3_v5=graph.addEdge(v3, v5);
1.76 + Edge v4_t=graph.addEdge(v4, t);
1.77 + Edge v5_t=graph.addEdge(v5, t);
1.78 +
1.79 + //Kis modositas
1.80 + //edge_iterator v2_s=graph.add_edge(v2, s);
1.81 +
1.82 + ListGraph::EdgeMap<int> length(graph);
1.83 +
1.84 + length.set(s_v2, 10);
1.85 + length.set(s_v3, 10);
1.86 + length.set(v2_v4, 5);
1.87 + length.set(v2_v5, 8);
1.88 + length.set(v3_v5, 5);
1.89 + length.set(v4_t, 8);
1.90 + length.set(v5_t, 8);
1.91 +
1.92 + //Kis modositas
1.93 + //length.put(v2_s, 100);
1.94 +
1.95 +
1.96 +
1.97 +
1.98 + /*Egyszerű példa
1.99 + NodeIt s=flow_test.add_node();
1.100 + NodeIt v1=flow_test.add_node();
1.101 + NodeIt v2=flow_test.add_node();
1.102 + NodeIt t=flow_test.add_node();
1.103 +
1.104 + node_property_vector<list_graph, std::string> node_name(flow_test);
1.105 + node_name.put(s, "s");
1.106 + node_name.put(v1, "v1");
1.107 + node_name.put(v2, "v2");
1.108 + node_name.put(t, "t");
1.109 +
1.110 + edge_iterator s_v1=flow_test.add_edge(s, v1);
1.111 + edge_iterator v1_v2=flow_test.add_edge(v1, v2);
1.112 + edge_iterator v2_t=flow_test.add_edge(v2, t);
1.113 +
1.114 + edge_property_vector<list_graph, int> length(flow_test);
1.115 +
1.116 + length.put(s_v1, 16);
1.117 + length.put(v1_v2, 10);
1.118 + length.put(v2_t, 4);
1.119 + */
1.120 +
1.121 + std::cout << "Suurballe algorithm test..." << std::endl;
1.122 +
1.123 +
1.124 + int k=3;
1.125 + MinLengthPaths<ListGraph, int> surb_test(graph, length);
1.126 + std::cout << surb_test.run(s,t,k)<<std::endl;
1.127 +
1.128 + return 0;
1.129 +}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/klao/minlengthpaths.h Mon Apr 05 17:44:00 2004 +0000
2.3 @@ -0,0 +1,164 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_MINLENGTHPATHS_H
2.6 +#define HUGO_MINLENGTHPATHS_H
2.7 +
2.8 +///\file
2.9 +///\brief An algorithm for finding k paths of minimal total length.
2.10 +
2.11 +#include <iostream>
2.12 +#include <dijkstra.h>
2.13 +#include <graph_wrapper.h>
2.14 +#include <maps.h>
2.15 +
2.16 +namespace hugo {
2.17 +
2.18 +
2.19 +///\brief Implementation of an algorithm for finding k paths between 2 nodes
2.20 + /// of minimal total length
2.21 +///
2.22 +/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
2.23 +/// an algorithm which finds k edge-disjoint paths
2.24 +/// from a given source node to a given target node in an
2.25 +/// edge-weighted directed graph having minimal total weigth (length).
2.26 +///
2.27 +///
2.28 +
2.29 + template <typename Graph, typename T,
2.30 + typename LengthMap=typename Graph::EdgeMap<T> >
2.31 + class MinLengthPaths {
2.32 +
2.33 +
2.34 +// class ConstMap {
2.35 +// public :
2.36 +// typedef int ValueType;
2.37 +// typedef typename Graph::Edge KeyType;
2.38 +
2.39 +// int operator[](typename Graph::Edge e) const {
2.40 +// return 1;
2.41 +// }
2.42 +// };
2.43 +
2.44 +
2.45 + typedef typename Graph::Node Node;
2.46 + typedef typename Graph::NodeIt NodeIt;
2.47 + typedef typename Graph::Edge Edge;
2.48 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.49 + typedef typename Graph::EdgeMap<int> EdgeIntMap;
2.50 +
2.51 + typedef ConstMap<Edge,int> ConstMap;
2.52 +
2.53 + typedef TrivGraphWrapper<const Graph> TrivGraphType;
2.54 + typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
2.55 + ConstMap> ResGraphType;
2.56 +
2.57 +
2.58 + //template <typename Graph, typename T>
2.59 + class ModLengthMap {
2.60 + typedef typename ResGraphType::NodeMap<T> NodeMap;
2.61 + const ResGraphType& G;
2.62 + const EdgeIntMap& rev;
2.63 + const LengthMap &ol;
2.64 + const NodeMap &pot;
2.65 + public :
2.66 + typedef typename LengthMap::KeyType KeyType;
2.67 + typedef typename LengthMap::ValueType ValueType;
2.68 +
2.69 + ValueType operator[](typename ResGraphType::Edge e) const {
2.70 + if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
2.71 + ///\TODO This has to be removed
2.72 + std::cout<<"Negative length!!"<<std::endl;
2.73 + }
2.74 + return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
2.75 + }
2.76 +
2.77 + ModLengthMap( const ResGraphType& _G, const EdgeIntMap& _rev,
2.78 + const LengthMap &o, const NodeMap &p) :
2.79 + G(_G), rev(_rev), ol(o), pot(p){};
2.80 + };
2.81 +
2.82 +
2.83 + const Graph& G;
2.84 + const LengthMap& length;
2.85 +
2.86 + //auxiliary variable
2.87 + //The value is 1 iff the edge is reversed
2.88 + EdgeIntMap reversed;
2.89 +
2.90 +
2.91 + public :
2.92 +
2.93 +
2.94 + MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
2.95 + length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
2.96 +
2.97 + ///Runs the algorithm
2.98 +
2.99 + ///Runs the algorithm
2.100 + ///Returns k if there are at least k edge-disjoint paths from s to t.
2.101 + ///Otherwise it returns the number of edge-disjoint paths from s to t.
2.102 + int run(Node s, Node t, int k) {
2.103 + ConstMap const1map(1);
2.104 +
2.105 + ResGraphType res_graph(G, reversed, const1map);
2.106 +
2.107 + //Initialize the copy of the Dijkstra potential to zero
2.108 + typename ResGraphType::NodeMap<T> dijkstra_dist(G);
2.109 + ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
2.110 +
2.111 + Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
2.112 +
2.113 + for (int i=0; i<k; ++i){
2.114 + dijkstra.run(s);
2.115 + if (!dijkstra.reached(t)){
2.116 + //There is no k path from s to t
2.117 + return ++i;
2.118 + };
2.119 +
2.120 + {
2.121 + //We have to copy the potential
2.122 + typename ResGraphType::NodeIt n;
2.123 + for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
2.124 + dijkstra_dist[n] += dijkstra.distMap()[n];
2.125 + }
2.126 + }
2.127 +
2.128 +
2.129 + /*
2.130 + {
2.131 + //We have to copy the potential
2.132 + typename ResGraphType::EdgeIt e;
2.133 + for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
2.134 + //dijkstra_dist[e] = dijkstra.distMap()[e];
2.135 + mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
2.136 + dijkstra.distMap()[res_graph.head(e)] +
2.137 + dijkstra.distMap()[res_graph.tail(e)];
2.138 + }
2.139 + }
2.140 + */
2.141 +
2.142 + //Reversing the sortest path
2.143 + Node n=t;
2.144 + Edge e;
2.145 + while (n!=s){
2.146 + e = dijkstra.pred(n);
2.147 + n = dijkstra.predNode(n);
2.148 + reversed[e] = 1-reversed[e];
2.149 + }
2.150 +
2.151 +
2.152 + }
2.153 + return k;
2.154 + }
2.155 +
2.156 +
2.157 +
2.158 +
2.159 +
2.160 + };//class MinLengthPaths
2.161 +
2.162 +
2.163 +
2.164 +
2.165 +} //namespace hugo
2.166 +
2.167 +#endif //HUGO_MINLENGTHPATHS_H