Aleph-w  1.9
General library for algorithms and data structures
graph-traverse.H
1 
2 /* Aleph-w
3 
4  / \ | | ___ _ __ | |__ __ __
5  / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
6  / ___ \| | __/ |_) | | | |_____\ V V / version 1.9b
7  /_/ \_\_|\___| .__/|_| |_| \_/\_/ https://github.com/lrleon/Aleph-w
8  |_|
9 
10  This file is part of Aleph-w library
11 
12  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica
13 
14  This program is free software: you can redistribute it and/or modify
15  it under the terms of the GNU General Public License as published by
16  the Free Software Foundation, either version 3 of the License, or
17  (at your option) any later version.
18 
19  This program is distributed in the hope that it will be useful, but
20  WITHOUT ANY WARRANTY; without even the implied warranty of
21  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22  General Public License for more details.
23 
24  You should have received a copy of the GNU General Public License
25  along with this program. If not, see <https://www.gnu.org/licenses/>.
26 */
27 # ifndef GRAPH_TRAVERSE_H
28 # define GRAPH_TRAVERSE_H
29 
30 # include <tpl_agraph.H>
31 # include <tpl_dynListStack.H>
32 # include <tpl_dynListQueue.H>
33 
39 template <class GT, class Itor,
40  template <typename T> class Q = DynListStack,
41  class Show_Arc = Dft_Show_Arc<GT>>
42 class Graph_Traverse
43 {
44  GT & g;
45  Show_Arc & sa;
46 
47 public:
48 
49  Graph_Traverse(GT & __g, Show_Arc & __sa) : g(__g), sa(__sa) {}
50 
51  Graph_Traverse(GT & __g, Show_Arc && __sa = Show_Arc()) : g(__g), sa(__sa) {}
52 
53  template <class Node_Op>
54  size_t operator () (typename GT::Node * start, Node_Op & op)
55  {
56  g.reset_nodes();
57  g.reset_arcs();
58 
59  size_t count = 1;
60  start->set_state(Processed);
61  if (not op(start))
62  return count;
63 
64  Q<typename GT::Arc*> q;
65  for (Itor it(start, sa); it.has_curr(); it.next_ne())
66  {
67  typename GT::Arc * a = it.get_curr_ne();
68  typename GT::Node * tgt = g.get_connected_node(a, start);
69  a->set_state(Processing);
70  tgt->set_state(Processing);
71  q.put(a);
72  }
73 
74  const size_t & n = g.vsize();
75  while (not q.is_empty() and count < n)
76  {
77  typename GT::Arc * arc = q.get();
78  assert(arc->state() == Processing);
79  arc->set_state(Processed);
80 
81  typename GT::Node * s = g.get_src_node(arc);
82  typename GT::Node * t = g.get_tgt_node(arc);
83  if (s->state() == Processed and t->state() == Processed)
84  continue;
85 
86  typename GT::Node * curr = s->state() == Processed ? t : s;
87  assert(curr->state() == Processing);
88  ++count;
89  curr->set_state(Processed);
90  if (not op(curr))
91  return count;
92 
93  for (Itor it(curr, sa); it.has_curr(); it.next_ne())
94  {
95  typename GT::Arc * a = it.get_curr_ne();
96  if (a->state() != Unprocessed)
97  continue;
98  typename GT::Node * tgt = g.get_connected_node(a, curr);
99  if (tgt->state() == Unprocessed)
100  {
101  assert(a->state() != Processing);
102  q.put(a);
103  a->set_state(Processing);
104  tgt->set_state(Processing);
105  }
106  else
107  a->set_state(Processed);
108  }
109  }
110 
111  return count;
112  }
113 
114  template <class Node_Op>
115  size_t operator () (typename GT::Node * start, Node_Op && op = Node_Op())
116  {
117  return (*this)(start, op);
118  }
119 
122  template <class Op>
123  size_t exec(typename GT::Node * start, Op & op)
124  {
125  g.reset_nodes();
126  g.reset_arcs();
127 
128  size_t count = 1;
129  start->set_state(Processed);
130  if (not op(start, nullptr))
131  return count;
132 
133  using Pair = tuple<typename GT::Node*, typename GT::Arc*>;
134  Q<Pair> q;
135  for (Itor it(start, sa); it.has_curr(); it.next_ne())
136  {
137  typename GT::Arc * a = it.get_curr_ne();
138  typename GT::Node * tgt = g.get_connected_node(a, start);
139  a->set_state(Processing);
140  tgt->set_state(Processing);
141  q.put(make_tuple(start, a));
142  }
143 
144  const size_t & n = g.vsize();
145  while (not q.is_empty() and count < n)
146  {
147  const Pair p = q.get();
148  typename GT::Arc * arc = get<1>(p);
149  assert(arc->state() == Processing);
150  assert(get<0>(p)->state() == Processed);
151  arc->set_state(Processed);
152 
153  typename GT::Node * curr = g.get_connected_node(arc, get<0>(p));
154  assert(curr->state() == Processing);
155  ++count;
156  curr->set_state(Processed);
157  if (not op(curr, arc))
158  return count;
159 
160  for (Itor it(curr, sa); it.has_curr(); it.next_ne())
161  {
162  typename GT::Arc * a = it.get_curr_ne();
163  if (a->state() != Unprocessed)
164  continue;
165  typename GT::Node * tgt = g.get_connected_node(a, curr);
166  if (tgt->state() == Unprocessed)
167  {
168  assert(a->state() != Processing);
169  a->set_state(Processing);
170  tgt->set_state(Processing);
171  q.put(make_tuple(curr, a));
172  }
173  else
174  a->set_state(Processed);
175  }
176  }
177 
178  return count;
179  }
180 
181  template <class Operation>
182  size_t exec(typename GT::Node * start, Operation && op = Operation())
183  {
184  return exec(start, op);
185  }
186 
187  template <class Node_Op, class Arc_Op>
188  tuple<size_t, size_t> operator () (typename GT::Node * start,
189  Node_Op & node_op, Arc_Op & arc_op)
190  {
191  g.reset_nodes();
192  g.reset_arcs();
193  Q<typename GT::Arc*> q;
194 
195  size_t node_count = 1;
196  size_t arc_count = 0;
197 
198  start->set_state(Processed);
199  if (not node_op(start))
200  return make_tuple(1, 0);
201 
202  for (Itor it(start, sa); it.has_curr(); it.next_ne())
203  {
204  typename GT::Arc * a = it.get_curr_ne();
205  typename GT::Node * tgt = g.get_connected_node(a, start);
206  a->set_state(Processing);
207  tgt->set_state(Processing);
208  q.put(a);
209  ++arc_count;
210  if (not arc_op(a))
211  return make_tuple(node_count, arc_count);
212  }
213 
214  while (not q.is_empty())
215  {
216  typename GT::Arc * arc = q.get();
217  assert(arc->state() == Processing);
218  arc->set_state(Processed);
219 
220  typename GT::Node * s = g.get_src_node(arc);
221  typename GT::Node * t = g.get_tgt_node(arc);
222  if (s->state() == Processed and t->state() == Processed)
223  continue;
224 
225  typename GT::Node * curr = s->state() == Processed ? t : s;
226  assert(curr->state() == Processing);
227  ++node_count;
228  curr->set_state(Processed);
229  if (not node_op(curr))
230  return make_tuple(node_count, arc_count);
231 
232  for (Itor it(curr, sa); it.has_curr(); it.next_ne())
233  {
234  typename GT::Arc * a = it.get_curr_ne();
235  if (a->state() != Unprocessed)
236  continue;
237  typename GT::Node * tgt = g.get_connected_node(a, curr);
238  if (tgt->state() != Processed)
239  {
240  q.put(a);
241  tgt->set_state(Processing);
242  a->set_state(Processing);
243  ++arc_count;
244  if (not arc_op(a))
245  return make_tuple(node_count, arc_count);
246  }
247  else
248  a->set_state(Processed);
249  }
250  }
251 
252  return make_tuple(node_count, arc_count);
253  }
254 
255  template <class Node_Op, class Arc_Op>
256  tuple<size_t, size_t> operator () (typename GT::Node * start,
257  Node_Op && node_op = Node_Op(),
258  Arc_Op && arc_op = Arc_Op())
259  {
260  return (*this)(start, node_op, arc_op);
261  }
262 };
263 
264 
265 template <class GT, class Itor,
266  class Show_Arc = Dft_Show_Arc<GT>>
267  using Graph_Traverse_DFS = Graph_Traverse<GT, Itor, DynListStack, Show_Arc>;
268 
269 template <class GT, class Itor,
270  class Show_Arc = Dft_Show_Arc<GT>>
271  using Graph_Traverse_BFS = Graph_Traverse<GT, Itor, DynListQueue, Show_Arc>;
272 
273 
274 # endif // GRAPH_TRAVERSE_H
Aleph::Processing
const unsigned char Processing
Graph_Traverse
Definition: graph-traverse.H:42
Aleph::Unprocessed
const unsigned char Unprocessed
Aleph::Processed
const unsigned char Processed
Aleph::Dft_Show_Arc
Definition: tpl_graph.H:1063
Aleph::DynListStack
DynList< T > DynListStack
Definition: tpl_dynListStack.H:46
Graph_Traverse::exec
size_t exec(typename GT::Node *start, Op &op)
Definition: graph-traverse.H:123
Leandro Rabindranath León