Merge branches/akos to trunk.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #include <mapstorage.h>
20 #include <mapselector.h>
22 #include <dijkstrabox.h>
24 #include <lemon/dijkstra.h>
25 #include <lemon/suurballe.h>
26 #include <lemon/path.h>
28 enum {INPUT, OUTPUT, MAP_NUM};
30 DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
35 SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
37 Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
38 num_set = new Gtk::SpinButton(*adjustment, 5,0);
40 Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
41 // hbox.pack_start(*label);
42 // hbox.pack_start(*num_set);
43 // hbox.show_all_children();
45 table.attach(*label, 0,1,2,3);
46 table.attach(*num_set, 1,2,2,3);
52 void DijkstraBox::run()
55 tabcbt.get_active_text()!="" &&
56 (edgemapcbts[INPUT])->get_active_text()!="" &&
57 (edgemapcbts[OUTPUT])->get_active_text()!="" &&
58 source.get_active_text()!="" &&
59 target.get_active_text()!=""
62 const Graph &g=mapstorage->graph;
65 get_from_to(from, to, (Graph&)g);
71 std::string inputmapName = edgemapcbts[INPUT]->get_active_text();
72 std::string outputmapName = edgemapcbts[OUTPUT]->get_active_text();
74 MapStorage::NumericEdgeMap& inputmap = mapstorage->getNumericEdgeMap(inputmapName);
75 MapStorage::NumericEdgeMap& outputmap = mapstorage->getNumericEdgeMap(outputmapName);
78 for (EdgeIt i(g); i!=INVALID; ++i)
83 Dijkstra<Graph, MapStorage::NumericEdgeMap > dijkstra(g, inputmap);
84 dijkstra.run(from, to);
86 if(dijkstra.reached(to))
90 while (n!=INVALID && n!=from)
92 Edge e=dijkstra.predEdge(n);
94 n=dijkstra.predNode(n);
97 o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
101 o << "Result: failed to find shortest path between ";
102 o << source.get_active_text() << " and " << target.get_active_text();
104 resultlabel.set_text(o.str());
106 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
107 // mapstorage->changeActiveMap(true, E_COLOR,
108 // (edgemapcbts[OUTPUT])->get_active_text());
109 // mapstorage->changeActiveMap(true, E_TEXT,
110 // (edgemapcbts[INPUT])->get_active_text());
115 void SuurballeBox::run()
118 tabcbt.get_active_text()!="" &&
119 (edgemapcbts[INPUT])->get_active_text()!="" &&
120 (edgemapcbts[OUTPUT])->get_active_text()!="" &&
121 source.get_active_text()!="" &&
122 target.get_active_text()!=""
125 const Graph &g=mapstorage->graph;
128 get_from_to(from, to, (Graph&)g);
130 std::ostringstream o;
134 MapStorage::NumericEdgeMap& inputmap=
135 mapstorage->getNumericEdgeMap(edgemapcbts[INPUT]->get_active_text());
136 MapStorage::NumericEdgeMap& outputmap=
137 mapstorage->getNumericEdgeMap(edgemapcbts[OUTPUT]->get_active_text());
139 //zero out output map
140 for (EdgeIt i(g); i!=INVALID; ++i)
145 Suurballe<Graph, MapStorage::NumericEdgeMap > sb((Graph&)g, inputmap, from, to);
147 int found=sb.run(num_set->get_value_as_int());
150 for(int j=0;j<found;j++)
154 for(int k=0;k<path.length();k++)
156 outputmap[path.nth(k)]=j+1;
159 o << "Result: found " << found << " paths between ";
160 o << source.get_active_text() << " and " << target.get_active_text();
164 o << "Result: failed to find shortest path between ";
165 o << source.get_active_text() << " and " << target.get_active_text();
167 resultlabel.set_text(o.str());
169 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
170 // mapstorage->changeActiveMap(true, E_COLOR,
171 // (edgemapcbts[OUTPUT])->get_active_text());
172 // mapstorage->changeActiveMap(true, E_TEXT,
173 // (edgemapcbts[INPUT])->get_active_text());
178 void DijkstraBox::build_box()
180 //if active tab is changed, labels of graph nodes had to be loaded into comboboxes
181 //this can be done after the maps are loaded into ComboBoxes
182 signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
184 addMapSelector("Cost map: ", true, NUM);
185 addMapSelector("Edges of path here: ", true, NUM);
187 Gtk::Label * source_label=new Gtk::Label("Source: ");
188 Gtk::Label * target_label=new Gtk::Label("Target: ");
190 table.attach(*source_label, 0,1,0,1);
191 table.attach(*target_label, 0,1,1,2);
192 table.attach(source, 1,2,0,1);
193 table.attach(target, 1,2,1,2);
198 resultlabel.set_text("Result: algorithm is not run yet.");
199 pack_start(resultlabel);
202 void SuurballeBox::build_box()
206 void DijkstraBox::maplists_updated()
208 if(tabcbt.get_active_text()!="")
212 const Graph &g=mapstorage->graph;
213 for (NodeIt i(g); i!=INVALID; ++i)
215 std::ostringstream text;
216 text << mapstorage->getLabel(i);
217 source.prepend_text(text.str());
218 target.prepend_text(text.str());
223 void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
226 for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
228 std::ostringstream text;
229 text << mapstorage->getLabel(i);
230 if(!(text.str().compare(source.get_active_text())))
235 if(!(text.str().compare(target.get_active_text())))