Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r82050 - in trunk: boost/graph libs/graph/doc libs/graph/example
From: jewillco_at_[hidden]
Date: 2012-12-17 12:11:02

Next message: cppljevans_at_[hidden]: "[Boost-commit] svn:boost r82051 - sandbox/variadic_templates/sandbox/array_dyn"
Previous message: marshall_at_[hidden]: "[Boost-commit] svn:boost r82049 - branches/release/boost/algorithm"

Author: jewillco
Date: 2012-12-17 12:11:02 EST (Mon, 17 Dec 2012)
New Revision: 82050
URL: http://svn.boost.org/trac/boost/changeset/82050

Log:
Added VF2 updates from Flavio De Lorenzi
Text files modified:
   trunk/boost/graph/vf2_sub_graph_iso.hpp | 38 --
   trunk/libs/graph/doc/vf2_sub_graph_iso.html | 411 ++++++++++++++++++++++-----------------
   trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp | 2
   3 files changed, 244 insertions(+), 207 deletions(-)

Modified: trunk/boost/graph/vf2_sub_graph_iso.hpp
==============================================================================
--- trunk/boost/graph/vf2_sub_graph_iso.hpp (original)
+++ trunk/boost/graph/vf2_sub_graph_iso.hpp 2012-12-17 12:11:02 EST (Mon, 17 Dec 2012)
@@ -282,44 +282,23 @@
 };

- // Used for bookkeeping of matched edges in equivalent_edge_exists
- // (when dealing with multi-graphs)
- template <typename Item, typename Enable = void>
- struct memory {
- void store(Item item) { items_.push_back(item); }
- bool exists(Item item) const {
- return (std::find(items_.begin(), items_.end(), item) != items_.end());
- }
-
- std::vector<Item> items_;
- };
-
-
- template <typename Item>
- struct memory<Item, typename boost::enable_if<has_less<Item> >::type> {
- void store(Item item) { items_.insert(item); }
- bool exists(Item item) const {
- return (items_.find(item) != items_.end());
- }
-
- std::set<Item> items_;
- };
-
-
 // Function object that checks whether a valid edge
 // exists. For multi-graphs matched edges are excluded
 template <typename Graph, typename Enable = void>
 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) {

 BGL_FORALL_OUTEDGES_T(s, e, g, Graph) {
- if ((target(e, g) == t) && is_valid_edge(e) && !edge_memory_.exists(e)) {
- edge_memory_.store(e);
+ if ((target(e, g) == t) && is_valid_edge(e) &&
+ (matched_edges_.find(e) == matched_edges_.end())) {
+ matched_edges_.insert(e);
 return true;
 }
 }
@@ -329,7 +308,7 @@

 private:

- memory<edge_type> edge_memory_;
+ std::set<edge_type> matched_edges_;
 };

 template <typename Graph>
@@ -768,7 +747,6 @@
 // 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_;
@@ -780,7 +758,7 @@
 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));

Modified: trunk/libs/graph/doc/vf2_sub_graph_iso.html
==============================================================================
--- trunk/libs/graph/doc/vf2_sub_graph_iso.html (original)
+++ trunk/libs/graph/doc/vf2_sub_graph_iso.html 2012-12-17 12:11:02 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">

+ -->
<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">
 
+ -->
 </style>
 </head>
 <body>
- <img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
- 
+ <img src="../../../boost.png" alt="C++ Boost" width="277" height="86">
 <h1>
 <tt>vf2_subgraph_iso</tt>
 </h1>
 <pre>
-// all defaults interface
+// All defaults interface
template <typename GraphSmall,
 typename GraphLarge,
 typename SubGraphIsoMapCallback>
@@ -46,7 +47,7 @@
 SubGraphIsoMapCallback user_callback)

-// named parameter version
+// Named parameter version
template <typename GraphSmall,
 typename GraphLarge,
 typename VertexOrderSmall,
@@ -61,7 +62,7 @@
 const bgl_named_params<Param, Tag, Rest>& params)

-// non-named parameter version
+// Non-named parameter version
template <typename GraphSmall,
 typename GraphLarge,
 typename IndexMapSmall,
@@ -84,7 +85,7 @@
 and G2=(V2, E2) is a
 bijective mapping M of the vertices of one graph to vertices of the other
 graph that preserves the edge structure of the graphs. M is said to be a
- graph-subgraph isomorphism iff M is an isomorphism between
+ graph-subgraph isomorphism if and only if M is an isomorphism between
 G1 and a subgraph of G2.
 

