COIN-OR::LEMON - Graph Library

source: glemon-0.x/dijkstrabox.cc @ 201:879e47e5b731

Last change on this file since 201:879e47e5b731 was 201:879e47e5b731, checked in by Akos Ladanyi, 17 years ago

Merge branches/akos to trunk.

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