COIN-OR::LEMON - Graph Library

source: glemon-0.x/dijkstrabox.cc @ 197:c1084e2bff10

Last change on this file since 197:c1084e2bff10 was 194:6b2b718420eb, checked in by Hegyi Péter, 13 years ago

Header reorganising

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