COIN-OR::LEMON - Graph Library

source: glemon-0.x/dijkstrabox.cc @ 165:2cd447b0bd3a

Last change on this file since 165:2cd447b0bd3a was 165:2cd447b0bd3a, checked in by Hegyi Péter, 17 years ago

Suurballe algorithm is implemented in glemon.

File size: 5.6 KB
Line 
1#include <dijkstrabox.h>
2#include <lemon/dijkstra.h>
3#include <lemon/suurballe.h>
4#include <lemon/path.h>
5
6enum {INPUT, OUTPUT, MAP_NUM};
7
8DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
9{
10  init(t);
11}
12   
13SuurballeBox::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);
28}
29   
30void DijkstraBox::run()
31{
32  if(
33     tabcbt.get_active_text()!="" &&
34     (edgemapcbts[INPUT])->get_active_text()!="" &&
35     (edgemapcbts[OUTPUT])->get_active_text()!="" &&
36     source.get_active_text()!="" &&
37     target.get_active_text()!=""
38     )
39    {
40      const Graph &g=mapstorage->graph;
41      Node from, to;
42
43      get_from_to(from, to, (Graph&)g);
44
45      std::ostringstream o;
46
47      if(!(from==to))
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         
60          Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
61          dijkstra.run(from, to);
62         
63          if(dijkstra.reached(to))
64            {
65              Node n=to;
66              int length=0;
67              while (n!=INVALID && n!=from)
68                {
69                  Edge e=dijkstra.predEdge(n);
70                  (*outputmap)[e]=1;
71                  n=dijkstra.predNode(n);
72                  length++;
73                }
74              o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
75            }
76          else
77            {
78              o << "Result: failed to find shortest path between ";
79              o << source.get_active_text() << " and " << target.get_active_text();
80            }
81          resultlabel.set_text(o.str());
82         
83          mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
84          //   mapstorage->changeActiveMap(true, E_COLOR,
85          //                          (edgemapcbts[OUTPUT])->get_active_text());
86          //   mapstorage->changeActiveMap(true, E_TEXT,
87          //                          (edgemapcbts[INPUT])->get_active_text());
88        }
89    }
90}
91
92void 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        }
154    }
155}
156   
157void DijkstraBox::build_box()
158{
159  //if active tab is changed, labels of graph nodes had to be loaded into comboboxes
160  //this can be done after the maps are loaded into ComboBoxes
161  signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
162
163  addMapSelector("Cost map: ", true);
164  addMapSelector("Edges of path here: ", true);
165
166  Gtk::Label * source_label=new Gtk::Label("Source: ");
167  Gtk::Label * target_label=new Gtk::Label("Target: ");
168
169  table.attach(*source_label, 0,1,0,1);
170  table.attach(*target_label, 0,1,1,2);
171  table.attach(source, 1,2,0,1);
172  table.attach(target, 1,2,1,2);
173
174
175  pack_start(table);
176
177  resultlabel.set_text("Result: algorithm is not run yet.");
178  pack_start(resultlabel);
179}
180
181void SuurballeBox::build_box()
182{
183}
184
185void DijkstraBox::maplists_updated()
186{
187  if(tabcbt.get_active_text()!="")
188    {
189      source.clear();
190      target.clear();
191      const Graph &g=mapstorage->graph;
192      for (NodeIt i(g); i!=INVALID; ++i)
193        {
194          std::ostringstream text;
195          text << (*((mapstorage->nodemap_storage)["label"]))[i];
196          source.prepend_text(text.str());
197          target.prepend_text(text.str());
198        }
199    }
200}
201
202void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
203{
204  int assigned=0;
205  for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
206    {
207      std::ostringstream text;
208      text << (*((mapstorage->nodemap_storage)["label"]))[i];
209      if(!(text.str().compare(source.get_active_text())))
210        {
211          from=i;
212          assigned++;
213        }
214      if(!(text.str().compare(target.get_active_text())))
215        {
216          to=i;
217          assigned++;
218        }
219    }
220}
Note: See TracBrowser for help on using the repository browser.