Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
aleph-graph.H
1 # ifndef ALEPH_GRAPH_H
2 # define ALEPH_GRAPH_H
3 
4 # include <memory>
5 
6 namespace Aleph {
7 
8 static const long No_Visited = 0; // nodo o arco no ha sido visitado
9 
11 enum Graph_Bits
12 {
13  Depth_First,
14  Breadth_First,
15  Test_Cycle,
16  Is_Acyclique,
17  Test_Path,
18  Find_Path,
19  Kruskal,
20  Prim,
21  Dijkstra,
22  Euler,
23  Maximum_Flow,
24  Spanning_Tree,
25  Build_Subtree,
26  Convert_Tree,
27  Cut,
28  Min,
29 
30  Num_Bits_Graph
31 };
32 
47 class Bit_Fields
48 {
49 public:
50 
51  unsigned int depth_first : 1;
52  unsigned int breadth_first : 1;
53  unsigned int test_cycle : 1;
54  unsigned int is_acyclique : 1;
55  unsigned int test_path : 1;
56  unsigned int find_path : 1;
57  unsigned int kruskal : 1;
58  unsigned int prim : 1;
59  unsigned int dijkstra : 1;
60  unsigned int euler : 1;
61  unsigned int maximum_flow : 1;
62  unsigned int spanning_tree : 1;
63  unsigned int build_subtree : 1;
64  unsigned int convert_tree : 1;
65  unsigned int cut : 1;
66  unsigned int min : 1;
67 
69  Bit_Fields()
70  : depth_first(0), breadth_first(0), test_cycle(0),
71  is_acyclique(0), test_path(0), find_path(0), kruskal(0),
72  prim(0), dijkstra(0), euler(0), maximum_flow(0),
73  spanning_tree(0), build_subtree(0), convert_tree(0),
74  cut(0), min(0) {}
75 
86  bool get_bit(const int & bit) const
87  throw(std::exception, std::out_of_range)
88  {
89  switch (bit)
90  {
91  case Aleph::Depth_First: return depth_first;
92  case Aleph::Breadth_First: return breadth_first;
93  case Aleph::Test_Cycle: return test_cycle;
94  case Aleph::Is_Acyclique: return is_acyclique;
95  case Aleph::Test_Path: return test_path;
96  case Aleph::Find_Path: return find_path;
97  case Aleph::Kruskal: return kruskal;
98  case Aleph::Prim: return prim;
99  case Aleph::Dijkstra: return dijkstra;
100  case Aleph::Euler: return euler;
101  case Aleph::Maximum_Flow: return maximum_flow;
102  case Aleph::Spanning_Tree: return spanning_tree;
103  case Aleph::Build_Subtree: return build_subtree;
104  case Aleph::Convert_Tree: return convert_tree;
105  case Aleph::Cut: return cut;
106  case Aleph::Min: return min;
107  default:
108  throw std::out_of_range("bit number out of range");
109  }
110  }
111 
124  void set_bit(const int & bit, const int & value)
125  {
126  I(value == 0 or value == 1);
127 
128  switch (bit)
129  {
130  case Aleph::Depth_First: depth_first = value; break;
131  case Aleph::Breadth_First: breadth_first = value; break;
132  case Aleph::Test_Cycle: test_cycle = value; break;
133  case Aleph::Is_Acyclique: is_acyclique = value; break;
134  case Aleph::Test_Path: test_path = value; break;
135  case Aleph::Find_Path: find_path = value; break;
136  case Aleph::Kruskal: kruskal = value; break;
137  case Aleph::Prim: prim = value; break;
138  case Aleph::Dijkstra: dijkstra = value; break;
139  case Aleph::Euler: euler = value; break;
140  case Aleph::Maximum_Flow: maximum_flow = value; break;
141  case Aleph::Spanning_Tree: spanning_tree = value; break;
142  case Aleph::Build_Subtree: build_subtree = value; break;
143  case Aleph::Convert_Tree: convert_tree = value; break;
144  case Aleph::Cut: cut = value; break;
145  case Aleph::Min: min = value; break;
146  default:
147  throw std::out_of_range("bit number out of range");
148  }
149  }
150 
152  void reset(const int & bit) { set_bit(bit, 0); }
153 
155  void reset()
156  {
157  depth_first = 0;
158  breadth_first = 0;
159  test_cycle = 0;
160  is_acyclique = 0;
161  test_path = 0;
162  find_path = 0;
163  kruskal = 0;
164  prim = 0;
165  dijkstra = 0;
166  euler = 0;
167  maximum_flow = 0;
168  spanning_tree = 0;
169  build_subtree = 0;
170  convert_tree = 0;
171  cut = 0;
172  min = 0;
173  }
174 };
175 
176 
177 struct Graph_Attr
178 {
179  Bit_Fields control_bits;
180  long counter;
181  void * cookie;
182 
183  Graph_Attr() : counter(No_Visited), cookie(NULL) { }
184 };
185 
186 
187 # define GRAPH_NODE_COMMON(GT_Node_Name) \
188  Graph_Attr attrs; \
189  typedef Node_Info Item_Type; \
190  typedef GT_Node_Name Node; \
191  typedef Node_Info Node_Type; \
192  Node_Info node_info; \
193  Node_Info & get_info() { return node_info; } \
194  const Node_Info & get_info() const { return node_info; } \
195  size_t num_arcs;
196 
197 
198 # define GRAPH_ARC_COMMON(GT_Arc_Name) \
199  typedef Arc_Info Item_Type; \
200  typedef GT_Arc_Name Arc; \
201  typedef Arc_Info Arc_Type; \
202  Arc_Info arc_info; \
203  Graph_Attr attrs; \
204  void * src_node; \
205  void * tgt_node; \
206  \
207  Arc_Info & get_info() { return arc_info; } \
208  \
209  const Arc_Info & get_info() const { return arc_info; } \
210  \
211  void * get_connected_node(void * node) \
212  { \
213  return src_node == node ? tgt_node : src_node; \
214  }
215 
216 
221 # define NODE_BITS(p) ((p)->attrs.control_bits)
222 
226 # define NODE_COUNTER(p) ((p)->attrs.counter)
227 
232 # define NODE_COLOR(p) ((p)->attrs.counter)
233 
242 # define IS_NODE_VISITED(p, bit) (NODE_BITS(p).get_bit(bit))
243 
248 # define NODE_COOKIE(p) ((p)->attrs.cookie)
249 
254 # define ARC_COUNTER(p) ((p)->attrs.counter)
255 
260 # define ARC_COLOR(p) ((p)->attrs.counter)
261 
266 # define ARC_BITS(p) ((p)->attrs.control_bits)
267 
275 # define IS_ARC_VISITED(p, bit) (ARC_BITS(p).get_bit(bit))
276 
281 # define ARC_COOKIE(p) ((p)->attrs.cookie)
282 
283 
284 # define GRAPH_ATTR_COMMON(Graph_Name) \
285  public: \
286  typedef Graph_Name<__Graph_Node, __Graph_Arc> Graph_Class; \
287  typedef __Graph_Node Node; \
288  typedef __Graph_Arc Arc; \
289  typedef typename Node::Node_Type Node_Type; \
290  typedef typename Arc::Arc_Type Arc_Type; \
291  \
292 protected: \
293  \
294  void * cookie; \
295  \
296  struct Reset_Node \
297  { \
298  void operator () (Graph_Name&, Node * node) const \
299  { \
300  NODE_BITS(node).reset(); \
301  NODE_COUNTER(node) = 0; \
302  NODE_COOKIE(node) = NULL; \
303  } \
304  }; \
305  \
306  struct Reset_Arc \
307  { \
308  void operator () (Graph_Name&, Arc * arc) const \
309  { \
310  ARC_BITS(arc).reset(); \
311  ARC_COUNTER(arc) = 0; \
312  ARC_COOKIE(arc) = NULL; \
313  } \
314  }; \
315  \
316  size_t num_nodes; \
317  size_t num_arcs; \
318  bool digraph; \
319  \
320  void init() \
321  { \
322  num_nodes = num_arcs = 0; \
323  cookie = NULL; \
324  digraph = false; \
325  } \
326  \
327 protected: \
328  \
329  void common_swap(Graph_Name & g) \
330  { \
331  if (digraph != g.digraph) \
332  throw std::domain_error("source and target incompatible"); \
333  \
334  std::swap(num_nodes, g.num_nodes); \
335  std::swap(num_arcs, g.num_arcs); \
336  std::swap(digraph, g.digraph); \
337  std::swap(cookie, g.cookie); \
338  } \
339  \
340 public: \
341  \
342  void *& get_cookie() { return cookie; } \
343  \
344  bool is_digraph() const { return digraph; } \
345  \
346  const size_t & get_num_nodes() const { return num_nodes; } \
347  \
348  const size_t & vsize() const { return get_num_nodes(); } \
349  \
350  Node * get_src_node(Arc * arc) const { return (Node*) arc->src_node; } \
351  \
352  Node * get_tgt_node(Arc * arc) const { return (Node*) arc->tgt_node; } \
353  \
354  Node * get_connected_node(Arc * arc, Node * node) const \
355  { \
356  return (Node*) arc->get_connected_node(node); \
357  } \
358  \
359  const size_t & get_num_arcs() const { return num_arcs; } \
360  \
361  const size_t & esize() const { return get_num_arcs(); } \
362  \
363  const size_t & get_num_arcs(Node * node) const \
364  { \
365  return node->num_arcs; \
366  } \
367  \
368  Bit_Fields & get_control_bits(Node * node) const \
369  { \
370  return NODE_BITS(node).reset(); \
371  } \
372  \
373  void reset_bit(Node * node, const int & bit) const \
374  { \
375  NODE_BITS(node).reset(bit); \
376  } \
377  \
378  void reset_bits(Node * node) const { NODE_BITS(node).reset(); } \
379  \
380  void set_bit(Node * node, const int bit, const int value) \
381  { \
382  NODE_BITS(node).set_bit(bit, value); \
383  } \
384  \
385  Bit_Fields & get_control_bits(Arc * arc) const { return ARC_BITS(arc); } \
386  \
387  void reset_bit(Arc * arc, const int bit) const \
388  { \
389  ARC_BITS(arc).reset(bit); \
390  } \
391  \
392  void reset_bits(Arc * arc) const { ARC_BITS(arc).reset(); } \
393  \
394  void set_bit(Arc * arc, const int bit, const int value) const \
395  { \
396  ARC_BITS(arc).set_bit(bit, value); \
397  } \
398  \
399  void *& get_cookie(Node * node) const { return NODE_COOKIE(node); } \
400  \
401  void *& get_cookie(Arc * arc) const { return ARC_COOKIE(arc); } \
402  \
403  long & get_counter(Node * node) const { return NODE_COUNTER(node); } \
404  \
405  void reset_counter(Node * node) const { NODE_COUNTER(node) = No_Visited; } \
406  \
407  void reset_node(Node * node) const \
408  { \
409  node_bits(node).reset(); \
410  NODE_COUNTER(node) = 0; \
411  NODE_COOKIE(node) = NULL; \
412  } \
413  \
414  long & get_counter(Arc * arc) const { return ARC_COUNTER(arc); } \
415  \
416  void reset_counter(Arc * arc) const { ARC_COUNTER(arc) = No_Visited; } \
417  \
418  void reset_arc(Arc * arc) const \
419  { \
420  ARC_BITS(arc).reset(); \
421  ARC_COUNTER(arc) = 0; \
422  ARC_COOKIE(arc) = NULL; \
423  } \
424  \
425  template <class N1, class N2> static \
426  void map_nodes(N1 * p, N2 * q) \
427  { \
428  I(p != NULL and q != NULL); \
429  \
430  if (NODE_COOKIE(p) == NULL) \
431  { \
432  NODE_COOKIE(p) = q; \
433  NODE_COOKIE(q) = p; \
434  return; \
435  } \
436  \
437  NODE_COOKIE(q) = NODE_COOKIE(p); \
438  NODE_COOKIE(p) = q; \
439  } \
440  \
441  template <class A1, class A2> static \
442  void map_arcs(A1 * p, A2 * q) \
443  { \
444  I(p != NULL and q != NULL); \
445  \
446  if (ARC_COOKIE(p) == NULL) \
447  { \
448  ARC_COOKIE(p) = q; \
449  ARC_COOKIE(q) = p; \
450  \
451  return; \
452  } \
453  \
454  ARC_COOKIE(q) = ARC_COOKIE(p); \
455  ARC_COOKIE(p) = q; \
456  }
457 
458 
459 # define GRAPH_ITERATIVE_METHODS \
460  void reset_bit_nodes(const int & bit) \
461  { \
462  for (Node_Iterator itor(*this); itor.has_curr(); itor.next()) \
463  reset_bit(itor.get_current_node(), bit); \
464  } \
465  \
466  void reset_bit_arcs(const int & bit) \
467  { \
468  for (Arc_Iterator itor(*this); itor.has_curr(); itor.next()) \
469  reset_bit(itor.get_current_arc(), bit); \
470  } \
471  void reset_bit_nodes() \
472  { \
473  for (Node_Iterator itor(*this); itor.has_curr(); itor.next()) \
474  reset_bits(itor.get_current_node()); \
475  } \
476  \
477  void reset_bit_arcs() \
478  { \
479  for (Arc_Iterator itor(*this); itor.has_curr(); itor.next()) \
480  reset_bits(itor.get_current_arc()); \
481  } \
482  \
483  Node * get_node(size_t k) \
484  { \
485  int m = num_nodes/2; \
486  Node_Iterator it(*this); \
487  \
488  if (k < m) \
489  for (int i = 0; i < k; ++i) \
490  it.next(); \
491  else \
492  { \
493  it.reset_last(); \
494  for (int i = num_nodes - 1; i > k; --i) \
495  it.prev(); \
496  } \
497  \
498  return it.get_curr(); \
499  } \
500  \
501  Node * get_arc(size_t k) \
502  { \
503  int m = num_arcs/2; \
504  Arc_Iterator it(*this); \
505  \
506  if (k < m) \
507  for (int i = 0; i < k; ++i) \
508  it.next(); \
509  else \
510  { \
511  it.reset_last(); \
512  for (int i = num_arcs - 1; i > k; --i) \
513  it.prev(); \
514  } \
515  \
516  return it.get_curr(); \
517  } \
518  \
519  void reset_counter_nodes() \
520  { \
521  for (Node_Iterator itor(*this); itor.has_curr(); itor.next()) \
522  reset_counter(itor.get_current_node()); \
523  } \
524  \
525  void reset_counter_arcs() \
526  { \
527  for (Arc_Iterator itor(*this); itor.has_curr(); itor.next()) \
528  reset_counter(itor.get_current_arc()); \
529  } \
530  \
531  void reset_cookie_nodes() \
532  { \
533  for (Node_Iterator itor(*this); itor.has_curr(); itor.next()) \
534  itor.get_current_node()->cookie = NULL; \
535  } \
536  \
537  void reset_cookie_arcs() \
538  { \
539  for (Arc_Iterator itor(*this); itor.has_curr(); itor.next()) \
540  itor.get_current_arc()->cookie = NULL; \
541  } \
542  inline void reset_nodes(); \
543  \
544  inline void reset_arcs(); \
545  \
546  typedef Node_Arc_Iterator Out_Iterator;
547 
548 
549 
550 # define GRAPH_SEARCH_METHODS \
551  template <class Equal> \
552  Node * search_node(const typename Node::Node_Type & node_info) \
553  { \
554  for (Node_Iterator itor(*this); itor.has_curr(); itor.next()) \
555  { \
556  Node * curr_node = itor.get_current_node(); \
557  if (Equal() (curr_node->get_info(), node_info)) \
558  return curr_node; \
559  } \
560  \
561  return NULL; \
562  } \
563  \
564  template <typename T, class Equal> \
565  Node * search_node(const T & data) \
566  { \
567  for (Node_Iterator it(*this); it.has_curr(); it.next()) \
568  { \
569  Node * p = it.get_current_node(); \
570  if (Equal () (p->get_info(), data)) \
571  return p; \
572  } \
573  \
574  return NULL; \
575  } \
576  \
577  Node * search_node(const typename Node::Node_Type & node_info) \
578  { \
579  return search_node<Aleph::equal_to<typename Node::Node_Type>>(node_info); \
580  } \
581  \
582  template <class Equal> \
583  Node * search_node(void * ptr) \
584  { \
585  for (Node_Iterator itor(*this); itor.has_curr(); itor.next()) \
586  { \
587  Node * curr_node = itor.get_current_node(); \
588  if (Equal () (curr_node, ptr)) \
589  return curr_node; \
590  } \
591  \
592  return NULL; \
593  } \
594  \
595  template <typename T, class Equal> \
596  Arc * search_Arc(const T & data) \
597  { \
598  for (Arc_Iterator it(*this); it.has_curr(); it.next()) \
599  { \
600  Arc * a = it.get_current_arc(); \
601  if (Equal () (a->get_info(), data)) \
602  return a; \
603  } \
604  \
605  return NULL; \
606  } \
607  \
608  template <class Equal> \
609  Arc * search_arc(const typename Arc::Arc_Type & arc_info) \
610  { \
611  for (Arc_Iterator it(*this); it.has_curr(); it.next()) \
612  { \
613  Arc * curr_arc = it.get_current_arc(); \
614  if (Equal () (curr_arc->get_info(), arc_info)) \
615  return curr_arc; \
616  } \
617  \
618  return NULL; \
619  } \
620  \
621  Arc * search_arc(const typename Arc::Arc_Type & arc_info) \
622  { \
623  return search_arc<Aleph::equal_to<Arc_Type>>(arc_info); \
624  } \
625  \
626  template <class Equal> \
627  Arc * search_arc(void * ptr) \
628  { \
629  for (Arc_Iterator itor(*this); itor.has_curr(); itor.next()) \
630  { \
631  Arc * curr_arc = itor.get_current_node(); \
632  if (Equal () (curr_arc, ptr)) \
633  return curr_arc; \
634  } \
635  \
636  return NULL; \
637  }
638 
639 
640 # define GRAPH_INSERTION_METHODS \
641  virtual Node * insert_node(const Node_Type & node_info) \
642  { \
643  return insert_node(new Node (node_info)); \
644  } \
645  \
646  virtual Node * insert_node(Node_Type && node_info = Node_Type()) \
647  { \
648  return insert_node(new Node(std::move(node_info))); \
649  } \
650  \
651  virtual Arc * \
652  insert_arc(Node * src, Node * tgt, const Arc_Type & arc_info) \
653  { \
654  std::unique_ptr<Arc> arc(new Arc(arc_info)); \
655  insert_arc(src, tgt, arc.get()); \
656  return arc.release(); \
657  } \
658  \
659  virtual Arc * \
660  insert_arc(Node * src, Node * tgt, Arc_Type && arc_info = Arc_Type()) \
661  { \
662  std::unique_ptr<Arc> arc(new Arc(std::move(arc_info))); \
663  insert_arc(src, tgt, arc.get()); \
664  return arc.release(); \
665  }
666 
667 
668 # define GRAPH_METHODS_IMPLS(Name) \
669  template <typename Node, typename Arc> \
670 void Name<Node, Arc>::reset_nodes() \
671 { \
672  Operate_On_Nodes <Graph_Class, Reset_Node> () (*this); \
673 } \
674  \
675  template <typename Node, typename Arc> \
676 void Name<Node, Arc>::reset_arcs() \
677 { \
678  Operate_On_Arcs <Graph_Class, Reset_Arc> () (*this); \
679 }
680 
681 # define GRAPH_FUNCTIONAL_METHODS(Name) \
682  template <class Operation> \
683  bool traverse_nodes(Operation & operation) const \
684  { \
685  for (Node_Iterator it(*const_cast<Name<Node,Arc>*>(this)); \
686  it.has_curr(); it.next()) \
687  if (not operation(it.get_curr())) \
688  return false; \
689  return true; \
690  } \
691  \
692  template <class Operation> \
693  bool traverse_nodes(Operation & operation) \
694  { \
695  for (Node_Iterator it(*this); it.has_curr(); it.next()) \
696  if (not operation(it.get_curr())) \
697  return false; \
698  return true; \
699  } \
700  \
701  template <class Operation> \
702  bool traverse_nodes(Operation && operation = Operation()) const \
703  { \
704  return const_cast<Name<Node,Arc>*>(this)-> \
705  traverse_nodes<Operation>(operation); \
706  } \
707  \
708  template <class Operation> \
709  bool traverse_nodes(Operation && operation = Operation()) \
710  { \
711  return traverse_nodes<Operation>(operation); \
712  } \
713  \
714  template <class Operation> \
715  bool traverse_arcs(Operation & operation) const \
716  { \
717  for (Arc_Iterator it(*const_cast<Name<Node,Arc>*>(this)); \
718  it.has_curr(); it.next()) \
719  if (not operation(it.get_curr())) \
720  return false; \
721  return true; \
722  } \
723  \
724  template <class Operation> \
725  bool traverse_arcs(Operation & operation) \
726  { \
727  for (Arc_Iterator it(*this); it.has_curr(); it.next()) \
728  if (not operation(it.get_curr())) \
729  return false; \
730  return true; \
731  } \
732  \
733  template <class Operation> \
734  bool traverse_arcs(Operation && operation = Operation()) const \
735  { \
736  return const_cast<Name<Node,Arc>*>(this)-> \
737  traverse_arcs<Operation>(operation); \
738  } \
739  \
740  template <class Operation> \
741  bool traverse_arcs(Operation && operation = Operation()) \
742  { \
743  return traverse_arcs<Operation>(operation); \
744  } \
745  \
746  template <class Operation> \
747  void for_each_node(Operation & operation) const \
748  { \
749  for (Node_Iterator it(*const_cast<Name<Node,Arc>*>(this)); \
750  it.has_curr(); it.next()) \
751  operation(it.get_curr()); \
752  } \
753  \
754  template <class Operation> \
755  void for_each_node(Operation & operation) \
756  { \
757  for (Node_Iterator it(*this); it.has_curr(); it.next()) \
758  operation(it.get_curr()); \
759  } \
760  \
761  template <class Operation> \
762  void for_each_node(Operation && operation = Operation()) const \
763  { \
764  const_cast<Name<Node,Arc>*>(this)-> \
765  for_each_node<Operation>(operation); \
766  } \
767  \
768  template <class Operation> \
769  void for_each_node(Operation && operation = Operation()) \
770  { \
771  for_each_node<Operation>(operation); \
772  } \
773  \
774  template <class Operation> \
775  bool all_node(Operation & operation) const \
776  { \
777  for (Node_Iterator it(*const_cast<Name<Node,Arc>*>(this)); \
778  it.has_curr(); it.next()) \
779  if (not operation(it.get_curr())) \
780  return false; \
781  return true; \
782  } \
783  \
784  template <class Operation> \
785  bool all_node(Operation & operation) \
786  { \
787  for (Node_Iterator it(*this); it.has_curr(); it.next()) \
788  if (not operation(it.get_curr())) \
789  return false; \
790  return true; \
791  } \
792  \
793  template <class Operation> \
794  bool all_node(Operation && operation = Operation()) const \
795  { \
796  return const_cast<Name<Node,Arc>*>(this)-> \
797  all_node<Operation>(operation); \
798  } \
799  \
800  template <class Operation> \
801  bool all_node(Operation && operation = Operation()) \
802  { \
803  return all_node<Operation>(operation); \
804  } \
805  \
806  template <class Operation> \
807  bool forall_node(Operation & operation) const \
808  { \
809  for (Node_Iterator it(*const_cast<Name<Node,Arc>*>(this)); \
810  it.has_curr(); it.next()) \
811  if (not operation(it.get_curr())) \
812  return false; \
813  return true; \
814  } \
815  \
816  template <class Operation> \
817  bool forall_node(Operation & operation) \
818  { \
819  for (Node_Iterator it(*this); it.has_curr(); it.next()) \
820  if (not operation(it.get_curr())) \
821  return false; \
822  return true; \
823  } \
824  \
825  template <class Operation> \
826  bool forall_node(Operation && operation = Operation()) const \
827  { \
828  return const_cast<Name<Node,Arc>*>(this)-> \
829  all_node<Operation>(operation); \
830  } \
831  \
832  template <class Operation> \
833  bool forall_node(Operation && operation = Operation()) \
834  { \
835  return all_node<Operation>(operation); \
836  } \
837  \
838  template <typename T = Node_Type, \
839  template <typename> class Container = DynList> \
840  Container<T> map_nodes(std::function<T(Node *)> operation) \
841  { \
842  Container<T> ret_val; \
843  this->for_each_node([&ret_val, &operation] (Node * p) \
844  { \
845  ret_val.append(operation(p)); \
846  }); \
847  return ret_val; \
848  } \
849  \
850  template <typename T> \
851  T foldl_nodes(const T & init, std::function<T(const T&, Node*)> operation) \
852  { \
853  T ret_val = init; \
854  this->for_each_node(/* Lambda */ [&ret_val, &operation] (Node * p) \
855  { \
856  ret_val = operation(ret_val, p); \
857  }); \
858  return ret_val; \
859  } \
860  \
861  template <class Operation> \
862  void for_each_arc(Operation & operation) const \
863  { \
864  for (Arc_Iterator it(*const_cast<Name<Node,Arc>*>(this)); \
865  it.has_curr(); it.next()) \
866  operation(it.get_curr()); \
867  } \
868  \
869  template <class Operation> \
870  void for_each_arc(Operation & operation) \
871  { \
872  for (Arc_Iterator it(*this); it.has_curr(); it.next()) \
873  operation(it.get_curr()); \
874  } \
875  \
876  template <class Operation> \
877  void for_each_arc(Operation && operation = Operation()) const \
878  { \
879  const_cast<Name<Node,Arc>*>(this)-> \
880  for_each_arc<Operation>(operation); \
881  } \
882  \
883  template <class Operation> \
884  void for_each_arc(Operation && operation = Operation()) \
885  { \
886  for_each_arc<Operation>(operation); \
887  } \
888  \
889  template <class Operation> \
890  bool all_arc(Operation & operation) const \
891  { \
892  for (Arc_Iterator it(*const_cast<Name<Node,Arc>*>(this)); \
893  it.has_curr(); it.next()) \
894  if (not operation(it.get_curr())) \
895  return false; \
896  return true; \
897  } \
898  \
899  template <class Operation> \
900  bool all_arc(Operation & operation) \
901  { \
902  for (Arc_Iterator it(*this); it.has_curr(); it.next()) \
903  if (not operation(it.get_curr())) \
904  return false; \
905  return true; \
906  } \
907  \
908  template <class Operation> \
909  bool all_arc(Operation && operation = Operation()) const \
910  { \
911  return const_cast<Name<Node,Arc>*>(this)-> \
912  all_arc<Operation>(operation); \
913  } \
914  \
915  template <class Operation> \
916  bool all_arc(Operation && operation = Operation()) \
917  { \
918  return all_arc<Operation>(operation); \
919  } \
920  \
921  template <class Operation> \
922  bool forall_arc(Operation & operation) const \
923  { \
924  return const_cast<Name<Node,Arc>*>(this)-> \
925  all_arc<Operation>(operation); \
926  } \
927  \
928  template <class Operation> \
929  bool forall_arc(Operation & operation) \
930  { \
931  return all_arc<Operation>(operation); \
932  } \
933  \
934  template <class Operation> \
935  bool forall_arc(Operation && operation = Operation()) const \
936  { \
937  return const_cast<Name<Node,Arc>*>(this)-> \
938  all_arc<Operation>(operation); \
939  } \
940  \
941  template <class Operation> \
942  bool forall_arc(Operation && operation = Operation()) \
943  { \
944  return all_arc<Operation>(operation); \
945  } \
946  \
947  template <typename T = Arc_Type, \
948  template <typename> class Container = DynList> \
949  Container<T> map_arcs(std::function<T(Arc *)> operation) \
950  { \
951  Container<T> ret_val; \
952  this->for_each_arc([&ret_val, &operation] (Arc * p) \
953  { \
954  ret_val.append(operation(p)); \
955  }); \
956  return ret_val; \
957  } \
958  \
959  template <typename T> \
960  T foldl_arcs(const T & init, std::function<T(const T&, Arc*)> operation) \
961  { \
962  T ret_val = init; \
963  this->for_each_arc([&ret_val, &operation] (Arc * p) \
964  { \
965  ret_val = operation(ret_val, p); \
966  }); \
967  return ret_val; \
968  } \
969  \
970  template <class Operation> \
971  void for_each_arc(Node * p, Operation & operation) const \
972  { \
973  for (Node_Arc_Iterator it(p); it.has_curr(); it.next()) \
974  operation(it.get_curr()); \
975  } \
976  \
977  template <class Operation> \
978  void for_each_arc(Node * p, Operation & operation) \
979  { \
980  for (Node_Arc_Iterator it(p); it.has_curr(); it.next()) \
981  operation(it.get_curr()); \
982  } \
983  \
984  template <class Operation> \
985  void for_each_arc(Node * p, Operation && operation = Operation()) const \
986  { \
987  for_each_arc<Operation>(p, operation); \
988  } \
989  \
990  template <class Operation> \
991  void for_each_arc(Node * p, Operation && operation = Operation()) \
992  { \
993  for_each_arc<Operation>(p, operation); \
994  } \
995  \
996  template <class Operation> \
997  bool all_arc(Node * p, Operation & operation) const \
998  { \
999  for (Node_Arc_Iterator it(p); it.has_curr(); it.next()) \
1000  if (not operation(it.get_curr())) \
1001  return false; \
1002  return true; \
1003  } \
1004  \
1005  template <class Operation> \
1006  bool all_arc(Node * p, Operation & operation) \
1007  { \
1008  for (Node_Arc_Iterator it(p); it.has_curr(); it.next()) \
1009  if (not operation(it.get_curr())) \
1010  return false; \
1011  return true; \
1012  } \
1013  \
1014  template <class Operation> \
1015  bool all_arc(Node * p, Operation && operation = Operation()) const \
1016  { \
1017  return all_arc<Operation>(p, operation); \
1018  } \
1019  \
1020  template <class Operation> \
1021  bool all_arc(Node * p, Operation && operation = Operation()) \
1022  { \
1023  return all_arc<Operation>(p, operation); \
1024  } \
1025  \
1026  template <class Operation> \
1027  bool forall_arc(Node * p, Operation & operation) const \
1028  { \
1029  return all_arc(p, operation); \
1030  } \
1031  \
1032  template <class Operation> \
1033  bool forall_arc(Node * p, Operation & operation) \
1034  { \
1035  return all_arc(p, operation); \
1036  } \
1037  \
1038  template <class Operation> \
1039  bool forall_arc(Node * p, Operation && operation = Operation()) const \
1040  { \
1041  return all_arc(p, operation); \
1042  } \
1043  \
1044  template <class Operation> \
1045  bool forall_arc(Node * p, Operation && operation = Operation()) \
1046  { \
1047  return all_arc<Operation>(p, operation); \
1048  } \
1049  \
1050  template <typename T = Arc_Type, \
1051  template <typename> class Container = Aleph::DynList> \
1052  Container<T> map_arcs(Node * p, std::function<T(Arc *)> operation) \
1053  { \
1054  Container<T> ret_val; \
1055  this->for_each_arc(p, [&ret_val, &operation] (Arc * a) \
1056  { \
1057  ret_val.append(operation(a)); \
1058  }); \
1059  return ret_val; \
1060  } \
1061  \
1062  template <typename T> \
1063  T foldl_arcs(Node * p, const T & init, \
1064  std::function<T(const T&, Arc*)> operation) \
1065  { \
1066  T ret_val = init; \
1067  this->for_each_arc(p, [&ret_val, &operation] (Arc * a) \
1068  { \
1069  ret_val = operation(ret_val, a); \
1070  }); \
1071  return ret_val; \
1072  } \
1073  \
1074  template <template <typename> class Container = Aleph::DynList> \
1075  Container<Node*> filter_nodes(std::function<bool(Node*)> operation) \
1076  { \
1077  Container<Node*> ret_val; \
1078  this->for_each_node([&ret_val, &operation] (Node * p) \
1079  { \
1080  if (operation(p)) \
1081  ret_val.append(p); \
1082  }); \
1083  return ret_val; \
1084  } \
1085  \
1086  template <template <typename> class Container = Aleph::DynList> \
1087  Container<Arc*> filter_arcs(std::function<bool(Arc*)> operation) \
1088  { \
1089  Container<Arc*> ret_val; \
1090  this->for_each_arc([&ret_val, &operation] (Arc * a) \
1091  { \
1092  if (operation(a)) \
1093  ret_val.append(a); \
1094  }); \
1095  return ret_val; \
1096  } \
1097  \
1098  template <template <typename> class Container = Aleph::DynList> \
1099  Container<Arc*> filter_arcs(Node * p, std::function<bool(Arc*)> operation) \
1100  { \
1101  Container<Arc*> ret_val; \
1102  this->for_each_node(p, [&ret_val, &operation] (Arc * a) \
1103  { \
1104  if (operation(a)) \
1105  ret_val.append(a); \
1106  }); \
1107  return ret_val; \
1108  } \
1109  \
1110  template <class Operation> \
1111  bool exists_node(Operation & operation) const \
1112  { \
1113  return this->traverse_nodes([&operation] (Node * p) \
1114  { \
1115  return not operation(p); \
1116  }); \
1117  } \
1118  \
1119  template <class Operation> \
1120  bool exists_node(Operation & operation) \
1121  { \
1122  return this->traverse_nodes([&operation] (Node * p) \
1123  { \
1124  return not operation(p); \
1125  }); \
1126  } \
1127  \
1128  template <class Operation> \
1129  bool exists_node(Operation && operation = Operation()) const \
1130  { \
1131  return exists_node(operation); \
1132  } \
1133  \
1134  template <class Operation> \
1135  bool exists_node(Operation && operation = Operation()) \
1136  { \
1137  return exists_node(operation); \
1138  } \
1139  \
1140  template <class Operation> \
1141  bool exists_arc(Operation & operation) const \
1142  { \
1143  return this->traverse_arcs([&operation] (Arc * a) \
1144  { \
1145  return not operation(a); \
1146  }); \
1147  } \
1148  \
1149  template <class Operation> \
1150  bool exists_arc(Operation & operation) \
1151  { \
1152  return this->traverse_arcs([&operation] (Arc * a) \
1153  { \
1154  return not operation(a); \
1155  }); \
1156  } \
1157  \
1158  template <class Operation> \
1159  bool exists_arc(Operation && operation = Operation()) const \
1160  { \
1161  return exists_arc(operation); \
1162  } \
1163  \
1164  template <class Operation> \
1165  bool exists_arc(Operation && operation = Operation()) \
1166  { \
1167  return exists_arc(operation); \
1168  } \
1169  \
1170  template <class Operation> \
1171  bool exists_arc(Node * p, Operation & operation) const \
1172  { \
1173  return this->traverse_arcs(p, [&operation] (Arc * a) \
1174  { \
1175  return not operation(a); \
1176  }); \
1177  } \
1178  \
1179  template <class Operation> \
1180  bool exists_arc(Node * p, Operation & operation) \
1181  { \
1182  return this->traverse_arcs(p, [&operation] (Arc * a) \
1183  { \
1184  return not operation(a); \
1185  }); \
1186  } \
1187  \
1188  template <class Operation> \
1189  bool exists_arc(Node * p, Operation && operation = Operation()) const \
1190  { \
1191  return exists_arc(p, operation); \
1192  } \
1193  \
1194  template <class Operation> \
1195  bool exists_arc(Node * p, Operation && operation = Operation()) \
1196  { \
1197  return exists_arc(p, operation); \
1198  } \
1199  \
1200  template <template <typename> class Container = Aleph::DynList> \
1201  Container<Node*> nodes() \
1202  { \
1203  Container<Node*> ret_val; \
1204  this->for_each_node([&ret_val] (Node * p) \
1205  { \
1206  ret_val.append(p); \
1207  }); \
1208  return ret_val; \
1209  } \
1210  \
1211  template <template <typename> class Container = Aleph::DynList> \
1212  Container<Arc*> arcs() \
1213  { \
1214  Container<Arc*> ret_val; \
1215  this->for_each_arc([&ret_val] (Arc * a) \
1216  { \
1217  ret_val.append(a); \
1218  }); \
1219  return ret_val; \
1220  } \
1221  \
1222  template <template <typename> class Container = Aleph::DynList> \
1223  Container<Arc*> arcs(Node * p) \
1224  { \
1225  Container<Arc*> ret_val; \
1226  this->for_each_arc(p, [&ret_val] (Arc * a) \
1227  { \
1228  ret_val.append(a); \
1229  }); \
1230  return ret_val; \
1231  } \
1232  \
1233  template <template <typename> class Container = Aleph::DynList> \
1234  Container<Node*> nodes() const \
1235  { \
1236  Container<Node*> ret_val; \
1237  this->for_each_node([&ret_val] (Node * p) \
1238  { \
1239  ret_val.append(p); \
1240  }); \
1241  return ret_val; \
1242  } \
1243  \
1244  template <template <typename> class Container = Aleph::DynList> \
1245  Container<Arc*> arcs() const \
1246  { \
1247  Container<Arc*> ret_val; \
1248  this->for_each_arc([&ret_val] (Arc * a) \
1249  { \
1250  ret_val.append(a); \
1251  }); \
1252  return ret_val; \
1253  } \
1254  \
1255  template <template <typename> class Container = Aleph::DynList> \
1256  Container<Arc*> arcs(Node * p) const \
1257  { \
1258  Container<Arc*> ret_val; \
1259  this->for_each_arc(p, [&ret_val] (Arc * a) \
1260  { \
1261  ret_val.append(a); \
1262  }); \
1263  return ret_val; \
1264  } \
1265 
1266 
1347 } // end namespace Aleph
1348 
1349 # endif
Aleph::Bit_Fields::Bit_Fields
Bit_Fields()
pertenece a un camino mínimo
Definition: aleph-graph.H:69
Aleph::Bit_Fields::is_acyclique
unsigned int is_acyclique
Bit de verificación de ciclo.
Definition: aleph-graph.H:54
Aleph::Bit_Fields::min
unsigned int min
nodo o arco de corte
Definition: aleph-graph.H:66
Aleph::Bit_Fields::get_bit
bool get_bit(const int &bit) const
Definition: aleph-graph.H:86
Aleph::Bit_Fields::breadth_first
unsigned int breadth_first
Bit de búsqueda en profundidad.
Definition: aleph-graph.H:52
Aleph::Graph_Attr
Definition: aleph-graph.H:177
Aleph::Bit_Fields::convert_tree
unsigned int convert_tree
Bit de subgrafo.
Definition: aleph-graph.H:64
Aleph::Bit_Fields::cut
unsigned int cut
Conversión a Tree_Node.
Definition: aleph-graph.H:65
Aleph::Bit_Fields::kruskal
unsigned int kruskal
Bit de búsqueda de camino.
Definition: aleph-graph.H:57
Aleph::Bit_Fields::test_path
unsigned int test_path
Bit de prueba de aciclicidad.
Definition: aleph-graph.H:55
Aleph::Bit_Fields::test_cycle
unsigned int test_cycle
Bit de búsqueda en amplitud.
Definition: aleph-graph.H:53
Aleph::Bit_Fields::find_path
unsigned int find_path
Bit de prueba de existencia de camino.
Definition: aleph-graph.H:56
Aleph::Bit_Fields::set_bit
void set_bit(const int &bit, const int &value)
Definition: aleph-graph.H:124
Aleph::Bit_Fields::prim
unsigned int prim
Bit de algoritmo de Kruskal.
Definition: aleph-graph.H:58
Aleph::Bit_Fields::build_subtree
unsigned int build_subtree
Bit de árbol abarcador.
Definition: aleph-graph.H:63
Aleph::Bit_Fields::spanning_tree
unsigned int spanning_tree
Bit para flujos máximos.
Definition: aleph-graph.H:62
Aleph::Bit_Fields::reset
void reset()
Reinicia todos los bits a cero.
Definition: aleph-graph.H:155
Aleph::Graph_Attr::counter
long counter
bits de control del arco
Definition: aleph-graph.H:180
Aleph::Bit_Fields::maximum_flow
unsigned int maximum_flow
Bit de camino euleriano.
Definition: aleph-graph.H:61
Aleph::Bit_Fields::euler
unsigned int euler
Bit de algoritmo de Dijkstra.
Definition: aleph-graph.H:60
Aleph::Bit_Fields
Definition: aleph-graph.H:47
Aleph::Bit_Fields::reset
void reset(const int &bit)
Reinicia bit a cero.
Definition: aleph-graph.H:152
Aleph::Bit_Fields::dijkstra
unsigned int dijkstra
Bit de algoritmo de Prim.
Definition: aleph-graph.H:59
Leandro Rabindranath León