1 ////////////////////////////////////////////////////////////////////////////////
3 // Author: Andy Rushton
4 // Copyright: (c) Southampton University 1999-2004
5 // (c) Andy Rushton 2004-2009
8 // Note: I tried to write this using STL lists for the node and arc lists, but
9 // it got far too hairy. The specific problem is that I wanted a digraph
10 // iterator to contain a list::iterator so I needed to be able to generate a
11 // list::iterator from a node or arc and STL list iterators don't give you that
12 // functionality. I tried burgling the data structures, but that was
13 // non-portable between different STL implementations so needed lots of #ifdefs
14 // and so was mind-bogglingly awful and unreadable - in other words a
15 // maintenance nightmare. I gave up and impemented my own lists - not difficult.
17 // I use circular double-linked lists. The circular design means that both
18 // ends of the list are equally accessible in unit time. An empty list
19 // contains no objects. There is no end node in the list - unlike the STL
20 // lists which have a dummy node for end iterators to point to -
21 // conceptually the end iterator points one element beyond the end of the
22 // list. However, I implement the end iterator concept in the iterator
23 // itself, so do not need the dummy end node.
25 ////////////////////////////////////////////////////////////////////////////////
26 #include <algorithm>
27 #include <deque>
29 ////////////////////////////////////////////////////////////////////////////////
30 // Internals
32 namespace stlplus
33 {
35 template<typename NT, typename AT>
36 class digraph_node
37 {
38 public:
39 master_iterator<digraph<NT,AT>, digraph_node<NT,AT> > m_master;
40 NT m_data;
41 digraph_node<NT,AT>* m_prev;
42 digraph_node<NT,AT>* m_next;
43 std::vector<digraph_arc<NT,AT>*> m_inputs;
44 std::vector<digraph_arc<NT,AT>*> m_outputs;
45 public:
46 digraph_node(const digraph<NT,AT>* owner, const NT& d = NT()) :
47 m_master(owner,this), m_data(d), m_prev(0), m_next(0)
48 {
49 }
50 ~digraph_node(void)
51 {
52 }
53 };
55 template<typename NT, typename AT>
56 class digraph_arc
57 {
58 public:
59 master_iterator<digraph<NT,AT>, digraph_arc<NT,AT> > m_master;
60 AT m_data;
61 digraph_arc<NT,AT>* m_prev;
62 digraph_arc<NT,AT>* m_next;
63 digraph_node<NT,AT>* m_from;
64 digraph_node<NT,AT>* m_to;
65 digraph_arc(const digraph<NT,AT>* owner, digraph_node<NT,AT>* from = 0, digraph_node<NT,AT>* to = 0, const AT& d = AT()) :
66 m_master(owner,this), m_data(d), m_prev(0), m_next(0), m_from(from), m_to(to)
67 {
68 }
69 };
71 ////////////////////////////////////////////////////////////////////////////////
72 // Iterators
73 ////////////////////////////////////////////////////////////////////////////////
75 ////////////////////////////////////////////////////////////////////////////////
76 // Node iterator
78 // construct a null iterator
79 template<typename NT, typename AT, typename NRef, typename NPtr>
80 digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(void)
81 {
82 }
84 // valid iterator
85 template<typename NT, typename AT, typename NRef, typename NPtr>
86 digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(digraph_node<NT,AT>* node) :
87 safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(node->m_master)
88 {
89 }
91 // end iterator
92 template<typename NT, typename AT, typename NRef, typename NPtr>
93 digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const digraph<NT,AT>* owner) :
94 safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(owner)
95 {
96 }
98 // alias an iterator
99 template<typename NT, typename AT, typename NRef, typename NPtr>
100 digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator) :
101 safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(iterator)
102 {
103 }
105 // destructor
106 template<typename NT, typename AT, typename NRef, typename NPtr>
107 digraph_iterator<NT,AT,NRef,NPtr>::~digraph_iterator(void)
108 {
109 }
111 template<typename NT, typename AT, typename NRef, typename NPtr>
112 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_iterator<NT,AT,NRef,NPtr>::constify (void) const
113 {
114 return digraph_iterator<NT,AT,const NT&,const NT*>(*this);
115 }
117 template<typename NT, typename AT, typename NRef, typename NPtr>
118 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::iterator digraph_iterator<NT,AT,NRef,NPtr>::deconstify (void) const
119 {
120 return digraph_iterator<NT,AT,NT&,NT*>(*this);
121 }
123 template<typename NT, typename AT, typename NRef, typename NPtr>
124 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (void)
125 throw(null_dereference,end_dereference)
126 {
127 this->assert_valid();
128 if (this->node()->m_next)
129 this->set(this->node()->m_next->m_master);
130 else
131 this->set_end();
132 return *this;
133 }
135 template<typename NT, typename AT, typename NRef, typename NPtr>
136 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (int)
137 throw(null_dereference,end_dereference)
138 {
139 // post-increment is defined in terms of the pre-increment
140 digraph_iterator<NT,AT,NRef,NPtr> result(*this);
141 ++(*this);
142 return result;
143 }
145 template<typename NT, typename AT, typename NRef, typename NPtr>
146 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator -- (void)
147 throw(null_dereference,end_dereference)
148 {
149 this->assert_valid();
150 if (this->node()->m_prev)
151 this->set(this->node()->m_prev->m_master);
152 else
153 this->set_end();
154 return *this;
155 }
157 template<typename NT, typename AT, typename NRef, typename NPtr>
158 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator -- (int)
159 throw(null_dereference,end_dereference)
160 {
161 // post-decrement is defined in terms of the pre-decrement
162 digraph_iterator<NT,AT,NRef,NPtr> result(*this);
163 --(*this);
164 return result;
165 }
167 template<typename NT, typename AT, typename NRef, typename NPtr>
168 bool digraph_iterator<NT,AT,NRef,NPtr>::operator == (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
169 {
170 return equal(r);
171 }
173 template<typename NT, typename AT, typename NRef, typename NPtr>
174 bool digraph_iterator<NT,AT,NRef,NPtr>::operator != (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
175 {
176 return !operator==(r);
177 }
179 template<typename NT, typename AT, typename NRef, typename NPtr>
180 bool digraph_iterator<NT,AT,NRef,NPtr>::operator < (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
181 {
182 return compare(r) < 0;
183 }
185 template<typename NT, typename AT, typename NRef, typename NPtr>
186 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::reference digraph_iterator<NT,AT,NRef,NPtr>::operator*(void) const
187 throw(null_dereference,end_dereference)
188 {
189 this->assert_valid();
190 return this->node()->m_data;
191 }
193 template<typename NT, typename AT, typename NRef, typename NPtr>
194 TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::pointer digraph_iterator<NT,AT,NRef,NPtr>::operator->(void) const
195 throw(null_dereference,end_dereference)
196 {
197 return &(operator*());
198 }
200 ////////////////////////////////////////////////////////////////////////////////
201 // Arc Iterator
203 template<typename NT, typename AT, typename ARef, typename APtr>
204 digraph_arc_iterator<NT,AT,ARef,APtr>::digraph_arc_iterator(void)
205 {
206 }
208 // valid iterator
209 template<typename NT, typename AT, typename NRef, typename NPtr>
210 digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(digraph_arc<NT,AT>* arc) :
211 safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(arc->m_master)
212 {
213 }
215 // end iterator
216 template<typename NT, typename AT, typename NRef, typename NPtr>
217 digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const digraph<NT,AT>* owner) :
218 safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(owner)
219 {
220 }
222 // alias an iterator
223 template<typename NT, typename AT, typename NRef, typename NPtr>
224 digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator) :
225 safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(iterator)
226 {
227 }
229 template<typename NT, typename AT, typename ARef, typename APtr>
230 digraph_arc_iterator<NT,AT,ARef,APtr>::~digraph_arc_iterator(void)
231 {
232 }
234 template<typename NT, typename AT, typename NRef, typename NPtr>
235 TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::constify (void) const
236 {
237 return digraph_arc_iterator<NT,AT,const AT&,const AT*>(*this);
238 }
240 template<typename NT, typename AT, typename NRef, typename NPtr>
241 TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::deconstify (void) const
242 {
243 return digraph_arc_iterator<NT,AT,AT&,AT*>(*this);
244 }
246 template<typename NT, typename AT, typename ARef, typename APtr>
247 TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (void)
248 throw(null_dereference,end_dereference)
249 {
250 this->assert_valid();
251 if (this->node()->m_next)
252 this->set(this->node()->m_next->m_master);
253 else
254 this->set_end();
255 return *this;
256 }
258 template<typename NT, typename AT, typename ARef, typename APtr>
259 TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (int)
260 throw(null_dereference,end_dereference)
261 {
262 // post-increment is defined in terms of the pre-increment
263 digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);
264 ++(*this);
265 return result;
266 }
268 template<typename NT, typename AT, typename ARef, typename APtr>
269 TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (void)
270 throw(null_dereference,end_dereference)
271 {
272 this->assert_valid();
273 if (this->node()->m_prev)
274 this->set(this->node()->m_prev->m_master);
275 else
276 this->set_end();
277 return *this;
278 }
280 template<typename NT, typename AT, typename ARef, typename APtr>
281 TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (int)
282 throw(null_dereference,end_dereference)
283 {
284 // post-decrement is defined in terms of the pre-decrement
285 digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);
286 --(*this);
287 return result;
288 }
290 template<typename NT, typename AT, typename ARef, typename APtr>
291 bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator == (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
292 {
293 return equal(r);
294 }
296 template<typename NT, typename AT, typename ARef, typename APtr>
297 bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator != (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
298 {
299 return !operator==(r);
300 }
302 template<typename NT, typename AT, typename ARef, typename APtr>
303 bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator < (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
304 {
305 return compare(r) < 0;
306 }
308 template<typename NT, typename AT, typename ARef, typename APtr>
309 TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::reference digraph_arc_iterator<NT,AT,ARef,APtr>::operator*(void) const
310 throw(null_dereference,end_dereference)
311 {
312 this->assert_valid();
313 return this->node()->m_data;
314 }
316 template<typename NT, typename AT, typename ARef, typename APtr>
317 TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::pointer digraph_arc_iterator<NT,AT,ARef,APtr>::operator->(void) const
318 throw(null_dereference,end_dereference)
319 {
320 return &(operator*());
321 }
323 ////////////////////////////////////////////////////////////////////////////////
324 // subtype utilities
326 template<typename NT, typename AT>
327 TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::constify_arcs(const TYPENAME digraph<NT,AT>::arc_vector& arcs) const
328 throw(wrong_object,null_dereference,end_dereference)
329 {
330 std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;
331 for (unsigned i = 0; i < arcs.size(); i++)
332 {
333 arcs[i].assert_valid(this);
334 result.push_back(arcs[i].constify());
335 }
336 return result;
337 }
339 template<typename NT, typename AT>
340 TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::deconstify_arcs(const TYPENAME digraph<NT,AT>::const_arc_vector& arcs) const
341 throw(wrong_object,null_dereference,end_dereference)
342 {
343 std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
344 for (unsigned i = 0; i < arcs.size(); i++)
345 {
346 arcs[i].assert_valid(this);
347 result.push_back(arcs[i].deconstify());
348 }
349 return result;
350 }
352 template<typename NT, typename AT>
353 TYPENAME digraph<NT,AT>::const_path_vector digraph<NT,AT>::constify_paths(const TYPENAME digraph<NT,AT>::path_vector& paths) const
354 throw(wrong_object,null_dereference,end_dereference)
355 {
356 std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
357 for (unsigned i = 0; i < paths.size(); i++)
358 result.push_back(constify_arcs(paths[i]));
359 return result;
360 }
362 template<typename NT, typename AT>
363 TYPENAME digraph<NT,AT>::path_vector digraph<NT,AT>::deconstify_paths(const TYPENAME digraph<NT,AT>::const_path_vector& paths) const
364 throw(wrong_object,null_dereference,end_dereference)
365 {
366 std::vector<std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result;
367 for (unsigned i = 0; i < paths.size(); i++)
368 result.push_back(deconstify_arcs(paths[i]));
369 return result;
370 }
372 template<typename NT, typename AT>
373 TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::constify_nodes(const TYPENAME digraph<NT,AT>::node_vector& nodes) const
374 throw(wrong_object,null_dereference,end_dereference)
375 {
376 std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
377 for (unsigned i = 0; i < nodes.size(); i++)
378 {
379 nodes[i].assert_valid(this);
380 result.push_back(nodes[i].constify());
381 }
382 return result;
383 }
385 template<typename NT, typename AT>
386 TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::deconstify_nodes(const TYPENAME digraph<NT,AT>::const_node_vector& nodes) const
387 throw(wrong_object,null_dereference,end_dereference)
388 {
389 std::vector<digraph_iterator<NT,AT,NT&,NT*> > result;
390 for (unsigned i = 0; i < nodes.size(); i++)
391 {
392 nodes[i].assert_valid(this);
393 result.push_back(nodes[i].deconstify());
394 }
395 return result;
396 }
398 template<typename NT, typename AT>
399 unsigned digraph<NT,AT>::npos(void)
400 {
401 return(unsigned)-1;
402 }
404 ////////////////////////////////////////////////////////////////////////////////
405 // Constructors etc.
407 template<typename NT, typename AT>
408 digraph<NT,AT>::digraph(void) :
409 m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)
410 {
411 // node and arc lists are circular double-linked lists
412 // they start out empty (no dummy end node)
413 }
415 template<typename NT, typename AT>
416 digraph<NT,AT>::~digraph(void)
417 {
418 clear();
419 }
421 template<typename NT, typename AT>
422 digraph<NT,AT>::digraph(const digraph<NT,AT>& r) :
423 m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)
424 {
425 *this = r;
426 }
428 template<typename NT, typename AT>
429 digraph<NT,AT>& digraph<NT,AT>::operator=(const digraph<NT,AT>& r)
430 {
431 // make it self-copy safe i.e. a=a; is a valid instruction
432 if (this == &r) return *this;
433 clear();
434 // first phase is to copy the nodes, creating a map of cross references from the old nodes to their new equivalents
435 std::map<digraph_iterator<NT,AT,const NT&,const NT*>, digraph_iterator<NT,AT,NT&,NT*> > xref;
436 for (digraph_iterator<NT,AT,const NT&,const NT*> n = r.begin(); n != r.end(); n++)
437 xref[n] = insert(*n);
438 // second phase is to copy the arcs, using the map to convert the old to and from nodes to the new nodes
439 for (digraph_arc_iterator<NT,AT, const AT&,const AT*> a = r.arc_begin(); a != r.arc_end(); a++)
440 arc_insert(xref[r.arc_from(a)],xref[r.arc_to(a)],*a);
441 return *this;
442 }
444 ////////////////////////////////////////////////////////////////////////////////
445 // Basic Node functions
447 template<typename NT, typename AT>
448 bool digraph<NT,AT>::empty(void) const
449 {
450 return m_nodes_begin == 0;
451 }
453 template<typename NT, typename AT>
454 unsigned digraph<NT,AT>::size(void) const
455 {
456 unsigned count = 0;
457 for (digraph_iterator<NT,AT,const NT&,const NT*> i = begin(); i != end(); i++)
458 count++;
459 return count;
460 }
462 template<typename NT, typename AT>
463 TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::insert(const NT& node_data)
464 {
465 digraph_node<NT,AT>* new_node = new digraph_node<NT,AT>(this,node_data);
466 if (!m_nodes_end)
467 {
468 // insert into an empty list
469 m_nodes_begin = new_node;
470 m_nodes_end = new_node;
471 }
472 else
473 {
474 // insert at the end of the list
475 new_node->m_prev = m_nodes_end;
476 m_nodes_end->m_next = new_node;
477 m_nodes_end = new_node;
478 }
479 return digraph_iterator<NT,AT,NT&,NT*>(new_node);
480 }
482 template<typename NT, typename AT>
483 TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::erase(TYPENAME digraph<NT,AT>::iterator iter)
484 throw(wrong_object,null_dereference,end_dereference)
485 {
486 iter.assert_valid(this);
487 // remove all arcs connected to this node first
488 // use arc_erase rather than arcs.erase because that tidies up the node at the other end of the arc too
489 for (unsigned i = fanin(iter); i--; )
490 arc_erase(input(iter,i));
491 for (unsigned j = fanout(iter); j--; )
492 arc_erase(output(iter,j));
493 // now unlink the node from the list and delete it
494 if (iter.node()->m_next)
495 iter.node()->m_next->m_prev = iter.node()->m_prev;
496 if (iter.node()->m_prev)
497 iter.node()->m_prev->m_next = iter.node()->m_next;
498 digraph_node<NT,AT>* next = iter.node()->m_next;
499 delete iter.node();
500 // return the next node in the list
501 if (next)
502 return digraph_iterator<NT,AT,NT&,NT*>(next);
503 else
504 return digraph_iterator<NT,AT,NT&,NT*>(this);
505 }
507 template<typename NT, typename AT>
508 void digraph<NT,AT>::clear(void)
509 {
510 // clearing the nodes also clears the arcs
511 for (digraph_iterator<NT,AT,NT&,NT*> i = begin(); i != end(); )
512 i = erase(i);
513 }
515 template<typename NT, typename AT>
516 TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::begin(void) const
517 {
518 if (m_nodes_begin)
519 return digraph_iterator<NT,AT,const NT&,const NT*>(m_nodes_begin);
520 else
521 return digraph_iterator<NT,AT,const NT&,const NT*>(this);
522 }
524 template<typename NT, typename AT>
525 TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::begin(void)
526 {
527 if (m_nodes_begin)
528 return digraph_iterator<NT,AT,NT&,NT*>(m_nodes_begin);
529 else
530 return digraph_iterator<NT,AT,NT&,NT*>(this);
531 }
533 template<typename NT, typename AT>
534 TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::end(void) const
535 {
536 return digraph_iterator<NT,AT,const NT&,const NT*>(this);
537 }
539 template<typename NT, typename AT>
540 TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::end(void)
541 {
542 return digraph_iterator<NT,AT,NT&,NT*>(this);
543 }
545 template<typename NT, typename AT>
546 unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::const_iterator iter) const
547 throw(wrong_object,null_dereference,end_dereference)
548 {
549 iter.assert_valid(this);
550 return iter.node()->m_inputs.size();
551 }
553 template<typename NT, typename AT>
554 unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::iterator iter)
555 throw(wrong_object,null_dereference,end_dereference)
556 {
557 iter.assert_valid(this);
558 return iter.node()->m_inputs.size();
559 }
561 template<typename NT, typename AT>
562 TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const
563 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
564 {
565 iter.assert_valid(this);
566 if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");
567 return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_inputs[i]);
568 }
570 template<typename NT, typename AT>
571 TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)
572 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
573 {
574 iter.assert_valid(this);
575 if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");
576 return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_inputs[i]);
577 }
579 template<typename NT, typename AT>
580 unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::const_iterator iter) const
581 throw(wrong_object,null_dereference,end_dereference)
582 {
583 iter.assert_valid(this);
584 return iter.node()->m_outputs.size();
585 }
587 template<typename NT, typename AT>
588 unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::iterator iter)
589 throw(wrong_object,null_dereference,end_dereference)
590 {
591 iter.assert_valid(this);
592 return iter.node()->m_outputs.size();
593 }
595 template<typename NT, typename AT>
596 TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const
597 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
598 {
599 iter.assert_valid(this);
600 if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");
601 return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_outputs[i]);
602 }
604 template<typename NT, typename AT>
605 TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)
606 throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
607 {
608 iter.assert_valid(this);
609 if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");
610 return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_outputs[i]);
611 }
613 template<typename NT, typename AT>
614 TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::const_iterator node) const
615 throw(wrong_object,null_dereference,end_dereference)
616 {
617 node.assert_valid(this);
618 std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;
619 for (unsigned i = 0; i < fanin(node); i++)
620 result.push_back(input(node,i));
621 return result;
622 }
624 template<typename NT, typename AT>
625 TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::iterator node)
626 throw(wrong_object,null_dereference,end_dereference)
627 {
628 node.assert_valid(this);
629 std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
630 for (unsigned i = 0; i < fanin(node); i++)
631 result.push_back(input(node,i));
632 return result;
633 }
635 template<typename NT, typename AT>
636 TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::const_iterator node) const
637 throw(wrong_object,null_dereference,end_dereference)
638 {
639 node.assert_valid(this);
640 std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;
641 for (unsigned i = 0; i < fanout(node); i++)
642 result.push_back(output(node,i));
643 return result;
644 }
646 template<typename NT, typename AT>
647 TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::iterator node)
648 throw(wrong_object,null_dereference,end_dereference)
649 {
650 node.assert_valid(this);
651 std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
652 for (unsigned i = 0; i < fanout(node); i++)
653 result.push_back(output(node,i));
654 return result;
655 }
657 template<typename NT, typename AT>
658 unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::const_iterator from,
659 TYPENAME digraph<NT,AT>::const_arc_iterator arc) const
660 throw(wrong_object,null_dereference,end_dereference)
661 {
662 from.assert_valid(this);
663 arc.assert_valid(this);
664 for (unsigned i = 0; i < fanout(from); i++)
665 {
666 if (output(from,i) == arc)
667 return i;
668 }
669 return digraph<NT,AT>::npos();
670 }
672 template<typename NT, typename AT>
673 unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::iterator from,
674 TYPENAME digraph<NT,AT>::arc_iterator arc)
675 throw(wrong_object,null_dereference,end_dereference)
676 {
677 from.assert_valid(this);
678 arc.assert_valid(this);
679 for (unsigned i = 0; i < fanout(from); i++)
680 {
681 if (output(from,i) == arc)
682 return i;
683 }
684 return digraph<NT,AT>::npos();
685 }
687 template<typename NT, typename AT>
688 unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::const_iterator to,
689 TYPENAME digraph<NT,AT>::const_arc_iterator arc) const
690 throw(wrong_object,null_dereference,end_dereference)
691 {
692 to.assert_valid(this);
693 arc.assert_valid(this);
694 for (unsigned i = 0; i < fanin(to); i++)
695 {
696 if (input(to,i) == arc)
697 return i;
698 }
699 return digraph<NT,AT>::npos();
700 }
702 template<typename NT, typename AT>
703 unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::iterator to,
704 TYPENAME digraph<NT,AT>::arc_iterator arc)
705 throw(wrong_object,null_dereference,end_dereference)
706 {
707 to.assert_valid(this);
708 arc.assert_valid(this);
709 for (unsigned i = 0; i < fanin(to); i++)
710 {
711 if (input(to,i) == arc)
712 return i;
713 }
714 return digraph<NT,AT>::npos();
715 }
717 ////////////////////////////////////////////////////////////////////////////////
718 // Basic Arc functions
720 template<typename NT, typename AT>
721 bool digraph<NT,AT>::arc_empty(void) const
722 {
723 return m_arcs_end == 0;
724 }
726 template<typename NT, typename AT>
727 unsigned digraph<NT,AT>::arc_size(void) const
728 {
729 unsigned count = 0;
730 for (digraph_arc_iterator<NT,AT, const AT&,const AT*> i = arc_begin(); i != arc_end(); i++)
731 count++;
732 return count;
733 }
735 template<typename NT, typename AT>
736 TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_insert(TYPENAME digraph<NT,AT>::iterator from,
737 TYPENAME digraph<NT,AT>::iterator to,
738 const AT& arc_data)
739 throw(wrong_object,null_dereference,end_dereference)
740 {
741 from.assert_valid(this);
742 to.assert_valid(this);
743 // create the new arc and link it in to the arc list
744 digraph_arc<NT,AT>* new_arc = new digraph_arc<NT,AT>(this, from.node(), to.node(), arc_data);
745 if (!m_arcs_end)
746 {
747 // insert into an empty list
748 m_arcs_begin = new_arc;
749 m_arcs_end = new_arc;
750 }
751 else
752 {
753 // insert at the end of the list
754 new_arc->m_prev = m_arcs_end;
755 m_arcs_end->m_next = new_arc;
756 m_arcs_end = new_arc;
757 }
758 // add this arc to the inputs and outputs of the end nodes
759 from.node()->m_outputs.push_back(new_arc);
760 to.node()->m_inputs.push_back(new_arc);
761 return digraph_arc_iterator<NT,AT,AT&,AT*>(new_arc);
762 }
764 template<typename NT, typename AT>
765 TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_erase(TYPENAME digraph<NT,AT>::arc_iterator iter)
766 throw(wrong_object,null_dereference,end_dereference)
767 {
768 iter.assert_valid(this);
769 // first remove this arc's pointers from the from/to nodes
770 for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator i = iter.node()->m_to->m_inputs.begin(); i != iter.node()->m_to->m_inputs.end(); )
771 {
772 if (*i == iter.node())
773 i = iter.node()->m_to->m_inputs.erase(i);
774 else
775 i++;
776 }
777 for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator o = iter.node()->m_from->m_outputs.begin(); o != iter.node()->m_from->m_outputs.end(); )
778 {
779 if (*o == iter.node())
780 o = iter.node()->m_from->m_outputs.erase(o);
781 else
782 o++;
783 }
784 // now unlink the arc from the list and delete it
785 if (iter.node()->m_next)
786 iter.node()->m_next->m_prev = iter.node()->m_prev;
787 if (iter.node()->m_prev)
788 iter.node()->m_prev->m_next = iter.node()->m_next;
789 digraph_arc<NT,AT>* next = iter.node()->m_next;
790 delete iter.node();
791 if (next)
792 return digraph_arc_iterator<NT,AT,AT&,AT*>(next);
793 else
794 return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
795 }
797 template<typename NT, typename AT>
798 void digraph<NT,AT>::arc_clear(void)
799 {
800 for (digraph_arc_iterator<NT,AT,AT&,AT*> a = arc_begin(); a != arc_end(); )
801 a = arc_erase(a);
802 }
804 template<typename NT, typename AT>
805 TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_begin(void) const
806 {
807 if (m_arcs_begin)
808 return digraph_arc_iterator<NT,AT, const AT&,const AT*>(m_arcs_begin);
809 else
810 return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);
811 }
813 template<typename NT, typename AT>
814 TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_begin(void)
815 {
816 if (m_arcs_begin)
817 return digraph_arc_iterator<NT,AT,AT&,AT*>(m_arcs_begin);
818 else
819 return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
820 }
822 template<typename NT, typename AT>
823 TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_end(void) const
824 {
825 return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);
826 }
828 template<typename NT, typename AT>
829 TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_end(void)
830 {
831 return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
832 }
834 template<typename NT, typename AT>
835 TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const
836 throw(wrong_object,null_dereference,end_dereference)
837 {
838 iter.assert_valid(this);
839 return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_from);
840 }
842 template<typename NT, typename AT>
843 TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::arc_iterator iter)
844 throw(wrong_object,null_dereference,end_dereference)
845 {
846 iter.assert_valid(this);
847 return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_from);
848 }
850 template<typename NT, typename AT>
851 TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const
852 throw(wrong_object,null_dereference,end_dereference)
853 {
854 iter.assert_valid(this);
855 return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_to);
856 }
858 template<typename NT, typename AT>
859 TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::arc_iterator iter)
860 throw(wrong_object,null_dereference,end_dereference)
861 {
862 iter.assert_valid(this);
863 return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_to);
864 }
866 template<typename NT, typename AT>
867 void digraph<NT,AT>::arc_move(TYPENAME digraph<NT,AT>::arc_iterator arc,
868 TYPENAME digraph<NT,AT>::iterator from,
869 TYPENAME digraph<NT,AT>::iterator to)
870 throw(wrong_object,null_dereference,end_dereference)
871 {
872 arc_move_to(arc,to);
873 arc_move_from(arc,from);
874 }
876 template<typename NT, typename AT>
877 void digraph<NT,AT>::arc_move_from(TYPENAME digraph<NT,AT>::arc_iterator arc,
878 TYPENAME digraph<NT,AT>::iterator from)
879 throw(wrong_object,null_dereference,end_dereference)
880 {
881 arc.assert_valid(this);
882 from.assert_valid(this);
883 for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator o = arc.node()->m_from->m_outputs.begin(); o != arc.node()->m_from->m_outputs.end(); )
884 {
885 if (*o == arc.node())
886 o = arc.node()->m_from->m_outputs.erase(o);
887 else
888 o++;
889 }
890 from.node()->m_outputs.push_back(arc.node());
891 arc.node()->m_from = from.node();
892 }
894 template<typename NT, typename AT>
895 void digraph<NT,AT>::arc_move_to(TYPENAME digraph<NT,AT>::arc_iterator arc,
896 TYPENAME digraph<NT,AT>::iterator to)
897 throw(wrong_object,null_dereference,end_dereference)
898 {
899 arc.assert_valid(this);
900 to.assert_valid(this);
901 for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator i = arc.node()->m_to->m_inputs.begin(); i != arc.node()->m_to->m_inputs.end(); )
902 {
903 if (*i == arc.node())
904 i = arc.node()->m_to->m_inputs.erase(i);
905 else
906 i++;
907 }
908 to.node()->m_inputs.push_back(arc.node());
909 arc.node()->m_to = to.node();
910 }
912 template<typename NT, typename AT>
913 void digraph<NT,AT>::arc_flip(TYPENAME digraph<NT,AT>::arc_iterator arc)
914 throw(wrong_object,null_dereference,end_dereference)
915 {
916 arc_move(arc,arc_to(arc),arc_from(arc));
917 }
919 ////////////////////////////////////////////////////////////////////////////////
922 template<typename NT, typename AT>
924 TYPENAME digraph<NT,AT>::const_iterator to) const
925 throw(wrong_object,null_dereference,end_dereference)
926 {
928 }
930 template<typename NT, typename AT>
932 TYPENAME digraph<NT,AT>::iterator to)
933 throw(wrong_object,null_dereference,end_dereference)
934 {
936 }
938 template<typename NT, typename AT>
939 TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::const_iterator from,
940 TYPENAME digraph<NT,AT>::const_iterator to) const
941 throw(wrong_object,null_dereference,end_dereference)
942 {
943 from.assert_valid(this);
944 to.assert_valid(this);
945 for (unsigned arc = 0; arc < fanout(from); arc++)
946 {
947 if (arc_to(output(from, arc)) == to)
948 return output(from,arc);
949 }
950 return arc_end();
951 }
953 template<typename NT, typename AT>
954 TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::iterator from,
955 TYPENAME digraph<NT,AT>::iterator to)
956 throw(wrong_object,null_dereference,end_dereference)
957 {
959 }
961 template<typename NT, typename AT>
962 TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::const_iterator from,
963 TYPENAME digraph<NT,AT>::const_iterator to) const
964 throw(wrong_object,null_dereference,end_dereference)
965 {
966 from.assert_valid(this);
967 to.assert_valid(this);
968 std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;
969 for (unsigned arc = 0; arc < fanout(from); arc++)
970 {
971 if (arc_to(output(from, arc)) == to)
972 result.push_back(output(from,arc));
973 }
974 return result;
975 }
977 template<typename NT, typename AT>
978 TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::iterator from,
979 TYPENAME digraph<NT,AT>::iterator to)
980 throw(wrong_object,null_dereference,end_dereference)
981 {
983 }
985 template<typename NT, typename AT>
986 TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::const_iterator to) const
987 throw(wrong_object,null_dereference,end_dereference)
988 {
989 std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
990 for (unsigned arc = 0; arc < fanin(to); arc++)
991 {
992 digraph_iterator<NT,AT,const NT&,const NT*> from = arc_from(input(to, arc));
993 if (std::find(result.begin(), result.end(), from) == result.end())
994 result.push_back(from);
995 }
996 return result;
997 }
999 template<typename NT, typename AT>
1000 TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::iterator to)
1001 throw(wrong_object,null_dereference,end_dereference)
1002 {
1004 }
1006 template<typename NT, typename AT>
1007 TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::const_iterator from) const
1008 throw(wrong_object,null_dereference,end_dereference)
1009 {
1010 std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1011 for (unsigned arc = 0; arc < fanout(from); arc++)
1012 {
1013 digraph_iterator<NT,AT,const NT&,const NT*> to = arc_to(output(from, arc));
1014 if (find(result.begin(), result.end(), to) == result.end())
1015 result.push_back(to);
1016 }
1017 return result;
1018 }
1020 template<typename NT, typename AT>
1021 TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::iterator from)
1022 throw(wrong_object,null_dereference,end_dereference)
1023 {
1025 }
1027 ////////////////////////////////////////////////////////////////////////////////
1028 // Topographical Sort Algorithms
1030 template<typename NT, typename AT>
1031 std::pair<TYPENAME digraph<NT,AT>::const_node_vector, TYPENAME digraph<NT,AT>::const_arc_vector>
1032 digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const
1033 {
1034 std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1035 std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > errors;
1036 // build a map containing the number of fanins to each node that must be visited before this one
1037 std::map<digraph_iterator<NT,AT,const NT&,const NT*>,unsigned> fanin_map;
1038 for (digraph_iterator<NT,AT,const NT&,const NT*> n = begin(); n != end(); n++)
1039 {
1040 unsigned predecessors = 0;
1041 // only count predecessors connected by selected arcs
1042 for (unsigned f = 0; f < fanin(n); f++)
1043 {
1044 digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(n,f);
1045 digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);
1046 if (!select || select(*this,input_arc))
1047 predecessors++;
1048 }
1049 if (predecessors == 0)
1050 {
1051 result.push_back(n);
1052 }
1053 else
1054 {
1055 fanin_map[n] = predecessors;
1056 }
1057 }
1058 // main algorithm applies the topographical sort repeatedly. For a DAG, it
1059 // will complete first time. However, with backward arcs, the first
1060 // iteration will fail. The algorithm then tries breaking random arcs to try
1061 // to get an ordering.
1062 for(unsigned i = 0; !fanin_map.empty(); )
1063 {
1064 // now visit each node in traversal order, decrementing the fanin count of
1065 // all successors. As each successor's fanin count goes to zero, it is
1066 // appended to the result.
1067 for (; i < result.size(); i++)
1068 {
1069 // Note: dereferencing gives us a node iterator
1070 digraph_iterator<NT,AT,const NT&,const NT*> current = result[i];
1071 for (unsigned f = 0; f < fanout(current); f++)
1072 {
1073 // only consider successors connected by selected arcs
1074 digraph_arc_iterator<NT,AT, const AT&,const AT*> output_arc = output(current, f);
1075 digraph_iterator<NT,AT,const NT&,const NT*> successor = arc_to(output_arc);
1076 if (!select || select(*this,output_arc))
1077 {
1078 // don't consider arcs that have been eliminated to break a loop
1079 if (fanin_map.find(successor) != fanin_map.end())
1080 {
1081 --fanin_map[successor];
1082 if ((fanin_map[successor]) == 0)
1083 {
1084 result.push_back(successor);
1085 fanin_map.erase(fanin_map.find(successor));
1086 }
1087 }
1088 }
1089 }
1090 }
1091 if (!fanin_map.empty())
1092 {
1093 // there must be backward arcs preventing completion
1094 // try removing arcs from the sort to get a partial ordering containing all the nodes
1096 // select an arc that is still relevant to the sort and break it
1097 // first select a node that has non-zero fanin and its predecessor that has non-zero fanin
1098 digraph_iterator<NT,AT,const NT&,const NT*> stuck_node = fanin_map.begin()->first;
1099 for (unsigned f = 0; f < fanin(stuck_node); f++)
1100 {
1101 // now successively remove input arcs that are still part of the sort until the fanin reduces to zero
1102 // first find a relevant arc - this must be a selected arc that has not yet been traversed by the first half of the algorithm
1103 digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(stuck_node, f);
1104 if (!select || select(*this,input_arc))
1105 {
1106 digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);
1107 if (fanin_map.find(predecessor) != fanin_map.end())
1108 {
1109 // found the right combination - remove this arc and then drop out of the fanin loop to restart the outer sort loop
1110 errors.push_back(input_arc);
1111 --fanin_map[stuck_node];
1112 if ((fanin_map[stuck_node]) == 0)
1113 {
1114 result.push_back(stuck_node);
1115 fanin_map.erase(fanin_map.find(stuck_node));
1116 break;
1117 }
1118 }
1119 }
1120 }
1121 }
1122 }
1123 return std::make_pair(result,errors);
1124 }
1126 template<typename NT, typename AT>
1127 std::pair<TYPENAME digraph<NT,AT>::node_vector, TYPENAME digraph<NT,AT>::arc_vector>
1128 digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select)
1129 {
1130 std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,
1131 std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > const_result =
1132 const_cast<const digraph<NT,AT>*>(this)->sort(select);
1134 std::pair<std::vector<digraph_iterator<NT,AT,NT&,NT*> >,
1135 std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result =
1136 std::make_pair(deconstify_nodes(const_result.first),deconstify_arcs(const_result.second));
1137 return result;
1138 }
1140 template<typename NT, typename AT>
1141 TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const
1142 {
1143 std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,
1144 std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result = sort(select);
1145 if (result.second.empty()) return result.first;
1146 return std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >();
1147 }
1149 template<typename NT, typename AT>
1150 TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select)
1151 {
1152 return deconstify_nodes(const_cast<const digraph<NT,AT>*>(this)->dag_sort(select));
1153 }
1154 ////////////////////////////////////////////////////////////////////////////////
1155 // Path Algorithms
1157 template<typename NT, typename AT>
1158 bool digraph<NT,AT>::path_exists_r(TYPENAME digraph<NT,AT>::const_iterator from,
1159 TYPENAME digraph<NT,AT>::const_iterator to,
1160 TYPENAME digraph<NT,AT>::const_iterator_set& visited,
1161 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1162 throw(wrong_object,null_dereference,end_dereference)
1163 {
1164 // Recursive part of the digraph::path_exists function. This is based on a
1165 // depth first search algorithm and stops the moment it finds a path
1166 // regardless of its length. Simply traverse every output and recurse on that
1167 // node until we find the to node or run out of things to recurse on. However,
1168 // to avoid infinite recursion due to cycles in the graph, I need to maintain
1169 // a set of visited nodes. The visited set is updated when a candidate is
1170 // found but tested before the recursion on the candidate so that the number of
1171 // function calls is minimised.
1172 for (unsigned i = 0; i < fanout(from); i++)
1173 {
1174 digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);
1175 if (!select || select(*this, arc))
1176 {
1177 digraph_iterator<NT,AT,const NT&,const NT*> node = arc_to(arc);
1178 // if the node is the target, return immediately
1179 if (node == to) return true;
1180 // update the visited set and give up if the insert fails, which indicates that the node has already been visited
1181 if (!(visited.insert(node).second)) return false;
1182 // now recurse - a path exists from from to to if a path exists from an adjacent node to to
1183 if (path_exists_r(node,to,visited,select)) return true;
1184 }
1185 }
1186 return false;
1187 }
1189 template<typename NT, typename AT>
1190 bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::const_iterator from,
1191 TYPENAME digraph<NT,AT>::const_iterator to,
1192 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1193 throw(wrong_object,null_dereference,end_dereference)
1194 {
1195 // set up the recursion with its initial visited set and then recurse
1196 std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
1197 visited.insert(from);
1198 return path_exists_r(from, to, visited, select);
1199 }
1201 template<typename NT, typename AT>
1202 bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::iterator from,
1203 TYPENAME digraph<NT,AT>::iterator to,
1204 TYPENAME digraph<NT,AT>::arc_select_fn select)
1205 throw(wrong_object,null_dereference,end_dereference)
1206 {
1207 return path_exists(from.constify(), to.constify(), select);
1208 }
1210 template<typename NT, typename AT>
1211 void digraph<NT,AT>::all_paths_r(TYPENAME digraph<NT,AT>::const_iterator from,
1212 TYPENAME digraph<NT,AT>::const_iterator to,
1213 TYPENAME digraph<NT,AT>::const_arc_vector& so_far,
1214 TYPENAME digraph<NT,AT>::const_path_vector& result,
1215 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1216 throw(wrong_object,null_dereference,end_dereference)
1217 {
1218 // This is the recursive part of the all_paths function. The field so_far
1219 // contains the path so far so that when 'to' is reached, the path is
1220 // complete. It serves the same purpose as the visited set in the path_exists
1221 // function except that it also preserves the path order. It also serves the
1222 // purpose of detecting cycles and thus stopping infinite recursion. Every
1223 // time the recursion reaches the to node, a copy of so_far is appended to the
1224 // path set.
1225 for (unsigned i = 0; i < fanout(from); i++)
1226 {
1227 digraph_arc_iterator<NT,AT, const AT&,const AT*> candidate = output(from,i);
1228 // assert_valid that the arc is selected and then assert_valid that the candidate has not
1229 // been visited on this path and only allow further recursion if it hasn't
1230 if ((!select || select(*this, candidate)) && std::find(so_far.begin(), so_far.end(), candidate) == so_far.end())
1231 {
1232 // extend the path tracing the route to this arc
1233 so_far.push_back(candidate);
1234 // if the candidate arc points to the target, update the result set and prevent further recursion, otherwise recurse
1235 if (arc_to(candidate) == to)
1236 result.push_back(so_far);
1237 else
1238 all_paths_r(arc_to(candidate),to,so_far,result,select);
1239 so_far.pop_back();
1240 }
1241 }
1242 }
1244 template<typename NT, typename AT>
1245 TYPENAME digraph<NT,AT>::const_path_vector
1246 digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::const_iterator from,
1247 TYPENAME digraph<NT,AT>::const_iterator to,
1248 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1249 throw(wrong_object,null_dereference,end_dereference)
1250 {
1251 // set up the recursion with empty data fields and then recurse
1252 std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
1253 std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > so_far;
1254 all_paths_r(from, to, so_far, result, select);
1255 return result;
1256 }
1258 template<typename NT, typename AT>
1259 TYPENAME digraph<NT,AT>::path_vector
1260 digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::iterator from,
1261 TYPENAME digraph<NT,AT>::iterator to,
1262 TYPENAME digraph<NT,AT>::arc_select_fn select)
1263 throw(wrong_object,null_dereference,end_dereference)
1264 {
1265 return deconstify_paths(all_paths(from.constify(), to.constify(), select));
1266 }
1268 template<typename NT, typename AT>
1269 void digraph<NT,AT>::reachable_nodes_r(TYPENAME digraph<NT,AT>::const_iterator from,
1270 TYPENAME digraph<NT,AT>::const_iterator_set& visited,
1271 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1272 throw(wrong_object,null_dereference,end_dereference)
1273 {
1274 // The recursive part of the reachable_nodes function.
1275 // This is a depth-first traversal again but this time it carries on to find all the reachable nodes
1276 // Just keep recursing on all the adjacent nodes of each node, skipping already visited nodes to avoid cycles
1277 for (unsigned i = 0; i < fanout(from); i++)
1278 {
1279 digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);
1280 if (!select || select(*this,arc))
1281 {
1282 digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_to(arc);
1283 if (visited.insert(candidate).second)
1284 reachable_nodes_r(candidate,visited,select);
1285 }
1286 }
1287 }
1289 template<typename NT, typename AT>
1290 TYPENAME digraph<NT,AT>::const_node_vector
1291 digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::const_iterator from,
1292 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1293 throw(wrong_object,null_dereference,end_dereference)
1294 {
1295 // seed the recursion, marking the starting node as already visited
1296 std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
1297 visited.insert(from);
1298 reachable_nodes_r(from, visited, select);
1299 // convert the visited set into the required output form
1300 // exclude the starting node
1301 std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1302 for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)
1303 if (*i != from)
1304 result.push_back(*i);
1305 return result;
1306 }
1308 template<typename NT, typename AT>
1309 TYPENAME digraph<NT,AT>::node_vector
1310 digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::iterator from,
1311 TYPENAME digraph<NT,AT>::arc_select_fn select)
1312 throw(wrong_object,null_dereference,end_dereference)
1313 {
1314 return deconstify_nodes(reachable_nodes(from.constify(), select));
1315 }
1317 template<typename NT, typename AT>
1318 void digraph<NT,AT>::reaching_nodes_r(TYPENAME digraph<NT,AT>::const_iterator to,
1319 TYPENAME digraph<NT,AT>::const_iterator_set& visited,
1320 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1321 throw(wrong_object,null_dereference,end_dereference)
1322 {
1323 // The recursive part of the reaching_nodes function.
1324 // Just like the reachable_nodes_r function but it goes backwards
1325 for (unsigned i = 0; i < fanin(to); i++)
1326 {
1327 digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = input(to,i);
1328 if (!select || select(*this,arc))
1329 {
1330 digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_from(input(to,i));
1331 if (visited.insert(candidate).second)
1332 reaching_nodes_r(candidate,visited,select);
1333 }
1334 }
1335 }
1337 template<typename NT, typename AT>
1338 TYPENAME digraph<NT,AT>::const_node_vector
1339 digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::const_iterator to,
1340 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1341 throw(wrong_object,null_dereference,end_dereference)
1342 {
1343 // seed the recursion, marking the starting node as already visited
1344 std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
1345 visited.insert(to);
1346 reaching_nodes_r(to,visited,select);
1347 // convert the visited set into the required output form
1348 // exclude the end node
1349 std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1350 for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)
1351 if (*i != to)
1352 result.push_back(*i);
1353 return result;
1354 }
1356 template<typename NT, typename AT>
1357 TYPENAME digraph<NT,AT>::node_vector
1358 digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::iterator to,
1359 TYPENAME digraph<NT,AT>::arc_select_fn select)
1360 throw(wrong_object,null_dereference,end_dereference)
1361 {
1362 return deconstify_nodes(reaching_nodes(to.constify(),select));
1363 }
1365 ////////////////////////////////////////////////////////////////////////////////
1366 // Shortest Path Algorithms
1368 template<typename NT, typename AT>
1369 TYPENAME digraph<NT,AT>::const_arc_vector
1370 digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::const_iterator from,
1371 TYPENAME digraph<NT,AT>::const_iterator to,
1372 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1373 throw(wrong_object,null_dereference,end_dereference)
1374 {
1375 std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > paths = all_paths(from,to,select);
1376 std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > shortest;
1377 for (TYPENAME std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > >::iterator i = paths.begin(); i != paths.end(); i++)
1378 if (shortest.empty() || i->size() < shortest.size())
1379 shortest = *i;
1380 return shortest;
1381 }
1383 template<typename NT, typename AT>
1384 TYPENAME digraph<NT,AT>::arc_vector
1385 digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::iterator from,
1386 TYPENAME digraph<NT,AT>::iterator to,
1387 TYPENAME digraph<NT,AT>::arc_select_fn select)
1388 throw(wrong_object,null_dereference,end_dereference)
1389 {
1390 return deconstify_arcs(shortest_path(from.constify(),to.constify(),select));
1391 }
1393 template<typename NT, typename AT>
1394 TYPENAME digraph<NT,AT>::const_path_vector
1395 digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::const_iterator from,
1396 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1397 throw(wrong_object,null_dereference,end_dereference)
1398 {
1399 from.assert_valid(this);
1400 // This is an unweighted shortest path algorithm based on the algorithm from
1401 // Weiss's book. This is essentially a breadth-first traversal or graph
1402 // colouring algorithm. It is an iterative algorithm, so no recursion here! It
1403 // works by creating a node queue initialised with the starting node. It then
1404 // consumes the queue from front to back. For each node, it finds the
1405 // successors and appends them to the queue. If a node is already 'known' it
1406 // is not added - this avoids cycles. Thus the queue insert ordering
1407 // represents the breadth-first ordering. On the way it creates a map of
1408 // visited nodes. This is a map not a set because it also stores the arc that
1409 // nominated this node as a shortest path. The full path can then be recreated
1410 // from the map by just walking back through the predecessors. The depth (or
1411 // colour) can be determined by the path length.
1412 std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
1413 // initialise the iteration by creating a queue and adding the start node
1414 std::deque<digraph_iterator<NT,AT,const NT&,const NT*> > nodes;
1415 nodes.push_back(from);
1416 // Create a map to store the set of known nodes mapped to their predecessor
1417 // arcs. Initialise it with the current node, which has no predecessor. Note
1418 // that the algorithm uses the feature of digraph iterators that they can be
1419 // null iterators and that all null iterators are equal.
1420 typedef std::map<digraph_iterator<NT,AT,const NT&,const NT*>,
1421 digraph_arc_iterator<NT,AT,const AT&,const AT*> > known_map;
1422 known_map known;
1423 known.insert(std::make_pair(from,digraph_arc_iterator<NT,AT, const AT&,const AT*>()));
1424 // now the iterative part of the algorithm
1425 while(!nodes.empty())
1426 {
1427 // pop the queue to get the next node to process - unfortunately the STL
1428 // deque::pop does not return the popped value
1429 digraph_iterator<NT,AT,const NT&,const NT*> current = nodes.front();
1430 nodes.pop_front();
1431 // now visit all the successors
1432 for (unsigned i = 0; i < fanout(current); i++)
1433 {
1434 digraph_arc_iterator<NT,AT, const AT&,const AT*> next_arc = output(current,i);
1435 // assert_valid whether the successor arc is a selected arc and can be part of a path
1436 if (!select || select(*this,next_arc))
1437 {
1438 digraph_iterator<NT,AT,const NT&,const NT*> next = arc_to(next_arc);
1439 // Discard any successors that are known because to be known already they
1440 // must have another shorter path. Otherwise add the successor node to the
1441 // queue to be visited later. To minimise the overhead of map lookup I use
1442 // the usual trick of trying to insert the node and determining whether
1443 // the node was known by the success or failure of the insertion - this is
1444 // a Good STL Trick (TM).
1445 if (known.insert(std::make_pair(next,next_arc)).second)
1446 nodes.push_back(next);
1447 }
1448 }
1449 }
1450 // The map contains the results as an unordered set of nodes, mapped to their
1451 // predecessor arcs and weight. This now needs to be converted into a set of
1452 // paths. This is done by starting with a node from the map, finding its
1453 // predecessor arc and therefore its predecessor node, looking that up in the
1454 // map to find its predecessor and so on until the start node is reached (it
1455 // has a null predecessor). Note that the known set includes the from node
1456 // which does not generate a path.
1457 for (TYPENAME known_map::iterator i = known.begin(); i != known.end(); i++)
1458 {
1459 if (i->first != from)
1460 {
1461 const_arc_vector this_path;
1462 for (TYPENAME known_map::iterator node = i;
1463 node->second.valid();
1464 node = known.find(arc_from(node->second)))
1465 this_path.insert(this_path.begin(),node->second);
1466 result.push_back(this_path);
1467 }
1468 }
1469 return result;
1470 }
1472 template<typename NT, typename AT>
1473 TYPENAME digraph<NT,AT>::path_vector
1474 digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::iterator from,
1475 TYPENAME digraph<NT,AT>::arc_select_fn select)
1476 throw(wrong_object,null_dereference,end_dereference)
1477 {
1478 return deconstify_paths(shortest_paths(from.constify(),select));
1479 }
1481 ////////////////////////////////////////////////////////////////////////////////
1483 } // end namespace stlplus