@@ -96,158 +97,188 @@
 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,
- look at the
+ 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>
+ 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
+ always_equivalent</a></tt> is used, which returns
 true for any pair of vertices or edges.
 
 
 The current implementation is based on the VF2 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 G1 and G2 determines
- the isomorphism mapping M, which associates vertices
- G1 with vertices of G2 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 s of the matching process can be associated with a partial
- mapping M(s). At each level, the algorithm computes the set of
- the vertex pairs that are candidates to be added to the current state
- s. If a pair of vertices (v, w) is feasible, the mapping
- is extended and the associated successor state s' is computed.
+ 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 G1 and
+ G2 determines the isomorphism mapping M,
+ which associates vertices G1 with vertices of
+ G2 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 s of the matching process
+ can be associated with a partial mapping M(s). At each level,
+ the algorithm computes the set of the vertex pairs that are candidates to
+ be added to the current state s. If a pair of vertices
+ (v, w) is feasible, the mapping is extended and the associated
+ successor state s' is computed.
 The whole procedure is then repeated for state s'.
 

 <h3>Where Defined</h3>
- boost/graph/vf2_sub_graph_iso.hpp
 
+ <a href="../../../boost/graph/vf2_sub_graph_iso.hpp">
+ <tt>boost/graph/vf2_sub_graph_iso.hpp</tt></a> 
 All functions are defined in the boost namespace.
 

 <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>
+
+ IN: <tt>const GraphSmall& graph_small</tt>
 <blockquote>
- A function object to be called when a graph-subgraph isomorphism has been discovered. The
- <tt>operator()</tt> must have following form:
+ 
+ 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.
+ 
+ </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.
+ 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.
+ 
+ </blockquote>
+
+ OUT: <tt>SubGraphIsoMapCallback user_callback</tt>
+ <blockquote>
+ 
+ A function object to be called when a graph-subgraph isomorphism has been discovered. The
+ <tt>operator()</tt> must have following form:
+ 
 <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_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 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.
- </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>.
- 
- Default The vertices are ordered by multiplicity of in/out degrees.
+ 
+ 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.
+ 
+ </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>.
+ 
+ Default The vertices are ordered by multiplicity of
+ in/out degrees.
+ 
 </blockquote>

 <h3>Named Parameters</h3>

