COIN-OR::LEMON - Graph Library

source: glemon-0.x/dijkstrabox.cc

Last change on this file was 188:c1c9fcf03e94, checked in by Alpar Juttner, 13 years ago

Syncronize glemon repo with the latest version of lemon.
(lemon::Path seems to seriously buggy)

File size: 6.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#include <dijkstrabox.h>
20#include <lemon/dijkstra.h>
21#include <lemon/suurballe.h>
22#include <lemon/path.h>
23
24enum {INPUT, OUTPUT, MAP_NUM};
25
26DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
27{
28  init(t);
29}
30   
31SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
32{
33  Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
34  num_set = new Gtk::SpinButton(*adjustment, 5,0);
35
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();
40
41  table.attach(*label, 0,1,2,3);
42  table.attach(*num_set, 1,2,2,3);
43
44
45//   pack_start(hbox);
46}
47   
48void DijkstraBox::run()
49{
50  if(
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()!=""
56     )
57    {
58      const Graph &g=mapstorage->graph;
59      Node from, to;
60
61      get_from_to(from, to, (Graph&)g);
62
63      std::ostringstream o;
64
65      if(!(from==to))
66        {
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()];
71
72          //zero out output map
73          for (EdgeIt i(g); i!=INVALID; ++i)
74            {
75              (*outputmap)[i]=0;
76            }
77         
78          Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
79          dijkstra.run(from, to);
80         
81          if(dijkstra.reached(to))
82            {
83              Node n=to;
84              int length=0;
85              while (n!=INVALID && n!=from)
86                {
87                  Edge e=dijkstra.predEdge(n);
88                  (*outputmap)[e]=1;
89                  n=dijkstra.predNode(n);
90                  length++;
91                }
92              o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
93            }
94          else
95            {
96              o << "Result: failed to find shortest path between ";
97              o << source.get_active_text() << " and " << target.get_active_text();
98            }
99          resultlabel.set_text(o.str());
100         
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());
106        }
107    }
108}
109
110void SuurballeBox::run()
111{
112  if(
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()!=""
118     )
119    {
120      const Graph &g=mapstorage->graph;
121      Node from, to;
122
123      get_from_to(from, to, (Graph&)g);
124
125      std::ostringstream o;
126
127      if(!(from==to))
128        {
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()];
133
134          //zero out output map
135          for (EdgeIt i(g); i!=INVALID; ++i)
136            {
137              (*outputmap)[i]=0;
138            }
139         
140          Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
141         
142          int found=sb.run(num_set->get_value_as_int());
143          if(found)
144            {
145              for(int j=0;j<found;j++)
146                {
147                  Path<Graph> path;
148                  path=sb.path(j);
149                  for(int k=0;k<path.length();k++)
150                    {
151                      (*outputmap)[path.nth(k)]=j+1;
152                    }
153                }
154              o << "Result: found " << found << " paths between ";
155              o << source.get_active_text() << " and " << target.get_active_text();
156            }
157          else
158            {
159              o << "Result: failed to find shortest path between ";
160              o << source.get_active_text() << " and " << target.get_active_text();
161            }
162          resultlabel.set_text(o.str());
163         
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());
169        }
170    }
171}
172   
173void DijkstraBox::build_box()
174{
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));
178
179  addMapSelector("Cost map: ", true);
180  addMapSelector("Edges of path here: ", true);
181
182  Gtk::Label * source_label=new Gtk::Label("Source: ");
183  Gtk::Label * target_label=new Gtk::Label("Target: ");
184
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);
189
190
191  pack_start(table);
192
193  resultlabel.set_text("Result: algorithm is not run yet.");
194  pack_start(resultlabel);
195}
196
197void SuurballeBox::build_box()
198{
199}
200
201void DijkstraBox::maplists_updated()
202{
203  if(tabcbt.get_active_text()!="")
204    {
205      source.clear();
206      target.clear();
207      const Graph &g=mapstorage->graph;
208      for (NodeIt i(g); i!=INVALID; ++i)
209        {
210          std::ostringstream text;
211          text << (*((mapstorage->nodemap_storage)["label"]))[i];
212          source.prepend_text(text.str());
213          target.prepend_text(text.str());
214        }
215    }
216}
217
218void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
219{
220  int assigned=0;
221  for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
222    {
223      std::ostringstream text;
224      text << (*((mapstorage->nodemap_storage)["label"]))[i];
225      if(!(text.str().compare(source.get_active_text())))
226        {
227          from=i;
228          assigned++;
229        }
230      if(!(text.str().compare(target.get_active_text())))
231        {
232          to=i;
233          assigned++;
234        }
235    }
236}
Note: See TracBrowser for help on using the repository browser.