|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r82061 - in branches/release: boost/graph boost/graph/detail boost/graph/distributed boost/graph/property_maps boost/pending libs/graph/doc libs/graph/example libs/graph/src libs/graph/test
From: jewillco_at_[hidden]
Date: 2012-12-17 18:59:50
Author: jewillco
Date: 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
New Revision: 82061
URL: http://svn.boost.org/trac/boost/changeset/82061
Log:
Merged Boost.Graph changes from trunk for 1.53
Added:
branches/release/boost/graph/detail/is_distributed_selector.hpp
- copied unchanged from r82010, /trunk/boost/graph/detail/is_distributed_selector.hpp
branches/release/boost/graph/vf2_sub_graph_iso.hpp (contents, props changed)
- copied, changed from r81725, /trunk/boost/graph/vf2_sub_graph_iso.hpp
branches/release/libs/graph/doc/vf2_sub_graph_iso.html (contents, props changed)
- copied, changed from r81725, /trunk/libs/graph/doc/vf2_sub_graph_iso.html
branches/release/libs/graph/example/vf2_sub_graph_iso_example.cpp
- copied, changed from r81725, /trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp
branches/release/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (contents, props changed)
- copied, changed from r81725, /trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp
branches/release/libs/graph/test/vf2_sub_graph_iso_test.cpp
- copied unchanged from r82007, /trunk/libs/graph/test/vf2_sub_graph_iso_test.cpp
Properties modified:
branches/release/boost/graph/ (props changed)
branches/release/boost/graph/adjacency_list.hpp (contents, props changed)
branches/release/boost/graph/astar_search.hpp (contents, props changed)
branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp (contents, props changed)
branches/release/boost/graph/compressed_sparse_row_graph.hpp (contents, props changed)
branches/release/boost/graph/detail/ (props changed)
branches/release/boost/graph/detail/adjacency_list.hpp (contents, props changed)
branches/release/boost/graph/detail/d_ary_heap.hpp (contents, props changed)
branches/release/boost/graph/detail/labeled_graph_traits.hpp (contents, props changed)
branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp (contents, props changed)
branches/release/boost/graph/directed_graph.hpp (contents, props changed)
branches/release/boost/graph/distributed/selector.hpp (contents, props changed)
branches/release/boost/graph/graph_concepts.hpp (contents, props changed)
branches/release/boost/graph/graph_traits.hpp (contents, props changed)
branches/release/boost/graph/graphml.hpp (contents, props changed)
branches/release/boost/graph/kamada_kawai_spring_layout.hpp (contents, props changed)
branches/release/boost/graph/labeled_graph.hpp (contents, props changed)
branches/release/boost/graph/metric_tsp_approx.hpp (contents, props changed)
branches/release/boost/graph/named_graph.hpp (contents, props changed)
branches/release/boost/graph/properties.hpp (contents, props changed)
branches/release/boost/graph/property_maps/constant_property_map.hpp (contents, props changed)
branches/release/boost/graph/reverse_graph.hpp (contents, props changed)
branches/release/boost/graph/tiernan_all_cycles.hpp (contents, props changed)
branches/release/boost/graph/undirected_graph.hpp (contents, props changed)
branches/release/boost/pending/property.hpp (contents, props changed)
branches/release/libs/graph/doc/ (props changed)
branches/release/libs/graph/doc/astar_search.html (contents, props changed)
branches/release/libs/graph/doc/graph_concepts.html (contents, props changed)
branches/release/libs/graph/doc/push_relabel_max_flow.html (contents, props changed)
branches/release/libs/graph/doc/read_graphml.html (contents, props changed)
branches/release/libs/graph/doc/read_graphml.rst (contents, props changed)
branches/release/libs/graph/doc/small_world_generator.html (contents, props changed)
branches/release/libs/graph/doc/table_of_contents.html (contents, props changed)
branches/release/libs/graph/example/ (props changed)
branches/release/libs/graph/example/Jamfile.v2 (contents, props changed)
branches/release/libs/graph/example/astar-cities.cpp (contents, props changed)
branches/release/libs/graph/example/undirected_adjacency_list.cpp (contents, props changed)
branches/release/libs/graph/example/undirected_adjacency_list.expected (contents, props changed)
branches/release/libs/graph/src/graphml.cpp (contents, props changed)
branches/release/libs/graph/test/ (props changed)
Text files modified:
branches/release/boost/graph/adjacency_list.hpp | 1
branches/release/boost/graph/astar_search.hpp | 195 ++++++++++
branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp | 11
branches/release/boost/graph/compressed_sparse_row_graph.hpp | 15
branches/release/boost/graph/detail/adjacency_list.hpp | 10
branches/release/boost/graph/detail/d_ary_heap.hpp | 5
branches/release/boost/graph/detail/labeled_graph_traits.hpp | 4
branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp | 11
branches/release/boost/graph/directed_graph.hpp | 133 +++++--
branches/release/boost/graph/distributed/selector.hpp | 8
branches/release/boost/graph/graph_concepts.hpp | 30 +
branches/release/boost/graph/graph_traits.hpp | 41 +
branches/release/boost/graph/graphml.hpp | 6
branches/release/boost/graph/kamada_kawai_spring_layout.hpp | 4
branches/release/boost/graph/labeled_graph.hpp | 18
branches/release/boost/graph/metric_tsp_approx.hpp | 4
branches/release/boost/graph/named_graph.hpp | 55 ++
branches/release/boost/graph/properties.hpp | 6
branches/release/boost/graph/property_maps/constant_property_map.hpp | 33 +
branches/release/boost/graph/reverse_graph.hpp | 2
branches/release/boost/graph/tiernan_all_cycles.hpp | 6
branches/release/boost/graph/undirected_graph.hpp | 92 ++++
branches/release/boost/graph/vf2_sub_graph_iso.hpp | 341 +++++++-----------
branches/release/boost/pending/property.hpp | 21 +
branches/release/libs/graph/doc/astar_search.html | 85 ++++
branches/release/libs/graph/doc/graph_concepts.html | 2
branches/release/libs/graph/doc/push_relabel_max_flow.html | 2
branches/release/libs/graph/doc/read_graphml.html | 8
branches/release/libs/graph/doc/read_graphml.rst | 7
branches/release/libs/graph/doc/small_world_generator.html | 4
branches/release/libs/graph/doc/table_of_contents.html | 3
branches/release/libs/graph/doc/vf2_sub_graph_iso.html | 722 +++++++++++++++++++--------------------
branches/release/libs/graph/example/Jamfile.v2 | 4
branches/release/libs/graph/example/astar-cities.cpp | 2
branches/release/libs/graph/example/undirected_adjacency_list.cpp | 18
branches/release/libs/graph/example/undirected_adjacency_list.expected | 2
branches/release/libs/graph/example/vf2_sub_graph_iso_example.cpp | 13
branches/release/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp | 92 ----
branches/release/libs/graph/src/graphml.cpp | 18
branches/release/libs/graph/test/Jamfile.v2 | 1
40 files changed, 1228 insertions(+), 807 deletions(-)
Modified: branches/release/boost/graph/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/adjacency_list.hpp (original)
+++ branches/release/boost/graph/adjacency_list.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -188,6 +188,7 @@
} // namespace detail
+ template <typename Selector> struct is_distributed_selector: mpl::false_ {};
//===========================================================================
Modified: branches/release/boost/graph/astar_search.hpp
==============================================================================
--- branches/release/boost/graph/astar_search.hpp (original)
+++ branches/release/boost/graph/astar_search.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -22,9 +22,12 @@
#include <boost/graph/relax.hpp>
#include <boost/graph/exception.hpp>
#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/vector_property_map.hpp>
+#include <boost/property_map/function_property_map.hpp>
#include <boost/concept/assert.hpp>
namespace boost {
@@ -159,8 +162,9 @@
template <class Edge, class Graph>
void tree_edge(Edge e, const Graph& g) {
using boost::get;
- m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
- m_combine, m_compare);
+ bool m_decreased =
+ relax(e, g, m_weight, m_predecessor, m_distance,
+ m_combine, m_compare);
if(m_decreased) {
m_vis.edge_relaxed(e, g);
@@ -175,8 +179,9 @@
template <class Edge, class Graph>
void gray_target(Edge e, const Graph& g) {
using boost::get;
- m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
- m_combine, m_compare);
+ bool m_decreased =
+ relax(e, g, m_weight, m_predecessor, m_distance,
+ m_combine, m_compare);
if(m_decreased) {
put(m_cost, target(e, g),
@@ -192,8 +197,9 @@
template <class Edge, class Graph>
void black_target(Edge e, const Graph& g) {
using boost::get;
- m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
- m_combine, m_compare);
+ bool m_decreased =
+ relax(e, g, m_weight, m_predecessor, m_distance,
+ m_combine, m_compare);
if(m_decreased) {
m_vis.edge_relaxed(e, g);
@@ -219,7 +225,6 @@
ColorMap m_color;
BinaryFunction m_combine;
BinaryPredicate m_compare;
- bool m_decreased;
C m_zero;
};
@@ -263,6 +268,77 @@
breadth_first_visit(g, s, Q, bfs_vis, color);
}
+ namespace graph_detail {
+ template <typename A, typename B>
+ struct select1st {
+ typedef std::pair<A, B> argument_type;
+ typedef A result_type;
+ A operator()(const std::pair<A, B>& p) const {return p.first;}
+ };
+ }
+
+ template <typename VertexListGraph, typename AStarHeuristic,
+ typename AStarVisitor, typename PredecessorMap,
+ typename CostMap, typename DistanceMap,
+ typename WeightMap,
+ typename CompareFunction, typename CombineFunction,
+ typename CostInf, typename CostZero>
+ inline void
+ astar_search_no_init_tree
+ (const VertexListGraph &g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ AStarHeuristic h, AStarVisitor vis,
+ PredecessorMap predecessor, CostMap cost,
+ DistanceMap distance, WeightMap weight,
+ CompareFunction compare, CombineFunction combine,
+ CostInf /*inf*/, CostZero zero)
+ {
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor
+ Vertex;
+ typedef typename property_traits<DistanceMap>::value_type Distance;
+ typedef d_ary_heap_indirect<
+ std::pair<Distance, Vertex>,
+ 4,
+ null_property_map<std::pair<Distance, Vertex>, std::size_t>,
+ function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >,
+ CompareFunction>
+ MutableQueue;
+ MutableQueue Q(
+ make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()),
+ null_property_map<std::pair<Distance, Vertex>, std::size_t>(),
+ compare);
+
+ vis.discover_vertex(s, g);
+ Q.push(std::make_pair(get(cost, s), s));
+ while (!Q.empty()) {
+ Vertex v;
+ Distance v_rank;
+ boost::tie(v_rank, v) = Q.top();
+ Q.pop();
+ vis.examine_vertex(v, g);
+ BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) {
+ Vertex w = target(e, g);
+ vis.examine_edge(e, g);
+ Distance e_weight = get(weight, e);
+ if (compare(e_weight, zero))
+ BOOST_THROW_EXCEPTION(negative_edge());
+ bool decreased =
+ relax(e, g, weight, predecessor, distance,
+ combine, compare);
+ Distance w_d = combine(get(distance, v), e_weight);
+ if (decreased) {
+ vis.edge_relaxed(e, g);
+ Distance w_rank = combine(get(distance, w), h(w));
+ put(cost, w, w_rank);
+ vis.discover_vertex(w, g);
+ Q.push(std::make_pair(w_rank, w));
+ } else {
+ vis.edge_not_relaxed(e, g);
+ }
+ }
+ vis.finish_vertex(v, g);
+ }
+ }
// Non-named parameter interface
template <typename VertexListGraph, typename AStarHeuristic,
@@ -303,6 +379,40 @@
}
+ // Non-named parameter interface
+ template <typename VertexListGraph, typename AStarHeuristic,
+ typename AStarVisitor, typename PredecessorMap,
+ typename CostMap, typename DistanceMap,
+ typename WeightMap,
+ typename CompareFunction, typename CombineFunction,
+ typename CostInf, typename CostZero>
+ inline void
+ astar_search_tree
+ (const VertexListGraph &g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ AStarHeuristic h, AStarVisitor vis,
+ PredecessorMap predecessor, CostMap cost,
+ DistanceMap distance, WeightMap weight,
+ CompareFunction compare, CombineFunction combine,
+ CostInf inf, CostZero zero)
+ {
+
+ typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
+ for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
+ put(distance, *ui, inf);
+ put(cost, *ui, inf);
+ put(predecessor, *ui, *ui);
+ vis.initialize_vertex(*ui, g);
+ }
+ put(distance, s, zero);
+ put(cost, s, h(s));
+
+ astar_search_no_init_tree
+ (g, s, h, vis, predecessor, cost, distance, weight,
+ compare, combine, inf, zero);
+
+ }
+
// Named parameter interfaces
template <typename VertexListGraph,
typename AStarHeuristic,
@@ -345,6 +455,46 @@
arg_pack[_distance_zero | D()]);
}
+ // Named parameter interfaces
+ template <typename VertexListGraph,
+ typename AStarHeuristic,
+ typename P, typename T, typename R>
+ void
+ astar_search_tree
+ (const VertexListGraph &g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ AStarHeuristic h, const bgl_named_params<P, T, R>& params)
+ {
+ using namespace boost::graph::keywords;
+ typedef bgl_named_params<P, T, R> params_type;
+ BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
+
+ // Distance type is the value type of the distance map if there is one,
+ // otherwise the value type of the weight map.
+ typedef
+ typename detail::override_const_property_result<
+ arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
+ weight_map_type;
+ typedef typename boost::property_traits<weight_map_type>::value_type W;
+ typedef
+ typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
+ distance_map_type;
+ typedef typename boost::property_traits<distance_map_type>::value_type D;
+ const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+
+ astar_search_tree
+ (g, s, h,
+ arg_pack[_visitor | make_astar_visitor(null_visitor())],
+ arg_pack[_predecessor_map | dummy_property_map()],
+ detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
+ detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack),
+ detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
+ arg_pack[_distance_compare | std::less<D>()],
+ arg_pack[_distance_combine | closed_plus<D>(inf)],
+ inf,
+ arg_pack[_distance_zero | D()]);
+ }
+
template <typename VertexListGraph,
typename AStarHeuristic,
typename P, typename T, typename R>
@@ -378,6 +528,37 @@
arg_pack[_distance_zero | D()]);
}
+ template <typename VertexListGraph,
+ typename AStarHeuristic,
+ typename P, typename T, typename R>
+ void
+ astar_search_no_init_tree
+ (const VertexListGraph &g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ AStarHeuristic h, const bgl_named_params<P, T, R>& params)
+ {
+ using namespace boost::graph::keywords;
+ typedef bgl_named_params<P, T, R> params_type;
+ BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
+ typedef
+ typename detail::override_const_property_result<
+ arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
+ weight_map_type;
+ typedef typename boost::property_traits<weight_map_type>::value_type D;
+ const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+ astar_search_no_init_tree
+ (g, s, h,
+ arg_pack[_visitor | make_astar_visitor(null_visitor())],
+ arg_pack[_predecessor_map | dummy_property_map()],
+ detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
+ detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack),
+ detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
+ arg_pack[_distance_compare | std::less<D>()],
+ arg_pack[_distance_combine | closed_plus<D>(inf)],
+ inf,
+ arg_pack[_distance_zero | D()]);
+ }
+
} // namespace boost
#endif // BOOST_GRAPH_ASTAR_SEARCH_HPP
Modified: branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp (original)
+++ branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -442,11 +442,11 @@
for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
edge_descriptor in_edge = get(m_rev_edge_map, *ei);
vertex_descriptor other_node = source(in_edge, m_g);
- if(get_tree(other_node) == tColorTraits::black() && has_parent(other_node)){
+ if(get_tree(other_node) == tColorTraits::black() && other_node != m_source){
if(get(m_res_cap_map, in_edge) > 0){
add_active_node(other_node);
}
- if(source(get_edge_to_parent(other_node), m_g) == current_node){
+ if(has_parent(other_node) && source(get_edge_to_parent(other_node), m_g) == current_node){
//we are the parent of that node
//it has to find a new parent, too
set_no_parent(other_node);
@@ -483,11 +483,11 @@
for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
const edge_descriptor out_edge = *ei;
const vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::white() && has_parent(other_node)){
+ if(get_tree(other_node) == tColorTraits::white() && other_node != m_sink){
if(get(m_res_cap_map, out_edge) > 0){
add_active_node(other_node);
}
- if(target(get_edge_to_parent(other_node), m_g) == current_node){
+ if(has_parent(other_node) && target(get_edge_to_parent(other_node), m_g) == current_node){
//we were it's parent, so it has to find a new one, too
set_no_parent(other_node);
m_child_orphans.push(other_node);
@@ -526,6 +526,9 @@
inline void add_active_node(vertex_descriptor v){
BOOST_ASSERT(get_tree(v) != tColorTraits::gray());
if(get(m_in_active_list_map, v)){
+ if (m_last_grow_vertex == v) {
+ m_last_grow_vertex = graph_traits<Graph>::null_vertex();
+ }
return;
} else{
put(m_in_active_list_map, v, true);
Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -37,7 +37,9 @@
#include <boost/integer.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/mpl/if.hpp>
+#include <boost/utility/enable_if.hpp>
#include <boost/graph/graph_selectors.hpp>
+#include <boost/graph/detail/is_distributed_selector.hpp>
#include <boost/graph/properties.hpp>
#include <boost/static_assert.hpp>
#include <boost/functional/hash.hpp>
@@ -1322,8 +1324,9 @@
typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
};
+// disable_if isn't truly necessary but required to avoid ambiguity with specializations below
template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
-struct property_map<BOOST_CSR_GRAPH_TYPE, Tag>:
+struct property_map<BOOST_CSR_GRAPH_TYPE, Tag, typename disable_if<detail::is_distributed_selector<Vertex> >::type>:
csr_property_map_helper<
BOOST_CSR_GRAPH_TYPE,
Tag,
@@ -1370,35 +1373,35 @@
}
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t>
+struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
{
typedef typed_identity_property_map<Vertex> type;
typedef type const_type;
};
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>
+struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
{
typedef detail::csr_edge_index_map<Vertex, EdgeIndex> type;
typedef type const_type;
};
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>
+struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
{
typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::vertex_map_type type;
typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::const_vertex_map_type const_type;
};
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-struct property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>
+struct property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
{
typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::edge_map_type type;
typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::const_edge_map_type const_type;
};
template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
-struct property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>
+struct property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
{
typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, typename BOOST_CSR_GRAPH_TYPE::graph_property_type> type;
typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, const typename BOOST_CSR_GRAPH_TYPE::graph_property_type> const_type;
Modified: branches/release/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/detail/adjacency_list.hpp (original)
+++ branches/release/boost/graph/detail/adjacency_list.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -309,14 +309,16 @@
public:
typedef Property property_type;
inline stored_ra_edge_iter() { }
- inline stored_ra_edge_iter(Vertex v, Iter i = Iter(),
- EdgeVec* edge_vec = 0)
+ inline explicit stored_ra_edge_iter(Vertex v) // Only used for comparisons
+ : stored_edge<Vertex>(v), m_i(0), m_vec(0){ }
+ inline stored_ra_edge_iter(Vertex v, Iter i, EdgeVec* edge_vec)
: stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
- inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
+ inline Property& get_property() { BOOST_ASSERT ((m_vec != 0)); return (*m_vec)[m_i].get_property(); }
inline const Property& get_property() const {
+ BOOST_ASSERT ((m_vec != 0));
return (*m_vec)[m_i].get_property();
}
- inline Iter get_iter() const { return m_vec->begin() + m_i; }
+ inline Iter get_iter() const { BOOST_ASSERT ((m_vec != 0)); return m_vec->begin() + m_i; }
protected:
std::size_t m_i;
EdgeVec* m_vec;
Modified: branches/release/boost/graph/detail/d_ary_heap.hpp
==============================================================================
--- branches/release/boost/graph/detail/d_ary_heap.hpp (original)
+++ branches/release/boost/graph/detail/d_ary_heap.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -126,18 +126,21 @@
}
Value& top() {
+ BOOST_ASSERT (!this->empty());
return data[0];
}
const Value& top() const {
+ BOOST_ASSERT (!this->empty());
return data[0];
}
void pop() {
+ BOOST_ASSERT (!this->empty());
put(index_in_heap, data[0], (size_type)(-1));
if (data.size() != 1) {
data[0] = data.back();
- put(index_in_heap, data[0], 0);
+ put(index_in_heap, data[0], (size_type)(0));
data.pop_back();
preserve_heap_property_down();
verify_heap();
Modified: branches/release/boost/graph/detail/labeled_graph_traits.hpp
==============================================================================
--- branches/release/boost/graph/detail/labeled_graph_traits.hpp (original)
+++ branches/release/boost/graph/detail/labeled_graph_traits.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -218,9 +218,9 @@
#define LABELED_GRAPH_PARAMS typename G, typename L, typename S
#define LABELED_GRAPH labeled_graph<G,L,S>
-// Specialize mutability traits for for the labeled graph.
+// Specialize mutability traits for the labeled graph.
// This specialization depends on the mutability of the underlying graph type.
-// If the underlying graph is fully mutable, this this is also fully mutable.
+// If the underlying graph is fully mutable, this is also fully mutable.
// Otherwise, it's different.
template <LABELED_GRAPH_PARAMS>
struct graph_mutability_traits< LABELED_GRAPH > {
Modified: branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
==============================================================================
--- branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp (original)
+++ branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -113,16 +113,17 @@
distance_weight_combine, distance_compare);
if (was_edge_relaxed) {
- vertex_queue.update(neighbor_vertex);
visitor.edge_relaxed(current_edge, graph);
+ if (is_neighbor_undiscovered) {
+ visitor.discover_vertex(neighbor_vertex, graph);
+ vertex_queue.push(neighbor_vertex);
+ } else {
+ vertex_queue.update(neighbor_vertex);
+ }
} else {
visitor.edge_not_relaxed(current_edge, graph);
}
- if (is_neighbor_undiscovered) {
- visitor.discover_vertex(neighbor_vertex, graph);
- vertex_queue.push(neighbor_vertex);
- }
} // end out edge iteration
visitor.finish_vertex(min_vertex, graph);
Modified: branches/release/boost/graph/directed_graph.hpp
==============================================================================
--- branches/release/boost/graph/directed_graph.hpp (original)
+++ branches/release/boost/graph/directed_graph.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -9,6 +9,10 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/pending/property.hpp>
+#include <boost/property_map/transform_value_property_map.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
namespace boost
{
@@ -27,8 +31,8 @@
*/
template <
typename VertexProp = no_property,
- typename EdgeProp= no_property,
- typename GraphProp= no_property>
+ typename EdgeProp = no_property,
+ typename GraphProp = no_property>
class directed_graph
{
public:
@@ -39,15 +43,14 @@
typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
-private:
- // Wrap the user-specified properties with an index.
- typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
- typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
-
+public:
+ // Embed indices into the vertex type.
+ typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
+ typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
public:
typedef adjacency_list<
listS, listS, bidirectionalS,
- vertex_property, edge_property, GraphProp,
+ internal_vertex_property, internal_edge_property, GraphProp,
listS
> graph_type;
@@ -80,8 +83,8 @@
typedef typename graph_type::edge_parallel_category edge_parallel_category;
typedef typename graph_type::traversal_category traversal_category;
- typedef unsigned vertex_index_type;
- typedef unsigned edge_index_type;
+ typedef std::size_t vertex_index_type;
+ typedef std::size_t edge_index_type;
directed_graph(GraphProp const& p = GraphProp())
: m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
@@ -137,6 +140,7 @@
vertices_size_type num_vertices() const
{ return m_num_vertices; }
+
private:
// This helper function manages the attribution of vertex indices.
vertex_descriptor make_index(vertex_descriptor v) {
@@ -150,7 +154,7 @@
{ return make_index(boost::add_vertex(m_graph)); }
vertex_descriptor add_vertex(vertex_property_type const& p)
- { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+ { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
void clear_vertex(vertex_descriptor v)
{
@@ -186,7 +190,7 @@
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v, edge_property_type const& p)
- { return make_index(boost::add_edge(u, v, edge_property(0u, p), m_graph)); }
+ { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
void remove_edge(vertex_descriptor u, vertex_descriptor v)
{
@@ -516,37 +520,32 @@
DIRECTED_GRAPH& g)
{ return remove_in_edge_if(v, pred, g.impl()); }
-// Helper code for working with property maps
-namespace detail
-{
- struct directed_graph_vertex_property_selector {
- template <class DirectedGraph, class Property, class Tag>
- struct bind_ {
- typedef typename DirectedGraph::graph_type Graph;
- typedef property_map<Graph, Tag> PropertyMap;
- typedef typename PropertyMap::type type;
- typedef typename PropertyMap::const_type const_type;
- };
- };
-
- struct directed_graph_edge_property_selector {
- template <class DirectedGraph, class Property, class Tag>
- struct bind_ {
- typedef typename DirectedGraph::graph_type Graph;
- typedef property_map<Graph, Tag> PropertyMap;
- typedef typename PropertyMap::type type;
- typedef typename PropertyMap::const_type const_type;
- };
- };
-}
+template <DIRECTED_GRAPH_PARAMS, typename Property>
+struct property_map<DIRECTED_GRAPH, Property>: property_map<typename DIRECTED_GRAPH::graph_type, Property> {};
-template <>
-struct vertex_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_vertex_property_selector type; };
-
-template <>
-struct edge_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_edge_property_selector type; };
+template <DIRECTED_GRAPH_PARAMS>
+struct property_map<DIRECTED_GRAPH, vertex_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::type>
+ type;
+};
+
+template <DIRECTED_GRAPH_PARAMS>
+struct property_map<DIRECTED_GRAPH, edge_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::type>
+ type;
+};
// PropertyGraph concepts
template <DIRECTED_GRAPH_PARAMS, typename Property>
@@ -559,6 +558,26 @@
get(Property p, DIRECTED_GRAPH const& g)
{ return get(p, g.impl()); }
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::type
+get(vertex_all_t, DIRECTED_GRAPH& g)
+{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type
+get(vertex_all_t, DIRECTED_GRAPH const& g)
+{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, edge_all_t>::type
+get(edge_all_t, DIRECTED_GRAPH& g)
+{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type
+get(edge_all_t, DIRECTED_GRAPH const& g)
+{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key>
inline typename property_traits<
typename property_map<
@@ -568,10 +587,40 @@
get(Property p, DIRECTED_GRAPH const& g, Key const& k)
{ return get(p, g.impl(), k); }
+template <DIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename DIRECTED_GRAPH::graph_type, vertex_all_t
+ >::const_type
+>::value_type
+get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(vertex_all, g.impl(), k).m_base; }
+
+template <DIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename DIRECTED_GRAPH::graph_type, edge_all_t
+ >::const_type
+>::value_type
+get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(edge_all, g.impl(), k).m_base; }
+
template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
{ put(p, g.impl(), k, v); }
+template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(vertex_all, g.impl(), k,
+ typename DIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
+}
+
+template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(edge_all, g.impl(), k,
+ typename DIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
+}
+
template <DIRECTED_GRAPH_PARAMS, class Property>
typename graph_property<DIRECTED_GRAPH, Property>::type&
get_property(DIRECTED_GRAPH& g, Property p)
Modified: branches/release/boost/graph/distributed/selector.hpp
==============================================================================
--- branches/release/boost/graph/distributed/selector.hpp (original)
+++ branches/release/boost/graph/distributed/selector.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -13,6 +13,8 @@
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif
+#include <boost/graph/detail/is_distributed_selector.hpp>
+
namespace boost {
/* The default local selector for a distributedS selector. */
@@ -31,6 +33,12 @@
typedef LocalS local_selector;
typedef DistributionS distribution;
};
+
+ namespace detail {
+ template<typename ProcessGroup, typename LocalS, typename DistributionS>
+ struct is_distributed_selector<distributedS<ProcessGroup, LocalS, DistributionS> >: mpl::true_ {};
+ }
+
}
#endif // BOOST_GRAPH_DISTRIBUTED_SELECTOR_HPP
Modified: branches/release/boost/graph/graph_concepts.hpp
==============================================================================
--- branches/release/boost/graph/graph_concepts.hpp (original)
+++ branches/release/boost/graph/graph_concepts.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -20,6 +20,9 @@
#include <boost/graph/numeric_values.hpp>
#include <boost/graph/buffer_concepts.hpp>
#include <boost/concept_check.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/static_assert.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/concept/assert.hpp>
@@ -55,12 +58,10 @@
BOOST_concept(Graph,(G))
{
typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
typedef typename graph_traits<G>::directed_category directed_category;
- typedef typename graph_traits<G>::edge_parallel_category
- edge_parallel_category;
-
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
+ typedef typename graph_traits<G>::edge_parallel_category edge_parallel_category;
+ typedef typename graph_traits<G>::traversal_category traversal_category;
BOOST_CONCEPT_USAGE(Graph)
{
@@ -75,11 +76,12 @@
: Graph<G>
{
typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
- typedef typename graph_traits<G>::out_edge_iterator
- out_edge_iterator;
+ typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator;
+ typedef typename graph_traits<G>::degree_size_type degree_size_type;
+ typedef typename graph_traits<G>::traversal_category traversal_category;
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<out_edge_iterator, void> >::value));
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<degree_size_type, void> >::value));
BOOST_CONCEPT_USAGE(IncidenceGraph) {
BOOST_CONCEPT_ASSERT((MultiPassInputIterator<out_edge_iterator>));
@@ -123,6 +125,8 @@
BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
bidirectional_graph_tag>));
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<in_edge_iterator, void> >::value));
+
p = in_edges(v, g);
n = in_degree(v, g);
e = *p.first;
@@ -153,6 +157,8 @@
BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
adjacency_graph_tag>));
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<adjacency_iterator, void> >::value));
+
p = adjacent_vertices(v, g);
v = *p.first;
const_constraints(g);
@@ -178,6 +184,9 @@
BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
vertex_list_graph_tag>));
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertex_iterator, void> >::value));
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<vertices_size_type, void> >::value));
+
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
// dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
// you want to use vector_as_graph, it is! I'm sure the graph
@@ -227,6 +236,9 @@
BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
edge_list_graph_tag>));
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edge_iterator, void> >::value));
+ BOOST_STATIC_ASSERT((boost::mpl::not_<boost::is_same<edges_size_type, void> >::value));
+
p = edges(g);
e = *p.first;
u = source(e, g);
Modified: branches/release/boost/graph/graph_traits.hpp
==============================================================================
--- branches/release/boost/graph/graph_traits.hpp (original)
+++ branches/release/boost/graph/graph_traits.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -20,6 +20,7 @@
#include <boost/mpl/not.hpp>
#include <boost/mpl/has_xxx.hpp>
#include <boost/mpl/void.hpp>
+#include <boost/mpl/identity.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/iterator/iterator_categories.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
@@ -28,23 +29,47 @@
namespace boost {
+ namespace detail {
+#define BOOST_GRAPH_MEMBER_OR_VOID(name) \
+ BOOST_MPL_HAS_XXX_TRAIT_DEF(name) \
+ template <typename T> struct BOOST_JOIN(get_member_, name) {typedef typename T::name type;}; \
+ template <typename T> struct BOOST_JOIN(get_opt_member_, name): \
+ boost::mpl::eval_if_c< \
+ BOOST_JOIN(has_, name)<T>::value, \
+ BOOST_JOIN(get_member_, name)<T>, \
+ boost::mpl::identity<void> > \
+ {};
+ BOOST_GRAPH_MEMBER_OR_VOID(adjacency_iterator)
+ BOOST_GRAPH_MEMBER_OR_VOID(out_edge_iterator)
+ BOOST_GRAPH_MEMBER_OR_VOID(in_edge_iterator)
+ BOOST_GRAPH_MEMBER_OR_VOID(vertex_iterator)
+ BOOST_GRAPH_MEMBER_OR_VOID(edge_iterator)
+ BOOST_GRAPH_MEMBER_OR_VOID(vertices_size_type)
+ BOOST_GRAPH_MEMBER_OR_VOID(edges_size_type)
+ BOOST_GRAPH_MEMBER_OR_VOID(degree_size_type)
+ }
+
template <typename G>
struct graph_traits {
+#define BOOST_GRAPH_PULL_OPT_MEMBER(name) \
+ typedef typename detail::BOOST_JOIN(get_opt_member_, name)<G>::type name;
+
typedef typename G::vertex_descriptor vertex_descriptor;
typedef typename G::edge_descriptor edge_descriptor;
- typedef typename G::adjacency_iterator adjacency_iterator;
- typedef typename G::out_edge_iterator out_edge_iterator;
- typedef typename G::in_edge_iterator in_edge_iterator;
- typedef typename G::vertex_iterator vertex_iterator;
- typedef typename G::edge_iterator edge_iterator;
+ BOOST_GRAPH_PULL_OPT_MEMBER(adjacency_iterator)
+ BOOST_GRAPH_PULL_OPT_MEMBER(out_edge_iterator)
+ BOOST_GRAPH_PULL_OPT_MEMBER(in_edge_iterator)
+ BOOST_GRAPH_PULL_OPT_MEMBER(vertex_iterator)
+ BOOST_GRAPH_PULL_OPT_MEMBER(edge_iterator)
typedef typename G::directed_category directed_category;
typedef typename G::edge_parallel_category edge_parallel_category;
typedef typename G::traversal_category traversal_category;
- typedef typename G::vertices_size_type vertices_size_type;
- typedef typename G::edges_size_type edges_size_type;
- typedef typename G::degree_size_type degree_size_type;
+ BOOST_GRAPH_PULL_OPT_MEMBER(vertices_size_type)
+ BOOST_GRAPH_PULL_OPT_MEMBER(edges_size_type)
+ BOOST_GRAPH_PULL_OPT_MEMBER(degree_size_type)
+#undef BOOST_GRAPH_PULL_OPT_MEMBER
static inline vertex_descriptor null_vertex();
};
Modified: branches/release/boost/graph/graphml.hpp
==============================================================================
--- branches/release/boost/graph/graphml.hpp (original)
+++ branches/release/boost/graph/graphml.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -204,14 +204,14 @@
const char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean", "int", "long", "float", "double", "string"};
void BOOST_GRAPH_DECL
-read_graphml(std::istream& in, mutate_graph& g);
+read_graphml(std::istream& in, mutate_graph& g, size_t desired_idx);
template<typename MutableGraph>
void
-read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp)
+read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp, size_t desired_idx = 0)
{
mutate_graph_impl<MutableGraph> mg(g,dp);
- read_graphml(in, mg);
+ read_graphml(in, mg, desired_idx);
}
template <typename Types>
Modified: branches/release/boost/graph/kamada_kawai_spring_layout.hpp
==============================================================================
--- branches/release/boost/graph/kamada_kawai_spring_layout.hpp (original)
+++ branches/release/boost/graph/kamada_kawai_spring_layout.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -475,12 +475,12 @@
* from every vertex to every other vertex, which is computed in the
* first stages of the algorithm. This value's type must be a model
* of BasicMatrix with value type equal to the value type of the
- * weight map. The default is a a vector of vectors.
+ * weight map. The default is a vector of vectors.
*
* \param spring_strength (UTIL/OUT) will be used to store the
* strength of the spring between every pair of vertices. This
* value's type must be a model of BasicMatrix with value type equal
- * to the value type of the weight map. The default is a a vector of
+ * to the value type of the weight map. The default is a vector of
* vectors.
*
* \param partial_derivatives (UTIL) will be used to store the
Modified: branches/release/boost/graph/labeled_graph.hpp
==============================================================================
--- branches/release/boost/graph/labeled_graph.hpp (original)
+++ branches/release/boost/graph/labeled_graph.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -21,7 +21,7 @@
#include <boost/graph/graph_traits.hpp>
// This file implements a utility for creating mappings from arbitrary
-// identifers to the vertices of a graph.
+// identifiers to the vertices of a graph.
namespace boost {
@@ -104,7 +104,7 @@
// Tag dispatch on random access containers (i.e., vectors). This function
// basically requires a) that Container is vector<Label> and that Label
// is an unsigned integral value. Note that this will resize the vector
- // to accomodate indices.
+ // to accommodate indices.
template <typename Container, typename Graph, typename Label, typename Prop>
std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
@@ -112,7 +112,7 @@
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- // If the label is out of bounds, resize the vector to accomodate.
+ // If the label is out of bounds, resize the vector to accommodate.
// Resize by 2x the index so we don't cause quadratic insertions over
// time.
if(l >= c.size()) {
@@ -140,7 +140,7 @@
// Tag dispatch on unique associative containers (i.e. maps).
template <typename Container, typename Graph, typename Label, typename Prop>
std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
- insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const&,
+ insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
unique_associative_container_tag)
{
// Here, we actually have to try the insertion first, and only add
@@ -150,6 +150,7 @@
std::pair<Iterator, bool> x = c.insert(std::make_pair(l, Vertex()));
if(x.second) {
x.first->second = add_vertex(g);
+ put(boost::vertex_all, g, x.first->second, p);
}
return std::make_pair(x.first->second, x.second);
}
@@ -246,7 +247,7 @@
* vertex labels and vertex descriptors.
*
* @todo This class is somewhat redundant for adjacency_list<*, vecS> if
- * the intended label is an unsigned int (and perhpahs some other cases), but
+ * the intended label is an unsigned int (and perhaps some other cases), but
* it does avoid some weird ambiguities (i.e. adding a vertex with a label that
* does not match its target index).
*
@@ -310,7 +311,7 @@
_map.insert(_map.end(), rng.first, rng.second);
}
- // Construct a grpah over n vertices, each of which receives a label from
+ // Construct a graph over n vertices, each of which receives a label from
// the range [l, l + n). Note that the graph is not directly constructed
// over the n vertices, but added sequentially. This constructor is
// necessarily slower than the underlying counterpart.
@@ -544,8 +545,9 @@
{ return g.label_vertex(v, l); }
template <LABELED_GRAPH_PARAMS>
-inline bool vertex_by_label(typename LABELED_GRAPH::label_type const l,
- LABELED_GRAPH& g)
+inline typename LABELED_GRAPH::vertex_descriptor
+vertex_by_label(typename LABELED_GRAPH::label_type const l,
+ LABELED_GRAPH& g)
{ return g.vertex(l); }
//@}
Modified: branches/release/boost/graph/metric_tsp_approx.hpp
==============================================================================
--- branches/release/boost/graph/metric_tsp_approx.hpp (original)
+++ branches/release/boost/graph/metric_tsp_approx.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -216,7 +216,7 @@
// Create tour using a preorder traversal of the mst
vector<Node> tour;
PreorderTraverser<Node, Tree> tvis(tour);
- traverse_tree(0, t, tvis);
+ traverse_tree(indexmap[start], t, tvis);
pair<GVItr, GVItr> g_verts(vertices(g));
for(PreorderTraverser<Node, Tree>::const_iterator curr(tvis.begin());
@@ -228,7 +228,7 @@
}
// Connect back to the start of the tour
- vis.visit_vertex(*g_verts.first, g);
+ vis.visit_vertex(start, g);
}
// Default tsp tour visitor that puts the tour in an OutputIterator
Modified: branches/release/boost/graph/named_graph.hpp
==============================================================================
--- branches/release/boost/graph/named_graph.hpp (original)
+++ branches/release/boost/graph/named_graph.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -11,14 +11,23 @@
#define BOOST_GRAPH_NAMED_GRAPH_HPP
#include <boost/config.hpp>
-#include <boost/type_traits/remove_cv.hpp>
-#include <boost/type_traits/remove_reference.hpp>
-#include <boost/multi_index_container.hpp>
+#include <boost/functional/hash.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
+#include <boost/multi_index_container.hpp>
#include <boost/optional.hpp>
+#include <boost/pending/property.hpp> // for boost::lookup_one_property
#include <boost/throw_exception.hpp>
+#include <boost/tuple/tuple.hpp> // for boost::make_tuple
+#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/remove_cv.hpp>
+#include <boost/type_traits/remove_reference.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <functional> // for std::equal_to
#include <stdexcept> // for std::runtime_error
+#include <utility> // for std::pair
namespace boost { namespace graph {
@@ -352,8 +361,15 @@
/// Retrieve the vertex associated with the given name, or add a new
/// vertex with that name if no such vertex is available.
-template<BGL_NAMED_GRAPH_PARAMS>
-Vertex
+/// Note: This is enabled only when the vertex property type is different
+/// from the vertex name to avoid ambiguous overload problems with
+/// the add_vertex() function that takes a vertex property.
+template<BGL_NAMED_GRAPH_PARAMS>
+ typename disable_if<is_same<
+ typename BGL_NAMED_GRAPH::vertex_name_type,
+ VertexProperty
+ >,
+Vertex>::type
add_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
BGL_NAMED_GRAPH& g)
{
@@ -401,6 +417,35 @@
g.derived());
}
+// Overloads to support EdgeMutablePropertyGraph graphs
+template <BGL_NAMED_GRAPH_PARAMS>
+std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
+add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
+ typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
+ typename edge_property_type<Graph>::type const& p,
+ BGL_NAMED_GRAPH& g) {
+ return add_edge(u, add_vertex(v_name, g.derived()), p, g.derived());
+}
+
+template <BGL_NAMED_GRAPH_PARAMS>
+std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
+add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
+ typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
+ typename edge_property_type<Graph>::type const& p,
+ BGL_NAMED_GRAPH& g) {
+ return add_edge(add_vertex(u_name, g.derived()), v, p, g.derived());
+}
+
+template <BGL_NAMED_GRAPH_PARAMS>
+std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
+add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
+ typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
+ typename edge_property_type<Graph>::type const& p,
+ BGL_NAMED_GRAPH& g) {
+ return add_edge(add_vertex(u_name, g.derived()),
+ add_vertex(v_name, g.derived()), p, g.derived());
+}
+
#undef BGL_NAMED_GRAPH
#undef BGL_NAMED_GRAPH_PARAMS
Modified: branches/release/boost/graph/properties.hpp
==============================================================================
--- branches/release/boost/graph/properties.hpp (original)
+++ branches/release/boost/graph/properties.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -224,7 +224,7 @@
{};
} // namespace detail
- template <class Graph, class Property>
+ template <class Graph, class Property, class Enable = void>
struct property_map:
mpl::if_<
is_same<typename detail::property_kind_from_graph<Graph, Property>::type, edge_property_tag>,
@@ -248,8 +248,8 @@
>::type type;
};
- template <class Graph> class vertex_property: vertex_property_type<Graph> {};
- template <class Graph> class edge_property: edge_property_type<Graph> {};
+ template <typename Graph> struct vertex_property: vertex_property_type<Graph> {};
+ template <typename Graph> struct edge_property: edge_property_type<Graph> {};
template <typename Graph>
class degree_property_map
Modified: branches/release/boost/graph/property_maps/constant_property_map.hpp
==============================================================================
--- branches/release/boost/graph/property_maps/constant_property_map.hpp (original)
+++ branches/release/boost/graph/property_maps/constant_property_map.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -54,6 +54,39 @@
make_constant_property(const Value& value)
{ return constant_property_map<Key, Value>(value); }
+/**
+ * Same as above, but pretends to be writable as well.
+ */
+template <typename Key, typename Value>
+struct constant_writable_property_map {
+ typedef Key key_type;
+ typedef Value value_type;
+ typedef Value& reference;
+ typedef boost::read_write_property_map_tag category;
+
+ constant_writable_property_map()
+ : m_value()
+ { }
+
+ constant_writable_property_map(const value_type &value)
+ : m_value(value)
+ { }
+
+ constant_writable_property_map(const constant_writable_property_map& copy)
+ : m_value(copy.m_value)
+ { }
+
+ friend Value get(const constant_writable_property_map& me, Key) {return me.m_value;}
+ friend void put(const constant_writable_property_map&, Key, Value) {}
+
+ value_type m_value;
+};
+
+template <typename Key, typename Value>
+inline constant_writable_property_map<Key, Value>
+make_constant_writable_property(const Value& value)
+{ return constant_writable_property_map<Key, Value>(value); }
+
} /* namespace boost */
#endif
Modified: branches/release/boost/graph/reverse_graph.hpp
==============================================================================
--- branches/release/boost/graph/reverse_graph.hpp (original)
+++ branches/release/boost/graph/reverse_graph.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -433,7 +433,7 @@
{
return m[k];
}
-};
+}
template <class E>
struct property_traits<detail::underlying_edge_desc_map_type<E> > {
Modified: branches/release/boost/graph/tiernan_all_cycles.hpp
==============================================================================
--- branches/release/boost/graph/tiernan_all_cycles.hpp (original)
+++ branches/release/boost/graph/tiernan_all_cycles.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -64,7 +64,7 @@
// basically modernized it to use real data structures (no more arrays and matrices).
// Oh... and there's explicit control structures - not just gotos.
//
-// The problem is definitely NP-complete, an an unbounded implementation of this
+// The problem is definitely NP-complete, an unbounded implementation of this
// will probably run for quite a while on a large graph. The conclusions
// of this paper also reference a Paton algorithm for undirected graphs as being
// much more efficient (apparently based on spanning trees). Although not implemented,
@@ -85,7 +85,7 @@
// }
/**
- * The default cycle visitor providse an empty visit function for cycle
+ * The default cycle visitor provides an empty visit function for cycle
* visitors.
*/
struct cycle_visitor
@@ -168,7 +168,7 @@
// conditions for allowing a traversal along this edge are:
// 1. the index of v must be greater than that at which the
- // the path is rooted (p.front()).
+ // path is rooted (p.front()).
// 2. the vertex v cannot already be in the path
// 3. the vertex v cannot be closed to the vertex u
Modified: branches/release/boost/graph/undirected_graph.hpp
==============================================================================
--- branches/release/boost/graph/undirected_graph.hpp (original)
+++ branches/release/boost/graph/undirected_graph.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -9,6 +9,10 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/pending/property.hpp>
+#include <boost/property_map/transform_value_property_map.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
namespace boost
{
@@ -39,16 +43,16 @@
typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
-private:
+public:
// Embed indices into the vertex type.
- typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
- typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
+ typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
+ typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
public:
typedef adjacency_list<listS,
listS,
undirectedS,
- vertex_property,
- edge_property,
+ internal_vertex_property,
+ internal_edge_property,
GraphProp,
listS> graph_type;
private:
@@ -151,7 +155,7 @@
{ return make_index(boost::add_vertex(m_graph)); }
vertex_descriptor add_vertex(vertex_property_type const& p)
- { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+ { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
void clear_vertex(vertex_descriptor v) {
std::pair<out_edge_iterator, out_edge_iterator>
@@ -188,7 +192,7 @@
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
edge_property_type const& p)
- { return make_index(boost::add_edge(u, v, edge_property(0u, p), m_graph)); }
+ { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
void remove_edge(vertex_descriptor u, vertex_descriptor v) {
// find all edges, (u, v)
@@ -525,6 +529,30 @@
template <UNDIRECTED_GRAPH_PARAMS, typename Property>
struct property_map<UNDIRECTED_GRAPH, Property>: property_map<typename UNDIRECTED_GRAPH::graph_type, Property> {};
+template <UNDIRECTED_GRAPH_PARAMS>
+struct property_map<UNDIRECTED_GRAPH, vertex_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::type>
+ type;
+};
+
+template <UNDIRECTED_GRAPH_PARAMS>
+struct property_map<UNDIRECTED_GRAPH, edge_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::type>
+ type;
+};
+
// PropertyGraph concepts
template <UNDIRECTED_GRAPH_PARAMS, typename Property>
inline typename property_map<UNDIRECTED_GRAPH, Property>::type
@@ -536,6 +564,26 @@
get(Property p, UNDIRECTED_GRAPH const& g)
{ return get(p, g.impl()); }
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type
+get(vertex_all_t, UNDIRECTED_GRAPH& g)
+{ return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type
+get(vertex_all_t, UNDIRECTED_GRAPH const& g)
+{ return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type
+get(edge_all_t, UNDIRECTED_GRAPH& g)
+{ return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type
+get(edge_all_t, UNDIRECTED_GRAPH const& g)
+{ return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key>
inline typename property_traits<
typename property_map<
@@ -545,10 +593,40 @@
get(Property p, UNDIRECTED_GRAPH const& g, Key const& k)
{ return get(p, g.impl(), k); }
+template <UNDIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename UNDIRECTED_GRAPH::graph_type, vertex_all_t
+ >::const_type
+>::value_type
+get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(vertex_all, g.impl(), k).m_base; }
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename UNDIRECTED_GRAPH::graph_type, edge_all_t
+ >::const_type
+>::value_type
+get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(edge_all, g.impl(), k).m_base; }
+
template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
{ put(p, g.impl(), k, v); }
+template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(vertex_all, g.impl(), k,
+ typename UNDIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
+}
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(edge_all, g.impl(), k,
+ typename UNDIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
+}
+
template <UNDIRECTED_GRAPH_PARAMS, class Property>
inline typename graph_property<UNDIRECTED_GRAPH, Property>::type&
get_property(UNDIRECTED_GRAPH& g, Property p)
Copied: branches/release/boost/graph/vf2_sub_graph_iso.hpp (from r81725, /trunk/boost/graph/vf2_sub_graph_iso.hpp)
==============================================================================
--- /trunk/boost/graph/vf2_sub_graph_iso.hpp (original)
+++ branches/release/boost/graph/vf2_sub_graph_iso.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -24,7 +24,9 @@
#include <boost/concept_check.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/mcgregor_common_subgraphs.hpp> // for always_equivalent
#include <boost/graph/named_function_params.hpp>
+#include <boost/type_traits/has_less.hpp>
#include <boost/mpl/int.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/tuple/tuple.hpp>
@@ -36,73 +38,23 @@
#endif
namespace boost {
-
- // Utility functions (analogue to mcgregor_common_subgraphs)
- // Returns binary predicate function object that compares vertices or edges
- // between graphs using property maps
- template <typename PropertyMap1,
- typename PropertyMap2>
- struct property_map_compatible {
-
- property_map_compatible(const PropertyMap1 property_map1,
- const PropertyMap2 property_map2)
- : property_map1_(property_map1), property_map2_(property_map2) {}
-
- template <typename Item1,
- typename Item2>
- bool operator()(const Item1 item1, const Item2 item2) const {
- return (get(property_map1_, item1) == get(property_map2_, item2));
- }
-
- private:
- const PropertyMap1 property_map1_;
- const PropertyMap2 property_map2_;
- };
-
- // Returns a property_map_compatible object that compares the values
- // of property_map1 and property_map2.
- template <typename PropertyMap1,
- typename PropertyMap2>
- property_map_compatible<PropertyMap1, PropertyMap2>
- make_property_map_compatible(const PropertyMap1 property_map1,
- const PropertyMap2 property_map2) {
- return property_map_compatible<PropertyMap1, PropertyMap2>
- (property_map1, property_map2);
- }
-
- // Binary function object that always returns true. Used when
- // vertices or edges are always compatible (i.e. have no labels).
- struct always_compatible {
- template <typename Item1,
- typename Item2>
- bool operator()(const Item1&, const Item2&) const {
- return true;
- }
- };
-
// Default print_callback
template <typename Graph1,
typename Graph2>
struct vf2_print_callback {
- vf2_print_callback(const Graph1& graph1, const Graph2& graph2,
- bool verify = false)
- : graph1_(graph1), graph2_(graph2), verify_(verify) {}
+ vf2_print_callback(const Graph1& graph1, const Graph2& graph2)
+ : graph1_(graph1), graph2_(graph2) {}
template <typename CorrespondenceMap1To2,
typename CorrespondenceMap2To1>
bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
- if (verify_)
- std::cout << "Verify: " << std::boolalpha
- << verify_vf2_sub_graph_iso(graph1_, graph2_, f)
- << std::endl;
-
- // Print sub graph isomorphism map
+ // Print (sub)graph isomorphism map
BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
- std::cout << '(' << get(vertex_index, graph1_, v) << ", "
- << get(vertex_index, graph1_, get(f, v)) << ") ";
+ std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", "
+ << get(vertex_index_t(), graph1_, get(f, v)) << ") ";
std::cout << std::endl;
@@ -112,8 +64,6 @@
private:
const Graph1& graph1_;
const Graph2& graph2_;
-
- const bool verify_;
};
namespace detail {
@@ -335,22 +285,20 @@
// Function object that checks whether a valid edge
// exists. For multi-graphs matched edges are excluded
template <typename Graph, typename Enable = void>
- struct compatible_edge_exists {
-
- compatible_edge_exists() {};
-
- typedef typename boost::graph_traits<Graph>::out_edge_iterator edge_iterator_type;
-
+ struct equivalent_edge_exists {
+ typedef typename boost::graph_traits<Graph>::edge_descriptor edge_type;
+
+ BOOST_CONCEPT_ASSERT(( LessThanComparable<edge_type> ));
+
template<typename EdgePredicate>
bool operator()(typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor t,
EdgePredicate is_valid_edge, const Graph& g) {
- edge_iterator_type ei, ei_end;
- for (boost::tie(ei, ei_end) = out_edges(s, g); ei != ei_end; ++ei) {
- if ((target(*ei, g) == t) && is_valid_edge(*ei) &&
- (matched_edges_.find(ei) == matched_edges_.end())) {
- matched_edges_.insert(ei);
+ BGL_FORALL_OUTEDGES_T(s, e, g, Graph) {
+ if ((target(e, g) == t) && is_valid_edge(e) &&
+ (matched_edges_.find(e) == matched_edges_.end())) {
+ matched_edges_.insert(e);
return true;
}
}
@@ -360,14 +308,11 @@
private:
- std::set<edge_iterator_type> matched_edges_;
+ std::set<edge_type> matched_edges_;
};
template <typename Graph>
- struct compatible_edge_exists<Graph, typename boost::disable_if<is_multigraph<Graph> >::type> {
-
- compatible_edge_exists() {};
-
+ struct equivalent_edge_exists<Graph, typename boost::disable_if<is_multigraph<Graph> >::type> {
template<typename EdgePredicate>
bool operator()(typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor t,
@@ -391,18 +336,18 @@
// fixed edge e2
template <typename Graph1,
typename Graph2,
- typename EdgeCompatibilityPredicate>
+ typename EdgeEquivalencePredicate>
struct edge1_predicate {
- edge1_predicate(EdgeCompatibilityPredicate edge_comp,
+ edge1_predicate(EdgeEquivalencePredicate edge_comp,
typename graph_traits<Graph2>::edge_descriptor e2)
: edge_comp_(edge_comp), e2_(e2) {}
- bool operator()(typename graph_traits<Graph1>::edge_descriptor e1) const {
+ bool operator()(typename graph_traits<Graph1>::edge_descriptor e1) {
return edge_comp_(e1, e2_);
}
- EdgeCompatibilityPredicate edge_comp_;
+ EdgeEquivalencePredicate edge_comp_;
typename graph_traits<Graph2>::edge_descriptor e2_;
};
@@ -411,32 +356,32 @@
// fixed edge e1
template <typename Graph1,
typename Graph2,
- typename EdgeCompatibilityPredicate>
+ typename EdgeEquivalencePredicate>
struct edge2_predicate {
- edge2_predicate(EdgeCompatibilityPredicate edge_comp,
+ edge2_predicate(EdgeEquivalencePredicate edge_comp,
typename graph_traits<Graph1>::edge_descriptor e1)
: edge_comp_(edge_comp), e1_(e1) {}
- bool operator()(typename graph_traits<Graph2>::edge_descriptor e2) const {
+ bool operator()(typename graph_traits<Graph2>::edge_descriptor e2) {
return edge_comp_(e1_, e2);
}
- EdgeCompatibilityPredicate edge_comp_;
+ EdgeEquivalencePredicate edge_comp_;
typename graph_traits<Graph1>::edge_descriptor e1_;
};
- enum problem_selector { sub_graph_iso, isomorphism };
+ enum problem_selector { subgraph_iso, isomorphism };
// The actual state associated with both graphs
template<typename Graph1,
typename Graph2,
typename IndexMap1,
typename IndexMap2,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename SubGraphIsoMapCallBack,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback,
problem_selector problem_selection>
class state {
@@ -454,8 +399,8 @@
IndexMap1 index_map1_;
- EdgeCompatibilityPredicate edge_comp_;
- VertexCompatibilityPredicate vertex_comp_;
+ EdgeEquivalencePredicate edge_comp_;
+ VertexEquivalencePredicate vertex_comp_;
base_state<Graph1, Graph2, IndexMap1, IndexMap2> state1_;
base_state<Graph2, Graph1, IndexMap2, IndexMap1> state2_;
@@ -465,7 +410,7 @@
// - graph sub-graph isomorphism, or
inline bool comp_term_sets(graph1_size_type a,
graph2_size_type b,
- boost::mpl::int_<sub_graph_iso>) const {
+ boost::mpl::int_<subgraph_iso>) const {
return a <= b;
}
@@ -484,8 +429,8 @@
state(const Graph1& graph1, const Graph2& graph2,
IndexMap1 index_map1, IndexMap2 index_map2,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp)
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp)
: graph1_(graph1), graph2_(graph2),
index_map1_(index_map1),
edge_comp_(edge_comp), vertex_comp_(vertex_comp),
@@ -514,7 +459,7 @@
graph1_size_type term_in1_count = 0, term_out1_count = 0, rest1_count = 0;
{
- compatible_edge_exists<Graph2> edge2_exists;
+ equivalent_edge_exists<Graph2> edge2_exists;
BGL_FORALL_INEDGES_T(v_new, e1, graph1_, Graph1) {
vertex1_type v = source(e1, graph1_);
@@ -524,7 +469,7 @@
if (v != v_new)
w = state1_.core(v);
if (!edge2_exists(w, w_new,
- edge2_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e1),
+ edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1),
graph2_))
return false;
@@ -540,7 +485,7 @@
}
{
- compatible_edge_exists<Graph2> edge2_exists;
+ equivalent_edge_exists<Graph2> edge2_exists;
BGL_FORALL_OUTEDGES_T(v_new, e1, graph1_, Graph1) {
vertex1_type v = target(e1, graph1_);
@@ -550,7 +495,7 @@
w = state1_.core(v);
if (!edge2_exists(w_new, w,
- edge2_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e1),
+ edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1),
graph2_))
return false;
@@ -569,7 +514,7 @@
graph2_size_type term_out2_count = 0, term_in2_count = 0, rest2_count = 0;
{
- compatible_edge_exists<Graph1> edge1_exists;
+ equivalent_edge_exists<Graph1> edge1_exists;
BGL_FORALL_INEDGES_T(w_new, e2, graph2_, Graph2) {
vertex2_type w = source(e2, graph2_);
@@ -579,7 +524,7 @@
v = state2_.core(w);
if (!edge1_exists(v, v_new,
- edge1_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e2),
+ edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
graph1_))
return false;
@@ -595,7 +540,7 @@
}
{
- compatible_edge_exists<Graph1> edge1_exists;
+ equivalent_edge_exists<Graph1> edge1_exists;
BGL_FORALL_OUTEDGES_T(w_new, e2, graph2_, Graph2) {
vertex2_type w = target(e2, graph2_);
@@ -605,7 +550,7 @@
v = state2_.core(w);
if (!edge1_exists(v_new, v,
- edge1_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e2),
+ edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
graph1_))
return false;
@@ -676,7 +621,7 @@
}
// Calls the user_callback with a graph (sub)graph mapping
- bool call_back(SubGraphIsoMapCallBack user_callback) const {
+ bool call_back(SubGraphIsoMapCallback user_callback) const {
return user_callback(state1_.get_map(), state2_.get_map());
}
@@ -705,15 +650,15 @@
typename IndexMap1,
typename IndexMap2,
typename VertexOrder1,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename SubGraphIsoMapCallBack,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback,
problem_selector problem_selection>
bool match(const Graph1& graph1, const Graph2& graph2,
- SubGraphIsoMapCallBack user_callback, const VertexOrder1& vertex_order1,
+ SubGraphIsoMapCallback user_callback, const VertexOrder1& vertex_order1,
state<Graph1, Graph2, IndexMap1, IndexMap2,
- EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
- SubGraphIsoMapCallBack, problem_selection>& s) {
+ EdgeEquivalencePredicate, VertexEquivalencePredicate,
+ SubGraphIsoMapCallback, problem_selection>& s) {
typename VertexOrder1::const_iterator graph1_verts_iter;
@@ -783,41 +728,39 @@
// lexicographical comparison
return std::make_pair(in_degree(v, graph_), out_degree(v, graph_)) <
std::make_pair(in_degree(w, graph_), out_degree(w, graph_));
-
}
- const Graph graph_;
+ const Graph& graph_;
};
- // Used to sort nodes by frequency/degrees
+ // Used to sort nodes by multiplicity of in/out degrees
template<typename Graph,
typename FrequencyMap>
struct vertex_frequency_degree_cmp {
typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
- vertex_frequency_degree_cmp(const Graph& graph, const FrequencyMap& freq)
+ vertex_frequency_degree_cmp(const Graph& graph, FrequencyMap freq)
: graph_(graph), freq_(freq) {}
bool operator()(const vertex_type& v, const vertex_type& w) const {
// lexicographical comparison
return std::make_pair(freq_[v], in_degree(v, graph_)+out_degree(v, graph_)) <
std::make_pair(freq_[w], in_degree(w, graph_)+out_degree(w, graph_));
-
}
const Graph& graph_;
- const FrequencyMap& freq_;
+ FrequencyMap freq_;
};
- // Sorts vertices of a graph by frequency/degree
+ // Sorts vertices of a graph by multiplicity of in/out degrees
template<typename Graph,
typename IndexMap,
typename VertexOrder>
- void sort_vertices(const Graph& graph, const IndexMap index_map, VertexOrder& order) {
+ void sort_vertices(const Graph& graph, IndexMap index_map, VertexOrder& order) {
typedef typename graph_traits<Graph>::vertices_size_type size_type;
-
+
boost::range::sort(order, vertex_in_out_degree_cmp<Graph>(graph));
std::vector<size_type> freq_vec(num_vertices(graph), 0);
@@ -849,6 +792,19 @@
} // namespace detail
+
+ // Returns vertex order (vertices sorted by multiplicity of in/out degrees)
+ template<typename Graph>
+ std::vector<typename graph_traits<Graph>::vertex_descriptor>
+ vertex_order_by_mult(const Graph& graph) {
+
+ std::vector<typename graph_traits<Graph>::vertex_descriptor> vertex_order;
+ std::copy(vertices(graph).first, vertices(graph).second, std::back_inserter(vertex_order));
+
+ detail::sort_vertices(graph, get(vertex_index, graph), vertex_order);
+ return vertex_order;
+ }
+
// Enumerates all graph sub-graph isomorphism mappings between graphs
// graph_small and graph_large. Continues until user_callback returns true or the
@@ -858,15 +814,15 @@
typename IndexMapSmall,
typename IndexMapLarge,
typename VertexOrderSmall,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename SubGraphIsoMapCallBack>
- bool vf2_sub_graph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback,
- IndexMapSmall index_map_small, IndexMapLarge index_map_large,
- const VertexOrderSmall& vertex_order_small,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp) {
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback>
+ bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ IndexMapSmall index_map_small, IndexMapLarge index_map_large,
+ const VertexOrderSmall& vertex_order_small,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
// Graph requirements
BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphSmall> ));
@@ -894,14 +850,14 @@
typedef typename property_traits<IndexMapLarge>::value_type IndexMapLargeValue;
BOOST_STATIC_ASSERT(( is_convertible<IndexMapLargeValue, size_type_large>::value ));
- // Edge & vertex compatibility requirements
+ // Edge & vertex requirements
typedef typename graph_traits<GraphSmall>::edge_descriptor edge_small_type;
typedef typename graph_traits<GraphLarge>::edge_descriptor edge_large_type;
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate,
edge_small_type, edge_large_type> ));
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate,
vertex_small_type, vertex_large_type> ));
// Vertex order requirements
@@ -927,60 +883,54 @@
return true;
detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge,
- EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
- SubGraphIsoMapCallBack, detail::sub_graph_iso>
+ EdgeEquivalencePredicate, VertexEquivalencePredicate,
+ SubGraphIsoMapCallback, detail::subgraph_iso>
s(graph_small, graph_large, index_map_small, index_map_large, edge_comp, vertex_comp);
return detail::match(graph_small, graph_large, user_callback, vertex_order_small, s);
}
- // All default interface for vf2_sub_graph_iso
+ // All default interface for vf2_subgraph_iso
template <typename GraphSmall,
typename GraphLarge,
- typename SubGraphIsoMapCallBack>
- bool vf2_sub_graph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback) {
+ typename SubGraphIsoMapCallback>
+ bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback) {
typedef typename graph_traits<GraphSmall>::vertex_descriptor vertex_small_type;
- std::vector<vertex_small_type> vertex_order_small;
- BGL_FORALL_VERTICES_T(v, graph_small, GraphSmall)
- vertex_order_small.push_back(v);
-
- detail::sort_vertices(graph_small, get(vertex_index, graph_small), vertex_order_small);
-
- return vf2_sub_graph_iso(graph_small, graph_large, user_callback,
- get(vertex_index, graph_small), get(vertex_index, graph_large),
- vertex_order_small,
- always_compatible(), always_compatible());
+ return vf2_subgraph_iso(graph_small, graph_large, user_callback,
+ get(vertex_index, graph_small), get(vertex_index, graph_large),
+ vertex_order_by_mult(graph_small),
+ always_equivalent(), always_equivalent());
}
- // Named parameter interface of vf2_sub_graph_iso
+ // Named parameter interface of vf2_subgraph_iso
template <typename GraphSmall,
typename GraphLarge,
typename VertexOrderSmall,
- typename SubGraphIsoMapCallBack,
+ typename SubGraphIsoMapCallback,
typename Param,
typename Tag,
typename Rest>
- bool vf2_sub_graph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback,
- const VertexOrderSmall& vertex_order_small,
- const bgl_named_params<Param, Tag, Rest>& params) {
-
- return vf2_sub_graph_iso(graph_small, graph_large, user_callback,
- choose_const_pmap(get_param(params, vertex_index1),
- graph_small, vertex_index),
- choose_const_pmap(get_param(params, vertex_index2),
- graph_large, vertex_index),
- vertex_order_small,
- choose_param(get_param(params, edges_equivalent_t()),
- always_compatible()),
- choose_param(get_param(params, vertices_equivalent_t()),
- always_compatible())
- );
+ bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ const VertexOrderSmall& vertex_order_small,
+ const bgl_named_params<Param, Tag, Rest>& params) {
+
+ return vf2_subgraph_iso(graph_small, graph_large, user_callback,
+ choose_const_pmap(get_param(params, vertex_index1),
+ graph_small, vertex_index),
+ choose_const_pmap(get_param(params, vertex_index2),
+ graph_large, vertex_index),
+ vertex_order_small,
+ choose_param(get_param(params, edges_equivalent_t()),
+ always_equivalent()),
+ choose_param(get_param(params, vertices_equivalent_t()),
+ always_equivalent())
+ );
}
@@ -993,15 +943,15 @@
typename IndexMap1,
typename IndexMap2,
typename VertexOrder1,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename GraphIsoMapCallBack>
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename GraphIsoMapCallback>
bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
- GraphIsoMapCallBack user_callback,
+ GraphIsoMapCallback user_callback,
IndexMap1 index_map1, IndexMap2 index_map2,
const VertexOrder1& vertex_order1,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp) {
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
// Graph requirements
BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph1> ));
@@ -1030,14 +980,14 @@
typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
BOOST_STATIC_ASSERT(( is_convertible<IndexMap2Value, size_type2>::value ));
- // Edge & vertex compatibility requirements
+ // Edge & vertex requirements
typedef typename graph_traits<Graph1>::edge_descriptor edge1_type;
typedef typename graph_traits<Graph2>::edge_descriptor edge2_type;
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate,
edge1_type, edge2_type> ));
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate,
vertex1_type, vertex2_type> ));
// Vertex order requirements
@@ -1046,7 +996,6 @@
BOOST_STATIC_ASSERT(( is_same<vertex1_type, order_value_type>::value ));
BOOST_ASSERT( num_vertices(graph1) == vertex_order1.size() );
-
if (num_vertices(graph1) != num_vertices(graph2))
return false;
@@ -1064,8 +1013,8 @@
return true;
detail::state<Graph1, Graph2, IndexMap1, IndexMap2,
- EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
- GraphIsoMapCallBack, detail::isomorphism>
+ EdgeEquivalencePredicate, VertexEquivalencePredicate,
+ GraphIsoMapCallback, detail::isomorphism>
s(graph1, graph2, index_map1, index_map2, edge_comp, vertex_comp);
return detail::match(graph1, graph2, user_callback, vertex_order1, s);
@@ -1075,22 +1024,16 @@
// All default interface for vf2_graph_iso
template <typename Graph1,
typename Graph2,
- typename GraphIsoMapCallBack>
+ typename GraphIsoMapCallback>
bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
- GraphIsoMapCallBack user_callback) {
+ GraphIsoMapCallback user_callback) {
typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_type;
- std::vector<vertex1_type> vertex_order1;
- BGL_FORALL_VERTICES_T(v, graph1, Graph1)
- vertex_order1.push_back(v);
-
- detail::sort_vertices(graph1, get(vertex_index, graph1), vertex_order1);
-
return vf2_graph_iso(graph1, graph2, user_callback,
get(vertex_index, graph1), get(vertex_index, graph2),
- vertex_order1,
- always_compatible(), always_compatible());
+ vertex_order_by_mult(graph1),
+ always_equivalent(), always_equivalent());
}
@@ -1098,12 +1041,12 @@
template <typename Graph1,
typename Graph2,
typename VertexOrder1,
- typename GraphIsoMapCallBack,
+ typename GraphIsoMapCallback,
typename Param,
typename Tag,
typename Rest>
bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
- GraphIsoMapCallBack user_callback,
+ GraphIsoMapCallback user_callback,
const VertexOrder1& vertex_order1,
const bgl_named_params<Param, Tag, Rest>& params) {
@@ -1114,9 +1057,9 @@
graph2, vertex_index),
vertex_order1,
choose_param(get_param(params, edges_equivalent_t()),
- always_compatible()),
+ always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
- always_compatible())
+ always_equivalent())
);
}
@@ -1126,17 +1069,17 @@
template<typename Graph1,
typename Graph2,
typename CorresponenceMap1To2,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate>
- inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
- const CorresponenceMap1To2 f,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp) {
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate>
+ inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph2> ));
- detail::compatible_edge_exists<Graph2> edge2_exists;
+ detail::equivalent_edge_exists<Graph2> edge2_exists;
BGL_FORALL_EDGES_T(e1, graph1, Graph1) {
typename graph_traits<Graph1>::vertex_descriptor s1, t1;
@@ -1151,7 +1094,7 @@
typename graph_traits<Graph2>::edge_descriptor e2;
if (!edge2_exists(s2, t2,
- detail::edge2_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp, e1),
+ detail::edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp, e1),
graph2))
return false;
@@ -1160,14 +1103,14 @@
return true;
}
- // Variant of verify_sub_graph_iso with all default parameters
+ // Variant of verify_subgraph_iso with all default parameters
template<typename Graph1,
typename Graph2,
typename CorresponenceMap1To2>
- inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
- const CorresponenceMap1To2 f) {
- return verify_vf2_sub_graph_iso(graph1, graph2, f,
- always_compatible(), always_compatible());
+ inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f) {
+ return verify_vf2_subgraph_iso(graph1, graph2, f,
+ always_equivalent(), always_equivalent());
}
Modified: branches/release/boost/pending/property.hpp
==============================================================================
--- branches/release/boost/pending/property.hpp (original)
+++ branches/release/boost/pending/property.hpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -244,6 +244,27 @@
} // namespace detail
+namespace detail {
+ // Stuff for directed_graph and undirected_graph to skip over their first
+ // vertex_index and edge_index properties when providing vertex_all and
+ // edge_all; make sure you know the exact structure of your properties if you
+ // use there.
+ struct remove_first_property {
+ template <typename F>
+ struct result {
+ typedef typename boost::function_traits<F>::arg1_type a1;
+ typedef typename boost::remove_reference<a1>::type non_ref;
+ typedef typename non_ref::next_type nx;
+ typedef typename boost::mpl::if_<boost::is_const<non_ref>, boost::add_const<nx>, nx>::type with_const;
+ typedef typename boost::add_reference<with_const>::type type;
+ };
+ template <typename Prop>
+ typename Prop::next_type& operator()(Prop& p) const {return p.m_base;}
+ template <typename Prop>
+ const typename Prop::next_type& operator()(const Prop& p) const {return p.m_base;}
+ };
+}
+
} // namesapce boost
#endif /* BOOST_PROPERTY_HPP */
Modified: branches/release/libs/graph/doc/astar_search.html
==============================================================================
--- branches/release/libs/graph/doc/astar_search.html (original)
+++ branches/release/libs/graph/doc/astar_search.html 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -37,10 +37,28 @@
typename P, typename T, typename R>
void
astar_search_no_init
+ (const IncidenceGraph &g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ AStarHeuristic h, const bgl_named_params<P, T, R>& params);
+
+template <typename VertexListGraph,
+ typename AStarHeuristic,
+ typename P, typename T, typename R>
+void
+astar_search_tree
(const VertexListGraph &g,
typename graph_traits<VertexListGraph>::vertex_descriptor s,
<a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params);
+template <typename VertexListGraph,
+ typename AStarHeuristic,
+ typename P, typename T, typename R>
+void
+astar_search_no_init_tree
+ (const IncidenceGraph &g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ AStarHeuristic h, const bgl_named_params<P, T, R>& params);
+
<i>// Non-named parameter interface</i>
template <typename VertexListGraph, typename AStarHeuristic,
typename AStarVisitor, typename PredecessorMap,
@@ -60,7 +78,23 @@
CompareFunction compare, CombineFunction combine,
CostInf inf, CostZero zero);
-<i>// Version that does not initialize property maps (used for implicit graphs)</i>
+template <typename VertexListGraph, typename AStarHeuristic,
+ typename AStarVisitor, typename PredecessorMap,
+ typename CostMap, typename DistanceMap,
+ typename WeightMap,
+ typename CompareFunction, typename CombineFunction,
+ typename CostInf, typename CostZero>
+inline void
+astar_search_tree
+ (const VertexListGraph &g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ AStarHeuristic h, AStarVisitor vis,
+ PredecessorMap predecessor, CostMap cost,
+ DistanceMap distance, WeightMap weight,
+ CompareFunction compare, CombineFunction combine,
+ CostInf inf, CostZero zero);
+
+<i>// Versions that do not initialize property maps (used for implicit graphs)</i>
template <typename IncidenceGraph, typename AStarHeuristic,
typename AStarVisitor, typename PredecessorMap,
typename CostMap, typename DistanceMap,
@@ -82,6 +116,22 @@
<b>Note that the index_map and color parameters are swapped in
astar_search_no_init() relative to astar_search(); the named parameter
interfaces are not affected.</b>
+
+template <typename IncidenceGraph, typename AStarHeuristic,
+ typename AStarVisitor, typename PredecessorMap,
+ typename CostMap, typename DistanceMap,
+ typename WeightMap,
+ typename CompareFunction, typename CombineFunction,
+ typename CostInf, typename CostZero>
+inline void
+astar_search_no_init_tree
+ (const IncidenceGraph &g,
+ typename graph_traits<IncidenceGraph>::vertex_descriptor s,
+ AStarHeuristic h, AStarVisitor vis,
+ PredecessorMap predecessor, CostMap cost,
+ DistanceMap distance, WeightMap weight,
+ CompareFunction compare, CombineFunction combine,
+ CostInf inf, CostZero zero);
</PRE>
<P>
@@ -125,7 +175,8 @@
the entire graph. Implicit searches can be performed with this
implementation of A* by creating special visitors that generate
neighbors of newly-expanded vertices. Please note that
-<tt>astar_search_no_init()</tt> must be used for implicit graphs; the basic
+<tt>astar_search_no_init()</tt> or <tt>astar_search_no_init_tree()</tt> must be
+used for implicit graphs; the basic
<tt>astar_search()</tt> function requires a graph that models
the Vertex List Graph concept. Both
versions
@@ -134,8 +185,9 @@
</P>
<P>
-This implementation of A* is based on an OPEN/CLOSED list formulation
-of the algorithm. Vertices on the OPEN list have been ``discovered''
+For the non-tree versions of the algorithm,
+this implementation of A* is based on an OPEN/CLOSED list formulation.
+Vertices on the OPEN list have been ``discovered''
by the algorithm, but not ``expanded'' (we have not discovered their
adjacent vertices). Vertices on the CLOSED list have been completely
examined by our search (we have expanded them and added their children
@@ -146,7 +198,11 @@
trapped by loops in the graph. The OPEN/CLOSED lists are implemented
using BGL's vertex coloring mechanisms. Vertices in OPEN are colored
gray, vertices in CLOSED are colored black, and undiscovered vertices
-are colored white.
+are colored white. For the versions of the algorithm whose names end in
+<tt>_tree</tt>, all vertices are assumed to always be white, leading to
+checking for repeated vertices being done using the distance map. If a dummy
+value is used for the distance map and the graph contains cycles, the algorithm
+will probably enter an infinite loop.
</P>
<P>
@@ -292,7 +348,8 @@
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
<blockquote>
This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This is necessary for efficient updates of
+ num_vertices(g))</tt>. This is necessary in non-tree versions of the
+ algorithm for efficient updates of
the heap data structure when an edge is relaxed. The type
<tt>VertexIndexMap</tt> must be a model of <a
href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable
@@ -338,7 +395,10 @@
<tt>combine</tt> function object and the zero object for the
identity element. Also the distance value type must have a <a
href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
- provided by the <tt>compare</tt> function object.<br>
+ provided by the <tt>compare</tt> function object. A
+ <tt>constant_writable_property_map</tt> returning the infinity value can be
+ used for this parameter in tree versions of the algorithm when the graph does
+ not contain a directed cycle.<br>
<b>Default:</b> <tt>shared_array_property_map</tt>
with the same value type as the
@@ -355,7 +415,10 @@
<tt>h</tt>) from the vertex to a goal. The type <tt>CostMap</tt>
must be a model of <a
href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
- Property Map</tt></a>. The vertex descriptor type of the graph
+ Property Map</tt></a> in non-tree versions of the algorithm, and <a
+ href="../../property_map/doc/WritablePropertyMap.html"><tt>Writable Property
+ Map</tt></a> in tree versions of the algorithm. The vertex descriptor type
+ of the graph
needs to be usable as the key type of the distance map. The value
type of the distance map is the element type of a <a
href="./Monoid.html"><tt>Monoid</tt></a> formed with the
@@ -364,7 +427,8 @@
href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
provided by the <tt>compare</tt> function object. The value type
for this map must be the same as the value type for the distance
- map.<br>
+ map. In tree versions of the algorithm, <tt>null_property_map</tt> can be
+ used for this parameter.<br>
<b>Default:</b> <tt>shared_array_property_map</tt>
with the same value type as the
@@ -375,7 +439,8 @@
UTIL/OUT: <tt>color_map(ColorMap c_map)</tt>
<blockquote>
- This is used during the execution of the algorithm to mark the
+ This is used during the execution of non-tree versions of the algorithm to
+ mark the
vertices, indicating whether they are on the OPEN or CLOSED lists.
The vertices start out white and become gray when they are inserted
into the OPEN list. They then turn black when they are examined and
Modified: branches/release/libs/graph/doc/graph_concepts.html
==============================================================================
--- branches/release/libs/graph/doc/graph_concepts.html (original)
+++ branches/release/libs/graph/doc/graph_concepts.html 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -396,7 +396,7 @@
demonstrates using the <TT>out_edges()</TT>, <TT>source()</TT>, and
<TT>target()</TT> with an undirected graph. The source code for this
example and the following one can be found in <a
-href="../example/undirected.cpp"><TT>examples/undirected.cpp</TT></a>.
+href="../example/undirected_adjacency_list.cpp"><TT>example/undirected_adjacency_list.cpp</TT></a>.
<P>
<PRE>
Modified: branches/release/libs/graph/doc/push_relabel_max_flow.html
==============================================================================
--- branches/release/libs/graph/doc/push_relabel_max_flow.html (original)
+++ branches/release/libs/graph/doc/push_relabel_max_flow.html 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -158,7 +158,7 @@
#include <boost/config.hpp>
#include <iostream>
#include <string>
-#include <boost/graph/push_relabel_map_flow.hpp>
+#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
Modified: branches/release/libs/graph/doc/read_graphml.html
==============================================================================
--- branches/release/libs/graph/doc/read_graphml.html (original)
+++ branches/release/libs/graph/doc/read_graphml.html 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -20,7 +20,7 @@
Authors: Tiago de Paula Peixoto -->
<pre class="literal-block">
void read_graphml(std::istream& in, MutableGraph& graph,
- dynamic_properties& dp);
+ dynamic_properties& dp, size_t graph_index = 0);
</pre>
<p>The <tt class="docutils literal"><span class="pre">read_graphml</span></tt> function interprets a graph described using the
<a class="reference external" href="http://graphml.graphdrawing.org/">GraphML</a> format and builds a BGL graph that captures that
@@ -39,6 +39,10 @@
and with the appropriate C++ value type based on the GraphML attribute type
definition. Graph properties are also set with the same
<a class="reference external" href="../../property_map/doc/dynamic_property_map.html">dynamic_properties</a> object, where the key type is the type of the graph itself.</p>
+<p>If the file contains multiple graphs, the <tt class="docutils literal"><span class="pre">graph_index</span></tt> parameter controls
+which graph will be loaded. It defaults to <tt class="docutils literal"><span class="pre">0</span></tt>, meaning that the first graph
+in the file will be loaded. If <tt class="docutils literal"><span class="pre">graph_index</span></tt> is greater than or equal to the
+number of graphs in the file, an empty graph will be returned.</p>
<dl class="docutils">
<dt>Requirements:</dt>
<dd><ul class="first last simple">
@@ -156,7 +160,7 @@
</div>
<div class="footer">
<hr class="footer" />
-Generated on: 2009-06-12 00:41 UTC.
+Generated on: 2012-11-12 22:25 UTC.
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
</div>
Modified: branches/release/libs/graph/doc/read_graphml.rst
==============================================================================
--- branches/release/libs/graph/doc/read_graphml.rst (original)
+++ branches/release/libs/graph/doc/read_graphml.rst 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -19,7 +19,7 @@
::
void read_graphml(std::istream& in, MutableGraph& graph,
- dynamic_properties& dp);
+ dynamic_properties& dp, size_t graph_index = 0);
The ``read_graphml`` function interprets a graph described using the
@@ -42,6 +42,11 @@
definition. Graph properties are also set with the same
dynamic_properties_ object, where the key type is the type of the graph itself.
+If the file contains multiple graphs, the ``graph_index`` parameter controls
+which graph will be loaded. It defaults to ``0``, meaning that the first graph
+in the file will be loaded. If ``graph_index`` is greater than or equal to the
+number of graphs in the file, an empty graph will be returned.
+
Requirements:
- The type of the graph must model the `Mutable Graph`_ concept.
- The type of the iterator must model the `Multi-Pass Iterator`_
Modified: branches/release/libs/graph/doc/small_world_generator.html
==============================================================================
--- branches/release/libs/graph/doc/small_world_generator.html (original)
+++ branches/release/libs/graph/doc/small_world_generator.html 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -45,7 +45,7 @@
small_world_iterator();
small_world_iterator(RandomGenerator& gen, vertices_size_type n,
- vertices_size_type k, double probability,
+ vertices_size_type k, double probability = 0.,
bool allow_self_loops = false);
// Iterator operations
reference operator*() const;
@@ -82,7 +82,7 @@
<pre>
small_world_iterator(RandomGenerator& gen, vertices_size_type n,
- vertices_size_type k, double probability,
+ vertices_size_type k, double probability = 0.,
bool allow_self_loops = false);
</pre>
<blockquote>
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -172,7 +172,7 @@
href="./johnson_all_pairs_shortest.html"><tt>johnson_all_pairs_shortest_paths</tt></A>
<li>floyd_warshall_all_pairs_shortest_paths</li>
<li>r_c_shortest_paths - resource-constrained shortest paths</li>
- <li>astar_search</li>
+ <li>astar_search (A* search algorithm)</li>
</OL>
<LI>Minimum Spanning Tree Algorithms
<OL>
@@ -240,6 +240,7 @@
<li>Graph Structure Comparisons
<ol>
<LI>isomorphism
+ <LI>vf2_sub_graph_iso (VF2 subgraph isomorphism algorithm)
<li>mcgregor_common_subgraphs</li>
</ol>
Copied: branches/release/libs/graph/doc/vf2_sub_graph_iso.html (from r81725, /trunk/libs/graph/doc/vf2_sub_graph_iso.html)
Modified: branches/release/libs/graph/example/Jamfile.v2
Modified: branches/release/libs/graph/example/astar-cities.cpp
Modified: branches/release/libs/graph/example/undirected_adjacency_list.cpp
Modified: branches/release/libs/graph/example/undirected_adjacency_list.expected
Copied: branches/release/libs/graph/example/vf2_sub_graph_iso_example.cpp (from r81725, /trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp)
Copied: branches/release/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (from r81725, /trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp)
Modified: branches/release/libs/graph/src/graphml.cpp
Modified: branches/release/libs/graph/test/Jamfile.v2
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
==============================================================================
--- /trunk/libs/graph/doc/vf2_sub_graph_iso.html (original)
+++ branches/release/libs/graph/doc/vf2_sub_graph_iso.html 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -1,21 +1,23 @@
-<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
+ "http://www.w3.org/TR/html4/strict.dtd">
<!--
- Copyright (c) Flavio De Lorenzi 2012
+ Copyright (C) Flavio De Lorenzi 2012
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt)
--->
+ -->
<html>
<head>
- <title>Boost Graph Library: VF2 (Sub)Graph Isomorphism</title>
+ <meta http-equiv="content-type" content="text/html; charset=iso-8859-15">
+ <title>Boost Graph Library: VF2 (Sub)Graph Isomorphism</title>
<style type="text/css">
<!--
body {
color: black;
background-color: white;
}
-
+
.comment {
color: #333333;
}
@@ -27,295 +29,323 @@
a:visited {
color: #551A8B;
}
- -->
+ -->
</style>
</head>
<body>
- <img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
- <br />
+ <p><img src="../../../boost.png" alt="C++ Boost" width="277" height="86"></p>
<h1>
- <tt>vf2_sub_graph_iso</tt>
+ <tt>vf2_subgraph_iso</tt>
</h1>
<pre>
-<em class="comment">// all defaults interface</em>
+<em class="comment">// All defaults interface</em>
template <typename GraphSmall,
typename GraphLarge,
- typename SubGraphIsoMapCallBack>
-bool vf2_sub_graph_iso(const GraphSmall& graph_small,
- const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback)
+ typename SubGraphIsoMapCallback>
+bool vf2_subgraph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback)
-<em class="comment">// named parameter version</em>
+<em class="comment">// Named parameter version</em>
template <typename GraphSmall,
typename GraphLarge,
typename VertexOrderSmall,
- typename SubGraphIsoMapCallBack,
+ typename SubGraphIsoMapCallback,
typename Param,
typename Tag,
typename Rest>
-bool vf2_sub_graph_iso(const GraphSmall& graph_small,
- const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback,
- const VertexOrderSmall& vertex_order_small,
- const bgl_named_params<Param, Tag, Rest>& params)
+bool vf2_subgraph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ const VertexOrderSmall& vertex_order_small,
+ const bgl_named_params<Param, Tag, Rest>& params)
-<em class="comment">// non-named parameter version</em>
+<em class="comment">// Non-named parameter version</em>
template <typename GraphSmall,
typename GraphLarge,
typename IndexMapSmall,
typename IndexMapLarge,
typename VertexOrderSmall,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename SubGraphIsoMapCallBack>
-bool vf2_sub_graph_iso(const GraphSmall& graph_small,
- const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback,
- IndexMapSmall index_map_small,
- IndexMapLarge index_map_large,
- const VertexOrderSmall& vertex_order_small,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp)
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback>
+bool vf2_subgraph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ IndexMapSmall index_map_small,
+ IndexMapLarge index_map_large,
+ const VertexOrderSmall& vertex_order_small,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp)
</pre>
<p>
An isomorphism between two graphs <em>G<sub>1</sub>=(V<sub>1</sub>, E<sub>1</sub>)</em>
and <em>G<sub>2</sub>=(V<sub>2</sub>, E<sub>2</sub>)</em> is a
bijective mapping <em>M</em> of the vertices of one graph to vertices of the other
graph that preserves the edge structure of the graphs. <em>M</em> is said to be a
- graph-subgraph isomorphism iff <em>M</em> is an isomorphism between
+ graph-subgraph isomorphism if and only if <em>M</em> is an isomorphism between
<em>G<sub>1</sub></em> and a subgraph of <em>G<sub>2</sub></em>.
</p>
<p>
This function finds all graph-subgraph isomorphism mappings between
graphs <tt>graph_small</tt> and <tt>graph_large</tt> and outputs them to
- <tt>user_callback</tt>. It continues until <tt>user_callback</tt>
- returns true or the search space has been fully explored.
- <tt>EdgeCompatibilityPredicate</tt> and
- <tt>VertexCompatibilityPredicate</tt> predicates are used to test whether
- edges and vertices are compatible. To use property maps for equivalence,
- look at the
- <tt>make_property_map_compatible</tt>
- function. By default <tt>always_compatible</tt> is used, which returns
+ <tt>user_callback</tt>. It continues until <tt>user_callback</tt>
+ returns true or the search space has been fully explored. <tt>vf2_subgraph_iso</tt>
+ returns true if a graph-subgraph isomorphism exists and false otherwise.
+ <tt>EdgeEquivalencePredicate</tt> and
+ <tt>VertexEquivalencePredicate</tt> predicates are used to test whether
+ edges and vertices are equivalent. To use property maps for equivalence,
+ see
+ <tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent">
+ make_property_map_equivalent</a></tt>
+ function. By default <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
+ always_equivalent</a></tt> is used, which returns
true for any pair of vertices or edges.
</p>
<p>
The current implementation is based on the <em>VF2</em> algorithm,
introduced by Cordella et al. An in-depth description of the algorithm is
- given in [<a href=#cordella2001>1</a>] and [<a href=#cordella2004>2</a>]
- and references therein. In brief, the process of finding a mapping between
- the two graphs <em>G<sub>1</sub></em> and <em>G<sub>2</sub></em> determines
- the isomorphism mapping <em>M</em>, which associates vertices
- <em>G<sub>1</sub></em> with vertices of <em>G<sub>2</sub></em> and vice
- versa. It can be described by means of a state space representation, which
- is explored by the algorithm according to a depth-first strategy. Each
- state <em>s</em> of the matching process can be associated with a partial
- mapping <em>M(s)</em>. At each level, the algorithm computes the set of
- the vertex pairs that are candidates to be added to the current state
- <em>s</em>. If a pair of vertices (<em>v, w</em>) is feasible, the mapping
- is extended and the associated successor state <em>s'</em> is computed.
- The whole procedure is then repeated for state <em>s'</em>. A somewhat more
- detailed description of the current implementation is given in the file
- vf2_sub_graph_iso_impl.pdf.
+ given in [1] and [2]
+ and references therein. The original code by P. Foggia and collaborators can
+ be found at [3]. In brief, the process of
+ finding a mapping between the two graphs <em>G<sub>1</sub></em> and
+ <em>G<sub>2</sub></em> determines the isomorphism mapping <em>M</em>,
+ which associates vertices <em>G<sub>1</sub></em> with vertices of
+ <em>G<sub>2</sub></em> and vice versa. It can be described by means of a
+ state space representation which is created by the algorithm
+ while exploring the search graph in depth-first fashion.
+ Each state <em>s</em> of the matching process
+ can be associated with a partial mapping <em>M(s)</em>. At each level,
+ the algorithm computes the set of the vertex pairs that are candidates to
+ be added to the current state <em>s</em>. If a pair of vertices
+ (<em>v, w</em>) is feasible, the mapping is extended and the associated
+ successor state <em>s'</em> is computed.
+ The whole procedure is then repeated for state <em>s'</em>.
</p>
<h3>Where Defined</h3>
- boost/graph/vf2_sub_graph_iso.hpp
<p>
+ <a href="../../../boost/graph/vf2_sub_graph_iso.hpp">
+ <tt>boost/graph/vf2_sub_graph_iso.hpp</tt></a><br>
All functions are defined in the boost namespace.
</p>
<h3>Parameters</h3>
-
- IN: <tt>const GraphSmall& graph_small</tt>
- <blockquote>
- The (first) smaller graph (fewer vertices) of the pair to be tested for
- isomorphism. The type <tt>GraphSmall</tt> must be a
- model of
- Vertex List Graph
- Edge List Graph,
- Bidirectional Graph and
- Adjacency Matrix.
- </blockquote>
-
- IN: <tt>const GraphLarge& graph_large</tt>
- <blockquote>
- The (second) larger graph to be tested.
- Type <tt>GraphLarge</tt> must be a model of
- Vertex List Graph
- Edge List Graph,
- Bidirectional Graph and
- Adjacency Matrix.
- </blockquote>
-
- OUT: <tt>SubGraphIsoMapCallBack user_callback</tt>
+
+ <p>IN: <tt>const GraphSmall& graph_small</tt></p>
<blockquote>
- A function object to be called when a graph-subgraph isomorphism has been discovered. The
- <tt>operator()</tt> must have following form:
+ <p>
+ The (first) smaller graph (fewer vertices) of the pair to be tested for
+ isomorphism. The type <tt>GraphSmall</tt> must be a
+ model of
+ Vertex List Graph,
+ Edge List Graph,
+ Bidirectional Graph and
+ Adjacency Matrix.
+ The edge descriptors <tt>graph_traits<GraphSmall>::edge_descriptor</tt>
+ must be <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+ LessThan Comparable</a>, cf. also the remark below.
+ </p>
+ </blockquote>
+
+ <p>IN: <tt>const GraphLarge& graph_large</tt></p>
+ <blockquote>
+ <p>
+ The (second) larger graph to be tested.
+ Type <tt>GraphLarge</tt> must be a model of
+ Vertex List Graph,
+ Edge List Graph,
+ Bidirectional Graph and
+ Adjacency Matrix.
+ The edge descriptors <tt>graph_traits<GraphLarge>::edge_descriptor</tt>
+ must be <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+ LessThan Comparable</a>, cf. also the remark below.
+ </p>
+ </blockquote>
+
+ <p>OUT: <tt>SubGraphIsoMapCallback user_callback</tt></p>
+ <blockquote>
+ <p>
+ A function object to be called when a graph-subgraph isomorphism has been discovered. The
+ <tt>operator()</tt> must have following form:
+ </p>
<pre>
template <typename CorrespondenceMap1To2,
typename CorrespondenceMap2To1>
bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const
</pre>
- Both the <tt>CorrespondenceMap1To2</tt>
- and <tt>CorresondenceMap2To1</tt> types are models
- of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
- Property Map</a> and map equivalent vertices across the two
- graphs given to <tt>vf2_sub_graph_iso</tt> (or <tt>vf2_graph_iso</tt>. For
- instance, if <tt>v</tt> is
- from <tt>graph_small</tt>, <tt>w</tt> is from <tt>graph_large</tt>,
- and the vertices can be considered equivalent,
- then <tt>get(f, v)</tt> will be <tt>w</tt> and <tt>get(g, w)</tt>
- will be <tt>v</tt>. If any vertex, say <tt>v</tt> in <tt>graph_small</tt>,
- does not match a vertex in <tt>graph_large</tt> ,
- then <tt>get(f, v)</tt> will be <tt>graph_traits<GraphLarge>::null_vertex()</tt>.
- Likewise for any un-matched vertices from <tt>graph_large</tt>,
- <tt>get(g, w)</tt> will be <tt>graph_traits<GraphSmall>::null_vertex()</tt>.
-
- Returning false from the callback will abort the search immediately. Otherwise,
- the entire search space will be explored. A "default" print callback
- is provided as a utility function and another one is
- given in Example 2.
- </blockquote>
-
- IN: <tt>const VertexOrderSmall& vertex_order_small</tt>
- <blockquote>
- The ordered vertices of the smaller (first) graph <tt>graph_small</tt>.
- During the matching process the vertices are examined in the order given by
- <tt>vertex_order_small</tt>. Type <tt>VertexOrderSmall</tt> must be a model
- of ContainerConcept
- with value type
- <tt>graph_traits<GraphSmall>::vertex_descriptor</tt>.
- <br />
- <b>Default</b> The vertices are ordered by multiplicity of in/out degree.
+ <p>
+ Both the <tt>CorrespondenceMap1To2</tt>
+ and <tt>CorresondenceMap2To1</tt> types are models
+ of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
+ Property Map</a> and map equivalent vertices across the two
+ graphs given to <tt>vf2_subgraph_iso</tt> (or <tt>vf2_graph_iso</tt>). For
+ instance, if <tt>v</tt> is
+ from <tt>graph_small</tt>, <tt>w</tt> is from <tt>graph_large</tt>,
+ and the vertices can be considered equivalent,
+ then <tt>get(f, v)</tt> will be <tt>w</tt> and <tt>get(g, w)</tt>
+ will be <tt>v</tt>. If any vertex, say <tt>v</tt> in <tt>graph_small</tt>,
+ does not match a vertex in <tt>graph_large</tt> ,
+ then <tt>get(f, v)</tt> will be <tt>graph_traits<GraphLarge>::null_vertex()</tt>.
+ Likewise for any unmatched vertices from <tt>graph_large</tt>,
+ <tt>get(g, w)</tt> will be <tt>graph_traits<GraphSmall>::null_vertex()</tt>.
+
+ Returning false from the callback will abort the search immediately. Otherwise,
+ the entire search space will be explored. A "default" print callback
+ is provided as a utility function.
+ </p>
+ </blockquote>
+
+ <p>IN: <tt>const VertexOrderSmall& vertex_order_small</tt></p>
+ <blockquote>
+ <p>
+ The ordered vertices of the smaller (first) graph <tt>graph_small</tt>.
+ During the matching process the vertices are examined in the order given by
+ <tt>vertex_order_small</tt>. Type <tt>VertexOrderSmall</tt> must be a model
+ of ContainerConcept
+ with value type
+ <tt>graph_traits<GraphSmall>::vertex_descriptor</tt>.
+ <br>
+ <b>Default</b> The vertices are ordered by multiplicity of
+ in/out degrees.
+ </p>
</blockquote>
<h3>Named Parameters</h3>
- IN: <tt>vertex_index1(IndexMapSmall index_map_small)</tt>
+ <p>IN: <tt>vertex_index1(IndexMapSmall index_map_small)</tt></p>
<blockquote>
- This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_small))</tt>.
- Type <tt>IndexMapSmall</tt> must be a model of
- Readable Property Map.
- <br />
- <b>Default:</b> <tt>get(vertex_index, graph_small)</tt>
- </blockquote>
-
- IN: <tt>vertex_index2(IndexMapLarge index_map_large)</tt>
- <blockquote>
- This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_large))</tt>.
- Type <tt>IndexMapLarge</tt> must be a model of
- Readable Property Map.
- <br />
- <b>Default:</b> <tt>get(vertex_index, graph_large)</tt>
+ <p>
+ This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_small))</tt>.
+ Type <tt>IndexMapSmall</tt> must be a model of
+ Readable Property Map.
+ <br>
+ <b>Default:</b> <tt>get(vertex_index, graph_small)</tt>
+ </p>
+ </blockquote>
+
+ <p>IN: <tt>vertex_index2(IndexMapLarge index_map_large)</tt></p>
+ <blockquote>
+ <p>
+ This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_large))</tt>.
+ Type <tt>IndexMapLarge</tt> must be a model of
+ Readable Property Map.
+ <br>
+ <b>Default:</b> <tt>get(vertex_index, graph_large)</tt>
+ </p>
+ </blockquote>
+
+ <p>IN: <tt>edges_equivalent(EdgeEquivalencePredicate edge_comp)</tt></p>
+ <blockquote>
+ <p>
+ This function object is used to determine if edges between the two graphs
+ <tt>graph_small</tt> and <tt>graph_large</tt> are equivalent.
+ Type <tt>EdgeEquivalencePredicate</tt> must be a model of
+ <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
+ Predicate</a> and have argument types of
+ <tt>graph_traits<GraphSmall>::edge_descriptor</tt> and
+ <tt>graph_traits<GraphLarge>::edge_descriptor</tt>.
+ The edge descriptors must be <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+ LessThan Comparable</a>. A return value of true indicates that the edges are equivalent.
+ <br>
+ <b>Default:</b> <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
+ always_equivalent</a></tt>
+ </p>
+ </blockquote>
+
+ <p>IN: <tt>vertices_equivalent(VertexEquivalencePredicate vertex_comp)</tt></p>
+ <blockquote>
+ <p>
+ This function object is used to determine if vertices between the two graphs
+ <tt>graph_small</tt> and <tt>graph_large</tt> are equivalent.
+ Type <tt>VertexEquivalencePredicate</tt> must be a model of
+ Binary Predicate
+ and have argument types of
+ <tt>graph_traits<GraphSmall>::vertex_descriptor</tt> and
+ <tt>graph_traits<GraphLarge>::vertex_descriptor</tt>. A return value of true
+ indicates that the vertices are equivalent.
+ <br>
+ <b>Default:</b> <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
+ always_equivalent</a></tt>
+ </p>
</blockquote>
-
- IN: <tt>edges_equivalent(EdgeCompatibilityPredicate edge_comp)</tt>
- <blockquote>
- This function object is used to determine if edges between the two graphs
- <tt>graph_small</tt> and <tt>graph_large</tt> are compatible.
- Type <tt>EdgeCompatiblePredicate</tt> must be a model of
- of <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
- Predicate</a> and have argument types of
- <tt>graph_traits<GraphSmall>::edge_descriptor</tt> and
- <tt>graph_traits<GraphLarge>::edge_descriptor</tt>. A return value of true
- indicates that the edges are compatible.
- <br />
- <b>Default:</b> <tt>always_compatible</tt>
- </blockquote>
-
- IN: <tt>vertices_equivalent(VertexCompatibilityPredicate vertex_comp)</tt>
- <blockquote>
- This function object is used to determine if vertices between the two graphs
- <tt>graph_small</tt> and <tt>graph_large</tt> are compatible.
- Type <tt>VertexCompatiblePredicate</tt> must be a model of
- Binary Predicate
- and have argument types of
- <tt>graph_traits<GraphSmall>::vertex_descriptor</tt> and
- <tt>graph_traits<GraphLarge>::vertex_descriptor</tt>. A return value of true
- indicates that the vertices are compatible.
- <br />
- <b>Default:</b> <tt>always_compatible</tt>
- </blockquote>
-
+
<h3>Related Functions</h3>
<p>
Non-named parameter, named-parameter and all default parameter versions of
function
</p>
- <pre>
-vf2_graph_iso(...)
- </pre>
+ <p><tt>vf2_graph_iso(...)</tt></p>
<p>
for isomorphism testing take the same parameters as the corresponding
- functions <tt>vf2_sub_graph_iso</tt> for sub-graph isomorphism testing.
+ functions <tt>vf2_subgraph_iso</tt> for subgraph isomorphism testing.
The algorithm finds all isomorphism mappings between graphs
<tt>graph1</tt> and <tt>graph2</tt> and outputs them to
<tt>user_callback</tt>. It continues until <tt>user_callback</tt>
returns true or the search space has been fully explored. As before,
- <tt>EdgeCompatibilityPredicate</tt> and
- <tt>VertexCompatibilityPredicate</tt> predicates are used to test
- whether edges and vertices are compatible with
- <tt>always_compatible</tt> as default.
+ <tt>EdgeEquivalencePredicate</tt> and
+ <tt>VertexEquivalencePredicate</tt> predicates are used to test
+ whether edges and vertices are equivalent. By default
+ <tt>always_equivalent</tt> is used.
</p>
-
- <h3>Utility Functions and Structs</h3>
- <pre id="make_property_map_compatible">
-template <typename PropertyMap1,
- typename PropertyMap2>
-property_map_compatible<PropertyMap1, PropertyMap2>
-make_property_map_compatible(const PropertyMap1 property_map1,
- const PropertyMap2 property_map2)
- </pre>
- <blockquote>
- Returns a binary predicate function object
- (<tt>property_map_compatible<PropertyMap1, PropertyMap2></tt>) that compares
- vertices or edges between graphs using property maps.
- </blockquote>
- <tt id="always_compatible">struct always_compatible</tt>
+ <h3>Utility Functions and Structs</h3>
+ <p>
+ <tt id="vf2_callback">
+template<typename Graph1,
+ typename Graph2>
+struct vf2_print_callback
+ </tt>
+ </p>
<blockquote>
- A binary function object that returns true for any pair of items.
+ <p>
+ Callback function object that prints out the correspondences between vertices
+ of <tt>Graph1</tt> and <tt>Graph2</tt>. The constructor takes
+ the two graphs <em>G<sub>1</sub></em> and <em>G<sub>2</sub></em>.
+ </p>
</blockquote>
- <pre id="vf2_callback">
-template <typename Graph1,
- typename Graph2>
-struct vf2_print_callback
+ <pre>
+template<typename Graph>
+std::vector<typename graph_traits<Graph>::vertex_descriptor>
+ vertex_order_by_mult(const Graph& graph)
</pre>
<blockquote>
- Callback function object that prints out the correspondences between vertices
- of <tt>Graph1</tt> and <tt>Graph2</tt>. The constructor takes the two graphs <em>G<sub>1</sub></em>
- and <em>G<sub>2</sub></em> and an optional <tt>bool</tt> parameter as arguments. If the latter is
- set to <tt>true</tt>, the callback function will verify the mapping before outputting
- it to standard output.
+ <p>
+ Returns a vector containing the vertices of a graph, sorted
+ by multiplicity of in/out degrees.
+ </p>
</blockquote>
<pre>
-<em class="comment">// Variant of verify_sub_graph_iso with all default parameters</em>
+<em class="comment">// Variant of verify_subgraph_iso with all default parameters</em>
template<typename Graph1,
typename Graph2,
typename CorresponenceMap1To2>
-inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
- const CorresponenceMap1To2 f)
+inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f)
<em class="comment">// Verifies a graph (sub)graph isomorphism map</em>
template<typename Graph1,
typename Graph2,
typename CorresponenceMap1To2,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate>
-inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
- const CorresponenceMap1To2 f,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp)
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate>
+inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp)
</pre>
<blockquote>
-This function can be used to verify a (sub)graph isomorphism mapping <em>f</em>. The parameters are
-akin to function <tt>vf2_sub_graph_iso</tt> (<tt>vf2_graph_iso</tt>).
+ <p>
+ This function can be used to verify a (sub)graph isomorphism
+ mapping <em>f</em>. The parameters are analogous to
+ function <tt>vf2_subgraph_iso</tt> (<tt>vf2_graph_iso</tt>).
+ </p>
</blockquote>
@@ -333,12 +363,12 @@
<p>
In the example below, a small graph <tt>graph1</tt> and a larger graph
<tt>graph2</tt> are defined. Here small and large refers to the number of
- vertices of the graphs. <tt>vf2_sub_graph_iso</tt> computes all the
- sub-graph isomorphism mappings between the two graphs and outputs them
+ vertices of the graphs. <tt>vf2_subgraph_iso</tt> computes all the
+ subgraph isomorphism mappings between the two graphs and outputs them
via <tt>callback</tt>.
</p>
<pre>
-typedef adjacency_list<vecS, vecS, bidirectionalS> graph_type;
+typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;
<em class="comment">// Build graph1</em>
int num_vertices1 = 8; graph_type graph1(num_vertices1);
@@ -353,195 +383,135 @@
add_edge(1, 5, graph2); add_edge(1, 7, graph2);
add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
-
-<em class="comment">// true instructs callback to verify a map using
-// verify_vf2_sub_graph_iso</em>
-vf2_print_callback<graph_type, graph_type> callback(graph1, graph2, true);
-
-bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
+<em class="comment">
+// Create callback to print mappings</em>
+vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
+
+<em class="comment">
+// Print out all subgraph isomorphism mappings between graph1 and graph2.
+// Vertices and edges are assumed to be always equivalent.</em>
+vf2_subgraph_iso(graph1, graph2, callback);
</pre>
-<p>
-The complete example can be found under
-examples/vf2_sub_graph_iso_example.cpp.
-<br>
-<p>
-
+ <p>
+ The complete example can be found under
+ examples/vf2_sub_graph_iso_example.cpp.
+ <br>
+ </p>
<h4>Example 2</h4>
- This example uses the GraphViz input parser, i.e. read_graphviz
- function to interpret the two graphs specified in files <em>graph_small.dot</em> and <em>graph_large.dot</em>
- using the using the GraphViz DOT language. Sample files are provided
- below. <tt>vf2_sub_graph_iso</tt> computes all the sub-graph isomorphism mappings
- between <tt>graph_small</tt> and <tt>graph_large</tt>.
+ <p>
+ In this example, the subgraph isomorphism mappings between multi-graphs are computed. The vertices
+ and edges of the multi-graphs are distinguished using property maps.
+ </p>
<pre>
-std::ifstream graph_small_file("graph_small.dot");
-std::ifstream graph_large_file("graph_large.dot");
-
-<em class="comment">// Vertex properties</em>
-typedef property <vertex_name_t, std::string> vertex_p;
-
-<em class="comment">// adjacency_list-based type</em>
-typedef adjacency_list <vecS, vecS, undirectedS, vertex_p> graph_t;
-
-<em class="comment">// Construct an empty graph_small and prepare the dynamic_property_maps.</em>
-graph_t graph_small(0);
-dynamic_properties dp_small;
-
-property_map<graph_t, vertex_name_t>::type name_small =
- get(vertex_name, graph_small);
-dp_small.property("node_id", name_small);
-
-<em class="comment">// Read graph_small</em>
-bool status = read_graphviz(graph_small_file, graph_small, dp_small, "node_id");
-
-<em class="comment">// Construct an empty graph_large and prepare the dynamic_property_maps,
-// following the read_graphviz example</em>
-graph_t graph_large(0);
-dynamic_properties dp_large;
-
-property_map<graph_t, vertex_name_t>::type name_large =
- get(vertex_name, graph_large);
-dp_large.property("node_id", name_large);
-
-<em class="comment">// Read graph_large</em>
-status = read_graphviz(graph_large_file, graph_large, dp_large, "node_id");
-
-<em class="comment">// Create the call_back function</em>
-typedef property_map<graph_t, vertex_name_t>::type p_map_t;
-print_callback<graph_t, graph_t, p_map_t, p_map_t> callback(graph_small, graph_large,
- name_small, name_large, true);
-<em class="comment"> // Compute the sub-graph isomorphism mappings</em>
-bool ret = vf2_sub_graph_iso(graph_small, graph_large, callback);
+<em class="comment">// Define edge and vertex properties</em>
+typedef property<edge_name_t, char> edge_property;
+typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_property;
+
+<em class="comment">// Using a vecS graphs => the index maps are implicit.</em>
+typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
+
+<em class="comment">// Create graph1</em>
+graph_type graph1;
+<em class="comment">// Add vertices... </em>
+add_vertex(vertex_property('a'), graph1);
+...
+<em class="comment">//... and edges </em>
+add_edge(0, 1, edge_property('b'), graph1);
+add_edge(0, 1, edge_property('b'), graph1);
+...
+
+<em class="comment">// Create graph2 </em>
+graph_type graph2;
+add_vertex(vertex_property('a'), graph2);
+...
+add_edge(0, 1, edge_property('a'), graph2);
+...
</pre>
- To output the mappings using the node names, the following callback function object is created:
+ <p>
+ To distinguish vertices and edges with property maps, binary predicates are created using the
+ <tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent">
+ make_property_map_equivalent</a></tt> function:
+ </p>
<pre>
-<em id="example_callback" class="comment">// Define a print_callback</em>
-template <typename Graph1,
- typename Graph2,
- typename PropertyMap1,
- typename PropertyMap2>
-struct print_callback {
-
- print_callback(const Graph1& graph1, const Graph2& graph2,
- PropertyMap1 p_map1, PropertyMap2 p_map2,
- bool verify = false)
- : graph1_(graph1), graph2_(graph2),
- p_map1_(p_map1), p_map2_(p_map2),
- verify_(verify) {}
-
- template <typename CorrespondenceMap1To2,
- typename CorrespondenceMap2To1>
- bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
-
- if (verify_)
- std::cout << "Verify: " << std::boolalpha
- << verify_vf2_sub_graph_iso(graph1_, graph2_, f)
- << std::endl;
-
-<em class="comment">// Print sub graph isomorphism map</em>
- BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
- std::cout << '(' << get(p_map1_,v) << ", "
- << get(p_map2_, get(f, v)) << ") ";
-
- std::cout << std::endl;
-
- return true;
- }
-
-private:
- const Graph1& graph1_;
- const Graph2& graph2_;
-
- const PropertyMap1& p_map1_;
- const PropertyMap2& p_map2_;
-
- const bool verify_;
-};
+<em class="comment">// Create the vertex binary predicate</em>
+typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
+typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
+vertex_comp_t vertex_comp =
+ make_property_map_equivalent(get(vertex_name, graph1), get(vertex_name, graph2));
+
+<em class="comment">// Create the vertex binary predicate</em>
+typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
+typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
+edge_comp_t edge_comp =
+ make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2));
</pre>
- Using the sample DOT-files <em>graph_small.dot</em>:
+ <p>
+ Finally, a callback function object is created and the subgraph isomorphism mappings are
+ computed:
+ </p>
+ <pre>
+<em class="comment">// Create callback</em>
+vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
- <pre id="dot_files">
-graph G_small {
-node1 -- node2;
-node1 -- node3;
-node3 -- node3;
-node4 -- node1;
-node4 -- node3;
-}
+<em class="comment">
+// Print out all subgraph isomorphism mappings between graph1 and graph2.
+// Function vertex_order_by_mult is used to compute the order of
+// vertices of graph1. This is the order in which the vertices are examined
+// during the matching process.</em>
+vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
+ edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
</pre>
- and <em>graph_large.dot</em>:
-
- <pre>
-graph G_large {
-node1 -- node3;
-node1 -- node4;
-node1 -- node6;
-node2 -- node4;
-node2 -- node5;
-node3 -- node3;
-node4 -- node5;
-node4 -- node6;
-node6 -- node6;
-}
- </pre>
+ <p>
+ For the complete example, see
+ <a href="../example/vf2_sub_graph_iso_multi_example.cpp">
+ <tt>examples/vf2_sub_graph_iso_multi_example.cpp</tt></a>.
+ <br>
+ </p>
- <tt>vf2_sub_graph_iso</tt> finds the mappings <tt>(node1, node4) (node2, node2)
- (node3, node6) (node4, node1)</tt> and <tt>(node1, node4) (node2, node5)
- (node3, node6) (node4, node1)</tt>.
- To compile this example, you will need to build and link against the
- "boost_graph" and "boost_regex" libraries
- (cf. read_graphviz).
-
-<p>
-The complete example is provided under
-examples/vf2_sub_graph_iso_gviz_example.cpp,
-including a Scilab script to generate simple dot-files
-examples/vf2_random_graphs.sce.
-<br>
-<p>
-
-
-<h4>Additional Examples</h4>
-
-<p>
-These are: a multi-graph example
-examples/vf2_sub_graph_iso_multi_example.cpp,
-<br>
-one using a compressed_sparse_row_graph (works not for <tt>directed</tt> because <tt>in_edges</tt> not available)
-examples/vf2_sub_graph_iso_csr_example.cpp,
-<br>
-one putting a grid_graph
-examples/vf2_sub_graph_iso_grd_example.cpp
-<br>
-and one matching bidirectional und undirected graphs
-examples/vf2_sub_graph_iso_undir_example.cpp.
-<br>
-<p>
+ <h3 id="notes">Notes</h3>
+ <p>
+ If the <tt>EdgeList</tt> allows for parallel edges, e.g. <tt>vecS</tt>, the
+ algorithm does some bookkeeping of already identified edges. Matched edges
+ are temporarily stored using <tt>std::set</tt> as container, requiring that
+ <tt>edge_descriptor</tt> are <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+ LessThan Comparable</a>. In contrast, if instead you enforce the absence of
+ parallel edges, e.g. by using <tt>setS</tt>, the lookup function falls back
+ to <tt>edge()</tt> without performing any bookkeeping.
+ </p>
<h3>Bibliography</h3>
<dl>
- <p></p><dt><a name="cordella2001">1</a>
- <dd>
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
- <br><em>An improved algorithm for matching large graphs</em>.
- <br>In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001.
- </dd>
- <p></p><dt><a name="cordella2004">2</a>
- <dd>
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
- <br><em>A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs</em>.
- <br>IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 1367-1372, 2004.
- </dd>
+ <dt><a name="cordella2001">1</a></dt>
+ <dd>
+ L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
+ <br><em>An improved algorithm for matching large graphs</em>.
+ <br>In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001.
+ <p></p>
+ </dd>
+ <dt><a name="cordella2004">2</a></dt>
+ <dd>
+ L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
+ <br><em>A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs</em>.
+ <br>IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 1367-1372, 2004.
+ <p></p>
+ </dd>
+ <dt><a name="foggia_etal">3</a></dt>
+ <dd>
+ <a href="http://www.cs.sunysb.edu/~algorith/implement/vflib/implement.shtml">
+ <tt>http://www.cs.sunysb.edu/~algorith/implement/vflib/implement.shtml></a>
+ <p></p>
+ </dd>
</dl>
-
- <hr />
- Copyright © 2012, Flavio De Lorenzi
- (<a href="mailto:fdlorenzi_at_[hidden]">fdlorenzi_at_[hidden]</a>)
-
+ <hr>
+ <p>
+ Copyright © 2012, Flavio De Lorenzi
+ (<a href="mailto:fdlorenzi_at_[hidden]">fdlorenzi_at_[hidden]</a>)
+ </p>
</body>
</html>
==============================================================================
--- branches/release/libs/graph/example/Jamfile.v2 (original)
+++ branches/release/libs/graph/example/Jamfile.v2 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -30,6 +30,7 @@
# exe cc-internet : cc-internet.cpp ../build//boost_graph ;
exe implicit_graph : implicit_graph.cpp ;
exe astar_maze : astar_maze.cpp ;
+exe astar-cities : astar-cities.cpp ;
exe stoer_wagner : stoer_wagner.cpp ;
exe bfs-example : bfs-example.cpp ;
exe bfs-example2 : bfs-example2.cpp ;
@@ -43,3 +44,6 @@
exe strong-components : strong-components.cpp ;
exe subgraph : subgraph.cpp ;
exe subgraph_properties : subgraph_properties.cpp ;
+exe vf2_sub_graph_iso_example : vf2_sub_graph_iso_example.cpp ;
+exe vf2_sub_graph_iso_multi_example : vf2_sub_graph_iso_multi_example.cpp ;
+
==============================================================================
--- branches/release/libs/graph/example/astar-cities.cpp (original)
+++ branches/release/libs/graph/example/astar-cities.cpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -192,7 +192,7 @@
vector<cost> d(num_vertices(g));
try {
// call astar named parameter interface
- astar_search
+ astar_search_tree
(g, start,
distance_heuristic<mygraph_t, cost, location*>
(locations, goal),
==============================================================================
--- branches/release/libs/graph/example/undirected_adjacency_list.cpp (original)
+++ branches/release/libs/graph/example/undirected_adjacency_list.cpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -26,12 +26,12 @@
add_edge(zero, two, undigraph);
add_edge(one, two, undigraph);
- std::cout << "out_edges(0): ";
+ std::cout << "out_edges(0):";
for (boost::tie(out, out_end) = out_edges(zero, undigraph); out != out_end; ++out)
- std::cout << *out;
- std::cout << std::endl << "in_edges(0): ";
+ std::cout << ' ' << *out;
+ std::cout << std::endl << "in_edges(0):";
for (boost::tie(in, in_end) = in_edges(zero, undigraph); in != in_end; ++in)
- std::cout << *in;
+ std::cout << ' ' << *in;
std::cout << std::endl;
}
@@ -91,6 +91,14 @@
#endif
std::cout << "weight[(u,v)] = " << get(weight, e1) << std::endl;
std::cout << "weight[(v,u)] = " << get(weight, e2) << std::endl;
+
+ std::cout << "the edges incident to v: ";
+ typename boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
+ typename boost::graph_traits<UndirectedGraph>::vertex_descriptor
+ s = vertex(0, undigraph);
+ for (boost::tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e)
+ std::cout << "(" << source(*e, undigraph)
+ << "," << target(*e, undigraph) << ")" << std::endl;
}
@@ -103,7 +111,7 @@
typedef adjacency_list < vecS, vecS, directedS,
no_property, Weight > DirectedGraph;
undirected_graph_demo1 < UndirectedGraph > ();
- undirected_graph_demo2 < UndirectedGraph > ();
directed_graph_demo < DirectedGraph > ();
+ undirected_graph_demo2 < UndirectedGraph > ();
return 0;
}
==============================================================================
--- branches/release/libs/graph/example/undirected_adjacency_list.expected (original)
+++ branches/release/libs/graph/example/undirected_adjacency_list.expected 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -1,3 +1,5 @@
+out_edges(0): (0,1) (0,2)
+in_edges(0): (1,0) (2,0)
in a directed graph is (u,v) == (v,u) ? 0
weight[(u,v)] = 1.2
weight[(v,u)] = 2.4
==============================================================================
--- /trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp (original)
+++ branches/release/libs/graph/example/vf2_sub_graph_iso_example.cpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -12,7 +12,8 @@
int main() {
- typedef adjacency_list<vecS, vecS, bidirectionalS> graph_type;
+
+ typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;
// Build graph1
int num_vertices1 = 8; graph_type graph1(num_vertices1);
@@ -28,12 +29,12 @@
add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
- // true instructs callback to verify a map using
- // verify_vf2_sub_graph_iso
- vf2_print_callback<graph_type, graph_type> callback(graph1, graph2, true);
+ // Create callback to print mappings
+ vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
- bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
- (void)ret;
+ // Print out all subgraph isomorphism mappings between graph1 and graph2.
+ // Vertices and edges are assumed to be always equivalent.
+ vf2_subgraph_iso(graph1, graph2, callback);
return 0;
}
==============================================================================
--- /trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (original)
+++ branches/release/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -6,60 +6,16 @@
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
-#include <string>
-#include <vector>
-#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
using namespace boost;
-
-template <typename Graph1,
- typename Graph2,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate>
-struct my_print_callback {
-
- my_print_callback(const Graph1& graph1, const Graph2& graph2,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp)
- : graph1_(graph1), graph2_(graph2), edge_comp_(edge_comp), vertex_comp_(vertex_comp) {}
-
- template <typename CorrespondenceMap1To2,
- typename CorrespondenceMap2To1>
- bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
-
- std::cout << "Verify: " << std::boolalpha
- << verify_vf2_sub_graph_iso(graph1_, graph2_, f, edge_comp_, vertex_comp_)
- << std::endl;
-
- // Print sub graph isomorphism map
- BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
- std::cout << '(' << v << ", " << get(f, v) << ") ";
-
- std::cout << std::endl;
-
- return true;
- }
-
-private:
- const Graph1& graph1_;
- const Graph2& graph2_;
- EdgeCompatibilityPredicate edge_comp_;
- VertexCompatibilityPredicate vertex_comp_;
-};
-
-
-
-
int main() {
typedef property<edge_name_t, char> edge_property;
- typedef property<vertex_name_t, char> vertex_property;
-
- //typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
- typedef adjacency_list<vecS, vecS, undirectedS, vertex_property, edge_property> graph_type;
- //typedef adjacency_list<setS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
- //typedef adjacency_list<setS, vecS, undirectedS, vertex_property, edge_property> graph_type;
+ typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_property;
+
+ // Using a vecS graphs => the index maps are implicit.
+ typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
// Build graph1
graph_type graph1;
@@ -77,7 +33,6 @@
add_edge(2, 2, edge_property('l'), graph1);
add_edge(2, 2, edge_property('l'), graph1);
-
// Build graph2
graph_type graph2;
@@ -92,7 +47,6 @@
add_edge(0, 1, edge_property('a'), graph2);
add_edge(0, 1, edge_property('b'), graph2);
-
add_edge(1, 2, edge_property('s'), graph2);
add_edge(2, 3, edge_property('b'), graph2);
@@ -112,34 +66,24 @@
// create predicates
typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
-
- typedef property_map_compatible<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
+ typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
vertex_comp_t vertex_comp =
- make_property_map_compatible(get(vertex_name, graph1), get(vertex_name, graph2));
+ make_property_map_equivalent(get(vertex_name, graph1), get(vertex_name, graph2));
typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
-
- typedef property_map_compatible<edge_name_map_t, edge_name_map_t> edge_comp_t;
+ typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
edge_comp_t edge_comp =
- make_property_map_compatible(get(edge_name, graph1), get(edge_name, graph2));
-
-
- graph_traits<graph_type>::vertex_iterator vi, vi_end;
-
- // define the order in whcih vertices of graph1 are examined
- std::vector<graph_traits<graph_type>::vertex_descriptor> vertex_order1;
- for (tie(vi, vi_end) = vertices(graph1); vi != vi_end; ++vi)
- vertex_order1.push_back(*vi);
-
- // true instructs callback to verify a map using
- // verify_vf2_sub_graph_iso
- my_print_callback<graph_type, graph_type, edge_comp_t, vertex_comp_t>
- callback(graph1, graph2, edge_comp, vertex_comp);
-
- bool ret = vf2_sub_graph_iso(graph1, graph2, callback, vertex_order1,
- edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
-
- (void)ret;
+ make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2));
+
+ // Create callback
+ vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
+
+ // Print out all subgraph isomorphism mappings between graph1 and graph2.
+ // Function vertex_order_by_mult is used to compute the order of
+ // vertices of graph1. This is the order in which the vertices are examined
+ // during the matching process.
+ vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
+ edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
return 0;
}
==============================================================================
--- branches/release/libs/graph/src/graphml.cpp (original)
+++ branches/release/libs/graph/src/graphml.cpp 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -34,17 +34,23 @@
}
static void get_graphs(const boost::property_tree::ptree& top,
+ size_t desired_idx /* or -1 for all */,
std::vector<const boost::property_tree::ptree*>& result) {
using boost::property_tree::ptree;
+ size_t current_idx = 0;
BOOST_FOREACH(const ptree::value_type& n, top) {
if (n.first == "graph") {
- result.push_back(&n.second);
- get_graphs(n.second, result);
+ if (current_idx == desired_idx || desired_idx == (size_t)(-1)) {
+ result.push_back(&n.second);
+ get_graphs(n.second, (size_t)(-1), result);
+ if (desired_idx != (size_t)(-1)) break;
+ }
+ ++current_idx;
}
}
}
- void run(std::istream& in)
+ void run(std::istream& in, size_t desired_idx)
{
using boost::property_tree::ptree;
ptree pt;
@@ -74,7 +80,7 @@
}
// Search for graphs
std::vector<const ptree*> graphs;
- get_graphs(gml, graphs);
+ get_graphs(gml, desired_idx, graphs);
BOOST_FOREACH(const ptree* gr, graphs) {
// Search for nodes
BOOST_FOREACH(const ptree::value_type& node, *gr) {
@@ -209,9 +215,9 @@
namespace boost
{
void BOOST_GRAPH_DECL
-read_graphml(std::istream& in, mutate_graph& g)
+read_graphml(std::istream& in, mutate_graph& g, size_t desired_idx)
{
graphml_reader reader(g);
- reader.run(in);
+ reader.run(in, desired_idx);
}
}
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 (original)
+++ branches/release/libs/graph/test/Jamfile.v2 2012-12-17 18:59:46 EST (Mon, 17 Dec 2012)
@@ -124,6 +124,7 @@
[ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
[ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
[ compile filtered_graph_properties_dijkstra.cpp ]
+ [ run vf2_sub_graph_iso_test.cpp ]
;
# Run SDB tests only when -sSDB= is set.