ROSE  0.11.96.11
GraphBoost.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
9 // be clobbered by the next update from Sawyer. The Sawyer repository is at
10 // https://github.com/matzke1/sawyer.
11 
12 
13 
14 
15 // Boost Graph Library (BGL) interface around Sawyer::Container::Graph
16 #ifndef Sawyer_GraphBoost_H
17 #define Sawyer_GraphBoost_H
18 
19 #include <Sawyer/Graph.h>
20 #include <Sawyer/Sawyer.h>
21 #include <boost/foreach.hpp>
22 #include <boost/graph/graph_traits.hpp>
23 #include <boost/graph/properties.hpp>
24 
25 namespace Sawyer {
26 
59 namespace Boost {
60 
82 template<class SawyerGraph, class BoostGraph>
83 void sawyerGraphToBoostGraph(const SawyerGraph &sg, BoostGraph &bg /*out*/) {
84  bg = BoostGraph(sg.nVertices());
85  BOOST_FOREACH (const typename SawyerGraph::Edge &edge, sg.edges())
86  bg.add_edge(edge.source()->id(), edge.target()->id());
87 }
88 
89 template<class SawyerGraph, class BoostGraph>
90 BoostGraph sawyerGraphToBoostGraph(const SawyerGraph &sg) {
91  BoostGraph bg;
93  return bg;
94 }
97 // Iterators
100 
101 // BGL vertex and edge iterators, when dereferenced, yield a BGL vertex descriptor; BGL vertex descriptors are used to look up
102 // property values in property maps. Since we want O(1) lookup times for properties, we'll use Sawyer vertex and edge ID
103 // numbers as BGL vertex and edge descriptors. Therefore, we need to provide iterators which when dereferenced return a Sawyer
104 // vertex or edge ID.
105 //
106 // Another reason for using Sawyer vertex and edge ID numbers as BGL vertex and edge descriptors is that BGL expects there to
107 // exist a single vertex descriptor that represents "no vertex". We can use (size_t)(-1) for this, but we would not have been
108 // able to use Sawyer "end" iterators since the end of one list is not equal to the end of another list.
109 
110 template<class V, class E, class VKey, class EKey, class Alloc>
112 public:
113  // Five standard iterator types
114  using iterator_category = std::bidirectional_iterator_tag;
115  using value_type = const size_t;
116  using difference_type = std::ptrdiff_t;
117  using pointer = const size_t*;
118  using reference = const size_t&;
119 
120 private:
122  BaseIter base_;
123 public:
125  VertexOuterIterator(const VertexOuterIterator &other): base_(other.base_) {}
126  explicit VertexOuterIterator(const BaseIter &base): base_(base) {}
127  VertexOuterIterator& operator=(const VertexOuterIterator &other) { base_ = other.base_; return *this; }
128  VertexOuterIterator& operator++() { ++base_; return *this; }
129  VertexOuterIterator& operator--() { --base_; return *this; }
130  VertexOuterIterator operator++(int) { VertexOuterIterator old = *this; ++base_; return old; }
131  VertexOuterIterator operator--(int) { VertexOuterIterator old = *this; --base_; return old; }
132  bool operator==(const VertexOuterIterator &other) const { return base_ == other.base_; }
133  bool operator!=(const VertexOuterIterator &other) const { return base_ != other.base_; }
134  const size_t& operator*() const { return base_->id(); }
135  // size_t* operator->() const; //no methods defined on size_t, so not needed
136 };
137 
138 template<class V, class E, class VKey, class EKey, class Alloc>
140 public:
141  // Five standard iterator types
142  using iterator_category = std::bidirectional_iterator_tag;
143  using value_type = const size_t;
144  using difference_type = std::ptrdiff_t;
145  using pointer = const size_t*;
146  using reference = const size_t&;
147 
148 private:
150  BaseIter base_;
151 public:
153  ConstVertexOuterIterator(const ConstVertexOuterIterator &other): base_(other.base_) {}
155  explicit ConstVertexOuterIterator(const BaseIter &base): base_(base) {}
156  ConstVertexOuterIterator& operator=(const ConstVertexOuterIterator &other) { base_ = other.base_; return *this; }
157  ConstVertexOuterIterator& operator++() { ++base_; return *this; }
158  ConstVertexOuterIterator& operator--() { --base_; return *this; }
159  ConstVertexOuterIterator operator++(int) { ConstVertexOuterIterator old = *this; ++base_; return old; }
160  ConstVertexOuterIterator operator--(int) { ConstVertexOuterIterator old = *this; --base_; return old; }
161  bool operator==(const ConstVertexOuterIterator &other) const { return base_ == other.base_; }
162  bool operator!=(const ConstVertexOuterIterator &other) const { return base_ != other.base_; }
163  const size_t& operator*() const { return base_->id(); }
164  // size_t* operator->() const; //no methods defined on size_t, so not needed
165 };
166 
167 template<class V, class E, class VKey, class EKey, class Alloc>
169 public:
170  // Five standard iterator types
171  using iterator_category = std::bidirectional_iterator_tag;
172  using value_type = const size_t;
173  using difference_type = std::ptrdiff_t;
174  using pointer = const size_t*;
175  using reference = const size_t&;
176 
177 private:
179  BaseIter base_;
180 public:
181  EdgeOuterIterator() {}
182  EdgeOuterIterator(const EdgeOuterIterator &other): base_(other.base_) {}
183  explicit EdgeOuterIterator(const BaseIter &base): base_(base) {}
184  EdgeOuterIterator& operator=(const EdgeOuterIterator &other) { base_ = other.base_; return *this; }
185  EdgeOuterIterator& operator++() { ++base_; return *this; }
186  EdgeOuterIterator& operator--() { --base_; return *this; }
187  EdgeOuterIterator operator++(int) { EdgeOuterIterator old = *this; ++base_; return old; }
188  EdgeOuterIterator operator--(int) { EdgeOuterIterator old = *this; --base_; return old; }
189  bool operator==(const EdgeOuterIterator &other) const { return base_ == other.base_; }
190  bool operator!=(const EdgeOuterIterator &other) const { return base_ != other.base_; }
191  const size_t& operator*() const { return base_->id(); }
192  // size_t* operator->() const; //no methods defined on size_t, so not needed
193 };
194 
195 template<class V, class E, class VKey, class EKey, class Alloc>
197 public:
198  // Five standard iterator types
199  using iterator_category = std::bidirectional_iterator_tag;
200  using value_type = const size_t;
201  using difference_type = std::ptrdiff_t;
202  using pointer = const size_t*;
203  using reference = const size_t&;
204 
205 private:
207  BaseIter base_;
208 public:
210  ConstEdgeOuterIterator(const ConstEdgeOuterIterator &other): base_(other.base_) {}
211  ConstEdgeOuterIterator(const EdgeOuterIterator<V, E, VKey, EKey, Alloc> &other): base_(other.base_) {}
212  explicit ConstEdgeOuterIterator(const BaseIter &base): base_(base) {}
213  ConstEdgeOuterIterator& operator=(const ConstEdgeOuterIterator &other) { base_ = other.base_; return *this; }
214  ConstEdgeOuterIterator& operator++() { ++base_; return *this; }
215  ConstEdgeOuterIterator& operator--() { --base_; return *this; }
216  ConstEdgeOuterIterator operator++(int) { ConstEdgeOuterIterator old = *this; ++base_; return old; }
217  ConstEdgeOuterIterator operator--(int) { ConstEdgeOuterIterator old = *this; --base_; return old; }
218  bool operator==(const ConstEdgeOuterIterator &other) const { return base_ == other.base_; }
219  bool operator!=(const ConstEdgeOuterIterator &other) const { return base_ != other.base_; }
220  const size_t& operator*() const { return base_->id(); }
221  // size_t* operator->() const; //no methods defined on size_t, so not needed
222 };
223 
225 // Internal properties
227 
228 // External properties can use the BGL mechanisms that are already defined, but we need something special for internal
229 // properties. A BGL property map is simply a class that provides a lookup mechanism when given a vertex or edge descriptor, so
230 // all we need is a class that will look up the user-supplied value for a vertex or edge.
231 
232 // User-defined value attached to a vertex.
233 template<class Graph>
235  Graph &graph_;
236 public:
237  typedef typename Graph::VertexValue ValueType;
238  VertexPropertyMap(Graph &graph): graph_(graph) {}
239  ValueType get(size_t vertexId) const {
240  return graph_.findVertex(vertexId)->value();
241  }
242  void put(size_t vertexId, const ValueType &value) {
243  graph_.findVertex(vertexId)->value() = value;
244  }
245  ValueType& at(size_t vertexId) {
246  return graph_.findVertex(vertexId)->value();
247  }
248  const ValueType& at(size_t vertexId) const {
249  return graph_.findVertex(vertexId)->value();
250  }
251 };
252 
253 // Const user-defined value attached to a vertex.
254 template<class Graph>
256  const Graph &graph_;
257 public:
258  typedef typename Graph::VertexValue ValueType;
259  ConstVertexPropertyMap(const Graph &graph): graph_(graph) {}
260  ValueType get(size_t vertexId) const {
261  return graph_.findVertex(vertexId)->value();
262  }
263  const ValueType& at(size_t vertexId) const {
264  return graph_.findVertex(vertexId)->value();
265  }
266 };
267 
268 // User-defined value attached to an edge. Graph is any non-const Sawyer::Container::Graph<>
269 template<class Graph>
271  Graph &graph_;
272 public:
273  typedef typename Graph::EdgeValue ValueType;
274  EdgePropertyMap(Graph &graph): graph_(graph) {}
275  ValueType get(size_t edgeId) const {
276  return graph_.findEdge(edgeId)->value();
277  }
278  void put(size_t edgeId, const ValueType &value) {
279  graph_.findEdge(edgeId)->value() = value;
280  }
281  ValueType& at(size_t edgeId) {
282  return graph_.findEdge(edgeId)->value();
283  }
284  const ValueType& at(size_t edgeId) const {
285  return graph_.findEdge(edgeId)->value();
286  }
287 };
288 
289 // Const user-defined value attached to a vertex. Graph is any const Sawyer::Container::Graph<>
290 template<class Graph>
292  const Graph &graph_;
293 public:
294  typedef typename Graph::EdgeValue ValueType;
295  ConstEdgePropertyMap(const Graph &graph): graph_(graph) {}
296  ValueType get(size_t edgeId) const {
297  return graph_.findEdge(edgeId)->value();
298  }
299  const ValueType& at(size_t edgeId) const {
300  return graph_.findEdge(edgeId)->value();
301  }
302 };
303 
304 // The ID (index) associated with each vertex. This is a read-only property since ID numbers are managed by the graph.
305 template<class Graph>
307  const Graph &graph_;
308 public:
309  ConstVertexIdPropertyMap(const Graph &graph): graph_(graph) {}
310  size_t get(size_t vertexId) const {
311  return vertexId;
312  }
313  const size_t& at(size_t vertexId) const {
314  return graph_.findVertex(vertexId)->id();
315  }
316 };
317 
318 // The ID (index) associated with each edge. This is a read-only property since ID numbers are managed by the graph.
319 template<class Graph>
321  const Graph &graph_;
322 public:
323  ConstEdgeIdPropertyMap(const Graph &graph): graph_(graph) {}
324  size_t get(size_t edgeId) const {
325  return edgeId;
326  }
327  const size_t& at(size_t edgeId) const {
328  return graph_.findEdge(edgeId)->id();
329  }
330 };
331 
332 // Tags for the user-defined vertex or edge value property. These are to access the user-defined data associated with each
333 // vertex are value corresponding to the "V" and "E" template parameters for Sawyer::Container::Graph
335  typedef boost::vertex_property_tag kind;
336 };
337 struct edge_value_t {
338  typedef boost::edge_property_tag kind;
339 };
340 
341 struct vertex_id_t {
342  typedef boost::vertex_property_tag kind;
343 };
344 
345 struct edge_id_t {
346  typedef boost::edge_property_tag kind;
347 };
348 
349 } // namespace
350 } // namespace
351 
352 
357 namespace boost {
358 
359 
361 // BGL trait classes
363 
364 #if 0 // [Robb P. Matzke 2014-05-23]: Temporarily disabled because it matches too much.
365 // Including this file with boost/wave/util/cpp_include_paths.hpp causes problems because code like this:
366 // using boost::multi_index::get;
367 // return get<from>(pragma_once_files).find(filename) != pragma_once_files.end();
368 // in wave matches these property_traits. E.g.,
369 // boost::property_traits<Sawyer::Boost::VertexPropertyMap<boost::wave::util::from> >
370 // and of course boost::wave::util::from has no VertexValue type. Someone with more boost property map and template
371 // programming experience is needed. For now, users should instantiate their own Sawyer::Boost::VertexPropertyMap<> class
372 // and use it to make their own specialization of boost::property_traits<>.
373 
374 template<class Graph>
375 struct property_traits<Sawyer::Boost::VertexPropertyMap<Graph> > {
376  typedef typename Graph::VertexValue value_type;
377  typedef typename Graph::VertexValue &reference;
378  typedef size_t key_type; // vertex ID number
379  typedef boost::read_write_property_map_tag category;
380 };
381 
382 template<class Graph>
383 struct property_traits<Sawyer::Boost::ConstVertexPropertyMap<Graph> > {
384  typedef typename Graph::VertexValue value_type;
385  typedef typename Graph::VertexValue const &reference;
386  typedef size_t key_type; // vertex ID number
387  typedef boost::readable_property_map_tag category;
388 };
389 
390 template<class Graph>
391 struct property_traits<Sawyer::Boost::EdgePropertyMap<Graph> > {
392  typedef typename Graph::EdgeValue value_type;
393  typedef typename Graph::EdgeValue &reference;
394  typedef size_t key_type; // edge ID number
395  typedef boost::read_write_property_map_tag category;
396 };
397 
398 template<class Graph>
399 struct property_traits<Sawyer::Boost::ConstEdgePropertyMap<Graph> > {
400  typedef typename Graph::EdgeValue value_type;
401  typedef typename Graph::EdgeValue const &reference;
402  typedef size_t key_type; // edge ID number
403  typedef boost::readable_property_map_tag category;
404 };
405 
406 template<class Graph>
407 struct property_traits<Sawyer::Boost::ConstVertexIdPropertyMap<Graph> > {
408  typedef size_t value_type;
409  typedef const size_t &reference;
410  typedef size_t key_type; // vertex ID number
411  typedef boost::readable_property_map_tag category;
412 };
413 
414 template<class Graph>
415 struct property_traits<Sawyer::Boost::ConstEdgeIdPropertyMap<Graph> > {
416  typedef size_t value_type;
417  typedef const size_t &reference;
418  typedef size_t key_type; // vertex ID number
419  typedef boost::readable_property_map_tag category;
420 };
421 
422 #endif
423 
424 
425 template<class Graph>
426 struct property_map<Graph, Sawyer::Boost::vertex_value_t> {
429 };
430 
431 template<class Graph>
432 struct property_map<Graph, Sawyer::Boost::edge_value_t> {
435 };
436 
437 template<class Graph>
438 struct property_map<Graph, Sawyer::Boost::vertex_id_t> {
441 };
442 
443 template<class Graph>
444 struct property_map<Graph, Sawyer::Boost::edge_id_t> {
447 };
448 
450 // Access members of property maps
452 
453 //--- vertex value ---
454 
455 template<class Graph>
456 typename Graph::VertexValue&
457 get(Sawyer::Boost::VertexPropertyMap<Graph> &pmap, size_t key) {
458  return pmap.at(key);
459 }
460 
461 template<class Graph>
462 const typename Graph::VertexValue&
463 get(const Sawyer::Boost::ConstVertexPropertyMap<Graph> &pmap, size_t key) {
464  return pmap.at(key);
465 }
466 
467 template<class Graph>
468 void
469 put(Sawyer::Boost::VertexPropertyMap<Graph> &pmap, size_t key, const typename Graph::VertexValue &value) {
470  pmap.at(key) = value;
471 }
472 
473 //--- edge value ---
474 
475 template<class Graph>
476 typename Graph::EdgeValue&
477 get(Sawyer::Boost::EdgePropertyMap<Graph> &pmap, size_t key) {
478  return pmap.at(key);
479 }
480 
481 template<class Graph>
482 typename Graph::EdgeValue&
483 get(const Sawyer::Boost::ConstEdgePropertyMap<Graph> &pmap, size_t key) {
484  return pmap.at(key);
485 }
486 
487 template<class Graph>
488 void
489 put(Sawyer::Boost::EdgePropertyMap<Graph> &pmap, size_t key,
490  const typename Graph::EdgeValue &value) {
491  pmap.at(key) = value;
492 }
493 
494 //--- vertex and edge ID (indices) ---
495 
496 template<class Graph>
497 const size_t&
498 get(const Sawyer::Boost::ConstVertexIdPropertyMap<Graph> &pmap, size_t key) {
499  return pmap.at(key);
500 }
501 
502 template<class Graph>
503 const size_t&
504 get(const Sawyer::Boost::ConstEdgeIdPropertyMap<Graph> &pmap, size_t key) {
505  return pmap.at(key);
506 }
507 
508 
510 // Graph traits
512 
513 template<class V, class E, class VKey, class EKey, class Alloc>
514 struct graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> > {
515  typedef bidirectional_graph_tag traversal_category;
516 
517  // Graph concepts
518  typedef size_t vertex_descriptor;
519  typedef size_t edge_descriptor;
520  typedef directed_tag directed_category;
521  typedef allow_parallel_edge_tag edge_parallel_category;
522  static size_t null_vertex() { return (size_t)(-1); }
523 
524  // VertexListGraph concepts
526  typedef size_t vertices_size_type;
527 
528  // EdgeListGraph concepts
530  typedef size_t edges_size_type;
531 
532  // IncidenceGraph concepts
534  typedef size_t degree_size_type;
535 
536  // BidirectionalGraph concepts
538 
539  // MutablePropertyGraph concepts
540  typedef typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::VertexValue vertex_property_type;
541  typedef typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::EdgeValue edge_property_type;
542 };
543 
544 template<class V, class E, class VKey, class EKey, class Alloc>
545 struct graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> > {
546  typedef bidirectional_graph_tag traversal_category;
547 
548  // Graph concepts
549  typedef size_t vertex_descriptor;
550  typedef size_t edge_descriptor;
551  typedef directed_tag directed_category;
552  typedef allow_parallel_edge_tag edge_parallel_category;
553 
554  // VertexListGraph concepts
556  typedef size_t vertices_size_type;
557 
558  // EdgeListGraph concepts
560  typedef size_t edges_size_type;
561 
562  // IncidenceGraph concepts
564  typedef size_t degree_size_type;
565 
566  // BidirectionalGraph concepts
568 };
569 
571 // Graph concepts
573 
574 
575 // BGL has a global entity that indicates no-vertex, but Sawyer doesn't--it has STL-like end() iterators.
576 template<class V, class E, class VKey, class EKey, class Alloc>
577 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
578 null_vertex() {
579  return (size_t)(-1);
580 }
581 
582 template<class V, class E, class VKey, class EKey, class Alloc>
583 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
584 null_vertex() {
585  return (size_t)(-1);
586 }
587 
589 // VertexListGraph concepts
591 
592 template<class V, class E, class VKey, class EKey, class Alloc>
593 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator,
594  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator>
596  return std::make_pair(Sawyer::Boost::VertexOuterIterator<V, E, VKey, EKey, Alloc>(graph.vertices().begin()),
598 }
599 
600 template<class V, class E, class VKey, class EKey, class Alloc>
601 std::pair<typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator,
602  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator>
604  return std::make_pair(Sawyer::Boost::ConstVertexOuterIterator<V, E, VKey, EKey, Alloc>(graph.vertices().begin()),
606 }
607 
608 template<class V, class E, class VKey, class EKey, class Alloc>
609 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertices_size_type
611  return graph.nVertices();
612 }
613 
614 template<class V, class E, class VKey, class EKey, class Alloc>
615 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertices_size_type
616 num_vertices(const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> &graph) {
617  return graph.nVertices();
618 }
619 
621 // EdgeListGraph concepts
623 
624 template<class V, class E, class VKey, class EKey, class Alloc>
625 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_iterator,
626  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_iterator>
628  return std::make_pair(Sawyer::Boost::EdgeOuterIterator<V, E, VKey, EKey, Alloc>(graph.edges().begin()),
630 }
631 
632 template<class V, class E, class VKey, class EKey, class Alloc>
633 std::pair<typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_iterator,
634  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_iterator>
636  return std::make_pair(Sawyer::Boost::ConstEdgeOuterIterator<V, E, VKey, EKey, Alloc>(graph.edges().begin()),
638 }
639 
640 template<class V, class E, class VKey, class EKey, class Alloc>
641 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edges_size_type
643  return graph.nEdges();
644 }
645 
646 template<class V, class E, class VKey, class EKey, class Alloc>
647 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edges_size_type
649  return graph.nEdges();
650 }
651 
653 // IncidenceGraph concepts
655 
656 template<class V, class E, class VKey, class EKey, class Alloc>
657 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
658 source(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
660  return graph.findEdge(edge)->source()->id();
661 }
662 
663 template<class V, class E, class VKey, class EKey, class Alloc>
664 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
665 source(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
667  return graph.findEdge(edge)->source()->id();
668 }
669 
670 template<class V, class E, class VKey, class EKey, class Alloc>
671 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
672 target(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
674  return graph.findEdge(edge)->target()->id();
675 }
676 
677 template<class V, class E, class VKey, class EKey, class Alloc>
678 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
679 target(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
681  return graph.findEdge(edge)->target()->id();
682 }
683 
684 template<class V, class E, class VKey, class EKey, class Alloc>
685 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator,
686  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator>
687 out_edges(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
690  return std::make_pair(Sawyer::Boost::EdgeOuterIterator<V, E, VKey, EKey, Alloc>(v->outEdges().begin()),
692 }
693 
694 template<class V, class E, class VKey, class EKey, class Alloc>
695 std::pair<typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator,
696  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator>
697 out_edges(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
702 }
703 
704 template<class V, class E, class VKey, class EKey, class Alloc>
705 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
706 out_degree(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
708  return graph.findVertex(vertex)->nOutEdges();
709 }
710 
711 template<class V, class E, class VKey, class EKey, class Alloc>
712 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
713 out_degree(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
715  return graph.findVertex(vertex)->nOutEdges();
716 }
717 
719 // BidirectionalGraph concepts
721 
722 template<class V, class E, class VKey, class EKey, class Alloc>
723 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator,
724  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator>
725 in_edges(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
728  return std::make_pair(Sawyer::Boost::EdgeOuterIterator<V, E, VKey, EKey, Alloc>(v->inEdges().begin()),
730 }
731 
732 template<class V, class E, class VKey, class EKey, class Alloc>
733 std::pair<typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator,
734  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator>
735 in_edges(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
740 }
741 
742 template<class V, class E, class VKey, class EKey, class Alloc>
743 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
744 in_degree(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
746  return graph.findVertex(vertex)->nInEdges();
747 }
748 
749 template<class V, class E, class VKey, class EKey, class Alloc>
750 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
751 in_degree(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
753  return graph.findVertex(vertex)->nInEdges();
754 }
755 
756 template<class V, class E, class VKey, class EKey, class Alloc>
757 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
758 degree(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
760  return in_degree(vertex) + out_degree(vertex);
761 }
762 
763 template<class V, class E, class VKey, class EKey, class Alloc>
764 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
765 degree(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
767  return in_degree(vertex) + out_degree(vertex);
768 }
769 
771 // PropertyMapGraph concepts
773 
774 template<class V, class E, class VKey, class EKey, class Alloc>
775 typename property_map<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::vertex_value_t>::type
778 }
779 
780 template<class V, class E, class VKey, class EKey, class Alloc>
781 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::vertex_value_t>::const_type
784 }
785 
786 template<class V, class E, class VKey, class EKey, class Alloc>
787 typename property_map<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::edge_value_t>::type
790 }
791 
792 template<class V, class E, class VKey, class EKey, class Alloc>
793 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::edge_value_t>::const_type
796 }
797 
798 template<class V, class E, class VKey, class EKey, class Alloc>
799 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::vertex_id_t>::const_type
802 }
803 
804 template<class V, class E, class VKey, class EKey, class Alloc>
805 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::edge_id_t>::const_type
808 }
809 
811 // MutableGraph concepts
813 
814 template<class V, class E, class VKey, class EKey, class Alloc>
815 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor, bool>
816 add_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor source,
817  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor target,
821  typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::EdgeIterator newEdge = graph.insertEdge(src, tgt, E());
822  return std::make_pair(newEdge->id(), true);
823 }
824 
825 template<class V, class E, class VKey, class EKey, class Alloc>
826 void
827 remove_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor source,
828  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor target,
832  graph.eraseEdges(src, tgt);
833 }
834 
835 template<class V, class E, class VKey, class EKey, class Alloc>
836 void
837 remove_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
839  graph.eraseEdge(graph.findEdge(edge));
840 }
841 
842 template<class Predicate, class V, class E, class VKey, class EKey, class Alloc>
843 void
844 remove_edge_if(Predicate predicate,
847  while (edge != graph.edges().end()) {
848  if (predicate(edge->id())) {
849  edge = graph.eraseEdge(edge);
850  } else {
851  ++edge;
852  }
853  }
854 }
855 
856 template<class Predicate, class V, class E, class VKey, class EKey, class Alloc>
857 void
858 remove_out_edge_if(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
859  Predicate predicate,
863  while (edge != v->outEdges().end()) {
864  if (predicate(edge->id())) {
865  edge = graph.eraseEdge(edge);
866  } else {
867  ++edge;
868  }
869  }
870 }
871 
872 template<class Predicate, class V, class E, class VKey, class EKey, class Alloc>
873 void
874 remove_in_edge_if(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
875  Predicate predicate,
879  while (edge != v->inEdges().end()) {
880  if (predicate(edge->id())) {
881  edge = graph.eraseEdge(edge);
882  } else {
883  ++edge;
884  }
885  }
886 }
887 
888 template<class V, class E, class VKey, class EKey, class Alloc>
889 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
891  return graph.insertVertex(V())->id();
892 }
893 
894 template<class V, class E, class VKey, class EKey, class Alloc>
895 void
896 clear_vertex(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
898  graph.clearEdges(graph.findVertex(vertex));
899 }
900 
901 template<class V, class E, class VKey, class EKey, class Alloc>
902 void
903 remove_vertex(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
905  graph.eraseVertex(graph.findVertex(vertex));
906 }
907 
908 
910 // MutablePropertyGraph concepts
912 
913 template<class V, class E, class VKey, class EKey, class Alloc>
914 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor, bool>
915 add_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor source,
916  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor target,
917  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_property_type const &pval,
921  typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::EdgeIterator newEdge = graph.insertEdge(src, tgt, pval);
922  return std::make_pair(newEdge->id(), true);
923 }
924 
925 template<class V, class E, class VKey, class EKey, class Alloc>
926 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
927 add_vertex(const typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_property_type &pval,
929  return graph.insertVertex(pval)->id();
930 }
931 
932 } // namespace
933 #endif
Sawyer::Container::BitVectorSupport::get
bool get(const Word *words, size_t idx)
Return a single bit.
Definition: BitVectorSupport.h:384
Sawyer::Boost::ConstVertexIdPropertyMap
Definition: GraphBoost.h:306
Sawyer::Container::Graph
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
Sawyer::Container::Graph::nEdges
size_t nEdges() const
Total number of edges.
Definition: Graph.h:1686
Sawyer::Container::Graph::VertexValue
V VertexValue
User-level data associated with vertices.
Definition: Graph.h:627
Sawyer::Container::Graph::Vertex::outEdges
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
Definition: Graph.h:1240
Sawyer::Container::Graph::Edge::id
const size_t & id() const
Unique edge ID number.
Definition: Graph.h:1135
Sawyer::Container::Graph::Vertex::id
const size_t & id() const
Unique vertex ID number.
Definition: Graph.h:1208
Sawyer::Container::Graph::nVertices
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1676
Sawyer::Container::Graph::eraseEdges
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1854
Sawyer::Boost::vertex_id_t
Definition: GraphBoost.h:341
Sawyer::Container::Graph::ConstVertexIterator
Bidirectional vertex node iterator.
Definition: Graph.h:1042
Sawyer::Boost::ConstEdgePropertyMap
Definition: GraphBoost.h:291
Sawyer::Boost::EdgeOuterIterator
Definition: GraphBoost.h:168
Sawyer::Container::Graph::findVertex
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition: Graph.h:1507
Sawyer::Boost::ConstEdgeIdPropertyMap
Definition: GraphBoost.h:320
Sawyer::Boost::VertexPropertyMap
Definition: GraphBoost.h:234
Sawyer::Container::Graph::vertices
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1460
Sawyer::Container::Graph::edges
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
Definition: Graph.h:1569
Sawyer::Container::Graph::findEdge
EdgeIterator findEdge(size_t id)
Finds the edge with specified ID number.
Definition: Graph.h:1616
Sawyer::Container::Graph::EdgeValue
E EdgeValue
User-level data associated with edges.
Definition: Graph.h:628
Sawyer::Boost::ConstVertexOuterIterator
Definition: GraphBoost.h:139
Sawyer::Container::Graph::eraseVertex
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1900
Sawyer::Container::Graph::ConstEdgeIterator
Bidirectional edge node iterator.
Definition: Graph.h:943
Sawyer::Boost::ConstVertexPropertyMap
Definition: GraphBoost.h:255
Sawyer::Boost::EdgePropertyMap
Definition: GraphBoost.h:270
Sawyer::Container::Graph::eraseEdge
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1802
Sawyer::Container::Graph::Vertex::inEdges
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
Definition: Graph.h:1219
Sawyer::Boost::VertexOuterIterator
Definition: GraphBoost.h:111
Sawyer::Container::Graph::VertexIterator
Bidirectional vertex node iterator.
Definition: Graph.h:1021
Sawyer
Name space for the entire library.
Definition: Access.h:13
Sawyer::Container::Graph::EdgeIterator
Bidirectional edge node iterator.
Definition: Graph.h:920
Sawyer::Boost::edge_id_t
Definition: GraphBoost.h:345
Sawyer::Container::Graph::insertEdge
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1742
Sawyer::Boost::edge_value_t
Definition: GraphBoost.h:337
sg
This namespace contains template functions that operate on the ROSE AST.
Definition: sageFunctors.h:15
Sawyer::Container::Graph::insertVertex
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
Definition: Graph.h:1712
Sawyer::Boost::vertex_value_t
Definition: GraphBoost.h:334
Sawyer::Boost::sawyerGraphToBoostGraph
void sawyerGraphToBoostGraph(const SawyerGraph &sg, BoostGraph &bg)
Convert a Sawyer graph to a Boost graph.
Definition: GraphBoost.h:83
Sawyer::Boost::ConstEdgeOuterIterator
Definition: GraphBoost.h:196
Sawyer::Container::Graph::clearEdges
void clearEdges()
Erase all edges, but leave all vertices.
Definition: Graph.h:1920