hegyi@163
|
1 |
#include <dijkstrabox.h>
|
hegyi@165
|
2 |
#include <lemon/dijkstra.h>
|
hegyi@165
|
3 |
#include <lemon/suurballe.h>
|
hegyi@165
|
4 |
#include <lemon/path.h>
|
hegyi@163
|
5 |
|
hegyi@163
|
6 |
enum {INPUT, OUTPUT, MAP_NUM};
|
hegyi@163
|
7 |
|
hegyi@163
|
8 |
DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
|
hegyi@163
|
9 |
{
|
hegyi@163
|
10 |
init(t);
|
hegyi@163
|
11 |
}
|
hegyi@163
|
12 |
|
hegyi@165
|
13 |
SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
|
hegyi@165
|
14 |
{
|
hegyi@165
|
15 |
Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
|
hegyi@165
|
16 |
num_set = new Gtk::SpinButton(*adjustment, 5,0);
|
hegyi@165
|
17 |
|
hegyi@165
|
18 |
Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
|
hegyi@165
|
19 |
// hbox.pack_start(*label);
|
hegyi@165
|
20 |
// hbox.pack_start(*num_set);
|
hegyi@165
|
21 |
// hbox.show_all_children();
|
hegyi@165
|
22 |
|
hegyi@165
|
23 |
table.attach(*label, 0,1,2,3);
|
hegyi@165
|
24 |
table.attach(*num_set, 1,2,2,3);
|
hegyi@165
|
25 |
|
hegyi@165
|
26 |
|
hegyi@165
|
27 |
// pack_start(hbox);
|
hegyi@165
|
28 |
}
|
hegyi@165
|
29 |
|
hegyi@163
|
30 |
void DijkstraBox::run()
|
hegyi@163
|
31 |
{
|
hegyi@163
|
32 |
if(
|
hegyi@163
|
33 |
tabcbt.get_active_text()!="" &&
|
hegyi@163
|
34 |
(edgemapcbts[INPUT])->get_active_text()!="" &&
|
hegyi@163
|
35 |
(edgemapcbts[OUTPUT])->get_active_text()!="" &&
|
hegyi@163
|
36 |
source.get_active_text()!="" &&
|
hegyi@163
|
37 |
target.get_active_text()!=""
|
hegyi@163
|
38 |
)
|
hegyi@163
|
39 |
{
|
hegyi@163
|
40 |
const Graph &g=mapstorage->graph;
|
hegyi@165
|
41 |
Node from, to;
|
hegyi@163
|
42 |
|
hegyi@165
|
43 |
get_from_to(from, to, (Graph&)g);
|
hegyi@163
|
44 |
|
hegyi@163
|
45 |
std::ostringstream o;
|
hegyi@163
|
46 |
|
hegyi@163
|
47 |
if(!(from==to))
|
hegyi@163
|
48 |
{
|
hegyi@165
|
49 |
Graph::EdgeMap<double> * inputmap=
|
hegyi@165
|
50 |
(mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
|
hegyi@165
|
51 |
Graph::EdgeMap<double> * outputmap=
|
hegyi@165
|
52 |
(mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
|
hegyi@165
|
53 |
|
hegyi@165
|
54 |
//zero out output map
|
hegyi@165
|
55 |
for (EdgeIt i(g); i!=INVALID; ++i)
|
hegyi@165
|
56 |
{
|
hegyi@165
|
57 |
(*outputmap)[i]=0;
|
hegyi@165
|
58 |
}
|
hegyi@165
|
59 |
|
hegyi@163
|
60 |
Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
|
hegyi@163
|
61 |
dijkstra.run(from, to);
|
hegyi@165
|
62 |
|
hegyi@163
|
63 |
if(dijkstra.reached(to))
|
hegyi@163
|
64 |
{
|
hegyi@163
|
65 |
Node n=to;
|
hegyi@163
|
66 |
int length=0;
|
hegyi@163
|
67 |
while (n!=INVALID && n!=from)
|
hegyi@163
|
68 |
{
|
hegyi@163
|
69 |
Edge e=dijkstra.predEdge(n);
|
hegyi@163
|
70 |
(*outputmap)[e]=1;
|
hegyi@163
|
71 |
n=dijkstra.predNode(n);
|
hegyi@163
|
72 |
length++;
|
hegyi@163
|
73 |
}
|
hegyi@163
|
74 |
o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
|
hegyi@163
|
75 |
}
|
hegyi@163
|
76 |
else
|
hegyi@163
|
77 |
{
|
hegyi@163
|
78 |
o << "Result: failed to find shortest path between ";
|
hegyi@163
|
79 |
o << source.get_active_text() << " and " << target.get_active_text();
|
hegyi@163
|
80 |
}
|
hegyi@163
|
81 |
resultlabel.set_text(o.str());
|
hegyi@165
|
82 |
|
hegyi@165
|
83 |
mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
|
hegyi@165
|
84 |
// mapstorage->changeActiveMap(true, E_COLOR,
|
hegyi@165
|
85 |
// (edgemapcbts[OUTPUT])->get_active_text());
|
hegyi@165
|
86 |
// mapstorage->changeActiveMap(true, E_TEXT,
|
hegyi@165
|
87 |
// (edgemapcbts[INPUT])->get_active_text());
|
hegyi@165
|
88 |
}
|
hegyi@165
|
89 |
}
|
hegyi@165
|
90 |
}
|
hegyi@163
|
91 |
|
hegyi@165
|
92 |
void SuurballeBox::run()
|
hegyi@165
|
93 |
{
|
hegyi@165
|
94 |
if(
|
hegyi@165
|
95 |
tabcbt.get_active_text()!="" &&
|
hegyi@165
|
96 |
(edgemapcbts[INPUT])->get_active_text()!="" &&
|
hegyi@165
|
97 |
(edgemapcbts[OUTPUT])->get_active_text()!="" &&
|
hegyi@165
|
98 |
source.get_active_text()!="" &&
|
hegyi@165
|
99 |
target.get_active_text()!=""
|
hegyi@165
|
100 |
)
|
hegyi@165
|
101 |
{
|
hegyi@165
|
102 |
const Graph &g=mapstorage->graph;
|
hegyi@165
|
103 |
Node from, to;
|
hegyi@165
|
104 |
|
hegyi@165
|
105 |
get_from_to(from, to, (Graph&)g);
|
hegyi@165
|
106 |
|
hegyi@165
|
107 |
std::ostringstream o;
|
hegyi@165
|
108 |
|
hegyi@165
|
109 |
if(!(from==to))
|
hegyi@165
|
110 |
{
|
hegyi@165
|
111 |
Graph::EdgeMap<double> * inputmap=
|
hegyi@165
|
112 |
(mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
|
hegyi@165
|
113 |
Graph::EdgeMap<double> * outputmap=
|
hegyi@165
|
114 |
(mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
|
hegyi@165
|
115 |
|
hegyi@165
|
116 |
//zero out output map
|
hegyi@165
|
117 |
for (EdgeIt i(g); i!=INVALID; ++i)
|
hegyi@165
|
118 |
{
|
hegyi@165
|
119 |
(*outputmap)[i]=0;
|
hegyi@165
|
120 |
}
|
hegyi@165
|
121 |
|
hegyi@165
|
122 |
Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
|
hegyi@165
|
123 |
|
hegyi@165
|
124 |
int found=sb.run(num_set->get_value_as_int());
|
hegyi@165
|
125 |
if(found)
|
hegyi@165
|
126 |
{
|
hegyi@165
|
127 |
for(int j=0;j<found;j++)
|
hegyi@165
|
128 |
{
|
hegyi@165
|
129 |
DirPath<Graph> path(g);
|
hegyi@165
|
130 |
sb.getPath(path, j);
|
hegyi@165
|
131 |
for(int k=0;k<path.length();k++)
|
hegyi@165
|
132 |
{
|
hegyi@165
|
133 |
DirPath<Graph>::EdgeIt ei;
|
hegyi@165
|
134 |
path.nth(ei,k);
|
hegyi@165
|
135 |
(*outputmap)[ei]=j+1;
|
hegyi@165
|
136 |
}
|
hegyi@165
|
137 |
}
|
hegyi@165
|
138 |
o << "Result: found " << found << " paths between ";
|
hegyi@165
|
139 |
o << source.get_active_text() << " and " << target.get_active_text();
|
hegyi@165
|
140 |
}
|
hegyi@165
|
141 |
else
|
hegyi@165
|
142 |
{
|
hegyi@165
|
143 |
o << "Result: failed to find shortest path between ";
|
hegyi@165
|
144 |
o << source.get_active_text() << " and " << target.get_active_text();
|
hegyi@165
|
145 |
}
|
hegyi@165
|
146 |
resultlabel.set_text(o.str());
|
hegyi@165
|
147 |
|
hegyi@163
|
148 |
mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
|
hegyi@165
|
149 |
// mapstorage->changeActiveMap(true, E_COLOR,
|
hegyi@165
|
150 |
// (edgemapcbts[OUTPUT])->get_active_text());
|
hegyi@165
|
151 |
// mapstorage->changeActiveMap(true, E_TEXT,
|
hegyi@165
|
152 |
// (edgemapcbts[INPUT])->get_active_text());
|
hegyi@163
|
153 |
}
|
hegyi@163
|
154 |
}
|
hegyi@163
|
155 |
}
|
hegyi@163
|
156 |
|
hegyi@163
|
157 |
void DijkstraBox::build_box()
|
hegyi@163
|
158 |
{
|
hegyi@163
|
159 |
//if active tab is changed, labels of graph nodes had to be loaded into comboboxes
|
hegyi@163
|
160 |
//this can be done after the maps are loaded into ComboBoxes
|
hegyi@163
|
161 |
signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
|
hegyi@163
|
162 |
|
hegyi@163
|
163 |
addMapSelector("Cost map: ", true);
|
hegyi@163
|
164 |
addMapSelector("Edges of path here: ", true);
|
hegyi@163
|
165 |
|
hegyi@163
|
166 |
Gtk::Label * source_label=new Gtk::Label("Source: ");
|
hegyi@163
|
167 |
Gtk::Label * target_label=new Gtk::Label("Target: ");
|
hegyi@163
|
168 |
|
hegyi@163
|
169 |
table.attach(*source_label, 0,1,0,1);
|
hegyi@163
|
170 |
table.attach(*target_label, 0,1,1,2);
|
hegyi@163
|
171 |
table.attach(source, 1,2,0,1);
|
hegyi@163
|
172 |
table.attach(target, 1,2,1,2);
|
hegyi@163
|
173 |
|
hegyi@163
|
174 |
|
hegyi@163
|
175 |
pack_start(table);
|
hegyi@163
|
176 |
|
hegyi@163
|
177 |
resultlabel.set_text("Result: algorithm is not run yet.");
|
hegyi@163
|
178 |
pack_start(resultlabel);
|
hegyi@163
|
179 |
}
|
hegyi@163
|
180 |
|
hegyi@165
|
181 |
void SuurballeBox::build_box()
|
hegyi@165
|
182 |
{
|
hegyi@165
|
183 |
}
|
hegyi@165
|
184 |
|
hegyi@163
|
185 |
void DijkstraBox::maplists_updated()
|
hegyi@163
|
186 |
{
|
hegyi@163
|
187 |
if(tabcbt.get_active_text()!="")
|
hegyi@163
|
188 |
{
|
hegyi@163
|
189 |
source.clear();
|
hegyi@163
|
190 |
target.clear();
|
hegyi@163
|
191 |
const Graph &g=mapstorage->graph;
|
hegyi@163
|
192 |
for (NodeIt i(g); i!=INVALID; ++i)
|
hegyi@163
|
193 |
{
|
hegyi@163
|
194 |
std::ostringstream text;
|
hegyi@163
|
195 |
text << (*((mapstorage->nodemap_storage)["label"]))[i];
|
hegyi@163
|
196 |
source.prepend_text(text.str());
|
hegyi@163
|
197 |
target.prepend_text(text.str());
|
hegyi@163
|
198 |
}
|
hegyi@163
|
199 |
}
|
hegyi@163
|
200 |
}
|
hegyi@165
|
201 |
|
hegyi@165
|
202 |
void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
|
hegyi@165
|
203 |
{
|
hegyi@165
|
204 |
int assigned=0;
|
hegyi@165
|
205 |
for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
|
hegyi@165
|
206 |
{
|
hegyi@165
|
207 |
std::ostringstream text;
|
hegyi@165
|
208 |
text << (*((mapstorage->nodemap_storage)["label"]))[i];
|
hegyi@165
|
209 |
if(!(text.str().compare(source.get_active_text())))
|
hegyi@165
|
210 |
{
|
hegyi@165
|
211 |
from=i;
|
hegyi@165
|
212 |
assigned++;
|
hegyi@165
|
213 |
}
|
hegyi@165
|
214 |
if(!(text.str().compare(target.get_active_text())))
|
hegyi@165
|
215 |
{
|
hegyi@165
|
216 |
to=i;
|
hegyi@165
|
217 |
assigned++;
|
hegyi@165
|
218 |
}
|
hegyi@165
|
219 |
}
|
hegyi@165
|
220 |
}
|