1.1 --- a/src/work/athos/dijkstra_demo.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,160 +0,0 @@
1.4 -#include <iostream>
1.5 -#include <string>
1.6 -
1.7 -#include "list_graph.hh"
1.8 -//#include "marci_property_vector.hh"
1.9 -#include <dijkstra_at.h>
1.10 -
1.11 -using namespace lemon;
1.12 -
1.13 -
1.14 -int main (int, char*[])
1.15 -{
1.16 -
1.17 -
1.18 - typedef ListGraph::NodeIt NodeIt;
1.19 - typedef ListGraph::EdgeIt EdgeIt;
1.20 - /*
1.21 - typedef ListGraph::EachNodeIt EachNodeIt;
1.22 - typedef ListGraph::EachEdgeIt EachEdgeIt;
1.23 - typedef ListGraph::OutEdgeIt OutEdgeIt;
1.24 - typedef ListGraph::InEdgeIt InEdgeIt;
1.25 - typedef ListGraph::SymEdgeIt SymEdgeIt;
1.26 - */
1.27 - ListGraph flowG;
1.28 -
1.29 - /*
1.30 - //Marci példája
1.31 -
1.32 -
1.33 - NodeIt s=flowG.addNode();
1.34 - NodeIt v1=flowG.addNode();
1.35 - NodeIt v2=flowG.addNode();
1.36 - NodeIt v3=flowG.addNode();
1.37 - NodeIt v4=flowG.addNode();
1.38 - NodeIt t=flowG.addNode();
1.39 -
1.40 -
1.41 - EdgeIt s_v1=flowG.addEdge(s, v1);
1.42 - EdgeIt s_v2=flowG.addEdge(s, v2);
1.43 - EdgeIt v1_v2=flowG.addEdge(v1, v2);
1.44 - EdgeIt v2_v1=flowG.addEdge(v2, v1);
1.45 - EdgeIt v1_v3=flowG.addEdge(v1, v3);
1.46 - EdgeIt v3_v2=flowG.addEdge(v3, v2);
1.47 - EdgeIt v2_v4=flowG.addEdge(v2, v4);
1.48 - EdgeIt v4_v3=flowG.addEdge(v4, v3);
1.49 - EdgeIt v3_t=flowG.addEdge(v3, t);
1.50 - EdgeIt v4_t=flowG.addEdge(v4, t);
1.51 -
1.52 - ListGraph::EdgeMap<int> cap(flowG);
1.53 -
1.54 - cap.set(s_v1, 16);
1.55 - cap.set(s_v2, 13);
1.56 - cap.set(v1_v2, 10);
1.57 - cap.set(v2_v1, 4);
1.58 - cap.set(v1_v3, 12);
1.59 - cap.set(v3_v2, 9);
1.60 - cap.set(v2_v4, 14);
1.61 - cap.set(v4_v3, 7);
1.62 - cap.set(v3_t, 20);
1.63 - cap.set(v4_t, 4);
1.64 - */
1.65 -
1.66 -
1.67 - //Ahuja könyv példája
1.68 -
1.69 - NodeIt s=flowG.addNode();
1.70 - NodeIt v2=flowG.addNode();
1.71 - NodeIt v3=flowG.addNode();
1.72 - NodeIt v4=flowG.addNode();
1.73 - NodeIt v5=flowG.addNode();
1.74 - NodeIt t=flowG.addNode();
1.75 -
1.76 - EdgeIt s_v2=flowG.addEdge(s, v2);
1.77 - EdgeIt s_v3=flowG.addEdge(s, v3);
1.78 - EdgeIt v2_v4=flowG.addEdge(v2, v4);
1.79 - EdgeIt v2_v5=flowG.addEdge(v2, v5);
1.80 - EdgeIt v3_v5=flowG.addEdge(v3, v5);
1.81 - EdgeIt v4_t=flowG.addEdge(v4, t);
1.82 - EdgeIt v5_t=flowG.addEdge(v5, t);
1.83 -
1.84 - //Kis modositas
1.85 - //edge_iterator v2_s=flowG.add_edge(v2, s);
1.86 -
1.87 - ListGraph::EdgeMap<int> cap(flowG);
1.88 -
1.89 - cap.set(s_v2, 10);
1.90 - cap.set(s_v3, 10);
1.91 - cap.set(v2_v4, 5);
1.92 - cap.set(v2_v5, 8);
1.93 - cap.set(v3_v5, 5);
1.94 - cap.set(v4_t, 8);
1.95 - cap.set(v5_t, 8);
1.96 -
1.97 - //Kis modositas
1.98 - //cap.put(v2_s, 100);
1.99 -
1.100 -
1.101 -
1.102 -
1.103 - /*Egyszerű példa
1.104 - NodeIt s=flow_test.add_node();
1.105 - NodeIt v1=flow_test.add_node();
1.106 - NodeIt v2=flow_test.add_node();
1.107 - NodeIt t=flow_test.add_node();
1.108 -
1.109 - node_property_vector<list_graph, std::string> node_name(flow_test);
1.110 - node_name.put(s, "s");
1.111 - node_name.put(v1, "v1");
1.112 - node_name.put(v2, "v2");
1.113 - node_name.put(t, "t");
1.114 -
1.115 - edge_iterator s_v1=flow_test.add_edge(s, v1);
1.116 - edge_iterator v1_v2=flow_test.add_edge(v1, v2);
1.117 - edge_iterator v2_t=flow_test.add_edge(v2, t);
1.118 -
1.119 - edge_property_vector<list_graph, int> cap(flow_test);
1.120 -
1.121 - cap.put(s_v1, 16);
1.122 - cap.put(v1_v2, 10);
1.123 - cap.put(v2_t, 4);
1.124 - */
1.125 -
1.126 - std::cout << "preflow-push algorithm test..." << std::endl;
1.127 -
1.128 - /*
1.129 - std::cout << "on directed graph graph" << std::endl; //<< flow_test;
1.130 - std::cout << "names and capacity values" << std::endl;
1.131 - for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
1.132 - std::cout << node_name.get(i) << ": ";
1.133 - std::cout << "out edges: ";
1.134 - for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
1.135 - std::cout << node_name.get(flow_test.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.target(j)) << " ";
1.136 - std::cout << "in edges: ";
1.137 - for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
1.138 - std::cout << node_name.get(flow_test.source(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.target(j)) << " ";
1.139 - std::cout << std::endl;
1.140 - }
1.141 - */
1.142 -
1.143 - //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
1.144 - // std::cout << i << " ";
1.145 - //}
1.146 -
1.147 - dijkstra_at<ListGraph, int> dijkstra_test(flowG, s, cap);
1.148 - //cout << preflow_push_test.run()<<endl;
1.149 -
1.150 - //cap.put(v5_t, 9);
1.151 - //cout << preflow_push_test.run()<<endl;
1.152 -
1.153 - return 0;
1.154 -}
1.155 -
1.156 -
1.157 -
1.158 -
1.159 -
1.160 -
1.161 -
1.162 -
1.163 -