COIN-OR::LEMON - Graph Library

source: lemon-0.x/gui/new_map_win.cc @ 1883:05b0e8d057a6

Last change on this file since 1883:05b0e8d057a6 was 1879:01d41844ef46, checked in by Hegyi Péter, 18 years ago

Kruskal algorithm can be run from GUI from now on.

File size: 10.4 KB
Line 
1#include <new_map_win.h>
2
3bool NewMapWin::closeIfEscapeIsPressed(GdkEventKey* e)
4{
5  if(e->keyval==GDK_Escape)
6  {
7    hide();
8  }
9  return true;
10}
11
12NewMapWin::NewMapWin(const std::string& title, NoteBookTab & mw, bool itisedge, bool edgenode):Gtk::Dialog(title, true, true),mytab(mw),node("Create NodeMap"),edge("Create EdgeMap")
13{
14  set_default_size(200, 50);
15
16  signal_key_press_event().connect(sigc::mem_fun(*this, &NewMapWin::closeIfEscapeIsPressed));
17
18  Gtk::VBox * vbox=get_vbox();
19
20  //entries
21  table=new Gtk::Table(3, 2, false);
22
23  label=new Gtk::Label;
24  label->set_text("Name of new map:");
25  name.set_text("");
26
27  (*table).attach(*label,0,1,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
28  (*table).attach(name,1,2,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
29
30  label=new Gtk::Label;
31  label->set_text("Default value in the map:");
32  default_value.set_text("0");
33
34  (*table).attach(*label,0,1,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
35  (*table).attach(default_value,1,2,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
36
37  //node vs. edge map selector
38  Gtk::RadioButton::Group group = node.get_group();
39  edge.set_group(group);
40 
41  if(edgenode)
42    {
43      (*table).attach(node,0,1,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
44      (*table).attach(edge,1,2,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
45    }
46  else
47    {
48      if(itisedge)
49        {
50          edge.set_active();
51        }
52      else
53        {
54          node.set_active();
55        }
56    }
57
58  vbox->pack_start(*table);
59
60  //OK button
61  add_button(Gtk::Stock::OK, Gtk::RESPONSE_OK);
62
63  show_all_children();
64
65}
66
67void NewMapWin::on_response(int response_id)
68{
69  if(response_id==Gtk::RESPONSE_OK)
70    {
71      double def_val=0;
72
73      //get and formulate text
74      std::string def_val_str=default_value.get_text();
75      std::string polishform=string2Polishform(def_val_str,edge.get_active());
76
77      //get name of text
78      std::string mapname=name.get_text();
79
80      if(!mapname.empty()&&!polishform.empty())
81        {
82          int abortion=0;
83          if(edge.get_active())
84            {
85              //create the new map
86              Graph::EdgeMap<double> * emptr=new Graph::EdgeMap<double> (mytab.mapstorage.graph);
87
88              std::stack<double> polishstack;
89 
90              for(EdgeIt k(mytab.mapstorage.graph); k!=INVALID; ++k)
91                {
92                  for(int i=0;i<(int)polishform.size();i++)
93                    {
94                      double op1, op2;
95                      bool operation=true;
96                      switch(polishform[i])
97                        {
98                        case '+':
99                        case '-':
100                        case '/':
101                        case '*':
102                          op1=polishstack.top();
103                          polishstack.pop();
104                          op2=polishstack.top();
105                          polishstack.pop();
106                          break;
107                        default:
108                          //substitute variable
109                          std::map< std::string,Graph::EdgeMap<double> * > ems=mytab.mapstorage.edgemap_storage;
110                          bool itisvar=(ems.find(ch2var[ polishform[i] ])!=ems.end());
111                          if(itisvar)
112                            {
113                              polishstack.push( (*(mytab.mapstorage.edgemap_storage[ ch2var[ polishform[i] ] ]))[k]);
114                            }
115                          else
116                            {
117                              char * def_val_ch=new char [(int)(ch2var[ polishform[i] ].length())];
118                              for(int j=0;j<(int)(ch2var[ polishform[i] ].length());j++)
119                                {
120                                  def_val_ch[j]=ch2var[ polishform[i] ][j];
121                                }
122                              polishstack.push(atof(def_val_ch));
123                              delete def_val_ch;
124                            }
125                          operation=false;
126                          break;
127                        }
128                      if(operation)
129                        {
130                          double res;
131                          switch(polishform[i])
132                            {
133                            case '+':
134                              res=op1+op2;
135                              break;
136                            case '-':
137                              res=op2-op1;
138                              break;
139                            case '/':
140                              res=op2/op1;
141                              break;
142                            case '*':
143                              res=op1*op2;
144                              break;
145                            default:
146                              std::cout << "How could we get here?" << std::endl;
147                              break;
148                            }
149                          polishstack.push(res);
150                        }
151                    }
152                  (*emptr)[k]=polishstack.top();
153                }
154
155              //if addition was not successful addEdgeMap returns one.
156              //cause can be that there is already a map named like the new one
157              if(mytab.mapstorage.addEdgeMap(mapname, emptr, def_val))
158                {
159                  abortion=1;
160                }
161
162              //add it to the list of the displayable maps
163              //furthermore it is done by signals
164              //mytab.registerNewEdgeMap(mapname);
165
166              //display it
167              //gdc.changeEdgeText(mapname);
168
169              //delete emptr;
170            }
171          else //!edge.get_active()
172            {
173              //create the new map
174              Graph::NodeMap<double> * emptr=new Graph::NodeMap<double> (mytab.mapstorage.graph);
175
176              std::stack<double> polishstack;
177 
178              for(NodeIt k(mytab.mapstorage.graph); k!=INVALID; ++k)
179                {
180                  for(int i=0;i<(int)polishform.size();i++)
181                    {
182                      double op1, op2;
183                      bool operation=true;
184                      switch(polishform[i])
185                        {
186                        case '+':
187                        case '-':
188                        case '/':
189                        case '*':
190                          op1=polishstack.top();
191                          polishstack.pop();
192                          op2=polishstack.top();
193                          polishstack.pop();
194                          break;
195                        default:
196                          std::map< std::string,Graph::NodeMap<double> * > nms=mytab.mapstorage.nodemap_storage;
197                          bool itisvar=(nms.find(ch2var[ polishform[i] ])!=nms.end());
198                          if(itisvar)
199                            {
200                              polishstack.push( (*(mytab.mapstorage.nodemap_storage[ ch2var[ polishform[i] ] ]))[k]);
201                            }
202                          else
203                            {
204                              char * def_val_ch=new char [(int)(ch2var[ polishform[i] ].length())];
205                              for(int j=0;j<(int)(ch2var[ polishform[i] ].length());j++)
206                                {
207                                  def_val_ch[j]=ch2var[ polishform[i] ][j];
208                                }
209                              polishstack.push(atof(def_val_ch));
210                              delete def_val_ch;
211                            }
212                          operation=false;
213                          break;
214                        }
215                      if(operation)
216                        {
217                          double res;
218                          switch(polishform[i])
219                            {
220                            case '+':
221                              res=op1+op2;
222                              break;
223                            case '-':
224                              res=op2-op1;
225                              break;
226                            case '/':
227                              res=op2/op1;
228                              break;
229                            case '*':
230                              res=op1*op2;
231                              break;
232                            default:
233                              std::cout << "How could we get here?" << std::endl;
234                              break;
235                            }
236                          polishstack.push(res);
237                        }
238                    }
239                  (*emptr)[k]=polishstack.top();
240                }
241
242              //if addition was not successful addNodeMap returns one.
243              //cause can be that there is already a map named like the new one
244              if(mytab.mapstorage.addNodeMap(mapname,emptr, def_val))
245                {
246                  abortion=1;
247                }
248
249              //add it to the list of the displayable maps
250              //furthermore it is done by signals
251              //mytab.registerNewNodeMap(mapname);
252
253              //display it
254              //gdc.changeNodeText(mapname);
255
256              //delete emptr;
257            }
258          if(!abortion)
259            {
260              name.set_text("");
261              default_value.set_text("0");
262              edge.show();
263              node.show();
264              hide();
265            }
266        }
267    }
268}
269
270
271std::string NewMapWin::string2Polishform(std::string rawcommand, bool itisedge)
272{
273  bool valid_entry=true;
274
275  std::map<std::string, int> str2i;
276
277  std::string command;
278
279  std::string variable;
280
281  char index='a';
282
283  for(int i=0;(valid_entry&&(i<(int)rawcommand.size()));i++)
284    {
285      switch(rawcommand[i])
286        {
287        case '+':
288        case '-':
289        case '*':
290        case '/':
291        case ')':
292        case '(':
293          if(!variable.empty())
294            {
295              valid_entry=validVariable(variable, itisedge);
296              ch2var[index]=variable;
297              command+=index;
298              index++;
299              variable.erase(0,variable.size());         
300            }
301          command+=rawcommand[i];
302          break;
303        default:
304          variable+=rawcommand[i];
305          break;
306        }
307    }
308
309  if(!variable.empty()&&valid_entry)
310    {
311      valid_entry=validVariable(variable, itisedge);
312      ch2var[index]=variable;
313      command+=index;
314      index++;
315      variable.erase(0,variable.size());         
316    }
317
318  if(valid_entry)
319    {
320      unsigned int pr=10000;
321      bool prevmult=false;
322      unsigned int prev_change=pr;
323      unsigned int prev_br=pr;
324      int counter=0;
325      std::string comm_nobr="";
326      std::vector<unsigned int> p;
327      p.resize(counter+1);
328     
329      //limits
330      //6 brackets embedded
331      //100 operation in a row from the same priority
332     
333      for(int i=0;i<(int)command.size();i++)
334        {
335          bool put_in_string=true;
336          switch(command[i])
337            {
338            case '(':
339              pr=prev_br+10000;
340              prev_br=pr;
341              prevmult=false;
342              put_in_string=false;
343              break;
344            case ')':
345              pr=prev_br-10000;
346              prev_br=pr;
347              prevmult=false;
348              put_in_string=false;
349              break;
350            case '+':
351            case '-':
352              if(prevmult)
353                {
354                  pr=prev_change;
355                }
356              p[counter]=pr;
357              pr-=100;
358
359              prevmult=false;
360              break;
361            case '/':
362            case '*':
363              if(!prevmult)
364                {
365                  prev_change=pr;
366                  pr+=200;
367                  pr-=1;
368                }
369              p[counter]=pr;
370              pr-=1;
371              prevmult=true;
372              break;
373            default:
374              p[counter]=65000;
375              break;
376            }
377          if(put_in_string)
378            {
379              counter++;
380              p.resize(counter+1);
381              comm_nobr=comm_nobr+command[i];
382            }
383        }
384
385      tree_node * root=weightedString2Tree(comm_nobr, p, 0);
386
387      std::string polishform=postOrder(root);
388
389      return polishform;
390    }
391  return "";
392}
393
394NewMapWin::tree_node * NewMapWin::weightedString2Tree(std::string to_tree, std::vector<unsigned int> & p, int offset)
395{
396  unsigned int min=p[offset];
397  int minplace=0;
398  for(int i=0;i<(int)to_tree.size();i++)
399    {
400      if(min>p[offset+i])
401        {
402          min=p[offset+i];
403          minplace=i;
404        }
405    }
406  tree_node * act_node=new tree_node;
407  act_node->ch=to_tree[minplace];
408  if(to_tree.size()>=3)
409    {
410      act_node->left_child=weightedString2Tree(to_tree.substr(0,minplace), p, offset);
411      act_node->right_child=weightedString2Tree(to_tree.substr(minplace+1,to_tree.size()-minplace-1), p, offset+minplace+1);
412    }
413  else
414    {
415      act_node->left_child=NULL;
416      act_node->right_child=NULL;
417    }
418  return act_node;
419}
420
421std::string NewMapWin::postOrder(tree_node * subtree)
422{
423  std::string subtree_to_string;
424  if(subtree->left_child)
425    {
426      subtree_to_string=postOrder(subtree->left_child);
427    }
428  if(subtree->right_child)
429    {
430      subtree_to_string=subtree_to_string+postOrder(subtree->right_child);
431    }
432  subtree_to_string=subtree_to_string+subtree->ch;
433  return subtree_to_string;
434}
435
436bool NewMapWin::validVariable(std::string variable, bool itisedge)
437{
438  bool cancel;
439  //is it mapname?
440  if(itisedge)
441    {
442      cancel=(mytab.mapstorage.edgemap_storage.find(variable)==mytab.mapstorage.edgemap_storage.end());
443    }
444  else
445    {
446      cancel=(mytab.mapstorage.nodemap_storage.find(variable)==mytab.mapstorage.nodemap_storage.end());
447    }
448  //maybe it is number
449  int point_num=0;
450  if(cancel)
451    {
452      cancel=false;
453      for(int j=0;(!cancel)&&(j<(int)variable.size());j++)
454        {
455          if(((variable[j]<'0')||(variable[j]>'9'))&&(variable[j]!='.'))
456            {
457              cancel=true;
458            }
459          else
460            {
461              if(variable[j]=='.')
462                {
463                  point_num++;
464                  if(point_num>1)
465                    {
466                      cancel=true;
467                    }
468                }
469            }
470        }
471    }
472  if(cancel)
473    {
474      return false;
475    }
476  return true;
477}
Note: See TracBrowser for help on using the repository browser.