author | hgs |
Thu, 14 Oct 2010 14:15:50 +0530 | |
changeset 72 | 403e7f6ed6c5 |
parent 0 | e4d67989cc36 |
permissions | -rw-r--r-- |
0
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
1 |
//======================================================================= |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
2 |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
3 |
// Copyright 2006 The Trustees of Indiana University. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
4 |
// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
5 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
6 |
// |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
7 |
// Distributed under the Boost Software License, Version 1.0. (See |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
8 |
// accompanying file LICENSE_1_0.txt or copy at |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
9 |
// http://www.boost.org/LICENSE_1_0.txt) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
10 |
//======================================================================= |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
11 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
12 |
// The mutating functions (add_edge, etc.) were added by Vladimir Prus. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
13 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
14 |
#ifndef BOOST_VECTOR_AS_GRAPH_HPP |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
15 |
#define BOOST_VECTOR_AS_GRAPH_HPP |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
16 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
17 |
#include <cassert> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
18 |
#include <utility> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
19 |
#include <vector> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
20 |
#include <cstddef> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
21 |
#include <boost/iterator.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
22 |
#include <boost/graph/graph_traits.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
23 |
#include <boost/pending/integer_range.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
24 |
#include <boost/property_map.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
25 |
#include <boost/graph/properties.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
26 |
#include <algorithm> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
27 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
28 |
/* |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
29 |
This module implements the VertexListGraph concept using a |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
30 |
std::vector as the "back-bone" of the graph (the vector *is* the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
31 |
graph object). The edge-lists type of the graph is templated, so the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
32 |
user can choose any STL container, so long as the value_type of the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
33 |
container is convertible to the size_type of the vector. For now any |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
34 |
graph properties must be stored seperately. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
35 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
36 |
This module requires the C++ compiler to support partial |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
37 |
specialization for the graph_traits class, so this is not portable |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
38 |
to VC++. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
39 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
40 |
*/ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
41 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
42 |
#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
43 |
#error The vector-as-graph module requires a compiler that supports partial specialization |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
44 |
#endif |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
45 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
46 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
47 |
namespace boost { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
48 |
namespace detail { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
49 |
template <class EdgeList> struct val_out_edge_ret; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
50 |
template <class EdgeList> struct val_out_edge_iter; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
51 |
template <class EdgeList> struct val_edge; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
52 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
53 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
54 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
55 |
#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
56 |
namespace boost { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
57 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
58 |
struct vector_as_graph_traversal_tag |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
59 |
: public vertex_list_graph_tag, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
60 |
public adjacency_graph_tag, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
61 |
public incidence_graph_tag { }; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
62 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
63 |
template <class EdgeList> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
64 |
struct graph_traits< std::vector<EdgeList> > |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
65 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
66 |
typedef typename EdgeList::value_type V; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
67 |
typedef V vertex_descriptor; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
68 |
typedef typename detail::val_edge<EdgeList>::type edge_descriptor; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
69 |
typedef typename EdgeList::const_iterator adjacency_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
70 |
typedef typename detail::val_out_edge_iter<EdgeList>::type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
71 |
out_edge_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
72 |
typedef void in_edge_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
73 |
typedef void edge_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
74 |
typedef typename integer_range<V>::iterator vertex_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
75 |
typedef directed_tag directed_category; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
76 |
typedef allow_parallel_edge_tag edge_parallel_category; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
77 |
typedef vector_as_graph_traversal_tag traversal_category; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
78 |
typedef typename std::vector<EdgeList>::size_type vertices_size_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
79 |
typedef void edges_size_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
80 |
typedef typename EdgeList::size_type degree_size_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
81 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
82 |
template <class EdgeList> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
83 |
struct edge_property_type< std::vector<EdgeList> > |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
84 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
85 |
typedef void type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
86 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
87 |
template <class EdgeList> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
88 |
struct vertex_property_type< std::vector<EdgeList> > |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
89 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
90 |
typedef void type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
91 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
92 |
template <class EdgeList> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
93 |
struct graph_property_type< std::vector<EdgeList> > |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
94 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
95 |
typedef void type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
96 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
97 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
98 |
#endif |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
99 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
100 |
namespace boost { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
101 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
102 |
namespace detail { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
103 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
104 |
// "val" is short for Vector Adjacency List |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
105 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
106 |
template <class EdgeList> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
107 |
struct val_edge |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
108 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
109 |
typedef typename EdgeList::value_type V; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
110 |
typedef std::pair<V,V> type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
111 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
112 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
113 |
// need rewrite this using boost::iterator_adaptor |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
114 |
template <class V, class Iter> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
115 |
class val_out_edge_iterator |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
116 |
: public boost::iterator<std::input_iterator_tag, std::pair<V,V>, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
117 |
std::ptrdiff_t, std::pair<V,V>*, const std::pair<V,V> > |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
118 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
119 |
typedef val_out_edge_iterator self; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
120 |
typedef std::pair<V,V> Edge; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
121 |
public: |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
122 |
val_out_edge_iterator() { } |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
123 |
val_out_edge_iterator(V s, Iter i) : _source(s), _iter(i) { } |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
124 |
Edge operator*() const { return Edge(_source, *_iter); } |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
125 |
self& operator++() { ++_iter; return *this; } |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
126 |
self operator++(int) { self t = *this; ++_iter; return t; } |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
127 |
bool operator==(const self& x) const { return _iter == x._iter; } |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
128 |
bool operator!=(const self& x) const { return _iter != x._iter; } |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
129 |
protected: |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
130 |
V _source; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
131 |
Iter _iter; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
132 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
133 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
134 |
template <class EdgeList> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
135 |
struct val_out_edge_iter |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
136 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
137 |
typedef typename EdgeList::value_type V; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
138 |
typedef typename EdgeList::const_iterator Iter; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
139 |
typedef val_out_edge_iterator<V,Iter> type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
140 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
141 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
142 |
template <class EdgeList> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
143 |
struct val_out_edge_ret |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
144 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
145 |
typedef typename val_out_edge_iter<EdgeList>::type IncIter; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
146 |
typedef std::pair<IncIter,IncIter> type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
147 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
148 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
149 |
} // namesapce detail |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
150 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
151 |
template <class EdgeList, class Alloc> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
152 |
typename detail::val_out_edge_ret<EdgeList>::type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
153 |
out_edges(typename EdgeList::value_type v, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
154 |
const std::vector<EdgeList, Alloc>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
155 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
156 |
typedef typename detail::val_out_edge_iter<EdgeList>::type Iter; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
157 |
typedef typename detail::val_out_edge_ret<EdgeList>::type return_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
158 |
return return_type(Iter(v, g[v].begin()), Iter(v, g[v].end())); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
159 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
160 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
161 |
template <class EdgeList, class Alloc> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
162 |
typename EdgeList::size_type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
163 |
out_degree(typename EdgeList::value_type v, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
164 |
const std::vector<EdgeList, Alloc>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
165 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
166 |
return g[v].size(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
167 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
168 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
169 |
template <class EdgeList, class Alloc> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
170 |
std::pair<typename EdgeList::const_iterator, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
171 |
typename EdgeList::const_iterator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
172 |
adjacent_vertices(typename EdgeList::value_type v, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
173 |
const std::vector<EdgeList, Alloc>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
174 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
175 |
return std::make_pair(g[v].begin(), g[v].end()); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
176 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
177 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
178 |
// source() and target() already provided for pairs in graph_traits.hpp |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
179 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
180 |
template <class EdgeList, class Alloc> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
181 |
std::pair<typename boost::integer_range<typename EdgeList::value_type> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
182 |
::iterator, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
183 |
typename boost::integer_range<typename EdgeList::value_type> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
184 |
::iterator > |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
185 |
vertices(const std::vector<EdgeList, Alloc>& v) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
186 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
187 |
typedef typename boost::integer_range<typename EdgeList::value_type> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
188 |
::iterator Iter; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
189 |
return std::make_pair(Iter(0), Iter(v.size())); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
190 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
191 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
192 |
template <class EdgeList, class Alloc> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
193 |
typename std::vector<EdgeList, Alloc>::size_type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
194 |
num_vertices(const std::vector<EdgeList, Alloc>& v) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
195 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
196 |
return v.size(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
197 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
198 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
199 |
template<class EdgeList, class Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
200 |
typename std::pair<typename detail::val_edge<EdgeList>::type, bool> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
201 |
add_edge(typename EdgeList::value_type u, typename EdgeList::value_type v, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
202 |
std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
203 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
204 |
typedef typename detail::val_edge<EdgeList>::type edge_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
205 |
g[u].insert(g[u].end(), v); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
206 |
return std::make_pair(edge_type(u, v), true); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
207 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
208 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
209 |
template<class EdgeList, class Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
210 |
typename std::pair<typename detail::val_edge<EdgeList>::type, bool> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
211 |
edge(typename EdgeList::value_type u, typename EdgeList::value_type v, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
212 |
std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
213 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
214 |
typedef typename detail::val_edge<EdgeList>::type edge_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
215 |
typename EdgeList::iterator i = g[u].begin(), end = g[u].end(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
216 |
for (; i != end; ++i) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
217 |
if (*i == v) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
218 |
return std::make_pair(edge_type(u, v), true); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
219 |
return std::make_pair(edge_type(), false); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
220 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
221 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
222 |
template<class EdgeList, class Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
223 |
void |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
224 |
remove_edge(typename EdgeList::value_type u, typename EdgeList::value_type v, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
225 |
std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
226 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
227 |
typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
228 |
if (i != g[u].end()) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
229 |
g[u].erase(i, g[u].end()); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
230 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
231 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
232 |
template<class EdgeList, class Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
233 |
void |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
234 |
remove_edge(typename detail::val_edge<EdgeList>::type e, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
235 |
std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
236 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
237 |
typename EdgeList::value_type u, v; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
238 |
u = e.first; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
239 |
v = e.second; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
240 |
// FIXME: edge type does not fully specify the edge to be deleted |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
241 |
typename EdgeList::iterator i = std::remove(g[u].begin(), g[u].end(), v); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
242 |
if (i != g[u].end()) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
243 |
g[u].erase(i, g[u].end()); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
244 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
245 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
246 |
template<class EdgeList, class Allocator, class Predicate> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
247 |
void |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
248 |
remove_edge_if(Predicate p, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
249 |
std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
250 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
251 |
for (std::size_t u = 0; u < g.size(); ++u) { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
252 |
// Oops! gcc gets internal compiler error on compose_....... |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
253 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
254 |
typedef typename EdgeList::iterator iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
255 |
iterator b = g[u].begin(), e = g[u].end(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
256 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
257 |
if (!g[u].empty()) { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
258 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
259 |
for(; b != e;) { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
260 |
if (p(std::make_pair(u, *b))) { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
261 |
--e; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
262 |
if (b == e) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
263 |
break; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
264 |
else |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
265 |
iter_swap(b, e); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
266 |
} else { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
267 |
++b; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
268 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
269 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
270 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
271 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
272 |
if (e != g[u].end()) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
273 |
g[u].erase(e, g[u].end()); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
274 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
275 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
276 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
277 |
template<class EdgeList, class Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
278 |
typename EdgeList::value_type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
279 |
add_vertex(std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
280 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
281 |
g.resize(g.size()+1); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
282 |
return g.size()-1; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
283 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
284 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
285 |
template<class EdgeList, class Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
286 |
void |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
287 |
clear_vertex(typename EdgeList::value_type u, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
288 |
std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
289 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
290 |
g[u].clear(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
291 |
for (std::size_t i = 0; i < g.size(); ++i) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
292 |
remove_edge(i, u, g); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
293 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
294 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
295 |
template<class EdgeList, class Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
296 |
void |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
297 |
remove_vertex(typename EdgeList::value_type u, |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
298 |
std::vector<EdgeList, Allocator>& g) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
299 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
300 |
typedef typename EdgeList::iterator iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
301 |
clear_vertex(u, g); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
302 |
g.erase(g.begin() + u); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
303 |
for (std::size_t i = 0; i < g.size(); ++i) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
304 |
for ( iterator it = g[i].begin(); it != g[i].end(); ++it ) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
305 |
// after clear_vertex *it is never equal to u |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
306 |
if ( *it > u ) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
307 |
--*it; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
308 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
309 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
310 |
template<typename EdgeList, typename Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
311 |
struct property_map<std::vector<EdgeList, Allocator>, vertex_index_t> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
312 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
313 |
typedef identity_property_map type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
314 |
typedef type const_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
315 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
316 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
317 |
template<typename EdgeList, typename Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
318 |
identity_property_map |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
319 |
get(vertex_index_t, const std::vector<EdgeList, Allocator>&) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
320 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
321 |
return identity_property_map(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
322 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
323 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
324 |
template<typename EdgeList, typename Allocator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
325 |
identity_property_map |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
326 |
get(vertex_index_t, std::vector<EdgeList, Allocator>&) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
327 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
328 |
return identity_property_map(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
329 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
330 |
} // namespace boost |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
331 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
332 |
#endif // BOOST_VECTOR_AS_GRAPH_HPP |