COIN-OR::LEMON - Graph Library

source: glemon/dijkstrabox.cc @ 3:2cc5ed6e6255

Last change on this file since 3:2cc5ed6e6255 was 1:67188bd752db, checked in by Peter Hegyi <hegyi@…>, 16 years ago

SVN revision 3500 made compilable with Lemon 1.0.

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