ROSE  0.9.9.139
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>
111 class VertexOuterIterator: public std::iterator<std::bidirectional_iterator_tag, const size_t> {
112 private:
114  BaseIter base_;
115 public:
117  VertexOuterIterator(const VertexOuterIterator &other): base_(other.base_) {}
118  explicit VertexOuterIterator(const BaseIter &base): base_(base) {}
119  VertexOuterIterator& operator=(const VertexOuterIterator &other) { base_ = other.base_; return *this; }
120  VertexOuterIterator& operator++() { ++base_; return *this; }
121  VertexOuterIterator& operator--() { --base_; return *this; }
122  VertexOuterIterator operator++(int) { VertexOuterIterator old = *this; ++base_; return old; }
123  VertexOuterIterator operator--(int) { VertexOuterIterator old = *this; --base_; return old; }
124  bool operator==(const VertexOuterIterator &other) const { return base_ == other.base_; }
125  bool operator!=(const VertexOuterIterator &other) const { return base_ != other.base_; }
126  const size_t& operator*() const { return base_->id(); }
127  // size_t* operator->() const; //no methods defined on size_t, so not needed
128 };
129 
130 template<class V, class E, class VKey, class EKey, class Alloc>
131 class ConstVertexOuterIterator: public std::iterator<std::bidirectional_iterator_tag, const size_t> {
132 private:
134  BaseIter base_;
135 public:
137  ConstVertexOuterIterator(const ConstVertexOuterIterator &other): base_(other.base_) {}
139  explicit ConstVertexOuterIterator(const BaseIter &base): base_(base) {}
140  ConstVertexOuterIterator& operator=(const ConstVertexOuterIterator &other) { base_ = other.base_; return *this; }
141  ConstVertexOuterIterator& operator++() { ++base_; return *this; }
142  ConstVertexOuterIterator& operator--() { --base_; return *this; }
143  ConstVertexOuterIterator operator++(int) { ConstVertexOuterIterator old = *this; ++base_; return old; }
144  ConstVertexOuterIterator operator--(int) { ConstVertexOuterIterator old = *this; --base_; return old; }
145  bool operator==(const ConstVertexOuterIterator &other) const { return base_ == other.base_; }
146  bool operator!=(const ConstVertexOuterIterator &other) const { return base_ != other.base_; }
147  const size_t& operator*() const { return base_->id(); }
148  // size_t* operator->() const; //no methods defined on size_t, so not needed
149 };
150 
151 template<class V, class E, class VKey, class EKey, class Alloc>
152 class EdgeOuterIterator: public std::iterator<std::bidirectional_iterator_tag, const size_t> {
153 private:
155  BaseIter base_;
156 public:
157  EdgeOuterIterator() {}
158  EdgeOuterIterator(const EdgeOuterIterator &other): base_(other.base_) {}
159  explicit EdgeOuterIterator(const BaseIter &base): base_(base) {}
160  EdgeOuterIterator& operator=(const EdgeOuterIterator &other) { base_ = other.base_; return *this; }
161  EdgeOuterIterator& operator++() { ++base_; return *this; }
162  EdgeOuterIterator& operator--() { --base_; return *this; }
163  EdgeOuterIterator operator++(int) { EdgeOuterIterator old = *this; ++base_; return old; }
164  EdgeOuterIterator operator--(int) { EdgeOuterIterator old = *this; --base_; return old; }
165  bool operator==(const EdgeOuterIterator &other) const { return base_ == other.base_; }
166  bool operator!=(const EdgeOuterIterator &other) const { return base_ != other.base_; }
167  const size_t& operator*() const { return base_->id(); }
168  // size_t* operator->() const; //no methods defined on size_t, so not needed
169 };
170 
171 template<class V, class E, class VKey, class EKey, class Alloc>
172 class ConstEdgeOuterIterator: public std::iterator<std::bidirectional_iterator_tag, const size_t> {
173 private:
175  BaseIter base_;
176 public:
178  ConstEdgeOuterIterator(const ConstEdgeOuterIterator &other): base_(other.base_) {}
179  ConstEdgeOuterIterator(const EdgeOuterIterator<V, E, VKey, EKey, Alloc> &other): base_(other.base_) {}
180  explicit ConstEdgeOuterIterator(const BaseIter &base): base_(base) {}
181  ConstEdgeOuterIterator& operator=(const ConstEdgeOuterIterator &other) { base_ = other.base_; return *this; }
182  ConstEdgeOuterIterator& operator++() { ++base_; return *this; }
183  ConstEdgeOuterIterator& operator--() { --base_; return *this; }
184  ConstEdgeOuterIterator operator++(int) { ConstEdgeOuterIterator old = *this; ++base_; return old; }
185  ConstEdgeOuterIterator operator--(int) { ConstEdgeOuterIterator old = *this; --base_; return old; }
186  bool operator==(const ConstEdgeOuterIterator &other) const { return base_ == other.base_; }
187  bool operator!=(const ConstEdgeOuterIterator &other) const { return base_ != other.base_; }
188  const size_t& operator*() const { return base_->id(); }
189  // size_t* operator->() const; //no methods defined on size_t, so not needed
190 };
191 
193 // Internal properties
195 
196 // External properties can use the BGL mechanisms that are already defined, but we need something special for internal
197 // properties. A BGL property map is simply a class that provides a lookup mechanism when given a vertex or edge descriptor, so
198 // all we need is a class that will look up the user-supplied value for a vertex or edge.
199 
200 // User-defined value attached to a vertex.
201 template<class Graph>
203  Graph &graph_;
204 public:
205  typedef typename Graph::VertexValue ValueType;
206  VertexPropertyMap(Graph &graph): graph_(graph) {}
207  ValueType get(size_t vertexId) const {
208  return graph_.findVertex(vertexId)->value();
209  }
210  void put(size_t vertexId, const ValueType &value) {
211  graph_.findVertex(vertexId)->value() = value;
212  }
213  ValueType& at(size_t vertexId) {
214  return graph_.findVertex(vertexId)->value();
215  }
216  const ValueType& at(size_t vertexId) const {
217  return graph_.findVertex(vertexId)->value();
218  }
219 };
220 
221 // Const user-defined value attached to a vertex.
222 template<class Graph>
224  const Graph &graph_;
225 public:
226  typedef typename Graph::VertexValue ValueType;
227  ConstVertexPropertyMap(const Graph &graph): graph_(graph) {}
228  ValueType get(size_t vertexId) const {
229  return graph_.findVertex(vertexId)->value();
230  }
231  const ValueType& at(size_t vertexId) const {
232  return graph_.findVertex(vertexId)->value();
233  }
234 };
235 
236 // User-defined value attached to an edge. Graph is any non-const Sawyer::Container::Graph<>
237 template<class Graph>
239  Graph &graph_;
240 public:
241  typedef typename Graph::EdgeValue ValueType;
242  EdgePropertyMap(Graph &graph): graph_(graph) {}
243  ValueType get(size_t edgeId) const {
244  return graph_.findEdge(edgeId)->value();
245  }
246  void put(size_t edgeId, const ValueType &value) {
247  graph_.findEdge(edgeId)->value() = value;
248  }
249  ValueType& at(size_t edgeId) {
250  return graph_.findEdge(edgeId)->value();
251  }
252  const ValueType& at(size_t edgeId) const {
253  return graph_.findEdge(edgeId)->value();
254  }
255 };
256 
257 // Const user-defined value attached to a vertex. Graph is any const Sawyer::Container::Graph<>
258 template<class Graph>
260  const Graph &graph_;
261 public:
262  typedef typename Graph::EdgeValue ValueType;
263  ConstEdgePropertyMap(const Graph &graph): graph_(graph) {}
264  ValueType get(size_t edgeId) const {
265  return graph_.findEdge(edgeId)->value();
266  }
267  const ValueType& at(size_t edgeId) const {
268  return graph_.findEdge(edgeId)->value();
269  }
270 };
271 
272 // The ID (index) associated with each vertex. This is a read-only property since ID numbers are managed by the graph.
273 template<class Graph>
275  const Graph &graph_;
276 public:
277  ConstVertexIdPropertyMap(const Graph &graph): graph_(graph) {}
278  size_t get(size_t vertexId) const {
279  return vertexId;
280  }
281  const size_t& at(size_t vertexId) const {
282  return graph_.findVertex(vertexId)->id();
283  }
284 };
285 
286 // The ID (index) associated with each edge. This is a read-only property since ID numbers are managed by the graph.
287 template<class Graph>
289  const Graph &graph_;
290 public:
291  ConstEdgeIdPropertyMap(const Graph &graph): graph_(graph) {}
292  size_t get(size_t edgeId) const {
293  return edgeId;
294  }
295  const size_t& at(size_t edgeId) const {
296  return graph_.findEdge(edgeId)->id();
297  }
298 };
299 
300 // Tags for the user-defined vertex or edge value property. These are to access the user-defined data associated with each
301 // vertex are value corresponding to the "V" and "E" template parameters for Sawyer::Container::Graph
303  typedef boost::vertex_property_tag kind;
304 };
305 struct edge_value_t {
306  typedef boost::edge_property_tag kind;
307 };
308 
309 struct vertex_id_t {
310  typedef boost::vertex_property_tag kind;
311 };
312 
313 struct edge_id_t {
314  typedef boost::edge_property_tag kind;
315 };
316 
317 } // namespace
318 } // namespace
319 
320 
325 namespace boost {
326 
327 
329 // BGL trait classes
331 
332 #if 0 // [Robb P. Matzke 2014-05-23]: Temporarily disabled because it matches too much.
333 // Including this file with boost/wave/util/cpp_include_paths.hpp causes problems because code like this:
334 // using boost::multi_index::get;
335 // return get<from>(pragma_once_files).find(filename) != pragma_once_files.end();
336 // in wave matches these property_traits. E.g.,
337 // boost::property_traits<Sawyer::Boost::VertexPropertyMap<boost::wave::util::from> >
338 // and of course boost::wave::util::from has no VertexValue type. Someone with more boost property map and template
339 // programming experience is needed. For now, users should instantiate their own Sawyer::Boost::VertexPropertyMap<> class
340 // and use it to make their own specialization of boost::property_traits<>.
341 
342 template<class Graph>
343 struct property_traits<Sawyer::Boost::VertexPropertyMap<Graph> > {
344  typedef typename Graph::VertexValue value_type;
345  typedef typename Graph::VertexValue &reference;
346  typedef size_t key_type; // vertex ID number
347  typedef boost::read_write_property_map_tag category;
348 };
349 
350 template<class Graph>
351 struct property_traits<Sawyer::Boost::ConstVertexPropertyMap<Graph> > {
352  typedef typename Graph::VertexValue value_type;
353  typedef typename Graph::VertexValue const &reference;
354  typedef size_t key_type; // vertex ID number
355  typedef boost::readable_property_map_tag category;
356 };
357 
358 template<class Graph>
359 struct property_traits<Sawyer::Boost::EdgePropertyMap<Graph> > {
360  typedef typename Graph::EdgeValue value_type;
361  typedef typename Graph::EdgeValue &reference;
362  typedef size_t key_type; // edge ID number
363  typedef boost::read_write_property_map_tag category;
364 };
365 
366 template<class Graph>
367 struct property_traits<Sawyer::Boost::ConstEdgePropertyMap<Graph> > {
368  typedef typename Graph::EdgeValue value_type;
369  typedef typename Graph::EdgeValue const &reference;
370  typedef size_t key_type; // edge ID number
371  typedef boost::readable_property_map_tag category;
372 };
373 
374 template<class Graph>
375 struct property_traits<Sawyer::Boost::ConstVertexIdPropertyMap<Graph> > {
376  typedef size_t value_type;
377  typedef const size_t &reference;
378  typedef size_t key_type; // vertex ID number
379  typedef boost::readable_property_map_tag category;
380 };
381 
382 template<class Graph>
383 struct property_traits<Sawyer::Boost::ConstEdgeIdPropertyMap<Graph> > {
384  typedef size_t value_type;
385  typedef const size_t &reference;
386  typedef size_t key_type; // vertex ID number
387  typedef boost::readable_property_map_tag category;
388 };
389 
390 #endif
391 
392 
393 template<class Graph>
394 struct property_map<Graph, Sawyer::Boost::vertex_value_t> {
397 };
398 
399 template<class Graph>
400 struct property_map<Graph, Sawyer::Boost::edge_value_t> {
403 };
404 
405 template<class Graph>
406 struct property_map<Graph, Sawyer::Boost::vertex_id_t> {
409 };
410 
411 template<class Graph>
412 struct property_map<Graph, Sawyer::Boost::edge_id_t> {
415 };
416 
418 // Access members of property maps
420 
421 //--- vertex value ---
422 
423 template<class Graph>
424 typename Graph::VertexValue&
425 get(Sawyer::Boost::VertexPropertyMap<Graph> &pmap, size_t key) {
426  return pmap.at(key);
427 }
428 
429 template<class Graph>
430 const typename Graph::VertexValue&
431 get(const Sawyer::Boost::ConstVertexPropertyMap<Graph> &pmap, size_t key) {
432  return pmap.at(key);
433 }
434 
435 template<class Graph>
436 void
437 put(Sawyer::Boost::VertexPropertyMap<Graph> &pmap, size_t key, const typename Graph::VertexValue &value) {
438  pmap.at(key) = value;
439 }
440 
441 //--- edge value ---
442 
443 template<class Graph>
444 typename Graph::EdgeValue&
445 get(Sawyer::Boost::EdgePropertyMap<Graph> &pmap, size_t key) {
446  return pmap.at(key);
447 }
448 
449 template<class Graph>
450 typename Graph::EdgeValue&
451 get(const Sawyer::Boost::ConstEdgePropertyMap<Graph> &pmap, size_t key) {
452  return pmap.at(key);
453 }
454 
455 template<class Graph>
456 void
457 put(Sawyer::Boost::EdgePropertyMap<Graph> &pmap, size_t key,
458  const typename Graph::EdgeValue &value) {
459  pmap.at(key) = value;
460 }
461 
462 //--- vertex and edge ID (indices) ---
463 
464 template<class Graph>
465 const size_t&
466 get(const Sawyer::Boost::ConstVertexIdPropertyMap<Graph> &pmap, size_t key) {
467  return pmap.at(key);
468 }
469 
470 template<class Graph>
471 const size_t&
472 get(const Sawyer::Boost::ConstEdgeIdPropertyMap<Graph> &pmap, size_t key) {
473  return pmap.at(key);
474 }
475 
476 
478 // Graph traits
480 
481 template<class V, class E, class VKey, class EKey, class Alloc>
482 struct graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> > {
483  typedef bidirectional_graph_tag traversal_category;
484 
485  // Graph concepts
486  typedef size_t vertex_descriptor;
487  typedef size_t edge_descriptor;
488  typedef directed_tag directed_category;
489  typedef allow_parallel_edge_tag edge_parallel_category;
490  static size_t null_vertex() { return (size_t)(-1); }
491 
492  // VertexListGraph concepts
494  typedef size_t vertices_size_type;
495 
496  // EdgeListGraph concepts
498  typedef size_t edges_size_type;
499 
500  // IncidenceGraph concepts
502  typedef size_t degree_size_type;
503 
504  // BidirectionalGraph concepts
506 
507  // MutablePropertyGraph concepts
508  typedef typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::VertexValue vertex_property_type;
509  typedef typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::EdgeValue edge_property_type;
510 };
511 
512 template<class V, class E, class VKey, class EKey, class Alloc>
513 struct graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> > {
514  typedef bidirectional_graph_tag traversal_category;
515 
516  // Graph concepts
517  typedef size_t vertex_descriptor;
518  typedef size_t edge_descriptor;
519  typedef directed_tag directed_category;
520  typedef allow_parallel_edge_tag edge_parallel_category;
521 
522  // VertexListGraph concepts
524  typedef size_t vertices_size_type;
525 
526  // EdgeListGraph concepts
528  typedef size_t edges_size_type;
529 
530  // IncidenceGraph concepts
532  typedef size_t degree_size_type;
533 
534  // BidirectionalGraph concepts
536 };
537 
539 // Graph concepts
541 
542 
543 // BGL has a global entity that indicates no-vertex, but Sawyer doesn't--it has STL-like end() iterators.
544 template<class V, class E, class VKey, class EKey, class Alloc>
545 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
546 null_vertex() {
547  return (size_t)(-1);
548 }
549 
550 template<class V, class E, class VKey, class EKey, class Alloc>
551 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
552 null_vertex() {
553  return (size_t)(-1);
554 }
555 
557 // VertexListGraph concepts
559 
560 template<class V, class E, class VKey, class EKey, class Alloc>
561 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator,
562  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator>
564  return std::make_pair(Sawyer::Boost::VertexOuterIterator<V, E, VKey, EKey, Alloc>(graph.vertices().begin()),
566 }
567 
568 template<class V, class E, class VKey, class EKey, class Alloc>
569 std::pair<typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator,
570  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_iterator>
572  return std::make_pair(Sawyer::Boost::ConstVertexOuterIterator<V, E, VKey, EKey, Alloc>(graph.vertices().begin()),
574 }
575 
576 template<class V, class E, class VKey, class EKey, class Alloc>
577 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertices_size_type
579  return graph.nVertices();
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> >::vertices_size_type
584 num_vertices(const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> &graph) {
585  return graph.nVertices();
586 }
587 
589 // EdgeListGraph 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> >::edge_iterator,
594  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_iterator>
596  return std::make_pair(Sawyer::Boost::EdgeOuterIterator<V, E, VKey, EKey, Alloc>(graph.edges().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> >::edge_iterator,
602  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_iterator>
604  return std::make_pair(Sawyer::Boost::ConstEdgeOuterIterator<V, E, VKey, EKey, Alloc>(graph.edges().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> >::edges_size_type
611  return graph.nEdges();
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> >::edges_size_type
617  return graph.nEdges();
618 }
619 
621 // IncidenceGraph concepts
623 
624 template<class V, class E, class VKey, class EKey, class Alloc>
625 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
626 source(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
628  return graph.findEdge(edge)->source()->id();
629 }
630 
631 template<class V, class E, class VKey, class EKey, class Alloc>
632 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
633 source(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
635  return graph.findEdge(edge)->source()->id();
636 }
637 
638 template<class V, class E, class VKey, class EKey, class Alloc>
639 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
640 target(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
642  return graph.findEdge(edge)->target()->id();
643 }
644 
645 template<class V, class E, class VKey, class EKey, class Alloc>
646 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
647 target(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
649  return graph.findEdge(edge)->target()->id();
650 }
651 
652 template<class V, class E, class VKey, class EKey, class Alloc>
653 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator,
654  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator>
655 out_edges(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
658  return std::make_pair(Sawyer::Boost::EdgeOuterIterator<V, E, VKey, EKey, Alloc>(v->outEdges().begin()),
660 }
661 
662 template<class V, class E, class VKey, class EKey, class Alloc>
663 std::pair<typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator,
664  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::out_edge_iterator>
665 out_edges(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
670 }
671 
672 template<class V, class E, class VKey, class EKey, class Alloc>
673 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
674 out_degree(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
676  return graph.findVertex(vertex)->nOutEdges();
677 }
678 
679 template<class V, class E, class VKey, class EKey, class Alloc>
680 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
681 out_degree(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
683  return graph.findVertex(vertex)->nOutEdges();
684 }
685 
687 // BidirectionalGraph concepts
689 
690 template<class V, class E, class VKey, class EKey, class Alloc>
691 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator,
692  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator>
693 in_edges(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
696  return std::make_pair(Sawyer::Boost::EdgeOuterIterator<V, E, VKey, EKey, Alloc>(v->inEdges().begin()),
698 }
699 
700 template<class V, class E, class VKey, class EKey, class Alloc>
701 std::pair<typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator,
702  typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::in_edge_iterator>
703 in_edges(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
708 }
709 
710 template<class V, class E, class VKey, class EKey, class Alloc>
711 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
712 in_degree(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
714  return graph.findVertex(vertex)->nInEdges();
715 }
716 
717 template<class V, class E, class VKey, class EKey, class Alloc>
718 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
719 in_degree(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
721  return graph.findVertex(vertex)->nInEdges();
722 }
723 
724 template<class V, class E, class VKey, class EKey, class Alloc>
725 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
726 degree(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
728  return in_degree(vertex) + out_degree(vertex);
729 }
730 
731 template<class V, class E, class VKey, class EKey, class Alloc>
732 typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::degree_size_type
733 degree(typename graph_traits<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
735  return in_degree(vertex) + out_degree(vertex);
736 }
737 
739 // PropertyMapGraph concepts
741 
742 template<class V, class E, class VKey, class EKey, class Alloc>
743 typename property_map<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::vertex_value_t>::type
746 }
747 
748 template<class V, class E, class VKey, class EKey, class Alloc>
749 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::vertex_value_t>::type
750 get(Sawyer::Boost::vertex_value_t, const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> &graph) {
752 }
753 
754 template<class V, class E, class VKey, class EKey, class Alloc>
755 typename property_map<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::edge_value_t>::type
758 }
759 
760 template<class V, class E, class VKey, class EKey, class Alloc>
761 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::edge_value_t>::type
762 get(Sawyer::Boost::edge_value_t, const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> &graph) {
764 }
765 
766 template<class V, class E, class VKey, class EKey, class Alloc>
767 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::vertex_id_t>::type
770 }
771 
772 template<class V, class E, class VKey, class EKey, class Alloc>
773 typename property_map<const Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>, Sawyer::Boost::edge_id_t>::type
776 }
777 
779 // MutableGraph concepts
781 
782 template<class V, class E, class VKey, class EKey, class Alloc>
783 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor, bool>
784 add_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor source,
785  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor target,
789  typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::EdgeIterator newEdge = graph.insertEdge(src, tgt, E());
790  return std::make_pair(newEdge->id(), true);
791 }
792 
793 template<class V, class E, class VKey, class EKey, class Alloc>
794 void
795 remove_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor source,
796  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor target,
800  graph.eraseEdges(src, tgt);
801 }
802 
803 template<class V, class E, class VKey, class EKey, class Alloc>
804 void
805 remove_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor edge,
807  graph.eraseEdge(graph.findEdge(edge));
808 }
809 
810 template<class Predicate, class V, class E, class VKey, class EKey, class Alloc>
811 void
812 remove_edge_if(Predicate predicate,
815  while (edge != graph.edges().end()) {
816  if (predicate(edge->id())) {
817  edge = graph.eraseEdge(edge);
818  } else {
819  ++edge;
820  }
821  }
822 }
823 
824 template<class Predicate, class V, class E, class VKey, class EKey, class Alloc>
825 void
826 remove_out_edge_if(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
827  Predicate predicate,
831  while (edge != v->outEdges().end()) {
832  if (predicate(edge->id())) {
833  edge = graph.eraseEdge(edge);
834  } else {
835  ++edge;
836  }
837  }
838 }
839 
840 template<class Predicate, class V, class E, class VKey, class EKey, class Alloc>
841 void
842 remove_in_edge_if(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
843  Predicate predicate,
847  while (edge != v->inEdges().end()) {
848  if (predicate(edge->id())) {
849  edge = graph.eraseEdge(edge);
850  } else {
851  ++edge;
852  }
853  }
854 }
855 
856 template<class V, class E, class VKey, class EKey, class Alloc>
857 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
859  return graph.insertVertex(V())->id();
860 }
861 
862 template<class V, class E, class VKey, class EKey, class Alloc>
863 void
864 clear_vertex(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
866  graph.clearEdges(graph.findVertex(vertex));
867 }
868 
869 template<class V, class E, class VKey, class EKey, class Alloc>
870 void
871 remove_vertex(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor vertex,
873  graph.eraseVertex(graph.findVertex(vertex));
874 }
875 
876 
878 // MutablePropertyGraph concepts
880 
881 template<class V, class E, class VKey, class EKey, class Alloc>
882 std::pair<typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_descriptor, bool>
883 add_edge(typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor source,
884  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor target,
885  typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::edge_property_type const &pval,
889  typename Sawyer::Container::Graph<V, E, VKey, EKey, Alloc>::EdgeIterator newEdge = graph.insertEdge(src, tgt, pval);
890  return std::make_pair(newEdge->id(), true);
891 }
892 
893 template<class V, class E, class VKey, class EKey, class Alloc>
894 typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_descriptor
895 add_vertex(const typename graph_traits<Sawyer::Container::Graph<V, E, VKey, EKey, Alloc> >::vertex_property_type &pval,
897  return graph.insertVertex(pval)->id();
898 }
899 
900 } // namespace
901 #endif
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
void clearEdges()
Erase all edges, but leave all vertices.
Definition: Graph.h:1914
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
Definition: Graph.h:1706
const size_t & id() const
Unique vertex ID number.
Definition: Graph.h:1202
VertexIterator eraseVertex(const VertexIterator &vertex)
Erases a vertex and its incident edges.
Definition: Graph.h:1894
const size_t & id() const
Unique edge ID number.
Definition: Graph.h:1129
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
size_t nEdges() const
Total number of edges.
Definition: Graph.h:1680
Bidirectional vertex node iterator.
Definition: Graph.h:1015
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
Definition: Graph.h:1213
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1454
void eraseEdges(const VertexIterator &source, const VertexIterator &target)
Erases all edges connecting two vertices.
Definition: Graph.h:1848
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition: Graph.h:1736
Bidirectional vertex node iterator.
Definition: Graph.h:1036
Name space for the entire library.
Definition: Access.h:11
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
Definition: Graph.h:1234
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition: Graph.h:1501
void sawyerGraphToBoostGraph(const SawyerGraph &sg, BoostGraph &bg)
Convert a Sawyer graph to a Boost graph.
Definition: GraphBoost.h:83
EdgeIterator findEdge(size_t id)
Finds the edge with specified ID number.
Definition: Graph.h:1610
Bidirectional edge node iterator.
Definition: Graph.h:937
Bidirectional edge node iterator.
Definition: Graph.h:914
V VertexValue
User-level data associated with vertices.
Definition: Graph.h:627
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
Definition: Graph.h:1563
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition: Graph.h:1796
E EdgeValue
User-level data associated with edges.
Definition: Graph.h:628