1 #include <dijkstrabox.h> |
1 #include <dijkstrabox.h> |
|
2 #include <lemon/dijkstra.h> |
|
3 #include <lemon/suurballe.h> |
|
4 #include <lemon/path.h> |
2 |
5 |
3 enum {INPUT, OUTPUT, MAP_NUM}; |
6 enum {INPUT, OUTPUT, MAP_NUM}; |
4 |
7 |
5 DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox() |
8 DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox() |
6 { |
9 { |
7 init(t); |
10 init(t); |
|
11 } |
|
12 |
|
13 SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t) |
|
14 { |
|
15 Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5); |
|
16 num_set = new Gtk::SpinButton(*adjustment, 5,0); |
|
17 |
|
18 Gtk::Label * label=new Gtk::Label("No. of paths to find: "); |
|
19 // hbox.pack_start(*label); |
|
20 // hbox.pack_start(*num_set); |
|
21 // hbox.show_all_children(); |
|
22 |
|
23 table.attach(*label, 0,1,2,3); |
|
24 table.attach(*num_set, 1,2,2,3); |
|
25 |
|
26 |
|
27 // pack_start(hbox); |
8 } |
28 } |
9 |
29 |
10 void DijkstraBox::run() |
30 void DijkstraBox::run() |
11 { |
31 { |
12 if( |
32 if( |
16 source.get_active_text()!="" && |
36 source.get_active_text()!="" && |
17 target.get_active_text()!="" |
37 target.get_active_text()!="" |
18 ) |
38 ) |
19 { |
39 { |
20 const Graph &g=mapstorage->graph; |
40 const Graph &g=mapstorage->graph; |
21 |
|
22 Graph::EdgeMap<double> * inputmap= |
|
23 (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()]; |
|
24 Graph::EdgeMap<double> * outputmap= |
|
25 (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()]; |
|
26 |
|
27 Node from, to; |
41 Node from, to; |
28 int assigned=0; |
42 |
|
43 get_from_to(from, to, (Graph&)g); |
|
44 |
29 std::ostringstream o; |
45 std::ostringstream o; |
30 |
46 |
31 //zero out output map |
|
32 for (EdgeIt i(g); i!=INVALID; ++i) |
|
33 { |
|
34 (*outputmap)[i]=0; |
|
35 } |
|
36 |
|
37 for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i) |
|
38 { |
|
39 std::ostringstream text; |
|
40 text << (*((mapstorage->nodemap_storage)["label"]))[i]; |
|
41 if(!(text.str().compare(source.get_active_text()))) |
|
42 { |
|
43 from=i; |
|
44 assigned++; |
|
45 } |
|
46 if(!(text.str().compare(target.get_active_text()))) |
|
47 { |
|
48 to=i; |
|
49 assigned++; |
|
50 } |
|
51 } |
|
52 if(!(from==to)) |
47 if(!(from==to)) |
53 { |
48 { |
|
49 Graph::EdgeMap<double> * inputmap= |
|
50 (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()]; |
|
51 Graph::EdgeMap<double> * outputmap= |
|
52 (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()]; |
|
53 |
|
54 //zero out output map |
|
55 for (EdgeIt i(g); i!=INVALID; ++i) |
|
56 { |
|
57 (*outputmap)[i]=0; |
|
58 } |
|
59 |
54 Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap); |
60 Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap); |
55 dijkstra.run(from, to); |
61 dijkstra.run(from, to); |
56 |
62 |
57 if(dijkstra.reached(to)) |
63 if(dijkstra.reached(to)) |
58 { |
64 { |
59 Node n=to; |
65 Node n=to; |
60 int length=0; |
66 int length=0; |
61 while (n!=INVALID && n!=from) |
67 while (n!=INVALID && n!=from) |
71 { |
77 { |
72 o << "Result: failed to find shortest path between "; |
78 o << "Result: failed to find shortest path between "; |
73 o << source.get_active_text() << " and " << target.get_active_text(); |
79 o << source.get_active_text() << " and " << target.get_active_text(); |
74 } |
80 } |
75 resultlabel.set_text(o.str()); |
81 resultlabel.set_text(o.str()); |
76 |
82 |
77 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text()); |
83 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text()); |
78 } |
84 // mapstorage->changeActiveMap(true, E_COLOR, |
79 // mapstorage->changeActiveMap(true, E_COLOR, |
85 // (edgemapcbts[OUTPUT])->get_active_text()); |
80 // (edgemapcbts[OUTPUT])->get_active_text()); |
86 // mapstorage->changeActiveMap(true, E_TEXT, |
81 // mapstorage->changeActiveMap(true, E_TEXT, |
87 // (edgemapcbts[INPUT])->get_active_text()); |
82 // (edgemapcbts[INPUT])->get_active_text()); |
88 } |
|
89 } |
|
90 } |
|
91 |
|
92 void SuurballeBox::run() |
|
93 { |
|
94 if( |
|
95 tabcbt.get_active_text()!="" && |
|
96 (edgemapcbts[INPUT])->get_active_text()!="" && |
|
97 (edgemapcbts[OUTPUT])->get_active_text()!="" && |
|
98 source.get_active_text()!="" && |
|
99 target.get_active_text()!="" |
|
100 ) |
|
101 { |
|
102 const Graph &g=mapstorage->graph; |
|
103 Node from, to; |
|
104 |
|
105 get_from_to(from, to, (Graph&)g); |
|
106 |
|
107 std::ostringstream o; |
|
108 |
|
109 if(!(from==to)) |
|
110 { |
|
111 Graph::EdgeMap<double> * inputmap= |
|
112 (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()]; |
|
113 Graph::EdgeMap<double> * outputmap= |
|
114 (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()]; |
|
115 |
|
116 //zero out output map |
|
117 for (EdgeIt i(g); i!=INVALID; ++i) |
|
118 { |
|
119 (*outputmap)[i]=0; |
|
120 } |
|
121 |
|
122 Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to); |
|
123 |
|
124 int found=sb.run(num_set->get_value_as_int()); |
|
125 if(found) |
|
126 { |
|
127 for(int j=0;j<found;j++) |
|
128 { |
|
129 DirPath<Graph> path(g); |
|
130 sb.getPath(path, j); |
|
131 for(int k=0;k<path.length();k++) |
|
132 { |
|
133 DirPath<Graph>::EdgeIt ei; |
|
134 path.nth(ei,k); |
|
135 (*outputmap)[ei]=j+1; |
|
136 } |
|
137 } |
|
138 o << "Result: found " << found << " paths between "; |
|
139 o << source.get_active_text() << " and " << target.get_active_text(); |
|
140 } |
|
141 else |
|
142 { |
|
143 o << "Result: failed to find shortest path between "; |
|
144 o << source.get_active_text() << " and " << target.get_active_text(); |
|
145 } |
|
146 resultlabel.set_text(o.str()); |
|
147 |
|
148 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text()); |
|
149 // mapstorage->changeActiveMap(true, E_COLOR, |
|
150 // (edgemapcbts[OUTPUT])->get_active_text()); |
|
151 // mapstorage->changeActiveMap(true, E_TEXT, |
|
152 // (edgemapcbts[INPUT])->get_active_text()); |
|
153 } |
83 } |
154 } |
84 } |
155 } |
85 |
156 |
86 void DijkstraBox::build_box() |
157 void DijkstraBox::build_box() |
87 { |
158 { |