- IN: <tt>vertex_index1(IndexMapSmall index_map_small)</tt>
- <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.
- 
- Default: <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.
- 
- Default: <tt>get(vertex_index, graph_large)</tt>
- </blockquote>
-
- IN: <tt>edges_equivalent(EdgeEquivalencePredicate 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 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>. A return value of true
- indicates that the edges are equivalent.
- 
- Default: <tt>always_equivalent</tt>
- </blockquote>
-
- IN: <tt>vertices_equivalent(VertexEquivalencePredicate vertex_comp)</tt>
+ IN: <tt>vertex_index1(IndexMapSmall index_map_small)</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 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.
- 
- Default: <tt>always_equivalent</tt>
+ 
+ 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.
+ 
+ Default: <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.
+ 
+ Default: <tt>get(vertex_index, graph_large)</tt>
+ 
+ </blockquote>
+
+ IN: <tt>edges_equivalent(EdgeEquivalencePredicate 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 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.
+ 
+ Default: <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
+ always_equivalent</a></tt>
+ 
+ </blockquote>
+
+ IN: <tt>vertices_equivalent(VertexEquivalencePredicate 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 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.
+ 
+ Default: <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
+ always_equivalent</a></tt>
+ 
 </blockquote>
-
+
 <h3>Related Functions</h3>
 
 Non-named parameter, named-parameter and all default parameter versions of
 function
 
- <tt>
-vf2_graph_iso(...)
- </tt>
+ <tt>vf2_graph_iso(...)</tt>
 
 for isomorphism testing take the same parameters as the corresponding
 functions <tt>vf2_subgraph_iso</tt> for subgraph isomorphism testing.
@@ -258,19 +289,23 @@
 <tt>EdgeEquivalencePredicate</tt> and
 <tt>VertexEquivalencePredicate</tt> predicates are used to test
 whether edges and vertices are equivalent. By default
- <tt>always_equivalent</tt> as used.
+ <tt>always_equivalent</tt> is used.
 
-
+
 <h3>Utility Functions and Structs</h3>
+ 
 <tt id="vf2_callback">
template<typename Graph1,
 typename Graph2>
struct vf2_print_callback
 </tt>
+ 
 <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 G1
- and G2.
+ 
+ Callback function object that prints out the correspondences between vertices
+ of <tt>Graph1</tt> and <tt>Graph2</tt>. The constructor takes
+ the two graphs G1 and G2.
+ 
 </blockquote>

 <pre>
@@ -279,7 +314,10 @@
 vertex_order_by_mult(const Graph& graph)
 </pre>
 <blockquote>
- Returns a vector containing the vertices of a graph, sorted by multiplicity of in/out degrees.
+ 
+ Returns a vector containing the vertices of a graph, sorted
+ by multiplicity of in/out degrees.
+ 
 </blockquote>

 <pre>
@@ -303,8 +341,11 @@
 VertexEquivalencePredicate vertex_comp)
 </pre>
 <blockquote>
-This function can be used to verify a (sub)graph isomorphism mapping f. The parameters are
-analogous to function <tt>vf2_subgraph_iso</tt> (<tt>vf2_graph_iso</tt>).
+ 
+ This function can be used to verify a (sub)graph isomorphism
+ mapping f. The parameters are analogous to
+ function <tt>vf2_subgraph_iso</tt> (<tt>vf2_graph_iso</tt>).
+ 
 </blockquote>

@@ -351,17 +392,16 @@
// Vertices and edges are assumed to be always equivalent.
vf2_subgraph_iso(graph1, graph2, callback);
 </pre>
-
-The complete example can be found under
-examples/vf2_sub_graph_iso_example.cpp.
- 
-
-
+ 
+ The complete example can be found under
+ examples/vf2_sub_graph_iso_example.cpp.
+ 
+ 

 <h4>Example 2</h4>
 
- In this example, the subgraph isomorphism mappings between multi-graphs are computed. The vertices
- and edges of the multi-graphs are differentiated using property maps.
+ 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.
 
 <pre>
// Define edge and vertex properties
@@ -387,12 +427,12 @@
...
add_edge(0, 1, edge_property('a'), graph2);
...
- </pre>
+ </pre>

 
- To differentiate 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:
+ 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:
 

 <pre>
@@ -410,8 +450,8 @@
 </pre>

 
- Finally, a callback function object is created and the subgraph isomorphism mappings are
- computed:
+ Finally, a callback function object is created and the subgraph isomorphism mappings are
+ computed:
 
 <pre>
// Create callback
@@ -420,39 +460,58 @@

// 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. That's the order in which the vertices are examined
+// 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));
 </pre>

-
-For the complete example, see
-examples/vf2_sub_graph_iso_multi_example.cpp.
- 
-
+ 
+ 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>.
+ 
+ 

+ <h3 id="notes">Notes</h3>
+ 
+ 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.
+ 

 <h3>Bibliography</h3>

 <dl>
- <dt><a name="cordella2001">1</a>
- <dd>
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
- An improved algorithm for matching large graphs.
- In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001.
- </dd>
- <dt><a name="cordella2004">2</a>
- <dd>
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
- A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.
- 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.
+ An improved algorithm for matching large graphs.
+ In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001.
+ 
+ </dd>
+ <dt><a name="cordella2004">2</a></dt>
+ <dd>
+ L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
+ A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.
+ IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 1367-1372, 2004.
+ 
+ </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>
+ 
+ </dd>
 </dl>
-
- <hr />
- Copyright © 2012, Flavio De Lorenzi
- (<a href="mailto:fdlorenzi_at_[hidden]">fdlorenzi_at_[hidden]</a>)
-
+ <hr>
+ 
+ Copyright © 2012, Flavio De Lorenzi
+ (<a href="mailto:fdlorenzi_at_[hidden]">fdlorenzi_at_[hidden]</a>)
+ 
 </body>
</html>

Modified: trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp
==============================================================================
--- trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (original)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp 2012-12-17 12:11:02 EST (Mon, 17 Dec 2012)
@@ -80,7 +80,7 @@

   // 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. That's the order in which the vertices are examined
+ // 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));

Next message: cppljevans_at_[hidden]: "[Boost-commit] svn:boost r82051 - sandbox/variadic_templates/sandbox/array_dyn"
Previous message: marshall_at_[hidden]: "[Boost-commit] svn:boost r82049 - branches/release/boost/algorithm"

Date view	Thread view	Subject view	Author view

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