No segmentation fault will be occured if two nodes are exactly overlap each other, AND they are connected.
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 <dijkstrabox.h>
20 #include <lemon/dijkstra.h>
21 #include <lemon/suurballe.h>
22 #include <lemon/path.h>
24 enum {INPUT, OUTPUT, MAP_NUM};
26 DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
31 SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
33 Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
34 num_set = new Gtk::SpinButton(*adjustment, 5,0);
36 Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
37 // hbox.pack_start(*label);
38 // hbox.pack_start(*num_set);
39 // hbox.show_all_children();
41 table.attach(*label, 0,1,2,3);
42 table.attach(*num_set, 1,2,2,3);
48 void DijkstraBox::run()
51 tabcbt.get_active_text()!="" &&
52 (edgemapcbts[INPUT])->get_active_text()!="" &&
53 (edgemapcbts[OUTPUT])->get_active_text()!="" &&
54 source.get_active_text()!="" &&
55 target.get_active_text()!=""
58 const Graph &g=mapstorage->graph;
61 get_from_to(from, to, (Graph&)g);
67 Graph::EdgeMap<double> * inputmap=
68 (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
69 Graph::EdgeMap<double> * outputmap=
70 (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
73 for (EdgeIt i(g); i!=INVALID; ++i)
78 Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
79 dijkstra.run(from, to);
81 if(dijkstra.reached(to))
85 while (n!=INVALID && n!=from)
87 Edge e=dijkstra.predEdge(n);
89 n=dijkstra.predNode(n);
92 o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
96 o << "Result: failed to find shortest path between ";
97 o << source.get_active_text() << " and " << target.get_active_text();
99 resultlabel.set_text(o.str());
101 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
102 // mapstorage->changeActiveMap(true, E_COLOR,
103 // (edgemapcbts[OUTPUT])->get_active_text());
104 // mapstorage->changeActiveMap(true, E_TEXT,
105 // (edgemapcbts[INPUT])->get_active_text());
110 void SuurballeBox::run()
113 tabcbt.get_active_text()!="" &&
114 (edgemapcbts[INPUT])->get_active_text()!="" &&
115 (edgemapcbts[OUTPUT])->get_active_text()!="" &&
116 source.get_active_text()!="" &&
117 target.get_active_text()!=""
120 const Graph &g=mapstorage->graph;
123 get_from_to(from, to, (Graph&)g);
125 std::ostringstream o;
129 Graph::EdgeMap<double> * inputmap=
130 (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
131 Graph::EdgeMap<double> * outputmap=
132 (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
134 //zero out output map
135 for (EdgeIt i(g); i!=INVALID; ++i)
140 Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
142 int found=sb.run(num_set->get_value_as_int());
145 for(int j=0;j<found;j++)
149 for(int k=0;k<path.length();k++)
151 (*outputmap)[path.nth(k)]=j+1;
154 o << "Result: found " << found << " paths between ";
155 o << source.get_active_text() << " and " << target.get_active_text();
159 o << "Result: failed to find shortest path between ";
160 o << source.get_active_text() << " and " << target.get_active_text();
162 resultlabel.set_text(o.str());
164 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
165 // mapstorage->changeActiveMap(true, E_COLOR,
166 // (edgemapcbts[OUTPUT])->get_active_text());
167 // mapstorage->changeActiveMap(true, E_TEXT,
168 // (edgemapcbts[INPUT])->get_active_text());
173 void DijkstraBox::build_box()
175 //if active tab is changed, labels of graph nodes had to be loaded into comboboxes
176 //this can be done after the maps are loaded into ComboBoxes
177 signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
179 addMapSelector("Cost map: ", true);
180 addMapSelector("Edges of path here: ", true);
182 Gtk::Label * source_label=new Gtk::Label("Source: ");
183 Gtk::Label * target_label=new Gtk::Label("Target: ");
185 table.attach(*source_label, 0,1,0,1);
186 table.attach(*target_label, 0,1,1,2);
187 table.attach(source, 1,2,0,1);
188 table.attach(target, 1,2,1,2);
193 resultlabel.set_text("Result: algorithm is not run yet.");
194 pack_start(resultlabel);
197 void SuurballeBox::build_box()
201 void DijkstraBox::maplists_updated()
203 if(tabcbt.get_active_text()!="")
207 const Graph &g=mapstorage->graph;
208 for (NodeIt i(g); i!=INVALID; ++i)
210 std::ostringstream text;
211 text << (*((mapstorage->nodemap_storage)["label"]))[i];
212 source.prepend_text(text.str());
213 target.prepend_text(text.str());
218 void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
221 for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
223 std::ostringstream text;
224 text << (*((mapstorage->nodemap_storage)["label"]))[i];
225 if(!(text.str().compare(source.get_active_text())))
230 if(!(text.str().compare(target.get_active_text())))