src/work/athos/suurballe.h
changeset 293 ae4911758833
parent 276 b38f4cfa76cf
child 294 f0ff6981d4fd
equal deleted inserted replaced
0:b1b36f30632f 1:ac37f5f2283f
    25 
    25 
    26     //Writing maps 
    26     //Writing maps 
    27     class ConstMap {
    27     class ConstMap {
    28     public :
    28     public :
    29       typedef int ValueType;
    29       typedef int ValueType;
       
    30       typedef typename Graph::Edge KeyType;
       
    31 
    30       int operator[](typename Graph::Edge e) const { 
    32       int operator[](typename Graph::Edge e) const { 
    31 	return 1;
    33 	return 1;
    32       } 
    34       } 
    33     };
    35     };
    34     /*
    36     /*
    56 
    58 
    57     typedef typename Graph::Node Node;
    59     typedef typename Graph::Node Node;
    58     typedef typename Graph::NodeIt NodeIt;
    60     typedef typename Graph::NodeIt NodeIt;
    59     typedef typename Graph::Edge Edge;
    61     typedef typename Graph::Edge Edge;
    60     typedef typename Graph::OutEdgeIt OutEdgeIt;
    62     typedef typename Graph::OutEdgeIt OutEdgeIt;
    61     typedef ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap > ResGraphType;
    63     typedef TrivGraphWrapper<const Graph> TrivGraphType;
       
    64     typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
       
    65       ConstMap> ResGraphType;
    62 
    66 
    63     const Graph& G;
    67     const Graph& G;
    64     const LengthMap& length;
    68     const LengthMap& length;
    65 
    69 
    66 
    70 
    80     bool run(Node s, Node t, int k) {
    84     bool run(Node s, Node t, int k) {
    81 
    85 
    82       LengthMap mod_length_c = length;
    86       LengthMap mod_length_c = length;
    83       ConstMap const1map;
    87       ConstMap const1map;
    84       //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
    88       //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
    85       ResGraphType res_graph(G, reversed, const1map);
    89       TrivGraphType ize(G);
       
    90       ResGraphType res_graph(ize, reversed, const1map);
    86       //ModLengthMap modified_length(length, dijkstra_dist);
    91       //ModLengthMap modified_length(length, dijkstra_dist);
    87       //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
    92       //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
    88       //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
    93       //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
    89       Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
    94       Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
    90       
    95       
   107 	
   112 	
   108 	//Reversing the sortest path
   113 	//Reversing the sortest path
   109 	Node n=t;
   114 	Node n=t;
   110 	Edge e;
   115 	Edge e;
   111 	while (n!=s){
   116 	while (n!=s){
   112 	  e=dijkstra.pred(n);
   117 	  e = dijkstra.pred(n);
   113 	  n=dijkstra.predNode(n);
   118 	  n = dijkstra.predNode(n);
   114 	  reversed[e] = 1-reversed[e];
   119 	  reversed[e] = 1-reversed[e];
   115 	}
   120 	}
   116 
   121 
   117 	  
   122 	  
   118       }
   123       }