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 Graph::EdgeMap<double> * inputmap=
72 (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
73 Graph::EdgeMap<double> * outputmap=
74 (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
77 for (EdgeIt i(g); i!=INVALID; ++i)
82 Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
83 dijkstra.run(from, to);
85 if(dijkstra.reached(to))
89 while (n!=INVALID && n!=from)
91 Edge e=dijkstra.predEdge(n);
93 n=dijkstra.predNode(n);
96 o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
100 o << "Result: failed to find shortest path between ";
101 o << source.get_active_text() << " and " << target.get_active_text();
103 resultlabel.set_text(o.str());
105 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
106 // mapstorage->changeActiveMap(true, E_COLOR,
107 // (edgemapcbts[OUTPUT])->get_active_text());
108 // mapstorage->changeActiveMap(true, E_TEXT,
109 // (edgemapcbts[INPUT])->get_active_text());
114 void SuurballeBox::run()
117 tabcbt.get_active_text()!="" &&
118 (edgemapcbts[INPUT])->get_active_text()!="" &&
119 (edgemapcbts[OUTPUT])->get_active_text()!="" &&
120 source.get_active_text()!="" &&
121 target.get_active_text()!=""
124 const Graph &g=mapstorage->graph;
127 get_from_to(from, to, (Graph&)g);
129 std::ostringstream o;
133 Graph::EdgeMap<double> * inputmap=
134 (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
135 Graph::EdgeMap<double> * outputmap=
136 (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
138 //zero out output map
139 for (EdgeIt i(g); i!=INVALID; ++i)
144 Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
146 int found=sb.run(num_set->get_value_as_int());
149 for(int j=0;j<found;j++)
153 for(int k=0;k<path.length();k++)
155 (*outputmap)[path.nth(k)]=j+1;
158 o << "Result: found " << found << " paths between ";
159 o << source.get_active_text() << " and " << target.get_active_text();
163 o << "Result: failed to find shortest path between ";
164 o << source.get_active_text() << " and " << target.get_active_text();
166 resultlabel.set_text(o.str());
168 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
169 // mapstorage->changeActiveMap(true, E_COLOR,
170 // (edgemapcbts[OUTPUT])->get_active_text());
171 // mapstorage->changeActiveMap(true, E_TEXT,
172 // (edgemapcbts[INPUT])->get_active_text());
177 void DijkstraBox::build_box()
179 //if active tab is changed, labels of graph nodes had to be loaded into comboboxes
180 //this can be done after the maps are loaded into ComboBoxes
181 signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
183 addMapSelector("Cost map: ", true);
184 addMapSelector("Edges of path here: ", true);
186 Gtk::Label * source_label=new Gtk::Label("Source: ");
187 Gtk::Label * target_label=new Gtk::Label("Target: ");
189 table.attach(*source_label, 0,1,0,1);
190 table.attach(*target_label, 0,1,1,2);
191 table.attach(source, 1,2,0,1);
192 table.attach(target, 1,2,1,2);
197 resultlabel.set_text("Result: algorithm is not run yet.");
198 pack_start(resultlabel);
201 void SuurballeBox::build_box()
205 void DijkstraBox::maplists_updated()
207 if(tabcbt.get_active_text()!="")
211 const Graph &g=mapstorage->graph;
212 for (NodeIt i(g); i!=INVALID; ++i)
214 std::ostringstream text;
215 text << (*((mapstorage->nodemap_storage)["label"]))[i];
216 source.prepend_text(text.str());
217 target.prepend_text(text.str());
222 void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
225 for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
227 std::ostringstream text;
228 text << (*((mapstorage->nodemap_storage)["label"]))[i];
229 if(!(text.str().compare(source.get_active_text())))
234 if(!(text.str().compare(target.get_active_text())))