[boost-doc-zh] r324 committed - 转换至1.40.0，第7批，完成以下库：...
- From: codesite-noreply@xxxxxxxxxx
- To: boost-doc-zh-notify@xxxxxxxxxxxxx
- Date: Mon, 07 Sep 2009 16:31:22 +0000
Revision: 324
Author: alai04
Date: Mon Sep 7 09:29:57 2009
Log: 转换至1.40.0，第7批，完成以下库：
graph
in_place_factory
integer
interval
io_state_savers
iostreams
iterators
property_map
http://code.google.com/p/boost-doc-zh/source/detail?r=324
Added:
/trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
/trunk/libs/graph/doc/mcgregor_common_subgraphs.html
/trunk/libs/graph/example/Jamfile.v2
/trunk/libs/graph/example/bron_kerbosch_clique_number.cpp
/trunk/libs/graph/example/bron_kerbosch_print_cliques.cpp
/trunk/libs/graph/example/closeness_centrality.cpp
/trunk/libs/graph/example/clustering_coefficient.cpp
/trunk/libs/graph/example/comm_network.graph
/trunk/libs/graph/example/degree_centrality.cpp
/trunk/libs/graph/example/dijkstra-no-color-map-example.cpp
/trunk/libs/graph/example/eccentricity.cpp
/trunk/libs/graph/example/helper.hpp
/trunk/libs/graph/example/inclusive_mean_geodesic.cpp
/trunk/libs/graph/example/influence_prestige.cpp
/trunk/libs/graph/example/info_network.graph
/trunk/libs/graph/example/labeled_graph.cpp
/trunk/libs/graph/example/mcgregor_subgraphs_example.cpp
/trunk/libs/graph/example/mean_geodesic.cpp
/trunk/libs/graph/example/prism_3_2.graph
/trunk/libs/graph/example/prob_network.graph
/trunk/libs/graph/example/scaled_closeness_centrality.cpp
/trunk/libs/graph/example/social_network.graph
/trunk/libs/graph/example/tiernan_girth_circumference.cpp
/trunk/libs/graph/example/tiernan_print_cycles.cpp
/trunk/libs/graph/test/bron_kerbosch_all_cliques.cpp
/trunk/libs/graph/test/closeness_centrality.cpp
/trunk/libs/graph/test/clustering_coefficient.cpp
/trunk/libs/graph/test/core_numbers_test.cpp
/trunk/libs/graph/test/degree_centrality.cpp
/trunk/libs/graph/test/dijkstra_no_color_map_compare.cpp
/trunk/libs/graph/test/eccentricity.cpp
/trunk/libs/graph/test/generator_test.cpp
/trunk/libs/graph/test/index_graph.cpp
/trunk/libs/graph/test/labeled_graph.cpp
/trunk/libs/graph/test/mcgregor_subgraphs_test.cpp
/trunk/libs/graph/test/mean_geodesic.cpp
/trunk/libs/graph/test/metis_test.cpp
/trunk/libs/graph/test/metric_tsp_approx.graph
/trunk/libs/graph/test/read_propmap.cpp
/trunk/libs/graph/test/subgraph_bundled.cpp
/trunk/libs/graph/test/subgraph_props.cpp
/trunk/libs/graph/test/test_construction.hpp
/trunk/libs/graph/test/test_destruction.hpp
/trunk/libs/graph/test/test_direction.hpp
/trunk/libs/graph/test/test_graph.hpp
/trunk/libs/graph/test/test_graphs.cpp
/trunk/libs/graph/test/test_iteration.hpp
/trunk/libs/graph/test/test_properties.hpp
/trunk/libs/graph/test/tiernan_all_cycles.cpp
/trunk/libs/graph/test/typestr.hpp
/trunk/libs/graph/test/weighted_graph.gr
/trunk/libs/property_map/doc/LvaluePropertyMap.html
/trunk/libs/property_map/doc/ReadWritePropertyMap.html
/trunk/libs/property_map/doc/ReadablePropertyMap.html
/trunk/libs/property_map/doc/WritablePropertyMap.html
/trunk/libs/property_map/doc/associative_property_map.html
/trunk/libs/property_map/doc/const_assoc_property_map.html
/trunk/libs/property_map/doc/identity_property_map.html
/trunk/libs/property_map/doc/iterator_property_map.html
/trunk/libs/property_map/doc/property_map.html
/trunk/libs/property_map/doc/ref_property_map.html
/trunk/libs/property_map/doc/shared_array_property_map.html
/trunk/libs/property_map/doc/vector_property_map.html
/trunk/libs/property_map/example
/trunk/libs/property_map/example/example1.cpp
/trunk/libs/property_map/example/example2.cpp
/trunk/libs/property_map/example/example3.cpp
Deleted:
/trunk/libs/graph/doc/default.css
/trunk/libs/property_map/LvaluePropertyMap.html
/trunk/libs/property_map/ReadWritePropertyMap.html
/trunk/libs/property_map/ReadablePropertyMap.html
/trunk/libs/property_map/WritablePropertyMap.html
/trunk/libs/property_map/associative_property_map.html
/trunk/libs/property_map/const_assoc_property_map.html
/trunk/libs/property_map/example1.cpp
/trunk/libs/property_map/example2.cpp
/trunk/libs/property_map/example3.cpp
/trunk/libs/property_map/identity_property_map.html
/trunk/libs/property_map/iterator_property_map.html
/trunk/libs/property_map/property_map.html
/trunk/libs/property_map/ref_property_map.html
/trunk/libs/property_map/vector_property_map.html
Modified:
/trunk/libs/graph/doc/AStarHeuristic.html
/trunk/libs/graph/doc/AStarVisitor.html
/trunk/libs/graph/doc/AddEdgeVisitor.html
/trunk/libs/graph/doc/AdjacencyMatrix.html
/trunk/libs/graph/doc/BasicMatrix.html
/trunk/libs/graph/doc/Buffer.html
/trunk/libs/graph/doc/ColorValue.html
/trunk/libs/graph/doc/DijkstraVisitor.html
/trunk/libs/graph/doc/EdgeMutableGraph.html
/trunk/libs/graph/doc/IteratorConstructibleGraph.html
/trunk/libs/graph/doc/Monoid.html
/trunk/libs/graph/doc/PlanarEmbedding.html
/trunk/libs/graph/doc/PropertyGraph.html
/trunk/libs/graph/doc/PropertyTag.html
/trunk/libs/graph/doc/VertexMutableGraph.html
/trunk/libs/graph/doc/adjacency_list.html
/trunk/libs/graph/doc/astar_heuristic.html
/trunk/libs/graph/doc/astar_search.html
/trunk/libs/graph/doc/bc_clustering.html
/trunk/libs/graph/doc/bellman_ford_shortest.html
/trunk/libs/graph/doc/betweenness_centrality.html
/trunk/libs/graph/doc/bibliography.html
/trunk/libs/graph/doc/biconnected_components.html
/trunk/libs/graph/doc/boyer_myrvold.html
/trunk/libs/graph/doc/breadth_first_search.html
/trunk/libs/graph/doc/breadth_first_visit.html
/trunk/libs/graph/doc/bundles.html
/trunk/libs/graph/doc/challenge.html
/trunk/libs/graph/doc/circle_layout.html
/trunk/libs/graph/doc/compressed_sparse_row.html
/trunk/libs/graph/doc/connected_components.html
/trunk/libs/graph/doc/constructing_algorithms.html
/trunk/libs/graph/doc/copy_graph.html
/trunk/libs/graph/doc/dag_shortest_paths.html
/trunk/libs/graph/doc/depth_first_search.html
/trunk/libs/graph/doc/depth_first_visit.html
/trunk/libs/graph/doc/dijkstra_shortest_paths.html
/trunk/libs/graph/doc/distance_recorder.html
/trunk/libs/graph/doc/edmonds_karp_max_flow.html
/trunk/libs/graph/doc/erdos_renyi_generator.html
/trunk/libs/graph/doc/exception.html
/trunk/libs/graph/doc/faq.html
/trunk/libs/graph/doc/floyd_warshall_shortest.html
/trunk/libs/graph/doc/fruchterman_reingold.html
/trunk/libs/graph/doc/gursoy_atun_layout.html
/trunk/libs/graph/doc/history.html
/trunk/libs/graph/doc/howard_cycle_ratio.html
/trunk/libs/graph/doc/incident.html
/trunk/libs/graph/doc/incremental_components.html
/trunk/libs/graph/doc/is_kuratowski_subgraph.html
/trunk/libs/graph/doc/is_straight_line_drawing.html
/trunk/libs/graph/doc/isomorphism.html
/trunk/libs/graph/doc/johnson_all_pairs_shortest.html
/trunk/libs/graph/doc/kamada_kawai_spring_layout.html
/trunk/libs/graph/doc/kevin_bacon.html
/trunk/libs/graph/doc/known_problems.html
/trunk/libs/graph/doc/kolmogorov_max_flow.html
/trunk/libs/graph/doc/kruskal_min_spanning_tree.html
/trunk/libs/graph/doc/layout_tolerance.html
/trunk/libs/graph/doc/lengauer_tarjan_dominator.htm
/trunk/libs/graph/doc/make_biconnected_planar.html
/trunk/libs/graph/doc/make_connected.html
/trunk/libs/graph/doc/make_maximal_planar.html
/trunk/libs/graph/doc/maximum_matching.html
/trunk/libs/graph/doc/metric_tsp_approx.html
/trunk/libs/graph/doc/minimum_degree_ordering.html
/trunk/libs/graph/doc/null_visitor.html
/trunk/libs/graph/doc/opposite.html
/trunk/libs/graph/doc/planar_canonical_ordering.html
/trunk/libs/graph/doc/planar_face_traversal.html
/trunk/libs/graph/doc/planar_graphs.html
/trunk/libs/graph/doc/plod_generator.html
/trunk/libs/graph/doc/predecessor_recorder.html
/trunk/libs/graph/doc/prim_minimum_spanning_tree.html
/trunk/libs/graph/doc/property.html
/trunk/libs/graph/doc/property_map.html
/trunk/libs/graph/doc/property_writer.html
/trunk/libs/graph/doc/push_relabel_max_flow.html
/trunk/libs/graph/doc/quick_tour.html
/trunk/libs/graph/doc/r_c_shortest_paths.html
/trunk/libs/graph/doc/random.html
/trunk/libs/graph/doc/random_layout.html
/trunk/libs/graph/doc/read_dimacs.html
/trunk/libs/graph/doc/read_graphml.html
/trunk/libs/graph/doc/read_graphviz.html
/trunk/libs/graph/doc/sequential_vertex_coloring.html
/trunk/libs/graph/doc/small_world_generator.html
/trunk/libs/graph/doc/sorted_erdos_renyi_gen.html
/trunk/libs/graph/doc/stanford_graph.html
/trunk/libs/graph/doc/straight_line_drawing.html
/trunk/libs/graph/doc/strong_components.html
/trunk/libs/graph/doc/subgraph.html
/trunk/libs/graph/doc/table_of_contents.html
/trunk/libs/graph/doc/time_stamper.html
/trunk/libs/graph/doc/topological_sort.html
/trunk/libs/graph/doc/transitive_closure.html
/trunk/libs/graph/doc/transpose_graph.html
/trunk/libs/graph/doc/trouble_shooting.html
/trunk/libs/graph/doc/undirected_dfs.html
/trunk/libs/graph/doc/using_adjacency_list.html
/trunk/libs/graph/doc/using_property_maps.html
/trunk/libs/graph/doc/write-graphviz.html
/trunk/libs/graph/doc/write_dimacs.html
/trunk/libs/graph/doc/write_graphml.html
/trunk/libs/graph/example/adjacency_list.cpp
/trunk/libs/graph/example/adjacency_list_io.cpp
/trunk/libs/graph/example/bfs.cpp
/trunk/libs/graph/example/bfs_neighbor.cpp
/trunk/libs/graph/example/canonical_ordering.cpp
/trunk/libs/graph/example/city_visitor.cpp
/trunk/libs/graph/example/cycle_ratio_example.cpp
/trunk/libs/graph/example/edge_property.cpp
/trunk/libs/graph/example/exterior_properties.cpp
/trunk/libs/graph/example/exterior_property_map.cpp
/trunk/libs/graph/example/interior_pmap_bundled.cpp
/trunk/libs/graph/example/interior_property_map.cpp
/trunk/libs/graph/example/iterator-property-map-eg.cpp
/trunk/libs/graph/example/johnson-eg.cpp
/trunk/libs/graph/example/knights-tour.cpp
/trunk/libs/graph/example/kuratowski_subgraph.cpp
/trunk/libs/graph/example/make_biconnected_planar.cpp
/trunk/libs/graph/example/make_connected.cpp
/trunk/libs/graph/example/make_maximal_planar.cpp
/trunk/libs/graph/example/neighbor_bfs.cpp
/trunk/libs/graph/example/planar_face_traversal.cpp
/trunk/libs/graph/example/property_iterator.cpp
/trunk/libs/graph/example/put-get-helper-eg.cpp
/trunk/libs/graph/example/quick-tour.cpp
/trunk/libs/graph/example/quick_tour.cpp
/trunk/libs/graph/example/straight_line_drawing.cpp
/trunk/libs/graph/test
/trunk/libs/graph/test/CMakeLists.txt
/trunk/libs/graph/test/Jamfile.v2
/trunk/libs/graph/test/adj_list_invalidation.cpp
/trunk/libs/graph/test/adj_list_loops.cpp
/trunk/libs/graph/test/adjacency_matrix_test.cpp
/trunk/libs/graph/test/all_planar_input_files_test.cpp
/trunk/libs/graph/test/basic_planarity_test.cpp
/trunk/libs/graph/test/betweenness_centrality_test.cpp
/trunk/libs/graph/test/csr_graph_test.cpp
/trunk/libs/graph/test/cycle_ratio_tests.cpp
/trunk/libs/graph/test/dag_longest_paths.cpp
/trunk/libs/graph/test/dijkstra_cc.cpp
/trunk/libs/graph/test/dijkstra_heap_performance.cpp
/trunk/libs/graph/test/dimacs.cpp
/trunk/libs/graph/test/graphml_test.cpp
/trunk/libs/graph/test/graphml_test.xml
/trunk/libs/graph/test/graphviz_test.cpp
/trunk/libs/graph/test/gursoy_atun_layout_test.cpp
/trunk/libs/graph/test/is_straight_line_draw_test.cpp
/trunk/libs/graph/test/isomorphism.cpp
/trunk/libs/graph/test/johnson-test.cpp
/trunk/libs/graph/test/kolmogorov_max_flow_test.cpp
/trunk/libs/graph/test/layout_test.cpp
/trunk/libs/graph/test/make_bicon_planar_test.cpp
/trunk/libs/graph/test/make_connected_test.cpp
/trunk/libs/graph/test/make_maximal_planar_test.cpp
/trunk/libs/graph/test/matching_test.cpp
/trunk/libs/graph/test/max_flow_test.cpp
/trunk/libs/graph/test/parallel_edges_loops_test.cpp
/trunk/libs/graph/test/property_iter.cpp
/trunk/libs/graph/test/random_matching_test.cpp
/trunk/libs/graph/test/subgraph.cpp
=======================================
--- /dev/null
+++ /trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html Mon
Sep 7 09:29:57 2009
@@ -0,0 +1,398 @@
+<HTML>
+<!--
+ Copyright (c) Michael Hansen 2009
+
+ 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)
+ -->
+<Head>
+<Title>Boost Graph Library: Dijkstra's Shortest Paths (No Color
Map)</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><A NAME="sec:dijkstra"></A>
+<TT>dijkstra_shortest_paths_no_color_map</TT>
+</H1>
+
+<P>
+<PRE>
+<i>// named parameter version</i>
+template <typename Graph, typename Param, typename Tag, typename
Rest>
+void dijkstra_shortest_paths_no_color_map
+ (const Graph& graph,
+ typename graph_traits<Graph>::vertex_descriptor start_vertex,
+ const bgl_named_params<Param,Tag,Rest>& params);
+
+<i>// non-named parameter version</i>
+template <typename Graph, typename <a
href="DijkstraVisitor.html">DijkstraVisitor</a>,
+ typename PredecessorMap, typename DistanceMap,
+ typename WeightMap, typename VertexIndexMap, typename <a
href="http://www.sgi.com/tech/stl/BinaryPredicate.html";>DistanceCompare</a>,
typename <a
href="http://www.sgi.com/tech/stl/BinaryFunction.html";>DistanceWeightCombine</a>,
+ typename DistanceInfinity, typename DistanceZero>
+void dijkstra_shortest_paths_no_color_map
+ (const Graph& graph,
+ typename graph_traits<Graph>::vertex_descriptor start_vertex,
+ PredecessorMap predecessor_map, DistanceMap distance_map, WeightMap
weight_map,
+ VertexIndexMap index_map,
+ DistanceCompare distance_compare, DistanceWeightCombine
distance_weight_combine,
+ DistanceInfinity distance_infinity, DistanceZero distance_zero);
+
+<i>// version that does not initialize the property maps</i>
+template <typename Graph, typename <a
href="DijkstraVisitor.html">DijkstraVisitor</a>,
+ typename PredecessorMap, typename DistanceMap,
+ typename WeightMap, typename VertexIndexMap, typename <a
href="http://www.sgi.com/tech/stl/BinaryPredicate.html";>DistanceCompare</a>,
typename <a
href="http://www.sgi.com/tech/stl/BinaryFunction.html";>DistanceWeightCombine</a>,
+ typename DistanceInfinity, typename DistanceZero>
+void dijkstra_shortest_paths_no_color_map_no_init
+ (const Graph& graph,
+ typename graph_traits<Graph>::vertex_descriptor start_vertex,
+ PredecessorMap predecessor_map, DistanceMap distance_map, WeightMap
weight_map,
+ VertexIndexMap index_map,
+ DistanceCompare distance_compare, DistanceWeightCombine
distance_weight_combine,
+ DistanceInfinity distance_infinity, DistanceZero distance_zero);
+</PRE>
+
+<P>
+This algorithm [<A HREF="bibliography.html#dijkstra59">10</A>,<A
+HREF="bibliography.html#clr90">8</A>] solves the single-source
+shortest-paths problem on a weighted, directed or undirected graph for
+the case where all edge weights are nonnegative. Use the Bellman-Ford
+algorithm for the case when some edge weights are negative. Use
+breadth-first search instead of Dijkstra's algorithm when all edge
+weights are equal to one. For the definition of the shortest-path
+problem see Section <A
+HREF="graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths
+Algorithms</A> for some background to the shortest-path problem.
+</P>
+
+<P>
+ <tt>dijkstra_shortest_paths_no_color_map</tt> differs from the original
<tt>dijkstra_shortest_paths</tt> algorithm by not using a color map to
identify vertices as discovered or undiscovered. Instead, this is done
with the distance map: a vertex <i>u</i> such that
<i>distance_compare(distance_map[u], distance_infinity) == false</i> is
considered to be undiscovered.
+</P>
+
+<P>
+There are two main options for obtaining output from the
+<tt>dijkstra_shortest_paths_no_color_map()</tt> function. If you provide a
+distance property map through the <tt>distance_map()</tt> parameter
+then the shortest distance from the start vertex to every other
+vertex in the graph will be recorded in the distance map. Also you can
+record the shortest paths tree in a predecessor map: for each vertex
+<i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in
+the shortest paths tree (unless <i>p[u] = u</i>, in which case <i>u</i> is
+either the source or a vertex unreachable from the source). In
+addition to these two options, the user can provide their own
+custom-made visitor that takes actions during any of the
+algorithm's event points <a href="#4">[4]</a>.</P>
+
+<P>
+Dijkstra's algorithm finds all the shortest paths from the source
+vertex to every other vertex by iteratively "growing" the set of
+vertices <i>S</i> to which it knows the shortest path. At each step of
+the algorithm, the next vertex added to <i>S</i> is determined by a
+priority queue. The queue contains the vertices in <i>V - S</i><a
+href="#1">[1]</a> prioritized by their distance label, which is the
+length of the shortest path seen so far for each vertex. The vertex
+<i>u</i> at the top of the priority queue is then added to <i>S</i>,
+and each of its out-edges is relaxed: if the distance to <i>u</i> plus
+the weight of the out-edge <i>(u,v)</i> is less than the distance
+label for <i>v</i> then the estimated distance for vertex <i>v</i> is
+reduced. The algorithm then loops back, processing the next vertex at
+the top of the priority queue. The algorithm finishes when the
+priority queue is empty.
+</P>
+<p>
+The following is the pseudo-code for Dijkstra's single-source shortest
+paths algorithm. <i>w</i> is the edge weight, <i>d</i> is the distance
label,
+and <i>p</i> is the predecessor of each vertex which is used to encode
+the shortest paths tree. <i>Q</i> is a priority queue that supports the
+DECREASE-KEY operation. The visitor event points for the algorithm are
+indicated by the labels on the right.
+</p>
+
+<table>
+<tr>
+<td valign="top">
+<pre>
+DIJKSTRA(<i>G</i>, <i>s</i>, <i>w</i>)
+ <b>for</b> each vertex <i>u in V</i> <b>(This loop is not run in
dijkstra_shortest_paths_no_color_map_no_init)</b>
+ <i>d[u] := infinity</i>
+ <i>p[u] := u</i>
+ <b>end for</b>
+ <i>d[s] := 0</i>
+ INSERT(<i>Q</i>, <i>s</i>)
+ <b>while</b> (<i>Q != Ø</i>)
+ <i>u :=</i> EXTRACT-MIN(<i>Q</i>)
+ <b>for</b> each vertex <i>v in Adj[u]</i>
+ <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
+ <i>d[v] := w(u,v) + d[u]</i>
+ <i>p[v] := u</i>
+ DECREASE-KEY(<i>Q</i>, <i>v</i>)
+ <b>else</b>
+ ...
+ <b>if</b> (<i>d[v]</i> was originally infinity)
+ INSERT(<i>Q</i>, <i>v</i>)
+ <b>end for</b>
+ <b>end while</b>
+ return (<i>d</i>, <i>p</i>)
+</pre>
+</td>
+<td valign="top">
+<pre>
+
+initialize vertex <i>u</i>
+
+
+
+
+discover vertex <i>s</i>
+
+examine vertex <i>u</i>
+examine edge <i>(u,v)</i>
+
+edge <i>(u,v)</i> relaxed
+
+
+
+edge <i>(u,v)</i> not relaxed
+
+discover vertex <i>v</i>
+finish vertex <i>u</i>
+</pre>
+</td>
+</tr>
+</table>
+
+<h3>Where Defined</h3>
+
+<a
href="../../../boost/graph/dijkstra_shortest_paths_no_color_map.hpp"><tt>boost/graph/dijkstra_shortest_paths_no_color_map.hpp</tt></a>
+
+<h3>Parameters</h3>
+
+IN: <tt>const Graph& graph</tt>
+<blockquote>
+ The graph object on which the algorithm will be applied.
+ The type <tt>Graph</tt> must be a model of
+ <a href="./VertexListGraph.html">Vertex List Graph</a>
+ and <a href="./IncidenceGraph.html">Incidence Graph</a>.<br>
+</blockquote>
+
+IN: <tt>vertex_descriptor start_vertex</tt>
+<blockquote>
+ The source vertex. All distance will be calculated from this vertex,
+ and the shortest paths tree will be rooted at this vertex.<br>
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+IN: <tt>weight_map(WeightMap weight_map)</tt>
+<blockquote>
+ The weight or ``length'' of each edge in the graph. The weights
+ must all be non-negative and non-infinite <a href="#3">[3]</a>. The
algorithm will throw a
+ <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
+ exception is one of the edges is negative.
+ The type <tt>WeightMap</tt> must be a model of
+ <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
Property Map</a>. The edge descriptor type of
+ the graph needs to be usable as the key type for the weight
+ map. The value type for this map must be
+ the same as the value type of the distance map.<br>
+ <b>Default:</b> <tt>get(edge_weight, graph)</tt><br>
+</blockquote>
+
+IN: <tt>index_map(VertexIndexMap index_map)</tt>
+<blockquote>
+ This maps each vertex to an integer in the range <tt>[0,
+ num_vertices(graph))</tt>. This is necessary for efficient updates of
the
+ heap data structure [<A
+ HREF="bibliography.html#driscoll88">61</A>] when an edge is relaxed.
+ The type
+ <tt>VertexIndexMap</tt> must be a model of
+ <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
Property Map</a>. The value type of the map must be an
+ integer type. The vertex descriptor type of the graph needs to be
+ usable as the key type of the map.<br>
+ <b>Default:</b> <tt>get(vertex_index, graph)</tt>.
+ Note: if you use this default, make sure your graph has
+ an internal <tt>vertex_index</tt> property. For example,
+ <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ not have an internal <tt>vertex_index</tt> property.
+ <br>
+</blockquote>
+
+OUT: <tt>predecessor_map(PredecessorMap predecessor_map)</tt>
+<blockquote>
+ The predecessor map records the edges in the minimum spanning
+ tree. Upon completion of the algorithm, the edges <i>(p[u],u)</i>
+ for all <i>u in V</i> are in the minimum spanning tree. If <i>p[u] =
+ u</i> then <i>u</i> is either the source vertex or a vertex that is
+ not reachable from the source. The <tt>PredecessorMap</tt> type
+ must be a <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
+ Property Map</a> whose key and value types are the same as the vertex
+ descriptor type of the graph.<br>
+ <b>Default:</b> <tt>dummy_property_map</tt><br>
+
+ <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
+</blockquote>
+
+UTIL/OUT: <tt>distance_map(DistanceMap distance_map)</tt>
+<blockquote>
+ The shortest path weight from the source vertex <tt>start_vertex</tt> to
each
+ vertex in the graph <tt>graph</tt> is recorded in this property map. The
+ shortest path weight is the sum of the edge weights along the
+ shortest path. The type <tt>DistanceMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
+ Property Map</a>. 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">Monoid</a> formed with the
<tt>distance_weight_combine</tt>
+ function object and the <tt>distance_zero</tt> object for the identity
+ element. Also the distance value type must have a <a
+ href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html";>
+ StrictWeakOrdering</a> provided by the <tt>distance_compare</tt> function
+ object.<br>
+ <b>Default:</b> <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a
+ <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
+ <tt>num_vertices(graph)</tt> and using the <tt>index_map</tt> for the
index
+ map.<br>
+</blockquote>
+
+IN: <tt>distance_compare(CompareFunction distance_compare)</tt>
+<blockquote>
+ This function is use to compare distances to determine which vertex
+ is closer to the source vertex. The <tt>DistanceCompareFunction</tt>
type
+ must be a model of <a
+ href="http://www.sgi.com/tech/stl/BinaryPredicate.html";>Binary
+ Predicate</a> and have argument types that match the value type of
+ the <tt>DistanceMap</tt> property map.<br>
+
+ <b>Default:</b>
+ <tt>std::less<D></tt> with <tt>D=typename
+ property_traits<DistanceMap>::value_type</tt><br>
+</blockquote>
+
+IN: <tt>distance_combine(CombineFunction distance_weight_combine)</tt>
+<blockquote>
+ This function is used to combine distances to compute the distance
+ of a path. The <tt>DistanceWeightCombineFunction</tt> type must be a
model of <a
+ href="http://www.sgi.com/tech/stl/BinaryFunction.html";>Binary
+ Function</a>. The first argument type of the binary function must
+ match the value type of the <tt>DistanceMap</tt> property map and
+ the second argument type must match the value type of the
+ <tt>WeightMap</tt> property map. The result type must be the same
+ type as the distance value type.<br>
+
+ <b>Default:</b> <tt>boost::closed_plus<D></tt> with
+ <tt>D=typename property_traits<DistanceMap>::value_type</tt><br>
+</blockquote>
+
+IN: <tt>distance_inf(D distance_infinity)</tt>
+<blockquote>
+ The <tt>distance_infinity</tt> object must be the greatest value of any
<tt>D</tt> object.
+ That is, <tt>distance_compare(d, distance_infinity) == true</tt> for any
<tt>d != distance_infinity</tt>.
+ The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
+ <b>Default:</b> <tt>std::numeric_limits<D>::max()</tt><br>
+</blockquote>
+
+IN: <tt>distance_zero(D distance_zero)</tt>
+<blockquote>
+ The <tt>distance_zero</tt> value must be the identity element for the
+ <a href="./Monoid.html">Monoid</a> formed by the distance values
+ and the <tt>distance_weight_combine</tt> function object.
+ The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
+ <b>Default:</b> <tt>D()</tt>with
+ <tt>D=typename property_traits<DistanceMap>::value_type</tt><br>
+</blockquote>
+
+OUT: <tt>visitor(DijkstraVisitor v)</tt>
+<blockquote>
+ Use this to specify actions that you would like to happen
+ during certain event points within the algorithm.
+ The type <tt>DijkstraVisitor</tt> must be a model of the
+ <a href="./DijkstraVisitor.html">Dijkstra Visitor</a> concept.
+ The visitor object is passed by value <a
+ href="#2">[2]</a>.<br>
+ <b>Default:</b> <tt>dijkstra_visitor<null_visitor></tt><br>
+</blockquote>
+
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V log V)</i>.
+
+
+<h3>Visitor Event Points</h3>
+
+<ul>
+<li><b><tt>vis.initialize_vertex(u, g)</tt></b>
+ is invoked on each vertex in the graph before the start of the
+ algorithm.
+<li><b><tt>vis.examine_vertex(u, g)</tt></b>
+ is invoked on a vertex as it is removed from the priority queue
+ and added to set <i>S</i>. At this point we know that <i>(p[u],u)</i>
+ is a shortest-paths tree edge so
+ <i>d[u] = delta(s,u) = d[p[u]] + w(p[u],u)</i>. Also, the distances
+ of the examined vertices is monotonically increasing
+ <i>d[u<sub>1</sub>] <= d[u<sub>2</sub>] <= d[u<sub>n</sub>]</i>.
+<li><b><tt>vis.examine_edge(e, g)</tt></b>
+ is invoked on each out-edge of a vertex immediately after it has
+ been added to set <i>S</i>.
+<li><b><tt>vis.edge_relaxed(e, g)</tt></b>
+ is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) < d[v]</i>.
+ The edge <i>(u,v)</i> that participated in the last
+ relaxation for vertex <i>v</i> is an edge in the shortest paths tree.
+<li><b><tt>vis.discover_vertex(v, g)</tt></b>
+ is invoked on vertex <i>v</i> when the edge
+ <i>(u,v)</i> is examined and <i>v</i> has not yet been discovered (i.e.
its distance was infinity before relaxation was attempted on the edge).
This
+ is also when the vertex is inserted into the priority queue.
+<li><b><tt>vis.edge_not_relaxed(e, g)</tt></b>
+ is invoked if the edge is not relaxed (see above).
+<li><b><tt>vis.finish_vertex(u, g)</tt></b>
+ is invoked on a vertex after all of its out edges have
+ been examined.
+</ul>
+
+<H3>Example</H3>
+
+<P>
+See <a href="../example/dijkstra-no-color-map-example.cpp">
+<TT>example/dijkstra-no-color-map-example.cpp</TT></a> for an example of
using Dijkstra's algorithm.
+
+<H3>See also</H3> <a
href="dijkstra_shortest_paths.html">dijkstra_shortest_paths</a> for a
version of dijkstra's shortest path that uses a color map.
+
+<H3>Notes</H3>
+
+<p>Based on the documentation for <a
href="dijkstra_shortest_paths.html">dijkstra_shortest_paths</a>.
+
+<p><a name="1">[1]</a>
+The algorithm used here saves a little space by not putting all <i>V -
+S</i> vertices in the priority queue at once, but instead only those
+vertices in <i>V - S</i> that are discovered and therefore have a
+distance less than infinity.
+
+<p><a name="2">[2]</a>
+ Since the visitor parameter is passed by value, if your visitor
+ contains state then any changes to the state during the algorithm
+ will be made to a copy of the visitor object, not the visitor object
+ passed in. Therefore you may want the visitor to hold this state by
+ pointer or reference.
+
+<p><a name="3">[3]</a>
+ The algorithm will not work correctly if any of the edge weights are
equal to infinity since the infinite distance value is used to determine if
a vertex has been discovered.
+
+<p><a name="4">[4]</a>
+ Calls to the visitor events occur in the same order as
<tt>dijkstra_shortest_paths</tt> (i.e. <i>discover_vertex(u)</i> will
always be called after <i>examine_vertex(u)</i> for an undiscovered vertex
<i>u</i>). However, the vertices of the graph given to
<i>dijkstra_shortest_paths_no_color_map</i> will <b>not</b> necessarily be
visited in the same order as <i>dijkstra_shortest_paths</i>.
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2009</TD><TD>
+Trustees of Indiana University</TD></TR></TABLE>
+
+</BODY>
+</HTML>
=======================================
--- /dev/null
+++ /trunk/libs/graph/doc/mcgregor_common_subgraphs.html Mon Sep 7
09:29:57 2009
@@ -0,0 +1,451 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
+<!--
+ Copyright (c) Michael Hansen 2009
+
+ 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: McGregor Common Subgraphs</title>
+ <style type="text/css">
+ <!--
+ body {
+ color: black;
+ background-color: white;
+ }
+
+ .comment {
+ color: #333333;
+ }
+
+ a {
+ color: blue;
+ }
+
+ a:visited {
+ color: #551A8B;
+ }
+ -->
+ </style>
+ </head>
+ <body>
+ <img src="../../../boost.png" alt="C++ Boost" width="277" height="86"
/>
+ <br />
+ <h1>
+ <tt>mcgregor_common_subgraphs</tt>
+ </h1>
+ <pre>
+<em class="comment">// named parameter version</em>
+template <typename GraphFirst,
+ typename GraphSecond,
+ typename SubGraphCallback,
+ typename Param,
+ typename Tag,
+ typename Rest>
+ void mcgregor_common_subgraphs
+ (const GraphFirst& graph1,
+ const GraphSecond& graph2,
+ SubGraphCallback user_callback,
+ bool only_connected_subgraphs,
+ const bgl_named_params<Param, Tag, Rest>& params);
+
+<em class="comment">// non-named parameter version</em>
+template <typename GraphFirst,
+ typename GraphSecond,
+ typename <a
href="../../property_map/doc/ReadablePropertyMap.html">VertexIndexMapFirst</a>,
+ typename <a
href="../../property_map/doc/ReadablePropertyMap.html">VertexIndexMapSecond</a>,
+ typename <a
href="http://www.sgi.com/tech/stl/BinaryFunction.html";>EdgeEquivalencePredicate</a>,
+ typename <a
href="http://www.sgi.com/tech/stl/BinaryFunction.html";>VertexEquivalencePredicate</a>,
+ typename SubGraphCallback>
+ void mcgregor_common_subgraphs
+ (const GraphFirst& graph1,
+ const GraphSecond& graph2,
+ const VertexIndexMapFirst vindex_map1,
+ const VertexIndexMapSecond vindex_map2,
+ EdgeEquivalencePredicate edges_equivalent,
+ VertexEquivalencePredicate vertices_equivalent,
+ bool only_connected_subgraphs,
+ SubGraphCallback user_callback);
+ </pre>
+
+ <p>
+ This algorithm finds all common subgraphs
+ between <tt>graph1</tt> and <tt>graph2</tt> and outputs them
+ to <tt>user_callback</tt>. The <tt>edges_equivalent</tt>
+ and <tt>vertices_equivalent</tt> predicates are used to
+ determine edges and vertex equivalence between the two graphs.
+ To use property maps for equivalence, look at
+ the <tt><a
href="#make_property_map_equivalent">make_property_map_equivalent</a></tt>
+ function. By
+ default, <tt><a href="#always_equivalent">always_equivalent</a></tt>
+ is used, which returns true for any pair of edges or vertices.
+ </p>
+ <p>
+ McGregor's algorithm does a depth-first search on the space of
+ possible common subgraphs. At each level, every unvisited pair
+ of vertices from <tt>graph1</tt> and <tt>graph2</tt> are checked
+ to see if they can extend the current subgraph. This is done in
+ three steps (assume <tt>vertex1</tt> is
+ from <tt>graph1</tt> and <tt>vertex2</tt> is
+ from <tt>graph2</tt>):
+ <ol>
+ <li>
+ Verify that the <tt>vertex1</tt> and <tt>vertex2</tt> are
+ equivalent using the <tt>vertices_equivalent</tt> predicate.
+ </li>
+ <li>
+ For every vertex pair
+ (<tt>existing_vertex1</tt>, <tt>existing_vertex2</tt>) in
+ the current subgraph, ensure that any edges
+ between <tt>vertex1</tt> and <tt>existing_vertex1</tt>
+ in <tt>graph1</tt> and between <tt>vertex2</tt>
+ and <tt>existing_vertex2</tt> in <tt>graph2</tt> match
+ (i.e. either both exist of both don't exist). If both edges
+ exist, they are checked for equivalence using
+ the <tt>edges_equivalent</tt> predicate.
+ </li>
+ <li>
+ Lastly (and optionally), make sure that the new subgraph
+ vertex has at least one edge connecting it to the existing
+ subgraph. When the <tt>only_connected_subgraphs</tt>
+ parameter is false, this step is skipped.
+ </li>
+ </ol>
+ </p>
+
+ <h3>Where Defined</h3>
+ <a
href="../../../boost/graph/mcgregor_common_subgraphs.hpp"><tt>boost/graph/mcgregor_common_subgraphs.hpp</tt></a>
+ <p>
+ All functions are defined in the boost namespace.
+ </p>
+
+ <h3>Parameters</h3>
+
+ IN: <tt>const GraphFirst& graph1</tt>
+ <blockquote>
+ The first graph of the pair to be searched. The
+ type <tt>GraphFirst</tt> must be a model of
+ <a href="./VertexListGraph.html">Vertex List Graph</a>
+ and <a href="./IncidenceGraph.html">Incidence Graph</a>. All
+ parameters with a "<tt>1</tt>"
+ (i.e. <tt>vindex_map1</tt>, <tt>correspondence_map_1_to_2</tt>)
+ use this graph's vertices as keys.
+ </blockquote>
+
+ IN: <tt>const GraphSecond& graph2</tt>
+ <blockquote>
+ The second graph of the pair to be searched. The
+ type <tt>Graphsecond</tt> must be a model of
+ <a href="./VertexListGraph.html">Vertex List Graph</a>
+ and <a href="./IncidenceGraph.html">Incidence Graph</a>. All
+ parameters with a "<tt>2</tt>"
+ (i.e. <tt>vindex_map2</tt>, <tt>correspondence_map_2_to_1</tt>)
+ use this graph's vertices as keys.
+ </blockquote>
+
+ IN: <tt>bool only_connected_subgraphs</tt>
+ <blockquote>
+ If <tt>true</tt>, subgraphs are expanded only when matching vertices
+ have at least one edge connecting them to the existing subgraph.
+ </blockquote>
+
+ OUT: <tt>SubGraphCallback user_callback</tt>
+ <blockquote>
+ A function object that will be invoked when a subgraph has been
discovered. The operator() must have the following form:
+ <pre>
+template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ typename
graph_traits<GraphFirst>::vertices_size_type subgraph_size);
+ </pre>
+ Both the <tt>CorrespondenceMapFirstToSecond</tt>
+ and <tt>CorresondenceMapSecondToFirst</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>mcgregor_common_subgraphs</tt>. For
+ example, if <tt>vertex1</tt> is
+ from <tt>graph1</tt>, <tt>vertex2</tt> is from <tt>graph2</tt>,
+ and the vertices can be considered equivalent in the subgraph,
+ then <tt>get(correspondence_map_1_to_2, vertex1)</tt> will
+ be <tt>vertex2</tt> and <tt>get(correspondence_map_2_to_1,
+ vertex2)</tt> will be <tt>vertex1</tt>. If any vertex,
+ say <tt>vertex1</tt> in <tt>graph1</tt>, doesn't match a vertex
+ in the other graph (<tt>graph2</tt> in this example),
+ then <tt>get(correspondence_map_1_to_2, vertex1)</tt> will
+ be <tt>graph_traits<GraphSecond>::null_vertex()</tt>.
+ Likewise for any un-matched vertices from <tt>graph2</tt>,
+ <tt>get(correspondence_map_2_to_1, vertex2)</tt> will
+ be <tt>graph_traits<GraphFirst>::null_vertex()</tt>.
+ <br /><br /> The <tt>subgraph_size</tt> parameter is the number
+ of vertices in the subgraph, or the number of matched vertex
+ pairs contained in the correspondence maps. This can be used to
+ quickly filter out subgraphs whose sizes do not fall within the
+ desired range.<br /><br />Returning <tt>false</tt> from the
+ callback will abort the search immediately. Otherwise, the
+ entire search space will be explored [<a href="#1">1</a>].
+ </blockquote>
+
+ <h3>Named Parameters</h3>
+
+ IN: <tt>vertex_index1(VertexIndexMapFirst vindex_map1)</tt>
+ <blockquote>
+ This maps each vertex to an integer in the range <tt>[0,
+ num_vertices(graph1)]</tt>. This is necessary for efficient
storage
+ of the subgraphs. The type VertexIndexMapFirst must be a model of
+ <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
Property Map</a>.
+ <br />
+ <b>Default:</b> <tt>get(vertex_index, graph1)</tt>
+ </blockquote>
+
+ IN: <tt>vertex_index2(VertexIndexMapsecond vindex_map2)</tt>
+ <blockquote>
+ This maps each vertex to an integer in the range <tt>[0,
+ num_vertices(graph2)]</tt>. This is necessary for efficient
storage
+ of the subgraphs. The type VertexIndexMapFirst must be a model of
+ <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
Property Map</a>.
+ <br />
+ <b>Default:</b> <tt>get(vertex_index, graph2)</tt>
+ </blockquote>
+
+ IN: <tt>edges_equivalent(EdgeEquivalencePredicate
edges_equivalent)</tt>
+ <blockquote>
+ This function is used to determine if edges
+ between <tt>graph1</tt> and <tt>graph2</tt> are equivalent.
+ The <tt>EdgeEquivalencePredicate</tt> type 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<GraphFirst>::edge_descriptor</tt>
+ and <tt>graph_traits<GraphSecond>::edge_descriptor</tt>.
+ A return value of <tt>true</tt> indicates that the edges are
+ equivalent. <br />
+ <b>Default:</b> <tt><a
href="#always_equivalent">always_equivalent</a></tt>
+ </blockquote>
+
+ IN: <tt>vertices_equivalent(VertexEquivalencePredicate
vertices_equivalent)</tt>
+ <blockquote>
+ This function is used to determine if vertices
+ between <tt>graph1</tt> and <tt>graph2</tt> are equivalent.
+ The <tt>VertexEquivalencePredicate</tt> type 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<GraphFirst>::vertex_descriptor</tt>
+ and <tt>graph_traits<GraphSecond>::vertex_descriptor</tt>.
+ A return value of <tt>true</tt> indicates that the vertices are
+ equivalent.<br />
+ <b>Default:</b> <tt><a
href="#always_equivalent">always_equivalent</a></tt>
+ </blockquote>
+
+ <h3>Related Functions</h3>
+ <p>
+ Each <tt>mcgregor_common_subgraphs_*</tt> function below takes
+ the same parameters as <tt>mcgregor_common_subgraphs</tt>.
+ </p>
+ <tt>mcgregor_common_subgraphs_unique(...);</tt>
+ <blockquote>
+ Keeps an internal cache of all discovered subgraphs and
+ only invokes the <tt>user_callback</tt> for unique
+ subgraphs. Returning <tt>false</tt>
+ from <tt>user_callback</tt> will terminate the search as
+ expected.
+ </blockquote>
+
+ <tt>mcgregor_common_subgraphs_maximum(...);</tt>
+ <blockquote>
+ Explores the <em>entire</em> search space and invokes
+ the <tt>user_callback</tt> afterward with each of the largest
+ discovered subgraphs. Returning <tt>false</tt> from
+ the <tt>user_callback</tt> will <b>not</b> terminate the search
+ because it is invoked after the search has been completed.
+ </blockquote>
+
+ <tt>mcgregor_common_subgraphs_maximum_unique(...);</tt>
+ <blockquote>
+ Explores the <em>entire</em> search space and invokes
+ the <tt>user_callback</tt> afterward with each of the largest,
+ unique discovered subgraphs. Returning <tt>false</tt> from
+ the <tt>user_callback</tt> will <b>not</b> terminate the search
+ because it is invoked after the search has been completed.
+ </blockquote>
+
+ <h3>Utility Functions/Structs</h3>
+ <tt id="make_property_map_equivalent">
+property_map_equivalent<PropertyMapFirst, PropertyMapSecond><br />
+ make_property_map_equivalent(const PropertyMapFirst
property_map1, const PropertyMapSecond property_map2);
+ </tt>
+ <blockquote>
+ Returns a binary predicate function object
+ (<tt>property_map_equivalent<PropertyMapFirst,
+ PropertyMapSecond></tt>) that compares vertices or edges
+ between graphs using property maps. If, for
+ example, <tt>vertex1</tt> and <tt>vertex2</tt> are the two
+ parameters given when the function object is invoked,
+ the <tt>operator()</tt> is effectively:
+ <tt>return (get(m_property_map1, vertex1) == get(m_property_map2,
vertex2));</tt>
+ </blockquote>
+
+ <tt id="always_equivalent">struct always_equivalent</tt>
+ <blockquote>
+ A binary function object that returns true for any pair of items.
+ </blockquote>
+
+ <tt>
+void fill_membership_map<GraphSecond><br />
+(const GraphFirst& graph1, const CorrespondenceMapFirstToSecond
correspondence_map_1_to_2, MembershipMapFirst membership_map1);
+ </tt>
+ <blockquote>
+ Takes a subgraph (represented as a correspondence map) and fills
+ the vertex membership map (vertex -> bool) (<tt>true</tt> means
+ the vertex is present in the subgraph).
+ <tt>MembershipMapFirst</tt> must
+ model <a
href="../../property_map/doc/WritablePropertyMap.html">Writable
+ Property Map</a>.
+ </blockquote>
+
+ <tt>
+typename membership_filtered_graph_traits<Graph,
MembershipMap>::graph_type<br />
+ make_membership_filtered_graph(const Graph& graph,
MembershipMap& membership_map);
+ </tt>
+ <blockquote>
+ Creates a <a href="filtered_graph.html">Filtered Graph</a> from
+ a subgraph, represented here as a vertex membership map (vertex
+ -> bool where a value of <tt>true</tt> means that the vertex is
+ present in the subgraph). All edges between the included
+ vertices are preserved. See the example section for details.
+ </blockquote>
+
+ <h3>Complexity</h3>
+ <p>
+ The time complexity for searching the entire space is <em>O(V1 *
+ V2)</em> where V1 is number of vertices in the first graph and
+ V2 is the number of vertices in the second graph.
+ </p>
+
+ <h3>Examples</h3>
+ <p>
+ Before calling any of the <tt>mcregor_common_subgraphs</tt>
+ algorithms, you must create a function object to act as a callback:
+ </p>
+ <pre>
+template <typename GraphFirst,
+ typename GraphSecond>
+struct print_callback {
+
+ print_callback(const GraphFirst& graph1,
+ const GraphSecond& graph2) :
+ m_graph1(graph1), m_graph2(graph2) { }
+
+template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ typename
graph_traits<GraphFirst>::vertices_size_type subgraph_size) {
+
+ <em class="comment">// Print out correspondences between vertices</em>
+ BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
+
+ <em class="comment">// Skip unmapped vertices</em>
+ if (get(correspondence_map_1_to_2, vertex1) !=
graph_traits<GraphSecond>::null_vertex()) {
+ std::cout << vertex1 << " <-> " << get(correspondence_map_1_to_2,
vertex1) << std::endl;
+ }
+
+ }
+
+ std::cout << "---" << std::endl;
+
+ return (true);
+ }
+
+ private:
+ const GraphFirst& m_graph1;
+ const GraphSecond& m_graph2;
+
+};
+
+<em class="comment">// Assuming the graph types GraphFirst and GraphSecond
have already been defined</em>
+GraphFirst graph1;
+GraphSecond graph2;
+
+print_callback<GraphFirst, GraphSecond> my_callback(graph1, graph2);
+ </pre>
+
+ <h4>Example 1</h4>
+ <p>
+ If all the vertices and edges in your graph are identical, you
+ can start enumerating subgraphs immediately:
+ </p>
+ <pre>
+<em class="comment">// Print out all connected common subgraphs between
graph1 and graph2.
+// All vertices and edges are assumed to be equivalent and both graph1 and
graph2
+// have implicit vertex index properties.</em>
+mcgregor_common_subgraphs(graph1, graph2, true, my_callback);
+ </pre>
+
+ <h4>Example 2</h4>
+ <p>
+ If the vertices and edges of your graphs can be differentiated
+ with property maps, you can use
+ the <tt>make_property_map_equivalent</tt> function to create a
+ binary predicate for vertex or edge equivalence:
+ </p>
+
+ <pre>
+<em class="comment">// Assume both graphs were defined with implicit
vertex name,
+// edge name, and vertex index properties</em>
+property_map<GraphFirst, vertex_name_t> vname_map1 =
get(vertex_name, graph1);
+property_map<GraphSecond, vertex_name_t> vname_map1 =
get(vertex_name, graph2);
+
+property_map<GraphFirst, edge_name_t> ename_map1 = get(edge_name,
graph1);
+property_map<GraphSecond, edge_name_t> ename_map1 = get(edge_name,
graph2);
+
+<em class="comment">// Print out all connected common subgraphs between
graph1 and graph2.</em>
+mcgregor_common_subgraphs(graph1, graph2, true, my_callback,
+ edges_equivalent(make_property_map_equivalent(ename_map1, ename_map2)).
+ vertices_equivalent(make_property_map_equivalent(vname_map1,
vname_map2)));
+ </pre>
+
+ <h4>Example 3</h4>
+ <p>
+ There are some helper functions that can be used to obtain a
+ filtered graph from the correspondence maps given in your
+ callback:
+ </p>
+ <pre>
+<em class="comment">// Assuming we're inside the operator() of the
callback with a member variable m_graph1 representing the first graph
passed to mcgregor_common_subgraphs.
+// ...</em>
+
+<em class="comment">// Step 1: Transform a correspondence map into a
membership map. Any vertex -> bool property map will work</em>
+typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap;
+MembershipMap membership_map1(num_vertices(m_graph1), get(vertex_index,
m_graph1));
+
+<em class="comment">// Fill the membership map for m_graph1. GraphSecond
is the type of the second graph given to mcgregor_common_subgraphs.</em>
+fill_membership_map<GraphSecond>(m_graph1,
correspondence_map_1_to_2, membership_map1);
+
+<em class="comment">// Step 2: Use the membership map from Step 1 to
obtain a filtered graph</em>
+typedef typename membership_filtered_graph_traits<GraphFirst,
MembershipMap>::graph_type
+ MembershipFilteredGraph;
+
+MembershipFilteredGraph subgraph1 =
make_membership_filtered_graph(m_graph1, membership_map1);
+
+<em class="comment">// The filtered graph can be used like a regular BGL
graph...</em>
+BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph) {
+ std::cout << vertex1 << " is present in the subgraph of graph1" <<
std::endl;
+}
+ </pre>
+
+ <h3>Notes</h3>
+ <p>
+ <a name="1">[1]</a>
+ For <tt>mcgregor_common_subgraphs_maximum</tt>
+ and <tt>mcgregor_common_subgraphs_maximum_unique</tt> the entire
+ search space is always explored, so the return value of the
+ callback has no effect.
+ </p>
+
+ <hr />
+ Copyright © 2009 Trustees of Indiana University
+
+ </body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/Jamfile.v2 Mon Sep 7 09:29:57 2009
@@ -0,0 +1,21 @@
+# Copyright (C) 2007-2009 Andrew Sutton
+#
+# 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)
+
+
+# exe labeled_graph : labeled_graph.cpp ;
+# exe quick_tour_new : quick_tour_new.cpp ;
+exe degree_centrality : degree_centrality.cpp ;
+exe influence_prestige : influence_prestige.cpp ;
+exe closeness_centrality : closeness_centrality.cpp ;
+exe scaled_closeness_centrality : scaled_closeness_centrality.cpp ;
+exe mean_geodesic : mean_geodesic.cpp ;
+exe inclusive_mean_geodesic : inclusive_mean_geodesic.cpp ;
+exe eccentricity : eccentricity.cpp ;
+exe clustering_coefficient : clustering_coefficient.cpp ;
+exe tiernan_print_cycles : tiernan_print_cycles.cpp ;
+exe tiernan_girth_circumference : tiernan_girth_circumference.cpp ;
+exe bron_kerbosch_print_cliques : bron_kerbosch_print_cliques.cpp ;
+exe bron_kerbosch_clique_number : bron_kerbosch_clique_number.cpp ;
+exe mcgregor_subgraphs_example : mcgregor_subgraphs_example.cpp ;
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/bron_kerbosch_clique_number.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,36 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[code_bron_kerbosch_clique_number
+#include <iostream>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/bron_kerbosch_all_cliques.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and read it from standard input.
+ Graph g;
+ read_graph(g, cin);
+
+ // Use the Bron-Kerbosch algorithm to find all cliques, and
+ size_t c = bron_kerbosch_clique_number(g);
+ cout << "clique number: " << c << endl;
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/bron_kerbosch_print_cliques.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,74 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[code_bron_kerbosch_print_cliques
+#include <iostream>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/bron_kerbosch_all_cliques.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The clique_printer is a visitor that will print the vertices that
comprise
+// a clique. Note that the vertices are not given in any specific order.
+template <typename OutputStream>
+struct clique_printer
+{
+ clique_printer(OutputStream& stream)
+ : os(stream)
+ { }
+
+ template <typename Clique, typename Graph>
+ void clique(const Clique& c, const Graph& g)
+ {
+ // Iterate over the clique and print each vertex within it.
+ typename Clique::const_iterator i, end = c.end();
+ for(i = c.begin(); i != end; ++i) {
+ os << g[*i].name << " ";
+ }
+ os << endl;
+ }
+ OutputStream& os;
+};
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and and its name map accessor.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standard input.
+ read_graph(g, nm, cin);
+
+ // Instantiate the visitor for printing cliques
+ clique_printer<ostream> vis(cout);
+
+ // Use the Bron-Kerbosch algorithm to find all cliques, printing them
+ // as they are found.
+ bron_kerbosch_all_cliques(g, vis);
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/closeness_centrality.cpp Mon Sep 7 09:29:57
2009
@@ -0,0 +1,85 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[closeness_centrality_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/closeness_centrality.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// Declare a matrix type and its corresponding property map that
+// will contain the distances between each pair of vertices.
+typedef exterior_vertex_property<Graph, int> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+// Declare the weight map so that each edge returns the same value.
+typedef constant_property_map<Edge, int> WeightMap;
+
+// Declare a container and its corresponding property map that
+// will contain the resulting closeness centralities of each
+// vertex in the graph.
+typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
+typedef ClosenessProperty::container_type ClosenessContainer;
+typedef ClosenessProperty::map_type ClosenessMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and a property map that provides access to[
+ // tha actor names.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standard input.
+ read_graph(g, nm, cin);
+
+ // Compute the distances between all pairs of vertices using
+ // the Floyd-Warshall algorithm. Note that the weight map is
+ // created so that every edge has a weight of 1.
+ DistanceMatrix distances(num_vertices(g));
+ DistanceMatrixMap dm(distances, g);
+ WeightMap wm(1);
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+
+ // Compute the closeness centrality for graph.
+ ClosenessContainer cents(num_vertices(g));
+ ClosenessMap cm(cents, g);
+ all_closeness_centralities(g, dm, cm);
+
+ // Print the closeness centrality of each vertex.
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name << get(cm, *i) << endl;
+ }
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/clustering_coefficient.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,69 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+
+//[code_clustering_coefficient
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/clustering_coefficient.hpp>
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// The clustering property, container, and map define the containment
+// and abstract accessor for the clustering coefficients of vertices.
+typedef exterior_vertex_property<Graph, float> ClusteringProperty;
+typedef ClusteringProperty::container_type ClusteringContainer;
+typedef ClusteringProperty::map_type ClusteringMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and a name map that provides access to
+ // then actor names.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standard input.
+ read_graph(g, nm, cin);
+
+ // Compute the clustering coefficients of each vertex in the graph
+ // and the mean clustering coefficient which is returned from the
+ // computation.
+ ClusteringContainer coefs(num_vertices(g));
+ ClusteringMap cm(coefs, g);
+ float cc = all_clustering_coefficients(g, cm);
+
+ // Print the clustering coefficient of each vertex.
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name << get(cm, *i) << endl;
+ }
+ cout << "mean clustering coefficient: " << cc << endl;
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/comm_network.graph Mon Sep 7 09:29:57 2009
@@ -0,0 +1,12 @@
+Mary,Jill
+Jill,Scott
+Scott,Mary
+Scott,Bill
+Bill,Josh
+Josh,Frank
+Frank,Scott
+Frank,Anne
+Anne,Howard
+Howard,Frank
+Frank,Laurie
+Laurie,Mary
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/degree_centrality.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,67 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+
+//[degree_centrality_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/degree_centrality.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// Declare a container type for degree centralities and its
+// corresponding property map.
+typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
+typedef CentralityProperty::container_type CentralityContainer;
+typedef CentralityProperty::map_type CentralityMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and a property map that provides access
+ // to the actor names.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standard input.
+ read_graph(g, nm, cin);
+
+ // Compute the degree centrality for graph.
+ CentralityContainer cents(num_vertices(g));
+ CentralityMap cm(cents, g);
+ all_degree_centralities(g, cm);
+
+ // Print the degree centrality of each vertex.
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << setiosflags(ios::left) << setw(12)
+ << g[*i].name << cm[*i] << endl;
+ }
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/dijkstra-no-color-map-example.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,99 @@
+//=======================================================================
+// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
+// Copyright 2009 Trustees of Indiana University.
+// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
+//
+// 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)
+//
+// NOTE: Based off of dijkstra-example.cpp
+//=======================================================================
+#include <boost/config.hpp>
+#include <iostream>
+#include <fstream>
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
+
+using namespace boost;
+
+int
+main(int, char *[])
+{
+ typedef adjacency_list < listS, vecS, directedS,
+ no_property, property < edge_weight_t, int > > graph_t;
+ typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
+ typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
+ typedef std::pair<int, int> Edge;
+
+ const int num_nodes = 5;
+ enum nodes { A, B, C, D, E };
+ char name[] = "ABCDE";
+ Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
+ Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
+ };
+ int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
+ int num_arcs = sizeof(edge_array) / sizeof(Edge);
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+ graph_t g(num_nodes);
+ property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight,
g);
+ for (std::size_t j = 0; j < num_arcs; ++j) {
+ edge_descriptor e; bool inserted;
+ tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second,
g);
+ weightmap[e] = weights[j];
+ }
+#else
+ graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
+ property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight,
g);
+#endif
+ std::vector<vertex_descriptor> p(num_vertices(g));
+ std::vector<int> d(num_vertices(g));
+ vertex_descriptor s = vertex(A, g);
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+ // VC++ has trouble with the named parameters mechanism
+ property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index,
g);
+ dijkstra_shortest_paths_no_color_map(g, s, &p[0], &d[0], weightmap,
+ indexmap, std::less<int>(),
+ closed_plus<int>(),
+ (std::numeric_limits<int>::max)(),
0,
+ default_dijkstra_visitor());
+#else
+ dijkstra_shortest_paths_no_color_map(g, s,
predecessor_map(&p[0]).distance_map(&d[0]));
+#endif
+
+ std::cout << "distances and parents:" << std::endl;
+ graph_traits < graph_t >::vertex_iterator vi, vend;
+ for (tie(vi, vend) = vertices(g); vi != vend; ++vi) {
+ std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
+ std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::
+ endl;
+ }
+ std::cout << std::endl;
+
+ std::ofstream dot_file("figs/dijkstra-no-color-map-eg.dot");
+
+ dot_file << "digraph D {\n"
+ << " rankdir=LR\n"
+ << " size=\"4,3\"\n"
+ << " ratio=\"fill\"\n"
+ << " edge[style=\"bold\"]\n" << " node[shape=\"circle\"]\n";
+
+ graph_traits < graph_t >::edge_iterator ei, ei_end;
+ for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
+ graph_traits < graph_t >::edge_descriptor e = *ei;
+ graph_traits < graph_t >::vertex_descriptor
+ u = source(e, g), v = target(e, g);
+ dot_file << name[u] << " -> " << name[v]
+ << "[label=\"" << get(weightmap, e) << "\"";
+ if (p[v] == u)
+ dot_file << ", color=\"black\"";
+ else
+ dot_file << ", color=\"grey\"";
+ dot_file << "]";
+ }
+ dot_file << "}";
+ return EXIT_SUCCESS;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/eccentricity.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,89 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+
+//[eccentricity_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/eccentricity.hpp>
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// Declare a matrix type and its corresponding property map that
+// will contain the distances between each pair of vertices.
+typedef exterior_vertex_property<Graph, int> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+// Declare the weight map so that each edge returns the same value.
+typedef constant_property_map<Edge, int> WeightMap;
+
+// Declare a container and its corresponding property map that
+// will contain the resulting eccentricities of each vertex in
+// the graph.
+typedef boost::exterior_vertex_property<Graph, int> EccentricityProperty;
+typedef EccentricityProperty::container_type EccentricityContainer;
+typedef EccentricityProperty::map_type EccentricityMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and a name map that provides access to
+ // then actor names.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standard input.
+ read_graph(g, nm, cin);
+
+ // Compute the distances between all pairs of vertices using
+ // the Floyd-Warshall algorithm. Note that the weight map is
+ // created so that every edge has a weight of 1.
+ DistanceMatrix distances(num_vertices(g));
+ DistanceMatrixMap dm(distances, g);
+ WeightMap wm(1);
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+
+ // Compute the eccentricities for graph - this computation returns
+ // both the radius and diameter as well.
+ int r, d;
+ EccentricityContainer eccs(num_vertices(g));
+ EccentricityMap em(eccs, g);
+ tie(r, d) = all_eccentricities(g, dm, em);
+
+ // Print the closeness centrality of each vertex.
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name << get(em, *i) << endl;
+ }
+ cout << "radius: " << r << endl;
+ cout << "diamter: " << d << endl;
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/helper.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,113 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_EXAMPLE_HELPER_HPP
+#define BOOST_GRAPH_EXAMPLE_HELPER_HPP
+
+#include <string>
+#include <sstream>
+#include <map>
+#include <algorithm>
+
+#include <boost/graph/properties.hpp>
+
+template <typename Graph, typename NameMap, typename VertexMap>
+typename boost::graph_traits<Graph>::vertex_descriptor
+add_named_vertex(Graph& g, NameMap nm, const std::string& name, VertexMap&
vm)
+{
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename VertexMap::iterator Iterator;
+
+ Vertex v;
+ Iterator iter;
+ bool inserted;
+ tie(iter, inserted) = vm.insert(make_pair(name, Vertex()));
+ if(inserted) {
+ // The name was unique so we need to add a vertex to the graph
+ v = add_vertex(g);
+ iter->second = v;
+ put(nm, v, name); // store the name in the name map
+ }
+ else {
+ // We had alread inserted this name so we can return the
+ // associated vertex.
+ v = iter->second;
+ }
+ return v;
+}
+
+template <typename Graph, typename NameMap, typename InputStream>
+inline std::map<std::string, typename
boost::graph_traits<Graph>::vertex_descriptor>
+read_graph(Graph& g, NameMap nm, InputStream& is)
+{
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+ std::map<std::string, Vertex> verts;
+ for(std::string line; std::getline(is, line); ) {
+ if(line.empty()) continue;
+ std::size_t index = line.find_first_of(',');
+ std::string first(line, 0, index);
+ std::string second(line, index + 1);
+
+ Vertex u = add_named_vertex(g, nm, first, verts);
+ Vertex v = add_named_vertex(g, nm, second, verts);
+ add_edge(u, v, g);
+ }
+ return verts;
+}
+
+template <typename Graph, typename InputStream>
+inline std::map<std::string, typename
boost::graph_traits<Graph>::vertex_descriptor>
+read_graph(Graph& g, InputStream& is)
+{
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef boost::null_property_map<Vertex, std::string> NameMap;
+ return read_graph(g, NameMap(), is);
+}
+
+template <typename Graph, typename NameMap, typename WeightMap, typename
InputStream>
+inline std::map<std::string, typename
boost::graph_traits<Graph>::vertex_descriptor>
+read_weighted_graph(Graph& g, NameMap nm, WeightMap wm, InputStream& is)
+{
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
+ std::map<std::string, Vertex> verts;
+ for(std::string line; std::getline(is, line); ) {
+ if(line.empty()) continue;
+ std::size_t i = line.find_first_of(',');
+ std::size_t j = line.find_first_of(',', i + 1);
+ std::string first(line, 0, i);
+ std::string second(line, i + 1, j - i - 1);
+ std::string prob(line, j + 1);
+
+ // convert the probability to a float
+ std::stringstream ss(prob);
+ float p;
+ ss >> p;
+
+ // add the vertices to the graph
+ Vertex u = add_named_vertex(g, nm, first, verts);
+ Vertex v = add_named_vertex(g, nm, second, verts);
+
+ // add the edge and set the weight
+ Edge e = add_edge(u, v, g).first;
+ put(wm, e, p);
+ }
+ return verts;
+}
+
+
+template <typename Graph, typename WeightMap, typename InputStream>
+inline std::map<std::string, typename
boost::graph_traits<Graph>::vertex_descriptor>
+read_weighted_graph(Graph& g, WeightMap wm, InputStream& is)
+{
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef boost::null_property_map<Vertex, std::string> NameMap;
+
+ return read_weighted_graph(g, NameMap(), wm, is);
+}
+
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/inclusive_mean_geodesic.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,158 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[inclusive_mean_geodesic_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/geodesic_distance.hpp>
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// This template structure defines the function that we will apply
+// to compute both the per-vertex mean geodesic distances and the
+// graph's mean geodesic distance.
+template <typename Graph,
+ typename DistanceType,
+ typename ResultType,
+ typename Divides = divides<ResultType> >
+struct inclusive_average
+{
+ typedef DistanceType distance_type;
+ typedef ResultType result_type;
+
+ result_type operator ()(distance_type d, const Graph& g)
+ {
+ if(d == numeric_values<distance_type>::infinity()) {
+ return numeric_values<result_type>::infinity();
+ }
+ else {
+ return div(result_type(d), result_type(num_vertices(g)));
+ }
+ }
+ Divides div;
+};
+
+// The Page type stores the name of each vertex in the graph and
+// represents web pages that can be navigated to.
+struct WebPage
+{
+ string name;
+};
+
+// The Link type stores an associated probability of traveling
+// from one page to another.
+struct Link
+{
+ float probability;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<WebPage, Link> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string WebPage::*>::type NameMap;
+
+// Declare a matrix type and its corresponding property map that
+// will contain the distances between each pair of vertices.
+typedef exterior_vertex_property<Graph, float> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+// Declare the weight map as an accessor into the bundled
+// edge property.
+typedef property_map<Graph, float Link::*>::type WeightMap;
+
+// Declare a container and its corresponding property map that
+// will contain the resulting mean geodesic distances of each
+// vertex in the graph.
+typedef exterior_vertex_property<Graph, float> GeodesicProperty;
+typedef GeodesicProperty::container_type GeodesicContainer;
+typedef GeodesicProperty::map_type GeodesicMap;
+
+static float exclusive_geodesics(const Graph&, DistanceMatrixMap,
GeodesicMap);
+static float inclusive_geodesics(const Graph&, DistanceMatrixMap,
GeodesicMap);
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph, a name map that providse abstract access
+ // to the web page names, and the weight map as an accessor to
+ // the edge weights (or probabilities).
+ Graph g;
+ NameMap nm(get(&WebPage::name, g));
+ WeightMap wm(get(&Link::probability, g));
+
+ // Read the weighted graph from standard input.
+ read_weighted_graph(g, nm, wm, cin);
+
+ // Compute the distances between all pairs of vertices using
+ // the Floyd-Warshall algorithm. The weight map was created
+ // above so it could be populated when the graph was read in.
+ DistanceMatrix distances(num_vertices(g));
+ DistanceMatrixMap dm(distances, g);
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+
+ // Create the containers and the respective property maps that
+ // will contain the mean geodesics averaged both including
+ // self-loop distances and excluding them.
+ GeodesicContainer exclude(num_vertices(g));
+ GeodesicContainer include(num_vertices(g));
+ GeodesicMap exmap(exclude, g);
+ GeodesicMap inmap(include, g);
+
+ float ex = exclusive_geodesics(g, dm, exmap);
+ float in = inclusive_geodesics(g, dm, inmap);
+
+ // Print the mean geodesic distance of each vertex and finally,
+ // the graph itself.
+ cout << setw(12) << setiosflags(ios::left) << "vertex";
+ cout << setw(12) << setiosflags(ios::left) << "excluding";
+ cout << setw(12) << setiosflags(ios::left) << "including" << endl;
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name
+ << setw(12) << get(exmap, *i)
+ << setw(12) << get(inmap, *i) << endl;
+ }
+ cout << "small world (excluding self-loops): " << ex << endl;
+ cout << "small world (including self-loops): " << in << endl;
+
+ return 0;
+}
+
+float
+exclusive_geodesics(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm)
+{
+ // Compute the mean geodesic distances, which excludes distances
+ // of self-loops by default. Return the measure for the entire graph.
+ return all_mean_geodesics(g, dm, gm);
+}
+
+
+float
+inclusive_geodesics(const Graph &g, DistanceMatrixMap dm, GeodesicMap gm)
+{
+ // Create a new measure object for computing the mean geodesic
+ // distance of all vertices. This measure will actually be used
+ // for both averages.
+ inclusive_average<Graph, float, float> m;
+
+ // Compute the mean geodesic distance using the inclusive average
+ // to account for self-loop distances. Return the measure for the
+ // entire graph.
+ return all_mean_geodesics(g, dm, gm, m);
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/influence_prestige.cpp Mon Sep 7 09:29:57
2009
@@ -0,0 +1,75 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[influence_prestige_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/degree_centrality.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// Declare a container type for influence and prestige (both
+// of which are degree centralities) and its corresponding
+// property map.
+typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
+typedef CentralityProperty::container_type CentralityContainer;
+typedef CentralityProperty::map_type CentralityMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and a property map that provides
+ // access to the actor names.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standard input.
+ read_graph(g, nm, cin);
+
+ // Compute the influence for the graph.
+ CentralityContainer influence(num_vertices(g));
+ CentralityMap im(influence, g);
+ all_influence_values(g, im);
+
+ // Compute the influence for the graph.
+ CentralityContainer prestige(num_vertices(g));
+ CentralityMap pm(prestige, g);
+ all_prestige_values(g, pm);
+
+ // Print the degree centrality of each vertex
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ Vertex v = *i;
+ cout << setiosflags(ios::left) << setw(12)
+ << g[v].name << "\t"
+ << im[v] << "\t"
+ << pm[v] << endl;
+ }
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/info_network.graph Mon Sep 7 09:29:57 2009
@@ -0,0 +1,11 @@
+myspace,digg
+blogger,digg
+blogger,slahsdot
+blogger,wikipedia
+digg,slashdot
+digg,wikipedia
+blogspot,slashdot
+blogspot,wikipedia
+slashdot,bbc
+slashdot,wikipedia
+bbc,wikipedia
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/labeled_graph.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,68 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <string>
+
+#define BOOST_NO_HASH
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/labeled_graph.hpp>
+
+using namespace boost;
+using namespace std;
+
+int main() {
+
+ using namespace boost::graph_detail;
+
+ typedef directed_graph<> Digraph;
+
+ {
+ typedef labeled_graph<Digraph, unsigned> Graph;
+ Graph g;
+ add_vertex(1, g);
+ add_vertex(2, g);
+
+ Graph h(12);
+ }
+
+ {
+ typedef labeled_graph<Digraph, string> Graph;
+ Graph g;
+ add_vertex("foo", g);
+ add_vertex("bar", g);
+ }
+
+ {
+ typedef labeled_graph<Digraph, string, mapS> Graph;
+ Graph g;
+ add_vertex("foo", g);
+ add_vertex("bar", g);
+ add_vertex("foo", g);
+ }
+
+ {
+ typedef labeled_graph<Digraph*, int> TempGraph;
+ Digraph g;
+ TempGraph h(&g);
+ add_vertex(12, h);
+ }
+
+
+ {
+ // This is actually a fairly complicated specialization.
+ typedef adjacency_list<vecS, vecS, bidirectionalS> G;
+ typedef labeled_graph<G, size_t> Graph;
+ Graph g;
+ add_vertex(0, g);
+ add_vertex(1, g);
+ g.add_edge(0, 1);
+ }
+
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/mcgregor_subgraphs_example.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,148 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen
+//
+// 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)
+//=======================================================================
+
+#include <fstream>
+#include <iostream>
+#include <string>
+
+#include <boost/lexical_cast.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/filtered_graph.hpp>
+#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/mcgregor_common_subgraphs.hpp>
+#include <boost/property_map/shared_array_property_map.hpp>
+
+using namespace boost;
+
+// Callback that looks for the first common subgraph whose size
+// matches the user's preference.
+template <typename Graph>
+struct example_callback {
+
+ typedef typename graph_traits<Graph>::vertices_size_type VertexSizeFirst;
+
+ example_callback(const Graph& graph1) :
+ m_graph1(graph1) { }
+
+ template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ VertexSizeFirst subgraph_size) {
+
+ // Fill membership map for first graph
+ typedef typename property_map<Graph, vertex_index_t>::type
VertexIndexMap;
+ typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap;
+
+ MembershipMap membership_map1(num_vertices(m_graph1),
+ get(vertex_index, m_graph1));
+
+ fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2,
membership_map1);
+
+ // Generate filtered graphs using membership map
+ typedef typename membership_filtered_graph_traits<Graph,
MembershipMap>::graph_type
+ MembershipFilteredGraph;
+
+ MembershipFilteredGraph subgraph1 =
+ make_membership_filtered_graph(m_graph1, membership_map1);
+
+ // Print the graph out to the console
+ std::cout << "Found common subgraph (size " << subgraph_size << ")" <<
std::endl;
+ print_graph(subgraph1);
+ std::cout << std::endl;
+
+ // Explore the entire space
+ return (true);
+ }
+
+private:
+ const Graph& m_graph1;
+ VertexSizeFirst m_max_subgraph_size;
+};
+
+int main (int argc, char *argv[]) {
+
+ // Using a vecS graph here so that we don't have to mess around with
+ // a vertex index map; it will be implicit.
+ typedef adjacency_list<listS, vecS, directedS,
+ property<vertex_name_t, unsigned int,
+ property<vertex_index_t, unsigned int> >,
+ property<edge_name_t, unsigned int> > Graph;
+
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef property_map<Graph, vertex_name_t>::type VertexNameMap;
+ typedef property_map<Graph, edge_name_t>::type EdgeNameMap;
+
+ // Test maximum and unique variants on known graphs
+ Graph graph_simple1, graph_simple2;
+ example_callback<Graph> user_callback(graph_simple1);
+
+ VertexNameMap vname_map_simple1 = get(vertex_name, graph_simple1);
+ VertexNameMap vname_map_simple2 = get(vertex_name, graph_simple2);
+
+ // Graph that looks like a triangle
+ put(vname_map_simple1, add_vertex(graph_simple1), 1);
+ put(vname_map_simple1, add_vertex(graph_simple1), 2);
+ put(vname_map_simple1, add_vertex(graph_simple1), 3);
+
+ add_edge(0, 1, graph_simple1);
+ add_edge(0, 2, graph_simple1);
+ add_edge(1, 2, graph_simple1);
+
+ std::cout << "First graph:" << std::endl;
+ print_graph(graph_simple1);
+ std::cout << std::endl;
+
+ // Triangle with an extra vertex
+ put(vname_map_simple2, add_vertex(graph_simple2), 1);
+ put(vname_map_simple2, add_vertex(graph_simple2), 2);
+ put(vname_map_simple2, add_vertex(graph_simple2), 3);
+ put(vname_map_simple2, add_vertex(graph_simple2), 4);
+
+ add_edge(0, 1, graph_simple2);
+ add_edge(0, 2, graph_simple2);
+ add_edge(1, 2, graph_simple2);
+ add_edge(1, 3, graph_simple2);
+
+ std::cout << "Second graph:" << std::endl;
+ print_graph(graph_simple2);
+ std::cout << std::endl;
+
+ // All subgraphs
+ std::cout << "mcgregor_common_subgraphs:" << std::endl;
+ mcgregor_common_subgraphs
+ (graph_simple1, graph_simple2, true, user_callback,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1,
vname_map_simple2)));
+ std::cout << std::endl;
+
+ // Unique subgraphs
+ std::cout << "mcgregor_common_subgraphs_unique:" << std::endl;
+ mcgregor_common_subgraphs_unique
+ (graph_simple1, graph_simple2, true, user_callback,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1,
vname_map_simple2)));
+ std::cout << std::endl;
+
+ // Maximum subgraphs
+ std::cout << "mcgregor_common_subgraphs_maximum:" << std::endl;
+ mcgregor_common_subgraphs_maximum
+ (graph_simple1, graph_simple2, true, user_callback,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1,
vname_map_simple2)));
+ std::cout << std::endl;
+
+ // Maximum, unique subgraphs
+ std::cout << "mcgregor_common_subgraphs_maximum_unique:" << std::endl;
+ mcgregor_common_subgraphs_maximum_unique
+ (graph_simple1, graph_simple2, true, user_callback,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1,
vname_map_simple2)));
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/mean_geodesic.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,89 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[mean_geodesic_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/geodesic_distance.hpp>
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// Declare a matrix type and its corresponding property map that
+// will contain the distances between each pair of vertices.
+typedef exterior_vertex_property<Graph, int> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+// Declare the weight map so that each edge returns the same value.
+typedef constant_property_map<Edge, int> WeightMap;
+
+// Declare a container and its corresponding property map that
+// will contain the resulting mean geodesic distances of each
+// vertex in the graph.
+typedef exterior_vertex_property<Graph, float> GeodesicProperty;
+typedef GeodesicProperty::container_type GeodesicContainer;
+typedef GeodesicProperty::map_type GeodesicMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and a property map that provides access
+ // to the actor names.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standad input.
+ read_graph(g, nm, cin);
+
+ // Compute the distances between all pairs of vertices using
+ // the Floyd-Warshall algorithm. Note that the weight map is
+ // created so that every edge has a weight of 1.
+ DistanceMatrix distances(num_vertices(g));
+ DistanceMatrixMap dm(distances, g);
+ WeightMap wm(1);
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+
+ // Compute the mean geodesic distances for each vertex in
+ // the graph and get the average mean geodesic distace (the
+ // so-called small-world distance) as a result.
+ GeodesicContainer geodesics(num_vertices(g));
+ GeodesicMap gm(geodesics, g);
+ float sw = all_mean_geodesics(g, dm, gm);
+
+ // Print the mean geodesic distance of each vertex and finally,
+ // the graph itself.
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name << get(gm, *i) << endl;
+ }
+ cout << "small world distance: " << sw << endl;
+
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/prism_3_2.graph Mon Sep 7 09:29:57 2009
@@ -0,0 +1,16 @@
+0,1
+1,2
+2,0
+
+3,4
+4,5
+5,3
+
+0,3
+3,0
+
+1,4
+4,1
+
+2,5
+5,2
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/prob_network.graph Mon Sep 7 09:29:57 2009
@@ -0,0 +1,18 @@
+myspace,myspace,.5
+myspace,digg,.5
+blogger,digg,.33
+blogger,slashdot,.33
+blogger,wikipedia,.33
+digg,slashdot,.33
+digg,wikipedia,.33
+digg,digg,.33
+blogspot,slashdot,.5
+blogspot,wikipedia,.5
+slashdot,bbc,.5
+slashdot,wikipedia,.5
+bbc,wikipedia,.5
+bbc,bbc,.5
+wikipedia,wikipedia,.25
+wikipedia,blogger,.25
+wikipedia,myspace,.25
+wikipedia,blogspot,.25
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/scaled_closeness_centrality.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,114 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[scaled_closeness_centrality_example
+#include <iostream>
+#include <iomanip>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/closeness_centrality.hpp>
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// This template struct provides a generic version of a "scaling"
+// closeness measure. Specifically, this implementation divides
+// the number of vertices in the graph by the sum of geodesic
+// distances of each vertex. This measure allows customization
+// of the distance type, result type, and even the underlying
+// divide operation.
+template <typename Graph,
+ typename Distance,
+ typename Result,
+ typename Divide = divides<Result> >
+struct scaled_closeness_measure
+{
+ typedef Distance distance_type;
+ typedef Result result_type;
+
+ Result operator ()(Distance d, const Graph& g)
+ {
+ if(d == numeric_values<Distance>::infinity()) {
+ return numeric_values<Result>::zero();
+ }
+ else {
+ return div(Result(num_vertices(g)), Result(d));
+ }
+ }
+ Divide div;
+};
+
+// The Actor type stores the name of each vertex in the graph.
+struct Actor
+{
+ std::string name;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef undirected_graph<Actor> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+// The name map provides an abstract accessor for the names of
+// each vertex. This is used during graph creation.
+typedef property_map<Graph, string Actor::*>::type NameMap;
+
+// Declare a matrix type and its corresponding property map that
+// will contain the distances between each pair of vertices.
+typedef exterior_vertex_property<Graph, int> DistanceProperty;
+typedef DistanceProperty::matrix_type DistanceMatrix;
+typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+// Declare the weight map so that each edge returns the same value.
+typedef constant_property_map<Edge, int> WeightMap;
+
+// Declare a container and its corresponding property map that
+// will contain the resulting closeness centralities of each
+// vertex in the graph.
+typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
+typedef ClosenessProperty::container_type ClosenessContainer;
+typedef ClosenessProperty::map_type ClosenessMap;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and a property map that provides access
+ // to the actor names.
+ Graph g;
+ NameMap nm(get(&Actor::name, g));
+
+ // Read the graph from standard input.
+ read_graph(g, nm, cin);
+
+ // Compute the distances between all pairs of vertices using
+ // the Floyd-Warshall algorithm. Note that the weight map is
+ // created so that every edge has a weight of 1.
+ DistanceMatrix distances(num_vertices(g));
+ DistanceMatrixMap dm(distances, g);
+ WeightMap wm(1);
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+
+ // Create the scaled closeness measure.
+ scaled_closeness_measure<Graph, int, float> m;
+
+ // Compute the degree centrality for graph
+ ClosenessContainer cents(num_vertices(g));
+ ClosenessMap cm(cents, g);
+ all_closeness_centralities(g, dm, cm, m);
+
+ // Print the scaled closeness centrality of each vertex.
+ graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << setw(12) << setiosflags(ios::left)
+ << g[*i].name << get(cm, *i) << endl;
+ }
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/social_network.graph Mon Sep 7 09:29:57 2009
@@ -0,0 +1,12 @@
+Scott,Jill
+Mary,Scott
+Jill,Mary
+Bill,Scott
+Josh,Bill
+Scott,Frank
+Laurie,Frank
+Mary,Laurie
+Anne,Frank
+Howard,Anne
+Frank,Howard
+Josh,Frank
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/tiernan_girth_circumference.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,40 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[tiernan_girth_circumference
+#include <iostream>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and read it from standard input.
+ Graph g;
+ read_graph(g, cin);
+
+ // Compute the girth and circumference simulataneously
+ size_t girth, circ;
+ tie(girth, circ) = tiernan_girth_and_circumference(g);
+
+ // Print the result
+ cout << "girth: " << girth << endl;
+ cout << "circumference: " << circ << endl;
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/tiernan_print_cycles.cpp Mon Sep 7 09:29:57
2009
@@ -0,0 +1,68 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+//[tiernan_print_cycles
+#include <iostream>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The cycle_printer is a visitor that will print the path that comprises
+// the cycle. Note that the back() vertex of the path is not the same as
+// the front(). It is implicit in the listing of vertices that the back()
+// vertex is connected to the front().
+template <typename OutputStream>
+struct cycle_printer
+{
+ cycle_printer(OutputStream& stream)
+ : os(stream)
+ { }
+
+ template <typename Path, typename Graph>
+ void cycle(const Path& p, const Graph& g)
+ {
+ // Get the property map containing the vertex indices
+ // so we can print them.
+ typedef typename property_map<Graph, vertex_index_t>::const_type
IndexMap;
+ IndexMap indices = get(vertex_index, g);
+
+ // Iterate over path printing each vertex that forms the cycle.
+ typename Path::const_iterator i, end = p.end();
+ for(i = p.begin(); i != end; ++i) {
+ os << get(indices, *i) << " ";
+ }
+ os << endl;
+ }
+ OutputStream& os;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+ // Create the graph and read it from standard input.
+ Graph g;
+ read_graph(g, cin);
+
+ // Instantiate the visitor for printing cycles
+ cycle_printer<ostream> vis(cout);
+
+ // Use the Tiernan algorithm to visit all cycles, printing them
+ // as they are found.
+ tiernan_all_cycles(g, vis);
+
+ return 0;
+}
+//]
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/bron_kerbosch_all_cliques.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,78 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <iterator>
+#include <algorithm>
+#include <vector>
+#include <map>
+
+#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/bron_kerbosch_all_cliques.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+
+#include <boost/random/linear_congruential.hpp>
+
+using namespace std;
+using namespace boost;
+
+// TODO: This is probably not a very good test. We should be able to define
+// an identity test - something like find the clique of K5.
+
+struct clique_validator
+{
+ clique_validator()
+ { }
+
+ template <typename Clique, typename Graph>
+ inline void
+ clique(const Clique& c, Graph& g)
+ {
+ // Simply assert that each vertex in the clique is connected
+ // to all others in the clique.
+ typename Clique::const_iterator i, j, end = c.end();
+ for(i = c.begin(); i != end; ++i) {
+ for(j = c.begin(); j != end; ++j) {
+ if(i != j) {
+ BOOST_ASSERT(edge(*i, *j, g).second);
+ }
+ }
+ }
+ }
+};
+
+template <typename Graph>
+void test()
+{
+ typedef erdos_renyi_iterator<boost::minstd_rand, Graph> er;
+
+ // Generate random graphs with 15 vertices and 15% probability
+ // of edge connection.
+ static const size_t N = 20;
+ static const double P = 0.1;
+
+ boost::minstd_rand rng;
+ Graph g(er(rng, N, P), er(), N);
+ renumber_indices(g);
+ print_edges(g, get(vertex_index, g));
+
+ bron_kerbosch_all_cliques(g, clique_validator());
+}
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> DiGraph;
+
+ std::cout << "*** undirected ***\n";
+ test<Graph>();
+
+ std::cout << "*** directed ***\n";
+ test<DiGraph>();
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/closeness_centrality.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,134 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <vector>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/closeness_centrality.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
+
+using namespace std;
+using namespace boost;
+
+// number of vertices in the graph
+static const unsigned N = 5;
+
+template <typename Graph>
+struct vertex_vector
+{
+ typedef graph_traits<Graph> traits;
+ typedef vector<typename traits::vertex_descriptor> type;
+};
+
+template <typename Graph>
+void build_graph(Graph& g,
+ typename vertex_vector<Graph>::type& v)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // add vertices
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // add edges
+ add_edge(v[0], v[1], g);
+ add_edge(v[1], v[2], g);
+ add_edge(v[2], v[0], g);
+ add_edge(v[3], v[4], g);
+ add_edge(v[4], v[0], g);
+};
+
+
+template <typename Graph>
+void test_undirected()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, double> CentralityProperty;
+ typedef typename CentralityProperty::container_type
CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+ typedef constant_property_map<Edge, int> WeightMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ CentralityContainer centralities(num_vertices(g));
+ DistanceMatrix distances(num_vertices(g));
+
+ CentralityMap cm(centralities, g);
+ DistanceMatrixMap dm(distances, g);
+
+ WeightMap wm(1);
+
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+ all_closeness_centralities(g, dm, cm);
+
+ BOOST_ASSERT(cm[v[0]] == double(1)/5);
+ BOOST_ASSERT(cm[v[1]] == double(1)/7);
+ BOOST_ASSERT(cm[v[2]] == double(1)/7);
+ BOOST_ASSERT(cm[v[3]] == double(1)/9);
+ BOOST_ASSERT(cm[v[4]] == double(1)/6);
+}
+
+template <typename Graph>
+void test_directed()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, double> CentralityProperty;
+ typedef typename CentralityProperty::container_type
CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+ typedef constant_property_map<Edge, int> WeightMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ CentralityContainer centralities(num_vertices(g));
+ DistanceMatrix distances(num_vertices(g));
+
+ CentralityMap cm(centralities, g);
+ DistanceMatrixMap dm(distances, g);
+
+ WeightMap wm(1);
+
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+ all_closeness_centralities(g, dm, cm);
+
+ BOOST_ASSERT(cm[v[0]] == double(0));
+ BOOST_ASSERT(cm[v[1]] == double(0));
+ BOOST_ASSERT(cm[v[2]] == double(0));
+ BOOST_ASSERT(cm[v[3]] == double(1)/10);
+ BOOST_ASSERT(cm[v[4]] == double(0));
+}
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> Digraph;
+
+ test_undirected<Graph>();
+ test_directed<Digraph>();
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/clustering_coefficient.cpp Mon Sep 7 09:29:57
2009
@@ -0,0 +1,105 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/clustering_coefficient.hpp>
+
+using namespace std;
+using namespace boost;
+
+// number of vertices in the graph
+static const unsigned N = 5;
+
+template <typename Graph>
+struct vertex_vector
+{
+ typedef graph_traits<Graph> traits;
+ typedef vector<typename traits::vertex_descriptor> type;
+};
+
+template <typename Graph>
+void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // add vertices
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // add edges
+ add_edge(v[0], v[1], g);
+ add_edge(v[1], v[2], g);
+ add_edge(v[2], v[0], g);
+ add_edge(v[3], v[4], g);
+ add_edge(v[4], v[0], g);
+};
+
+template <typename Graph>
+void test_undirected()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef exterior_vertex_property<Graph, double> ClusteringProperty;
+ typedef typename ClusteringProperty::container_type
ClusteringContainer;
+ typedef typename ClusteringProperty::map_type ClusteringMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ ClusteringContainer cc(num_vertices(g));
+ ClusteringMap cm(cc, g);
+
+ BOOST_ASSERT(num_paths_through_vertex(g, v[0]) == 3);
+ BOOST_ASSERT(num_paths_through_vertex(g, v[1]) == 1);
+ BOOST_ASSERT(num_paths_through_vertex(g, v[2]) == 1);
+ BOOST_ASSERT(num_paths_through_vertex(g, v[3]) == 0);
+ BOOST_ASSERT(num_paths_through_vertex(g, v[4]) == 1);
+
+ BOOST_ASSERT(num_triangles_on_vertex(g, v[0]) == 1);
+ BOOST_ASSERT(num_triangles_on_vertex(g, v[1]) == 1);
+ BOOST_ASSERT(num_triangles_on_vertex(g, v[2]) == 1);
+ BOOST_ASSERT(num_triangles_on_vertex(g, v[3]) == 0);
+ BOOST_ASSERT(num_triangles_on_vertex(g, v[4]) == 0);
+
+ BOOST_ASSERT(clustering_coefficient(g, v[0]) == double(1)/3);
+ BOOST_ASSERT(clustering_coefficient(g, v[1]) == 1);
+ BOOST_ASSERT(clustering_coefficient(g, v[2]) == 1);
+ BOOST_ASSERT(clustering_coefficient(g, v[3]) == 0);
+ BOOST_ASSERT(clustering_coefficient(g, v[4]) == 0);
+
+ all_clustering_coefficients(g, cm);
+
+ BOOST_ASSERT(cm[v[0]] == double(1)/3);
+ BOOST_ASSERT(cm[v[1]] == 1);
+ BOOST_ASSERT(cm[v[2]] == 1);
+ BOOST_ASSERT(cm[v[3]] == 0);
+ BOOST_ASSERT(cm[v[4]] == 0);
+
+ // I would have used check_close, but apparently, that requires
+ // me to link this against a library - which I don't really want
+ // to do. Basically, this makes sure that that coefficient is
+ // within some tolerance (like 1/10 million).
+ double coef = mean_clustering_coefficient(g, cm);
+ BOOST_ASSERT((coef - (7.0f / 15.0f)) < 1e-7f);
+}
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> Digraph;
+
+ // TODO: write a test for directed clustering coefficient.
+
+ test_undirected<Graph>();
+ // test<Digraph>();
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/core_numbers_test.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,155 @@
+// (C) Copyright David Gleich 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <vector>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/core_numbers.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <stdio.h>
+
+using namespace boost;
+
+const char* errstr = "";
+
+int test_1() {
+ // core numbers of sample graph
+ typedef adjacency_list<vecS,vecS,undirectedS> Graph;
+
+ Graph G(21);
+ add_edge(0,1,G);
+ add_edge(1,2,G);
+ add_edge(1,3,G);
+ add_edge(2,3,G);
+ add_edge(1,4,G);
+ add_edge(3,4,G);
+ add_edge(4,5,G);
+ add_edge(4,6,G);
+ add_edge(5,6,G);
+ add_edge(4,7,G);
+ add_edge(5,7,G);
+ add_edge(6,7,G);
+ add_edge(7,8,G);
+ add_edge(3,9,G);
+ add_edge(8,9,G);
+ add_edge(8,10,G);
+ add_edge(9,10,G);
+ add_edge(10,11,G);
+ add_edge(10,12,G);
+ add_edge(3,13,G);
+ add_edge(9,13,G);
+ add_edge(3,14,G);
+ add_edge(9,14,G);
+ add_edge(13,14,G);
+ add_edge(16,17,G);
+ add_edge(16,18,G);
+ add_edge(17,19,G);
+ add_edge(18,19,G);
+ add_edge(19,20,G);
+
+ std::vector<int> core_nums(num_vertices(G));
+ core_numbers(G,
+ make_iterator_property_map(core_nums.begin(),
get(vertex_index,G)));
+
+ for (size_t i=0; i<num_vertices(G); ++i) {
+ printf("vertex %3zu : %i\n", i, core_nums[i]);
+ }
+
+ int correct[21]={1,2,2,3,3,3,3,3,2,3,2,1,1,3,3,0,2,2,2,2,1};
+ for (size_t i=0; i<num_vertices(G); ++i) {
+ if (core_nums[i] != correct[i]) {
+ return 1; // error!
+ }
+ }
+ return 0;
+}
+
+int test_2() {
+ // core numbers of sample graph
+ typedef adjacency_list < listS, vecS, undirectedS,
+ no_property, property < edge_weight_t, int > > graph_t;
+ int num_nodes = 3;
+ typedef std::pair<int,int> Edge;
+
+ Edge edge_array[] = { Edge(0,1), Edge(0,2), Edge(1,2) };
+ int weights[] = {-1, -2, -2};
+ int num_arcs = sizeof(edge_array) / sizeof(Edge);
+
+ graph_t G(edge_array, edge_array + num_arcs, weights, num_nodes);
+ property_map<graph_t, edge_weight_t>::type weightmap =
get(edge_weight, G);
+
+ std::vector<int> core_nums(num_vertices(G));
+ weighted_core_numbers(G,
+ make_iterator_property_map(core_nums.begin(),
get(vertex_index,G)));
+
+ for (size_t i=0; i<num_vertices(G); ++i) {
+ printf("vertex %3zu : %i\n", i, core_nums[i]);
+ }
+
+ int correct[3]={-1,-1,-4};
+ for (size_t i=0; i<num_vertices(G); ++i) {
+ if (core_nums[i] != correct[i]) {
+ return 1; // error!
+ }
+ }
+ return 0;
+}
+
+int test_3() {
+ // core numbers of a directed graph, the core numbers of a directed
+ // cycle are always one
+ typedef adjacency_list < vecS, vecS, directedS > graph_t;
+ int num_nodes = 5;
+ typedef std::pair<int,int> Edge;
+
+ Edge edge_array[] = {
Edge(0,1),Edge(1,2),Edge(2,3),Edge(3,4),Edge(4,0) };
+ int num_arcs = sizeof(edge_array) / sizeof(Edge);
+
+ graph_t G(edge_array, edge_array + num_arcs, num_nodes);
+
+ std::vector<int> core_nums(num_vertices(G));
+ core_numbers(G,
+ make_iterator_property_map(core_nums.begin(),
get(vertex_index,G)));
+
+ for (size_t i=0; i<num_vertices(G); ++i) {
+ printf("vertex %3zu : %i\n", i, core_nums[i]);
+ }
+
+ int correct[5]={1,1,1,1,1};
+ for (size_t i=0; i<num_vertices(G); ++i) {
+ if (core_nums[i] != correct[i]) {
+ return 1; // error!
+ }
+ }
+ return 0;
+}
+
+int main(int argc, char **argv) {
+ int nfail = 0, ntotal = 0;
+ int rval;
+
+ const char* name;
+
+ name= "core_numbers";
+ rval= test_1(); ntotal++;
+ if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
+ else { printf("%20s success\n", name); }
+
+ name= "weighted_core_numbers";
+ rval= test_2(); ntotal++;
+ if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
+ else { printf("%20s success\n", name); }
+
+ name= "directed_corenums";
+ rval= test_3(); ntotal++;
+ if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
+ else { printf("%20s success\n", name); }
+
+ printf("\n");
+ printf("Total tests : %3i\n", ntotal);
+ printf("Total failed : %3i\n", nfail);
+
+ return nfail!=0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/degree_centrality.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,123 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <vector>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/degree_centrality.hpp>
+#include <boost/graph/exterior_property.hpp>
+
+using namespace std;
+using namespace boost;
+
+// useful types
+// number of vertices in the graph
+static const unsigned N = 5;
+
+template <typename Graph>
+void build_graph(Graph& g,
+ vector<typename graph_traits<Graph>::vertex_descriptor>&
v)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // add vertices
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // add edges
+ add_edge(v[0], v[1], g);
+ add_edge(v[1], v[2], g);
+ add_edge(v[2], v[0], g);
+ add_edge(v[3], v[4], g);
+ add_edge(v[4], v[0], g);
+};
+
+template <typename Graph>
+void test_undirected()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
+ typedef typename CentralityProperty::container_type
CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ CentralityContainer cents(num_vertices(g));
+ CentralityMap cm(cents, g);
+ all_degree_centralities(g, cm);
+
+ BOOST_ASSERT(cm[v[0]] == 3);
+ BOOST_ASSERT(cm[v[1]] == 2);
+ BOOST_ASSERT(cm[v[2]] == 2);
+ BOOST_ASSERT(cm[v[3]] == 1);
+ BOOST_ASSERT(cm[v[4]] == 2);
+}
+
+template <typename Graph>
+void test_influence()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
+ typedef typename CentralityProperty::container_type
CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ Graph g;
+
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ CentralityContainer cents(num_vertices(g));
+ CentralityMap cm(cents, g);
+ all_influence_values(g, cm);
+
+ BOOST_ASSERT(cm[v[0]] == 1);
+ BOOST_ASSERT(cm[v[1]] == 1);
+ BOOST_ASSERT(cm[v[2]] == 1);
+ BOOST_ASSERT(cm[v[3]] == 1);
+ BOOST_ASSERT(cm[v[4]] == 1);
+}
+
+template <typename Graph>
+void test_prestige()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
+ typedef typename CentralityProperty::container_type
CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ Graph g;
+
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ CentralityContainer cents(num_vertices(g));
+ CentralityMap cm(cents, g);
+ all_prestige_values(g, cm);
+
+ BOOST_ASSERT(cm[v[0]] == 2);
+ BOOST_ASSERT(cm[v[1]] == 1);
+ BOOST_ASSERT(cm[v[2]] == 1);
+ BOOST_ASSERT(cm[v[3]] == 0);
+ BOOST_ASSERT(cm[v[4]] == 1);
+}
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> Digraph;
+
+ test_undirected<Graph>();
+ test_influence<Digraph>();
+ test_prestige<Digraph>();
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/dijkstra_no_color_map_compare.cpp Mon Sep 7
09:29:57 2009
@@ -0,0 +1,124 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen
+//
+// 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)
+//=======================================================================
+
+#include <iostream>
+#include <map>
+#include <vector>
+
+#include <boost/lexical_cast.hpp>
+#include <boost/random.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#define INITIALIZE_VERTEX 0
+#define DISCOVER_VERTEX 1
+#define EXAMINE_VERTEX 2
+#define EXAMINE_EDGE 3
+#define EDGE_RELAXED 4
+#define EDGE_NOT_RELAXED 5
+#define FINISH_VERTEX 6
+
+template <typename Graph>
+void run_dijkstra_test(const Graph& graph)
+{
+ using namespace boost;
+
+ // Set up property maps
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
+
+ typedef typename std::map<vertex_t, vertex_t> vertex_map_t;
+ typedef associative_property_map<vertex_map_t> predecessor_map_t;
+ vertex_map_t default_vertex_map, no_color_map_vertex_map;
+ predecessor_map_t default_predecessor_map(default_vertex_map),
+ no_color_map_predecessor_map(no_color_map_vertex_map);
+
+ typedef typename std::map<vertex_t, double> vertex_double_map_t;
+ typedef associative_property_map<vertex_double_map_t> distance_map_t;
+ vertex_double_map_t default_vertex_double_map,
no_color_map_vertex_double_map;
+ distance_map_t default_distance_map(default_vertex_double_map),
+ no_color_map_distance_map(no_color_map_vertex_double_map);
+
+ // Run dijkstra algoirthms
+ dijkstra_shortest_paths(graph, vertex(0, graph),
+ predecessor_map(default_predecessor_map)
+ .distance_map(default_distance_map));
+
+ dijkstra_shortest_paths_no_color_map(graph, vertex(0, graph),
+
predecessor_map(no_color_map_predecessor_map)
+
.distance_map(no_color_map_distance_map));
+
+ // Verify that predecessor maps are equal
+ BOOST_CHECK(std::equal(default_vertex_map.begin(),
default_vertex_map.end(),
+ no_color_map_vertex_map.begin()));
+
+ // Verify that distance maps are equal
+ BOOST_CHECK(std::equal(default_vertex_double_map.begin(),
default_vertex_double_map.end(),
+ no_color_map_vertex_double_map.begin()));
+}
+
+int test_main(int argc, char* argv[])
+{
+ using namespace boost;
+
+ int vertices_to_create = 10;
+ int edges_to_create = 500;
+ std::size_t random_seed = time(0);
+
+ if (argc > 1) {
+ vertices_to_create = lexical_cast<int>(argv[1]);
+ }
+
+ if (argc > 2) {
+ edges_to_create = lexical_cast<int>(argv[2]);
+ }
+
+ if (argc > 3) {
+ random_seed = lexical_cast<std::size_t>(argv[3]);
+ }
+
+ minstd_rand generator(random_seed);
+
+ // Set up graph
+ typedef adjacency_list<listS, listS, directedS,
+ property<vertex_index_t, int >,
+ property<edge_weight_t, double> > graph_t;
+
+ typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
+ typedef graph_traits<graph_t>::edge_descriptor edge_t;
+
+ graph_t graph;
+ generate_random_graph(graph, vertices_to_create, edges_to_create,
generator);
+
+ // Set up property maps
+ typedef property_map<graph_t, vertex_index_t>::type index_map_t;
+ index_map_t index_map = get(vertex_index, graph);
+ int vertex_index = 0;
+
+ BGL_FORALL_VERTICES(current_vertex, graph, graph_t) {
+ put(index_map, current_vertex, vertex_index++);
+ }
+
+ typedef property_map<graph_t, edge_weight_t>::type weight_map_t;
+ weight_map_t weight_map = get(edge_weight, graph);
+ randomize_property<edge_weight_t>(graph, generator);
+
+ // Run comparison test with original dijkstra_shortest_paths
+ std::cout << "Running dijkstra shortest paths test with " <<
num_vertices(graph) <<
+ " vertices and " << num_edges(graph) << " edges " << std::endl;
+
+ run_dijkstra_test(graph);
+
+ return 0;
+}
+
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/eccentricity.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,144 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/eccentricity.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
+
+
+using namespace std;
+using namespace boost;
+
+// number of vertices in the graph
+static const unsigned N = 5;
+
+template <typename Graph>
+struct vertex_vector
+{
+ typedef graph_traits<Graph> traits;
+ typedef vector<typename traits::vertex_descriptor> type;
+};
+
+template <typename Graph>
+void build_graph(Graph& g,
+ typename vertex_vector<Graph>::type& v)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // add vertices
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // add edges
+ add_edge(v[0], v[1], g);
+ add_edge(v[1], v[2], g);
+ add_edge(v[2], v[0], g);
+ add_edge(v[3], v[4], g);
+ add_edge(v[4], v[0], g);
+};
+
+
+template <typename Graph>
+void test_undirected()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, int> EccentricityProperty;
+ typedef typename EccentricityProperty::container_type
EccentricityContainer;
+ typedef typename EccentricityProperty::map_type EccentricityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+ typedef constant_property_map<Edge, int> WeightMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ EccentricityContainer eccs(num_vertices(g));
+ DistanceMatrix distances(num_vertices(g));
+
+ EccentricityMap em(eccs, g);
+ DistanceMatrixMap dm(distances, g);
+
+ WeightMap wm(1);
+
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+ all_eccentricities(g, dm, em);
+ int rad = radius(g, em);
+ int dia = diameter(g, em);
+
+ BOOST_ASSERT(em[v[0]] == 2);
+ BOOST_ASSERT(em[v[1]] == 3);
+ BOOST_ASSERT(em[v[2]] == 3);
+ BOOST_ASSERT(em[v[3]] == 3);
+ BOOST_ASSERT(em[v[4]] == 2);
+ BOOST_ASSERT(rad == 2);
+ BOOST_ASSERT(dia == 3);
+}
+
+template <typename Graph>
+void test_directed()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, int> EccentricityProperty;
+ typedef typename EccentricityProperty::container_type
EccentricityContainer;
+ typedef typename EccentricityProperty::map_type EccentricityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+ typedef constant_property_map<Edge, int> WeightMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ EccentricityContainer eccs(num_vertices(g));
+ DistanceMatrix distances(num_vertices(g));
+
+ EccentricityMap em(eccs, g);
+ DistanceMatrixMap dm(distances, g);
+
+ WeightMap wm(1);
+
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+ all_eccentricities(g, dm, em);
+ int rad = radius(g, em);
+ int dia = diameter(g, em);
+
+ int inf = numeric_values<int>::infinity();
+ BOOST_ASSERT(em[v[0]] == inf);
+ BOOST_ASSERT(em[v[1]] == inf);
+ BOOST_ASSERT(em[v[2]] == inf);
+ BOOST_ASSERT(em[v[3]] == 4);
+ BOOST_ASSERT(em[v[4]] == inf);
+ BOOST_ASSERT(rad == 4);
+ BOOST_ASSERT(dia == inf);
+}
+
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> Digraph;
+
+ test_undirected<Graph>();
+ test_directed<Digraph>();
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/generator_test.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,124 @@
+// Copyright 2009 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+// Authors: Nicholas Edmonds
+// Andrew Lumsdaine
+
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#include <boost/graph/rmat_graph_generator.hpp>
+#include <boost/graph/small_world_generator.hpp>
+#include <boost/graph/ssca_graph_generator.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+#include <boost/graph/mesh_graph_generator.hpp>
+
+#include <boost/graph/adjacency_list.hpp>
+
+using namespace boost;
+
+int test_main(int argc, char** argv) {
+
+ typedef rand48 RandomGenerator;
+
+ typedef adjacency_list<vecS, vecS, directedS> Graph;
+
+ RandomGenerator gen;
+
+ size_t N = 100;
+ size_t M = 1000;
+ double p = 0.05;
+
+ // Test Erdos-Renyi generator
+ {
+ erdos_renyi_iterator<RandomGenerator, Graph> start(gen, N, p);
+ erdos_renyi_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ {
+ sorted_erdos_renyi_iterator<RandomGenerator, Graph> start(gen, N, p);
+ sorted_erdos_renyi_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ // Test Small World generator
+ {
+ small_world_iterator<RandomGenerator, Graph> start(gen, N, M, p);
+ small_world_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ // Test SSCA generator
+ {
+ ssca_iterator<RandomGenerator, Graph> start(gen, N, 5, 0.5, 5, p);
+ ssca_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ // Test Mesh generator
+ {
+ mesh_iterator<Graph> start(N, N);
+ mesh_iterator<Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ // Test R-MAT generator
+ double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
+
+ {
+ rmat_iterator<RandomGenerator, Graph> start(gen, N, M, a, b, c, d);
+ rmat_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ {
+ unique_rmat_iterator<RandomGenerator, Graph> start(gen, N, M, a, b, c,
d);
+ unique_rmat_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ {
+ sorted_unique_rmat_iterator<RandomGenerator, Graph> start(gen, N, M,
a, b, c, d);
+ sorted_unique_rmat_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ {
+ sorted_unique_rmat_iterator<RandomGenerator, Graph> start(gen, N, M,
a, b, c, d, true);
+ sorted_unique_rmat_iterator<RandomGenerator, Graph> end;
+
+ while (start != end) ++start;
+
+ BOOST_CHECK(start == end);
+ }
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/index_graph.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,94 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+template <typename Graph>
+void test()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
+
+ static const size_t N = 5;
+
+ Graph g;
+ IndexMap x = get(vertex_index, g);
+
+ // build up the graph
+ Vertex v[N];
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // after the first build, we should have these conditions
+ BOOST_ASSERT(max_vertex_index(g) == N);
+ for(size_t i = 0; i < N; ++i) {
+ BOOST_ASSERT(get_vertex_index(v[i], g) == i);
+ }
+
+ // Remove all vertices and then re-add them.
+ for(size_t i = 0; i < N; ++i) remove_vertex(v[i], g);
+ BOOST_ASSERT(num_vertices(g) == 0);
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
+ }
+ BOOST_ASSERT(num_vertices(g) == N);
+
+ // Before renumbering, our vertices should be off by N. In other words,
+ // we're not in a good state.
+ BOOST_ASSERT(max_vertex_index(g) == 10);
+ for(size_t i = 0; i < N; ++i) {
+ BOOST_ASSERT(get_vertex_index(v[i], g) == N + i);
+ }
+
+ // Renumber vertices
+ renumber_vertex_indices(g);
+
+ // And we should be back to the initial condition
+ BOOST_ASSERT(max_vertex_index(g) == N);
+ for(size_t i = 0; i < N; ++i) {
+ BOOST_ASSERT(get_vertex_index(v[i], g) == i);
+ }
+}
+
+// Make sure that graphs constructed over n vertices will actually number
+// their vertices correctly.
+template <typename Graph>
+void build()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator Iterator;
+ typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
+
+ static const size_t N = 5;
+
+ Graph g(N);
+ BOOST_ASSERT(max_vertex_index(g) == N);
+
+ IndexMap x = get(vertex_index, g);
+
+ // Each vertex should be numbered correctly.
+ Iterator i, end;
+ tie(i, end) = vertices(g);
+ for(size_t x = 0; i != end; ++i, ++x) {
+ BOOST_ASSERT(get_vertex_index(*i, g) == x);
+ }
+}
+
+int main(int, char*[])
+{
+ test< undirected_graph<> >();
+ test< directed_graph<> >();
+
+ build< undirected_graph<> >();
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/labeled_graph.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,147 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <string>
+#include <set>
+
+#define BOOST_NO_HASH
+
+#include <boost/assert.hpp>
+#include <boost/range.hpp>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/labeled_graph.hpp>
+
+#include "typestr.hpp"
+
+using std::cout;
+using std::string;
+using namespace boost;
+
+void test_norm();
+void test_temp();
+void test_bacon();
+
+int main() {
+ test_norm();
+ test_temp();
+ test_bacon();
+}
+
+//////////////////////////////////////
+// Utility Functions and Types
+//////////////////////////////////////
+
+
+struct Actor {
+ Actor() { }
+ Actor(string const& s) : name(s) { }
+ string name;
+};
+
+struct Movie {
+ Movie() { }
+ Movie(string const& s) : name(s) { }
+ string name;
+};
+
+
+template <typename Graph>
+void init_graph(Graph& g) {
+ for(int i = 0; i < 6; ++i) {
+ add_vertex(i, g);
+ }
+}
+
+template <typename Graph>
+void label_graph(Graph& g)
+{
+ typedef typename graph_traits<Graph>::vertex_iterator Iter;
+ Iter f, l;
+ int x = 0;
+ for(tie(f, l) = vertices(g); f != l; ++f, ++x) {
+ label_vertex(*f, x, g);
+ }
+}
+
+template <typename Graph>
+void build_graph(Graph& g) {
+ // This is the graph shown on the wikipedia page for Graph Theory.
+ add_edge_by_label(5, 3, g);
+ add_edge_by_label(3, 4, g);
+ add_edge_by_label(3, 2, g);
+ add_edge_by_label(4, 1, g);
+ add_edge_by_label(4, 0, g);
+ add_edge_by_label(2, 1, g);
+ add_edge_by_label(1, 0, g);
+ BOOST_ASSERT(num_vertices(g) == 6);
+ BOOST_ASSERT(num_edges(g) == 7);
+}
+
+//////////////////////////////////////
+// Temporal Labelings
+//////////////////////////////////////
+
+void test_norm() {
+ {
+ typedef labeled_graph<undirected_graph<>, unsigned> Graph;
+ Graph g;
+ init_graph(g);
+ build_graph(g);
+ }
+
+ {
+ typedef labeled_graph<directed_graph<>, unsigned> Graph;
+ Graph g;
+ init_graph(g);
+ build_graph(g);
+ }
+}
+
+//////////////////////////////////////
+// Temporal Labelings
+//////////////////////////////////////
+
+
+void test_temp() {
+ typedef undirected_graph<> Graph;
+ typedef labeled_graph<Graph*, int> LabGraph;
+ Graph g(6);
+ LabGraph lg(&g);
+ label_graph(lg);
+ build_graph(lg);
+}
+
+//////////////////////////////////////
+// Labeled w/ Properties
+//////////////////////////////////////
+
+void test_bacon() {
+ string bacon("Kevin Bacon");
+ string slater("Christian Slater");
+ Movie murder("Murder in the First");
+ {
+
+ typedef labeled_graph<undirected_graph<Actor, Movie>, string>
Graph;
+ Graph g;
+ add_vertex(bacon, g);
+ add_vertex(slater, g);
+ add_edge_by_label(bacon, slater, murder, g);
+ }
+
+ {
+ string bacon = "Kevin Bacon";
+ string slater = "Christian Slater";
+
+ typedef labeled_graph<directed_graph<Actor, Movie>, string> Graph;
+ Graph g;
+ add_vertex(bacon, g);
+ add_vertex(slater, g);
+ add_edge_by_label(bacon, slater, murder, g);
+ }
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/mcgregor_subgraphs_test.cpp Mon Sep 7 09:29:57
2009
@@ -0,0 +1,470 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen
+//
+// 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)
+//=======================================================================
+
+#include <cmath>
+#include <iostream>
+#include <fstream>
+#include <sstream>
+#include <vector>
+
+#include <boost/lexical_cast.hpp>
+#include <boost/random.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/filtered_graph.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/graph/isomorphism.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/graph/mcgregor_common_subgraphs.hpp>
+#include <boost/property_map/shared_array_property_map.hpp>
+#include <boost/test/minimal.hpp>
+
+using namespace boost;
+
+bool was_common_subgraph_found = false, output_graphs = false;
+std::vector<std::string> simple_subgraph_list;
+
+// Callback that compares incoming graphs to the supplied common
+// subgraph.
+template <typename Graph>
+struct test_callback {
+
+ test_callback(Graph& common_subgraph,
+ const Graph& graph1,
+ const Graph& graph2) :
+ m_graph1(graph1),
+ m_graph2(graph2),
+ m_common_subgraph(common_subgraph) { }
+
+ template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ typename graph_traits<Graph>::vertices_size_type
subgraph_size) {
+
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+ typedef std::pair<Edge, bool> EdgeInfo;
+
+ typedef typename property_map<Graph, vertex_index_t>::type
VertexIndexMap;
+ typedef typename property_map<Graph, vertex_name_t>::type
VertexNameMap;
+ typedef typename property_map<Graph, edge_name_t>::type EdgeNameMap;
+
+ if (subgraph_size != num_vertices(m_common_subgraph)) {
+ return (true);
+ }
+
+ // Fill membership maps for both graphs
+ typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap;
+
+ MembershipMap membership_map1(num_vertices(m_graph1),
+ get(vertex_index, m_graph1));
+
+ MembershipMap membership_map2(num_vertices(m_graph2),
+ get(vertex_index, m_graph2));
+
+ fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2,
membership_map1);
+ fill_membership_map<Graph>(m_graph2, correspondence_map_2_to_1,
membership_map2);
+
+ // Generate filtered graphs using membership maps
+ typedef typename membership_filtered_graph_traits<Graph,
MembershipMap>::graph_type
+ MembershipFilteredGraph;
+
+ MembershipFilteredGraph subgraph1 =
+ make_membership_filtered_graph(m_graph1, membership_map1);
+
+ MembershipFilteredGraph subgraph2 =
+ make_membership_filtered_graph(m_graph2, membership_map2);
+
+ VertexIndexMap vindex_map1 = get(vertex_index, subgraph1);
+ VertexIndexMap vindex_map2 = get(vertex_index, subgraph2);
+
+ VertexNameMap vname_map_common = get(vertex_name, m_common_subgraph);
+ VertexNameMap vname_map1 = get(vertex_name, subgraph1);
+ VertexNameMap vname_map2 = get(vertex_name, subgraph2);
+
+ EdgeNameMap ename_map_common = get(edge_name, m_common_subgraph);
+ EdgeNameMap ename_map1 = get(edge_name, subgraph1);
+ EdgeNameMap ename_map2 = get(edge_name, subgraph2);
+
+ // Verify that subgraph1 matches the supplied common subgraph
+ BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph) {
+
+ Vertex vertex_common = vertex(get(vindex_map1, vertex1),
m_common_subgraph);
+
+ // Match vertex names
+ if (get(vname_map_common, vertex_common) != get(vname_map1,
vertex1)) {
+
+ // Keep looking
+ return (true);
+
+ }
+
+ BGL_FORALL_VERTICES_T(vertex1_2, subgraph1, MembershipFilteredGraph)
{
+
+ Vertex vertex_common2 = vertex(get(vindex_map1, vertex1_2),
m_common_subgraph);
+ EdgeInfo edge_common = edge(vertex_common, vertex_common2,
m_common_subgraph);
+ EdgeInfo edge1 = edge(vertex1, vertex1_2, subgraph1);
+
+ if ((edge_common.second != edge1.second) ||
+ ((edge_common.second && edge1.second) &&
+ (get(ename_map_common, edge_common.first) != get(ename_map1,
edge1.first)))) {
+
+ // Keep looking
+ return (true);
+
+ }
+ }
+
+ } // BGL_FORALL_VERTICES_T (subgraph1)
+
+ // Verify that subgraph2 matches the supplied common subgraph
+ BGL_FORALL_VERTICES_T(vertex2, subgraph2, MembershipFilteredGraph) {
+
+ Vertex vertex_common = vertex(get(vindex_map2, vertex2),
m_common_subgraph);
+
+ // Match vertex names
+ if (get(vname_map_common, vertex_common) != get(vname_map2,
vertex2)) {
+
+ // Keep looking
+ return (true);
+
+ }
+
+ BGL_FORALL_VERTICES_T(vertex2_2, subgraph2, MembershipFilteredGraph)
{
+
+ Vertex vertex_common2 = vertex(get(vindex_map2, vertex2_2),
m_common_subgraph);
+ EdgeInfo edge_common = edge(vertex_common, vertex_common2,
m_common_subgraph);
+ EdgeInfo edge2 = edge(vertex2, vertex2_2, subgraph2);
+
+ if ((edge_common.second != edge2.second) ||
+ ((edge_common.second && edge2.second) &&
+ (get(ename_map_common, edge_common.first) != get(ename_map2,
edge2.first)))) {
+
+ // Keep looking
+ return (true);
+
+ }
+ }
+
+ } // BGL_FORALL_VERTICES_T (subgraph2)
+
+ // Check isomorphism just to be thorough
+ if (verify_isomorphism(subgraph1, subgraph2,
correspondence_map_1_to_2)) {
+
+ was_common_subgraph_found = true;
+
+ if (output_graphs) {
+
+ std::fstream file_subgraph("found_common_subgraph.dot",
std::fstream::out);
+ write_graphviz(file_subgraph, subgraph1,
+ make_label_writer(get(vertex_name, m_graph1)),
+ make_label_writer(get(edge_name, m_graph1)));
+
+ }
+
+ // Stop iterating
+ return (false);
+
+ }
+
+ // Keep looking
+ return (true);
+ }
+
+private:
+ const Graph& m_graph1, m_graph2;
+ Graph& m_common_subgraph;
+};
+
+template <typename Graph>
+struct simple_callback {
+
+ simple_callback(const Graph& graph1) :
+ m_graph1(graph1) { }
+
+ template <typename CorrespondenceMapFirstToSecond,
+ typename CorrespondenceMapSecondToFirst>
+ bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+ CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+ typename graph_traits<Graph>::vertices_size_type
subgraph_size) {
+
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef typename property_map<Graph, vertex_index_t>::type
VertexIndexMap;
+ typedef typename property_map<Graph, vertex_name_t>::type
VertexNameMap;
+ typedef typename property_map<Graph, edge_name_t>::type EdgeNameMap;
+
+ std::stringstream subgraph_string;
+
+ BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph) {
+
+ Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);
+
+ if (vertex2 != graph_traits<Graph>::null_vertex()) {
+ subgraph_string << vertex1 << "," << vertex2 << " ";
+ }
+
+ }
+
+ simple_subgraph_list.push_back(subgraph_string.str());
+
+ return (true);
+ }
+
+private:
+ const Graph& m_graph1;
+
+};
+
+template <typename Graph,
+ typename RandomNumberGenerator,
+ typename VertexNameMap,
+ typename EdgeNameMap>
+void add_random_vertices(Graph& graph, RandomNumberGenerator& generator,
+ int vertices_to_create, int max_edges_per_vertex,
+ VertexNameMap vname_map, EdgeNameMap ename_map) {
+
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef std::vector<Vertex> VertexList;
+
+ VertexList new_vertices;
+
+ for (int v_index = 0; v_index < vertices_to_create; ++v_index) {
+
+ Vertex new_vertex = add_vertex(graph);
+ put(vname_map, new_vertex, generator());
+ new_vertices.push_back(new_vertex);
+
+ }
+
+ // Add edges for every new vertex. Care is taken to avoid parallel
+ // edges.
+ for (typename VertexList::const_iterator v_iter = new_vertices.begin();
+ v_iter != new_vertices.end(); ++v_iter) {
+
+ Vertex source_vertex = *v_iter;
+ int edges_for_vertex = (std::min)((int)(generator() %
max_edges_per_vertex) + 1,
+ (int)num_vertices(graph));
+
+ while (edges_for_vertex > 0) {
+
+ Vertex target_vertex = random_vertex(graph, generator);
+
+ if (source_vertex == target_vertex) {
+ continue;
+ }
+
+ BGL_FORALL_OUTEDGES_T(source_vertex, edge, graph, Graph) {
+ if (target(edge, graph) == target_vertex) {
+ continue;
+ }
+ }
+
+ put(ename_map, add_edge(source_vertex, target_vertex, graph).first,
+ generator());
+
+ edges_for_vertex--;
+ }
+ }
+}
+
+bool has_subgraph_string(std::string set_string) {
+ return (std::find(simple_subgraph_list.begin(),
simple_subgraph_list.end(),
+ set_string) != simple_subgraph_list.end());
+}
+
+int test_main (int argc, char *argv[]) {
+ int vertices_to_create = 10;
+ int max_edges_per_vertex = 2;
+ std::size_t random_seed = time(0);
+
+ if (argc > 1) {
+ vertices_to_create = lexical_cast<int>(argv[1]);
+ }
+
+ if (argc > 2) {
+ max_edges_per_vertex = lexical_cast<int>(argv[2]);
+ }
+
+ if (argc > 3) {
+ output_graphs = lexical_cast<bool>(argv[3]);
+ }
+
+ if (argc > 4) {
+ random_seed = lexical_cast<std::size_t>(argv[4]);
+ }
+
+ minstd_rand generator(random_seed);
+
+ // Using a vecS graph here so that we don't have to mess around with
+ // a vertex index map; it will be implicit.
+ typedef adjacency_list<listS, vecS, directedS,
+ property<vertex_name_t, unsigned int,
+ property<vertex_index_t, unsigned int> >,
+ property<edge_name_t, unsigned int> > Graph;
+
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef property_map<Graph, vertex_name_t>::type VertexNameMap;
+ typedef property_map<Graph, edge_name_t>::type EdgeNameMap;
+
+ // Generate a random common subgraph and then add random vertices
+ // and edges to the two parent graphs.
+ Graph common_subgraph, graph1, graph2;
+
+ VertexNameMap vname_map_common = get(vertex_name, common_subgraph);
+ VertexNameMap vname_map1 = get(vertex_name, graph1);
+ VertexNameMap vname_map2 = get(vertex_name, graph2);
+
+ EdgeNameMap ename_map_common = get(edge_name, common_subgraph);
+ EdgeNameMap ename_map1 = get(edge_name, graph1);
+ EdgeNameMap ename_map2 = get(edge_name, graph2);
+
+ for (int vindex = 0; vindex < vertices_to_create; ++vindex) {
+ put(vname_map_common, add_vertex(common_subgraph), generator());
+ }
+
+ BGL_FORALL_VERTICES(source_vertex, common_subgraph, Graph) {
+
+ BGL_FORALL_VERTICES(target_vertex, common_subgraph, Graph) {
+
+ if (source_vertex != target_vertex) {
+ put(ename_map_common,
+ add_edge(source_vertex, target_vertex, common_subgraph).first,
+ generator());
+ }
+ }
+ }
+
+ randomize_property<vertex_name_t>(common_subgraph, generator);
+ randomize_property<edge_name_t>(common_subgraph, generator);
+
+ copy_graph(common_subgraph, graph1);
+ copy_graph(common_subgraph, graph2);
+
+ // Randomly add vertices and edges to graph1 and graph2.
+ add_random_vertices(graph1, generator, vertices_to_create,
+ max_edges_per_vertex, vname_map1, ename_map1);
+
+ add_random_vertices(graph2, generator, vertices_to_create,
+ max_edges_per_vertex, vname_map2, ename_map2);
+
+ if (output_graphs) {
+
+ std::fstream file_graph1("graph1.dot", std::fstream::out),
+ file_graph2("graph2.dot", std::fstream::out),
+ file_common_subgraph("expected_common_subgraph.dot",
std::fstream::out);
+
+ write_graphviz(file_graph1, graph1,
+ make_label_writer(vname_map1),
+ make_label_writer(ename_map1));
+
+ write_graphviz(file_graph2, graph2,
+ make_label_writer(vname_map2),
+ make_label_writer(ename_map2));
+
+ write_graphviz(file_common_subgraph, common_subgraph,
+ make_label_writer(get(vertex_name, common_subgraph)),
+ make_label_writer(get(edge_name, common_subgraph)));
+
+ }
+
+ std::cout << "Searching for common subgraph of size " <<
+ num_vertices(common_subgraph) << std::endl;
+
+ test_callback<Graph> user_callback(common_subgraph, graph1, graph2);
+
+ mcgregor_common_subgraphs(graph1, graph2, true, user_callback,
+ edges_equivalent(make_property_map_equivalent(ename_map1, ename_map2)).
+ vertices_equivalent(make_property_map_equivalent(vname_map1,
vname_map2)));
+
+ BOOST_CHECK(was_common_subgraph_found);
+
+ // Test maximum and unique variants on known graphs
+ Graph graph_simple1, graph_simple2;
+ simple_callback<Graph> user_callback_simple(graph_simple1);
+
+ VertexNameMap vname_map_simple1 = get(vertex_name, graph_simple1);
+ VertexNameMap vname_map_simple2 = get(vertex_name, graph_simple2);
+
+ put(vname_map_simple1, add_vertex(graph_simple1), 1);
+ put(vname_map_simple1, add_vertex(graph_simple1), 2);
+ put(vname_map_simple1, add_vertex(graph_simple1), 3);
+
+ add_edge(0, 1, graph_simple1);
+ add_edge(0, 2, graph_simple1);
+ add_edge(1, 2, graph_simple1);
+
+ put(vname_map_simple2, add_vertex(graph_simple2), 1);
+ put(vname_map_simple2, add_vertex(graph_simple2), 2);
+ put(vname_map_simple2, add_vertex(graph_simple2), 3);
+ put(vname_map_simple2, add_vertex(graph_simple2), 4);
+
+ add_edge(0, 1, graph_simple2);
+ add_edge(0, 2, graph_simple2);
+ add_edge(1, 2, graph_simple2);
+ add_edge(1, 3, graph_simple2);
+
+ // Unique subgraphs
+ std::cout << "Searching for unique subgraphs" << std::endl;
+ mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2,
+ true, user_callback_simple,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1,
vname_map_simple2)));
+
+ BOOST_CHECK(has_subgraph_string("0,0 1,1 "));
+ BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+ BOOST_CHECK(has_subgraph_string("0,0 2,2 "));
+ BOOST_CHECK(has_subgraph_string("1,1 2,2 "));
+
+ if (output_graphs) {
+ std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+ std::ostream_iterator<std::string>(std::cout, "\n"));
+
+ std::cout << std::endl;
+ }
+
+ simple_subgraph_list.clear();
+
+ // Maximum subgraphs
+ std::cout << "Searching for maximum subgraphs" << std::endl;
+ mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2,
+ true, user_callback_simple,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1,
vname_map_simple2)));
+
+ BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+
+ if (output_graphs) {
+ std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+ std::ostream_iterator<std::string>(std::cout, "\n"));
+
+ std::cout << std::endl;
+ }
+
+ simple_subgraph_list.clear();
+
+ // Maximum, unique subgraphs
+ std::cout << "Searching for maximum unique subgraphs" << std::endl;
+ mcgregor_common_subgraphs_maximum_unique(graph_simple1, graph_simple2,
+ true, user_callback_simple,
+ vertices_equivalent(make_property_map_equivalent(vname_map_simple1,
vname_map_simple2)));
+
+ BOOST_CHECK(simple_subgraph_list.size() == 1);
+ BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+
+ if (output_graphs) {
+ std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+ std::ostream_iterator<std::string>(std::cout, "\n"));
+
+ std::cout << std::endl;
+ }
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/mean_geodesic.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,142 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
+
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/geodesic_distance.hpp>
+
+using namespace std;
+using namespace boost;
+
+// useful types
+// number of vertices in the graph
+static const unsigned N = 5;
+
+template <typename Graph>
+struct vertex_vector
+{
+ typedef graph_traits<Graph> traits;
+ typedef vector<typename traits::vertex_descriptor> type;
+};
+
+template <typename Graph>
+void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // add vertices
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // add edges
+ add_edge(v[0], v[1], g);
+ add_edge(v[1], v[2], g);
+ add_edge(v[2], v[0], g);
+ add_edge(v[3], v[4], g);
+ add_edge(v[4], v[0], g);
+};
+
+
+template <typename Graph>
+void test_undirected()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, double> CentralityProperty;
+ typedef typename CentralityProperty::container_type
CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+ typedef constant_property_map<Edge, int> WeightMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ CentralityContainer centralities(num_vertices(g));
+ DistanceMatrix distances(num_vertices(g));
+
+ CentralityMap cm(centralities, g);
+ DistanceMatrixMap dm(distances, g);
+
+ WeightMap wm(1);
+
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+ double geo1 = all_mean_geodesics(g, dm, cm);
+ double geo2 = small_world_distance(g, cm);
+
+ BOOST_ASSERT(cm[v[0]] == double(5)/4);
+ BOOST_ASSERT(cm[v[1]] == double(7)/4);
+ BOOST_ASSERT(cm[v[2]] == double(7)/4);
+ BOOST_ASSERT(cm[v[3]] == double(9)/4);
+ BOOST_ASSERT(cm[v[4]] == double(6)/4);
+ BOOST_ASSERT(geo1 == double(34)/20);
+ BOOST_ASSERT(geo1 == geo2);
+}
+
+template <typename Graph>
+void test_directed()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, double> CentralityProperty;
+ typedef typename CentralityProperty::container_type
CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+ typedef constant_property_map<Edge, int> WeightMap;
+
+ Graph g;
+ vector<Vertex> v(N);
+ build_graph(g, v);
+
+ CentralityContainer centralities(num_vertices(g));
+ DistanceMatrix distances(num_vertices(g));
+
+ CentralityMap cm(centralities, g);
+ DistanceMatrixMap dm(distances, g);
+
+ WeightMap wm(1);
+
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+ double geo1 = all_mean_geodesics(g, dm, cm);
+ double geo2 = small_world_distance(g, cm);
+
+ double inf = numeric_values<double>::infinity();
+ BOOST_ASSERT(cm[v[0]] == inf);
+ BOOST_ASSERT(cm[v[1]] == inf);
+ BOOST_ASSERT(cm[v[2]] == inf);
+ BOOST_ASSERT(cm[v[3]] == double(10)/4);
+ BOOST_ASSERT(cm[v[4]] == inf);
+ BOOST_ASSERT(geo1 == inf);
+ BOOST_ASSERT(geo1 == geo2);
+}
+
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> Digraph;
+
+ test_undirected<Graph>();
+ test_directed<Digraph>();
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/metis_test.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,44 @@
+// Copyright (C) 2004-2008 The Trustees of Indiana University.
+
+// Use, modification and distribution is subject to 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)
+
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/metis.hpp>
+#include <fstream>
+
+#ifdef BOOST_NO_EXCEPTIONS
+void
+boost::throw_exception(std::exception const& ex)
+{
+ std::cout << ex.what() << std::endl;
+ abort();
+}
+#endif
+
+using namespace boost;
+
+/* An undirected graph with distance values stored on the vertices. */
+typedef adjacency_list<vecS, vecS, undirectedS,
+ property<vertex_distance_t, std::size_t> >
+ Graph;
+
+int main(int argc, char* argv[])
+{
+ // Parse command-line options
+ const char* filename = "weighted_graph.gr";
+ if (argc > 1) filename = argv[1];
+
+ // Open the METIS input file
+ std::ifstream in(filename);
+ assert (in.good());
+ graph::metis_reader reader(in);
+
+ // Load the graph using the default distribution
+ Graph g(reader.begin(), reader.end(),
+ reader.num_vertices());
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/metric_tsp_approx.graph Mon Sep 7 09:29:57 2009
@@ -0,0 +1,8 @@
+2,5
+2,3
+1,2
+4,5
+5,4
+4,3
+6,3
+3,1
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/read_propmap.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,30 @@
+// (C) Copyright 2009 Dmitry Bufistov, Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/adjacency_list.hpp>
+
+// Test contributed by Dmitry that validates a read-only property map bug
+// for bundled properties.
+// TODO: Integrate this into a testing framework.
+
+using namespace boost;
+
+struct EdgeProp
+{
+ double weight;
+};
+
+typedef adjacency_list<vecS, vecS, directedS, no_property, EdgeProp >
graph_t;
+int main()
+{
+ typedef property_map<graph_t, double EdgeProp::*>::type WeightMap;
+ typedef property_map<graph_t, double EdgeProp::*>::const_type
cWeightMap;
+ typedef graph_traits<graph_t>::edge_descriptor Edge;
+ function_requires<ReadablePropertyMapConcept<WeightMap, Edge> >();
+ function_requires<ReadablePropertyMapConcept<cWeightMap, Edge> >();
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/subgraph_bundled.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,140 @@
+// (C) Copyright Jeremy Siek 2004
+// (C) Copyright Andrew Sutton 2009
+// 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)
+
+#include <set>
+
+#include <boost/random/mersenne_twister.hpp>
+
+#if !defined(BOOST_NO_HASH)
+# define BOOST_NO_HASH
+#endif
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/subgraph.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/graph/graph_test.hpp>
+#include <boost/graph/iteration_macros.hpp>
+
+using namespace boost;
+
+struct node
+{
+ int color;
+};
+
+struct arc
+{
+ int weight;
+};
+typedef property<edge_index_t, std::size_t, arc> arc_prop;
+
+typedef adjacency_list<
+ vecS, vecS, bidirectionalS,
+ node, arc_prop
+> Graph;
+
+typedef subgraph<Graph> Subgraph;
+typedef graph_traits<Subgraph>::vertex_descriptor Vertex;
+typedef graph_traits<Subgraph>::edge_descriptor Edge;
+typedef graph_traits<Subgraph>::vertex_iterator VertexIter;
+typedef graph_traits<Subgraph>::edge_iterator EdgeIter;
+
+int test_main(int argc, char* argv[])
+{
+ mt19937 gen;
+ for (int t = 0; t < 100; t += 5) {
+ Subgraph g;
+ int N = t + 2;
+ std::vector<Vertex> vertex_set;
+ std::vector< std::pair<Vertex, Vertex> > edge_set;
+
+ generate_random_graph(g, N, N * 2, gen,
+ std::back_inserter(vertex_set),
+ std::back_inserter(edge_set));
+ graph_test< Subgraph > gt;
+
+ gt.test_incidence_graph(vertex_set, edge_set, g);
+ gt.test_bidirectional_graph(vertex_set, edge_set, g);
+ gt.test_adjacency_graph(vertex_set, edge_set, g);
+ gt.test_vertex_list_graph(vertex_set, g);
+ gt.test_edge_list_graph(vertex_set, edge_set, g);
+ gt.test_adjacency_matrix(vertex_set, edge_set, g);
+
+ std::vector<Vertex> sub_vertex_set;
+ std::vector<Vertex> sub_global_map;
+ std::vector<Vertex> global_sub_map(num_vertices(g));
+ std::vector< std::pair<Vertex, Vertex> > sub_edge_set;
+
+ Subgraph& g_s = g.create_subgraph();
+
+ const std::set<Vertex>::size_type Nsub = N/2;
+
+ // Collect a set of random vertices to put in the subgraph
+ std::set<Vertex> verts;
+ while (verts.size() < Nsub)
+ verts.insert(random_vertex(g, gen));
+
+ for (std::set<Vertex>::iterator it = verts.begin();
+ it != verts.end(); ++it) {
+ Vertex v_global = *it;
+ Vertex v = add_vertex(v_global, g_s);
+ sub_vertex_set.push_back(v);
+ sub_global_map.push_back(v_global);
+ global_sub_map[v_global] = v;
+ }
+
+ // compute induced edges
+ BGL_FORALL_EDGES(e, g, Subgraph)
+ if (container_contains(sub_global_map, source(e, g))
+ && container_contains(sub_global_map, target(e, g)))
+ sub_edge_set.push_back(std::make_pair(global_sub_map[source(e, g)],
+ global_sub_map[target(e,
g)]));
+
+ gt.test_incidence_graph(sub_vertex_set, sub_edge_set, g_s);
+ gt.test_bidirectional_graph(sub_vertex_set, sub_edge_set, g_s);
+ gt.test_adjacency_graph(sub_vertex_set, sub_edge_set, g_s);
+ gt.test_vertex_list_graph(sub_vertex_set, g_s);
+ gt.test_edge_list_graph(sub_vertex_set, sub_edge_set, g_s);
+ gt.test_adjacency_matrix(sub_vertex_set, sub_edge_set, g_s);
+
+ if (num_vertices(g_s) == 0)
+ return 0;
+
+ // Test property maps for vertices.
+ typedef property_map<Subgraph, int node::*>::type ColorMap;
+ ColorMap colors = get(&node::color, g_s);
+ for(std::pair<VertexIter, VertexIter> r = vertices(g_s); r.first !=
r.second; ++r.first)
+ colors[*r.first] = 0;
+
+ // Test property maps for edges.
+ typedef property_map<Subgraph, int arc::*>::type WeightMap;
+ WeightMap weights = get(&arc::weight, g_s);
+ for(std::pair<EdgeIter, EdgeIter> r = edges(g_s); r.first != r.second;
++r.first) {
+ weights[*r.first] = 12;
+ }
+
+ // A regression test: the copy constructor of subgraph did not
+ // copy one of the members, so local_edge->global_edge mapping
+ // was broken.
+ {
+ Subgraph g;
+ graph_traits<Graph>::vertex_descriptor v1, v2;
+ v1 = add_vertex(g);
+ v2 = add_vertex(g);
+ add_edge(v1, v2, g);
+
+ Subgraph sub = g.create_subgraph(vertices(g).first,
vertices(g).second);
+
+ graph_traits<Graph>::edge_iterator ei, ee;
+ for (tie(ei, ee) = edges(sub); ei != ee; ++ei) {
+ // This used to segfault.
+ get(edge_weight, sub, *ei);
+ }
+ }
+
+ }
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/subgraph_props.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,136 @@
+// (C) Copyright Andrew Sutton 2009
+// 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)
+
+#include <iostream>
+
+#if !defined(BOOST_NO_HASH)
+# define BOOST_NO_HASH
+#endif
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/subgraph.hpp>
+#include "typestr.hpp"
+
+using namespace boost;
+
+struct TestProps {
+ typedef property<vertex_name_t, std::size_t> VertexProp;
+ typedef property<edge_name_t, std::size_t> EdgeName;
+ typedef property<edge_index_t, std::size_t, EdgeName> EdgeProp;
+
+ typedef adjacency_list<
+ vecS, vecS, bidirectionalS, VertexProp, EdgeProp
+ > Graph;
+
+ typedef subgraph<Graph> Subgraph;
+ typedef graph_traits<Subgraph>::vertex_descriptor Vertex;
+ typedef graph_traits<Subgraph>::edge_descriptor Edge;
+ typedef graph_traits<Subgraph>::vertex_iterator VertexIter;
+ typedef std::pair<VertexIter, VertexIter> VertexRange;
+
+ static void run() {
+ // Create a graph with some vertices.
+ Subgraph g(5);
+ VertexRange r = vertices(g);
+
+ // Create a child subgraph and add some vertices.
+ Subgraph& sg = g.create_subgraph();
+ Vertex v = add_vertex(*r.first, sg);
+
+ typedef property_map<Subgraph, vertex_name_t>::type DefaultMap;
+ DefaultMap map = get(vertex_name, g);
+ BOOST_ASSERT(get(map, v) == 0);
+ put(map, v, 5);
+ BOOST_ASSERT(get(map, v) == 5);
+
+ typedef global_property<vertex_name_t> GlobalProp;
+ typedef property_map<Subgraph, GlobalProp>::type GlobalVertMap;
+ GlobalVertMap groot = get(global(vertex_name), g);
+ GlobalVertMap gsub = get(global(vertex_name), sg);
+ BOOST_ASSERT(get(groot, v) == 5);
+ BOOST_ASSERT(get(gsub, v) == 5);
+ put(gsub, v, 10);
+ BOOST_ASSERT(get(groot, v) == 10);
+ BOOST_ASSERT(get(gsub, v) == 10);
+ BOOST_ASSERT(get(map, v) == 10);
+
+ typedef local_property<vertex_name_t> LocalProp;
+ typedef property_map<Subgraph, LocalProp>::type LocalVertMap;
+ LocalVertMap lroot = get(local(vertex_name), g); // Actually
global!
+ LocalVertMap lsub = get(local(vertex_name), sg);
+ BOOST_ASSERT(get(lroot, v) == 10); // Recall it's 10 from above!
+ BOOST_ASSERT(get(lsub, v) == 0);
+ put(lsub, v, 5);
+ BOOST_ASSERT(get(lsub, v) == 5);
+ BOOST_ASSERT(get(lroot, v) == 10); // Don't change the root prop
+ BOOST_ASSERT(get(map, v) == 10); // Don't change the root prop
+
+// typedef detail::subgraph_local_pmap::bind_<LocalProp, Subgraph,
void> PM;
+// std::cout << typestr<PM::TagType>() << "\n";
+// std::cout << typestr<PM::PMap>() << "\n";
+ }
+};
+
+struct TestBundles {
+ struct Node {
+ Node() : value(-1) { }
+ int value;
+ };
+ struct Arc {
+ Arc() : value(-1) { }
+ int value;
+ };
+ typedef property<edge_index_t, std::size_t, Arc> EdgeProp;
+
+ typedef adjacency_list<
+ vecS, vecS, bidirectionalS, Node, EdgeProp
+ > Graph;
+
+ typedef subgraph<Graph> Subgraph;
+ typedef graph_traits<Subgraph>::vertex_descriptor Vertex;
+ typedef graph_traits<Subgraph>::edge_descriptor Edge;
+ typedef graph_traits<Subgraph>::vertex_iterator VertexIter;
+ typedef std::pair<VertexIter, VertexIter> VertexRange;
+
+ static void run() {
+ // Create a graph with some vertices.
+ Subgraph g(5);
+ VertexRange r = vertices(g);
+
+ // Create a child subgraph and add some vertices.
+ Subgraph& sg = g.create_subgraph();
+ Vertex v = add_vertex(*r.first, sg);
+
+ sg[v].value = 1;
+ BOOST_ASSERT(sg[v].value == 1);
+ BOOST_ASSERT(sg[global(v)].value == 1);
+ BOOST_ASSERT(sg[local(v)].value == -1);
+
+ sg[local(v)].value = 5;
+ BOOST_ASSERT(sg[local(v)].value == 5);
+ BOOST_ASSERT(sg[global(v)].value == 1);
+ BOOST_ASSERT(sg[v].value == 1);
+
+ typedef property_map<
+ Subgraph, local_property<int Node::*>
+ >::type LocalVertMap;
+ LocalVertMap lvm = get(local(&Node::value), sg);
+ BOOST_ASSERT(get(lvm, v) == 5);
+
+ typedef property_map<
+ Subgraph, global_property<int Node::*>
+ >::type GlobalVertMap;
+ GlobalVertMap gvm = get(global(&Node::value), sg);
+ BOOST_ASSERT(get(gvm, v) == 1);
+ }
+};
+
+int main(int argc, char* argv[])
+{
+ TestProps::run();
+ TestBundles::run();
+
+ return 0;
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/test_construction.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,128 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef TEST_CONSTRUCTION_HPP
+#define TEST_CONSTRUCTION_HPP
+
+#include <utility>
+
+/** @name Build Graph
+ * Build the standard graph structure used in the remaining tests.
Depending
+ * on the mutability traits of the graph G, this may or may not add N
vertices
+ * to graph. The Add and Label type parameters are used to dispatch a build
+ * method for normal or labeled graphs.
+ */
+//@{
+// This will basically catch adjacency matrices, which don't get built.
+template <typename Graph, typename Add, typename Label>
+void build_graph(Graph& g, Add, Label)
+{ }
+
+// This matches MutableGraph, so just add some vertices.
+template <typename Graph>
+void build_graph(Graph& g, boost::mpl::true_, boost::mpl::false_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
+ BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept<Graph>));
+
+ std::cout << "...build_normal\n";
+ for(std::size_t i = 0; i < N; ++i) {
+ add_vertex(g);
+ }
+ BOOST_ASSERT(num_vertices(g) == N);
+}
+
+// This will match labeled graphs.
+template <typename Graph>
+void build_graph(Graph& g, boost::mpl::false_, boost::mpl::true_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
+ // BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept<Graph>));
+
+ std::cout << "...build_labeled\n";
+ // Add each vertex labeled with the number i.
+ for(std::size_t i = 0; i < N; ++i) {
+ add_vertex(i, g);
+ }
+ BOOST_ASSERT(num_vertices(g) == N);
+}
+//@}
+
+/** @name Build Mutable
+ * For mutable property graphs, try to add a vertex with a property. This
test
+ * actually builds a new graph - or at least tries to. We're not testing
for
+ * labeled graphs since that's actually done in build_graph above.
+ */
+//@{
+template <typename Graph, typename Add, typename Label>
+void build_property_graph(Graph const& g, Add, Label)
+{ }
+
+template <typename Graph>
+void build_property_graph(Graph const& g, boost::mpl::true_,
boost::mpl::false_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((VertexMutablePropertyGraphConcept<Graph>));
+ typedef typename vertex_property<Graph>::type VertexProp;
+
+ std::cout << "...build mutable\n";
+
+ // Start with clean graph. Nothing really to assert. Just make sure it
+ // copmpiles.
+ Graph h;
+ add_vertex(VertexProp(), h);
+}
+//@}
+
+
+/** @name Connect Graph
+ * Given a constructed graph, connect the edges to create a the standard
+ * testing graph. To facilitate ease of use, we pass a vector of vertices
+ * along with the graph such that v[0] -> *vertices(g).first, etc. The
+ * Labeled type parameter is used to dispatch connection techniques for
+ * normal or labled graphs.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::false_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept<Graph>));
+ BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<Graph>));
+
+ std::cout << "...connect_normal\n";
+ Pair *f, *l;
+ for(tie(f, l) = edge_pairs(); f != l; ++f) {
+ Pair const& e = *f;
+ add_edge(verts[e.first], verts[e.second], g);
+ }
+
+ // Is the lollipop connected? Is the lollipop not connected to the
roof?
+ BOOST_ASSERT(edge(verts[5], verts[3], g).second == true);
+ BOOST_ASSERT(edge(verts[5], verts[0], g).second == false);
+}
+
+template <typename Graph, typename VertexSet>
+void connect_graph(Graph& g, VertexSet const& verts, boost::mpl::true_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept<Graph>));
+ // BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<Graph>));
+
+ std::cout << "...connect_labeled\n";
+ // With labeled graphs, we want to operate directly on the edge numbers
+ // rather than looking up the correct vertex index. This is because the
+ // vertices are already mapped to indices.
+ Pair* p = edge_pairs().first;
+ for(std::size_t i = 0; i < M; ++i) {
+ Pair const& e = p[i];
+ add_edge_by_label(e.first, e.second, g);
+ }
+
+ // Is the lollipop connected?
+ BOOST_ASSERT(edge_by_label(5, 3, g).second == true);
+ BOOST_ASSERT(edge_by_label(5, 0, g).second == false);
+}
+//@}
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/test_destruction.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,114 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef TEST_DESTRUCTION_HPP
+#define TEST_DESTRUCTION_HPP
+
+#include <utility>
+
+/** @name Destroy Graph
+ * Destroy the graph by removing vertices (if possible).
+ */
+//@{
+// This will basically catch adjacency matrices, which don't get torn down.
+template <typename Graph, typename VertexSet, typename Remove, typename
Label>
+void destroy_graph(Graph& g, VertexSet const& verts, Remove, Label)
+{ }
+
+// This matches MutableGraph, so just remove a vertex and then clear.
+template <typename Graph, typename VertexSet>
+void destroy_graph(Graph& g, VertexSet const& verts, boost::mpl::true_,
boost::mpl::false_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
+ BOOST_CONCEPT_ASSERT((VertexMutableGraphConcept<Graph>));
+
+ std::cout << "...destroy_normal\n";
+ // Remove the roof vertex
+ remove_vertex(verts[0], g);
+ BOOST_ASSERT(num_vertices(g) == N - 1);
+}
+
+// This will match labeled graphs.
+template <typename Graph, typename VertexSet>
+void destroy_graph(Graph& g, VertexSet const& verts, boost::mpl::false_,
boost::mpl::true_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
+ // function_requires< VeretexMutableGraphConcept<Graph> >();
+
+ std::cout << "...destroy_labeled\n";
+ // Remove the roof vertex
+ remove_vertex(0, g);
+ BOOST_ASSERT(num_vertices(g) == N - 1);
+}
+//@}
+
+
+/** @name Disconnect Graph
+ * Disconnect edges in the graph. Note that this doesn't fully disconnect
the
+ * graph. It simply determines if we can disconnect an edge or two and
verify
+ * that the resulting graph is valid. The Labeled type parameter is used to
+ * dispatch for unlabeled and labeled graphs.
+ *
+ * @todo This doesn't quite work for multigraphs...
+ */
+//@{
+
+template <typename Graph, typename VertexSet>
+void disconnect_graph(Graph& g, VertexSet const& verts,
boost::mpl::false_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((EdgeListGraphConcept<Graph>));
+ BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<Graph>));
+
+ std::cout << "...disconnect_normal\n";
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ // Disconnect the "lollipop" from the house.
+ Edge e = edge(verts[5], verts[3], g).first;
+ remove_edge(e, g);
+ BOOST_ASSERT(num_edges(g) == M - 1);
+
+ // Remove the "floor" edge from the house.
+ remove_edge(verts[3], verts[2], g);
+ BOOST_ASSERT(num_edges(g) == M - 2);
+
+ // Fully disconnect the roof vertex.
+ clear_vertex(verts[0], g);
+ BOOST_ASSERT(num_edges(g) == M - 4);
+
+ // What happens if we try to remove an edge that doesn't exist?
+ remove_edge(verts[5], verts[0], g);
+ BOOST_ASSERT(num_edges(g) == M - 4);
+}
+
+template <typename Graph, typename VertexSet>
+void disconnect_graph(Graph& g, VertexSet const& verts, boost::mpl::true_)
{
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((EdgeListGraphConcept<Graph>));
+ // BOOST_CONCEPT_ASSERT((EdgeMutableGraphConcept<Graph>));
+
+ std::cout << "...disconnect_labeled\n";
+ typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
+
+ // Disconnect the "lollipop" from the house.
+ Edge e = boost::edge_by_label(5, 3, g).first;
+ boost::remove_edge(e, g);
+ BOOST_ASSERT(boost::num_edges(g) == M - 1);
+
+ // Remove the "floor" edge from the house.
+ boost::remove_edge_by_label(3, 2, g);
+ BOOST_ASSERT(boost::num_edges(g) == M - 2);
+
+ // Fully disconnect the roof vertex.
+ clear_vertex_by_label(0, g);
+ BOOST_ASSERT(boost::num_edges(g) == M - 4);
+
+ // What happens if we try to remove an edge that doesn't exist?
+ boost::remove_edge_by_label(5, 0, g);
+ BOOST_ASSERT(boost::num_edges(g) == M - 4);
+}
+//@}
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/test_direction.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,129 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef TEST_DIRECTION_HPP
+#define TEST_DIRECTION_HPP
+
+#include <algorithm>
+#include <boost/range.hpp>
+
+/** @name Test Out-Directed Graph
+ * Test all graphs that have directed out edges.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_outdirected_graph(Graph const& g, VertexSet const& verts,
boost::mpl::true_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<Graph>));
+
+ std::cout << "...test_outdirected_graph\n";
+ typedef typename graph_traits<Graph>::out_edge_iterator OutIter;
+ typedef std::pair<OutIter, OutIter> OutRange;
+ typedef std::vector<OutRange> OutSet;
+
+ // Collect all of the out edge ranges from the graph.
+ OutSet outs(verts.size());
+ for(size_t i = 0; i < verts.size(); ++i) {
+ outs[i] = out_edges(verts[i], g);
+ }
+
+ BOOST_ASSERT(distance(outs[0]) == 0);
+ BOOST_ASSERT(distance(outs[1]) == 1);
+ BOOST_ASSERT(distance(outs[2]) == 1);
+ BOOST_ASSERT(distance(outs[3]) == 2);
+ BOOST_ASSERT(distance(outs[4]) == 2);
+ BOOST_ASSERT(distance(outs[5]) == 1);
+
+ // Verify that the edges are actually correct.
+ // TODO: Find a better way of testing connectivity with multiple edges.
+ BOOST_ASSERT(has_target(g, *outs[1].first, verts[0]));
+ BOOST_ASSERT(has_target(g, *outs[2].first, verts[1]));
+ // BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
+ // BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
+ // BOOST_ASSERT(has_target(g, *outs[3].first++, verts[4]));
+ // BOOST_ASSERT(has_target(g, *outs[3].first, verts[2]));
+ BOOST_ASSERT(has_target(g, *outs[5].first, verts[3]));
+}
+
+template <typename Graph, typename VertexSet>
+void test_outdirected_graph(Graph const& g, VertexSet const& verts,
boost::mpl::false_)
+{ }
+//@}
+
+/** @name Test In-Directed Graph
+ * Test all graphs that support in-directed edges.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_indirected_graph(Graph const& g, VertexSet const& verts,
boost::mpl::true_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept<Graph>));
+
+ std::cout << "...test_indirected_graph\n";
+ typedef typename graph_traits<Graph>::in_edge_iterator InIter;
+ typedef std::pair<InIter, InIter> InRange;
+ typedef std::vector<InRange> InSet;
+
+ // Collect all of the in edges from the graph.
+ InSet ins(verts.size());
+ for(size_t i = 0; i < verts.size(); ++i) {
+ ins[i] = in_edges(verts[i], g);
+ }
+
+ BOOST_ASSERT(distance(ins[0]) == 2);
+ BOOST_ASSERT(distance(ins[1]) == 2);
+ BOOST_ASSERT(distance(ins[2]) == 1);
+ BOOST_ASSERT(distance(ins[3]) == 1);
+ BOOST_ASSERT(distance(ins[4]) == 1);
+ BOOST_ASSERT(distance(ins[5]) == 0);
+
+ // Verify that the connected edges are correct.
+ // TODO: Find a better way of testing connectivity with multiple edges.
+ BOOST_ASSERT(has_source(g, *ins[2].first, verts[3]));
+ BOOST_ASSERT(has_source(g, *ins[3].first, verts[5]));
+ BOOST_ASSERT(has_source(g, *ins[4].first, verts[3]));
+}
+
+template <typename Graph, typename VertexSet>
+void test_indirected_graph(Graph const& g, VertexSet const& verts,
boost::mpl::false_)
+{ }
+//@}
+
+/** @name Undirected Graphs
+ * Test all graphs that have undirected edges.
+ */
+template <typename Graph, typename VertexSet>
+void test_undirected_graph(Graph const& g, VertexSet const& verts,
boost::mpl::true_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<Graph>));
+
+ std::cout << "...test_undirected_graph\n";
+ typedef typename graph_traits<Graph>::out_edge_iterator OutIter;
+ typedef std::pair<OutIter, OutIter> OutRange;
+ typedef std::vector<OutRange> OutSet;
+
+ // The set of out edges is the same as the set of incident edges.
+ OutSet outs(verts.size());
+ for(size_t i = 0; i < verts.size(); ++i) {
+ outs[i] = out_edges(verts[i], g);
+ }
+
+ // TODO: Actually test the end connections to ensure that these are
+ // definitely correct.
+ BOOST_ASSERT(distance(outs[0]) == 2);
+ BOOST_ASSERT(distance(outs[1]) == 3);
+ BOOST_ASSERT(distance(outs[2]) == 2);
+ BOOST_ASSERT(distance(outs[3]) == 3);
+ BOOST_ASSERT(distance(outs[4]) == 3);
+ BOOST_ASSERT(distance(outs[5]) == 1);
+}
+
+template <typename Graph, typename VertexSet>
+void test_undirected_graph(Graph const& g, VertexSet const& verts,
boost::mpl::false_)
+{ }
+//@}
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/test_graph.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,138 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef TEST_GRAPH_HPP
+#define TEST_GRAPH_HPP
+
+/** @file test_graph.hpp
+ * This file houses the generic graph testing framework, which is
essentially
+ * run using the test_graph function. This function is called, passing a
+ * graph object that be constructed and exercised according to the concepts
+ * that the graph models. This test is extensively metaprogrammed in order
to
+ * differentiate testable features of graph instances.
+ */
+
+#include "typestr.hpp"
+
+#include <utility>
+#include <vector>
+#include <boost/assert.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_mutability_traits.hpp>
+#include <boost/graph/labeled_graph.hpp>
+
+#define BOOST_META_ASSERT(x) BOOST_ASSERT(x::value)
+
+typedef std::pair<std::size_t, std::size_t> Pair;
+
+static const std::size_t N = 6;
+static const std::size_t M = 7;
+
+// A helper function that globally defines the graph being constructed.
Note
+// that this graph shown here: http://en.wikipedia.org/wiki/Graph_theory.
+std::pair<Pair*, Pair*> edge_pairs() {
+ static Pair pairs[] = {
+ Pair(5, 3), Pair(3, 4), Pair(3, 2), Pair(4, 0), Pair(4, 1),
+ Pair(2, 1), Pair(1, 0)
+ };
+ Pair* f = &pairs[0];
+ Pair* l = f + M;
+ return std::make_pair(f, l);
+}
+
+// Return true if the vertex v is the target of the edge e.
+template <typename Graph, typename Edge, typename Vertex>
+bool has_target(Graph const& g, Edge e, Vertex v)
+{ return boost::target(e, g) == v; }
+
+// Return true if the vertex v is the source of the edge e.
+template <typename Graph, typename Edge, typename Vertex>
+bool has_source(Graph const& g, Edge e, Vertex v)
+{ return boost::source(e, g) == v; }
+
+/** @name Property Bundles
+ * Support testing with bundled properties. Note that the vertex bundle and
+ * edge bundle MAY NOT be the same if you want to use the property map type
+ * generator to define property maps.
+ */
+//@{
+struct VertexBundle {
+ VertexBundle() : value() { }
+ VertexBundle(int n) : value(n) { }
+
+ bool operator==(VertexBundle const& x) const { return value ==
x.value; }
+ bool operator<(VertexBundle const& x) const { return value < x.value; }
+
+ int value;
+};
+
+struct EdgeBundle {
+ EdgeBundle() : value() { }
+ EdgeBundle(int n) : value(n) { }
+
+ bool operator==(EdgeBundle const& x) const { return value == x.value; }
+ bool operator<(EdgeBundle const& x) const { return value < x.value; }
+
+ int value;
+};
+//@}
+
+#include "test_construction.hpp"
+#include "test_destruction.hpp"
+#include "test_iteration.hpp"
+#include "test_direction.hpp"
+#include "test_properties.hpp"
+
+template <typename Graph>
+void test_graph(Graph& g) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((GraphConcept<Graph>));
+
+ std::cout << typestr(g) << "\n";
+
+ // Define a bunch of tags for the graph.
+ typename graph_has_add_vertex<Graph>::type can_add_vertex;
+ typename graph_has_remove_vertex<Graph>::type can_remove_vertex;
+ typename is_labeled_graph<Graph>::type is_labeled;
+ typename is_directed_unidirectional_graph<Graph>::type is_directed;
+ typename is_directed_bidirectional_graph<Graph>::type is_bidirectional;
+ typename is_undirected_graph<Graph>::type is_undirected;
+
+ // Test constrution and vertex list.
+ build_graph(g, can_add_vertex, is_labeled);
+ build_property_graph(g, can_add_vertex, is_labeled);
+ test_vertex_list_graph(g);
+
+ // Collect the vertices for an easy method of "naming" them.
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ std::vector<Vertex> verts;
+ std::pair<VertexIterator, VertexIterator> rng = vertices(g);
+ for( ; rng.first != rng.second; ++rng.first) {
+ verts.push_back(*rng.first);
+ }
+
+ // Test connection and edge list
+ connect_graph(g, verts, is_labeled);
+// connect_property_graph(g, verts, is_labeld);
+ test_edge_list_graph(g);
+
+ // Test properties
+ test_properties(g, verts);
+
+ // Test directionality.
+ test_outdirected_graph(g, verts, is_directed);
+ test_indirected_graph(g, verts, is_bidirectional);
+ test_undirected_graph(g, verts, is_undirected);
+
+ // Test disconnection
+ disconnect_graph(g, verts, is_labeled);
+ destroy_graph(g, verts, can_remove_vertex, is_labeled);
+}
+
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/test_graphs.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,155 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#define BOOST_NO_HASH
+
+#include "typestr.hpp"
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/adjacency_matrix.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/labeled_graph.hpp>
+#include <boost/graph/subgraph.hpp>
+
+#include "test_graph.hpp"
+
+// This test module is a testing ground to determine if graphs and graph
+// adaptors actually implement the graph concepts correctly.
+
+using namespace boost;
+
+int main()
+{
+ // Bootstrap all of the tests by declaring a kind graph and asserting
some
+ // basic properties about it.
+ {
+ typedef undirected_graph<VertexBundle, EdgeBundle> Graph;
+ BOOST_META_ASSERT(is_undirected_graph<Graph>);
+ BOOST_META_ASSERT(is_multigraph<Graph>);
+ BOOST_META_ASSERT(is_incidence_graph<Graph>);
+ BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(has_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_edge_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_mutable_graph<Graph>);
+ BOOST_META_ASSERT(is_mutable_property_graph<Graph>);
+ Graph g;
+ test_graph(g);
+ }
+ {
+ typedef directed_graph<VertexBundle, EdgeBundle> Graph;
+ BOOST_META_ASSERT(is_directed_graph<Graph>);
+ BOOST_META_ASSERT(is_multigraph<Graph>);
+ BOOST_META_ASSERT(is_incidence_graph<Graph>);
+ BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(has_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_edge_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_mutable_graph<Graph>);
+ BOOST_META_ASSERT(is_mutable_property_graph<Graph>);
+ Graph g;
+ test_graph(g);
+ }
+ {
+ typedef adjacency_list<vecS, vecS, undirectedS, VertexBundle,
EdgeBundle> Graph;
+ BOOST_META_ASSERT(is_undirected_graph<Graph>);
+ BOOST_META_ASSERT(is_multigraph<Graph>);
+ BOOST_META_ASSERT(is_incidence_graph<Graph>);
+ BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(has_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_edge_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_add_only_property_graph<Graph>);
+ Graph g;
+ test_graph(g);
+ }
+ {
+ typedef adjacency_list<vecS, vecS, directedS, VertexBundle,
EdgeBundle> Graph;
+ Graph g;
+ BOOST_META_ASSERT(is_directed_graph<Graph>);
+ BOOST_META_ASSERT(is_multigraph<Graph>);
+ BOOST_META_ASSERT(is_incidence_graph<Graph>);
+ BOOST_META_ASSERT(!is_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(is_directed_unidirectional_graph<Graph>);
+ BOOST_META_ASSERT(has_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_edge_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_add_only_property_graph<Graph>);
+ test_graph(g);
+ }
+ {
+ // Common bidi adjlist
+ typedef adjacency_list<vecS, vecS, bidirectionalS, VertexBundle,
EdgeBundle> Graph;
+ BOOST_META_ASSERT(is_directed_graph<Graph>);
+ BOOST_META_ASSERT(is_multigraph<Graph>);
+ BOOST_META_ASSERT(is_incidence_graph<Graph>);
+ BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(has_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_edge_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_add_only_property_graph<Graph>);
+ Graph g;
+ test_graph(g);
+ }
+ {
+ // Same as above, but testing VL==listS
+ typedef adjacency_list<vecS, listS, bidirectionalS, VertexBundle,
EdgeBundle> Graph;
+ BOOST_META_ASSERT(is_directed_graph<Graph>);
+ BOOST_META_ASSERT(is_multigraph<Graph>);
+ BOOST_META_ASSERT(is_incidence_graph<Graph>);
+ BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(has_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_edge_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_mutable_property_graph<Graph>);
+ Graph g;
+ test_graph(g);
+ }
+ {
+ // TODO: What other kinds of graphs do we have here...
+ typedef adjacency_matrix<directedS, VertexBundle, EdgeBundle>
Graph;
+ BOOST_META_ASSERT(is_directed_graph<Graph>);
+ BOOST_META_ASSERT(!is_multigraph<Graph>);
+ BOOST_META_ASSERT(has_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(has_edge_property<Graph>);
+ BOOST_META_ASSERT(has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_mutable_edge_graph<Graph>);
+ BOOST_META_ASSERT(is_mutable_edge_property_graph<Graph>);
+ Graph g(N);
+ test_graph(g);
+ }
+ {
+ typedef labeled_graph<directed_graph<>, unsigned> Graph;
+ BOOST_META_ASSERT(is_directed_graph<Graph>);
+ BOOST_META_ASSERT(is_multigraph<Graph>);
+ BOOST_META_ASSERT(is_incidence_graph<Graph>);
+ BOOST_META_ASSERT(is_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(is_directed_bidirectional_graph<Graph>);
+ BOOST_META_ASSERT(is_labeled_mutable_property_graph<Graph>);
+ BOOST_META_ASSERT(is_labeled_graph<Graph>);
+ BOOST_META_ASSERT(!has_vertex_property<Graph>);
+ BOOST_META_ASSERT(!has_bundled_vertex_property<Graph>);
+ BOOST_META_ASSERT(!has_edge_property<Graph>);
+ BOOST_META_ASSERT(!has_bundled_edge_property<Graph>);
+ BOOST_META_ASSERT(is_labeled_mutable_graph<Graph>);
+ Graph g;
+ test_graph(g);
+ }
+}
+
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/test_iteration.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,54 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef TEST_ITERATION_HPP
+#define TEST_ITERATION_HPP
+
+#include <algorithm>
+
+/** @name Test Vertex List
+ * Test the vertex list interface. Note that there are currently no graphs
that
+ * do not expose this interface.
+ */
+//@{
+template <typename Graph>
+void test_vertex_list_graph(Graph const& g) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept<Graph>));
+
+ std::cout << "...test_vertex_list_graph\n";
+ typedef typename graph_traits<Graph>::vertex_iterator Iterator;
+ typedef std::pair<Iterator, Iterator> Range;
+
+ Range rng = vertices(g);
+ BOOST_ASSERT(num_vertices(g) == N);
+ BOOST_ASSERT(rng.first != rng.second);
+ BOOST_ASSERT(std::distance(rng.first, rng.second) == int(N));
+}
+//@}
+
+/** @name Test Edge List
+ * Test the edge list interface. Note that there are currently no graphs
that
+ * do not expose this interface.
+ */
+//@{
+template <typename Graph>
+void test_edge_list_graph(Graph const& g) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((EdgeListGraphConcept<Graph>));
+
+ std::cout << "...test_edge_list_graph\n";
+ typedef typename graph_traits<Graph>::edge_iterator Iterator;
+ typedef std::pair<Iterator, Iterator> Range;
+
+ Range rng = edges(g);
+ BOOST_ASSERT(num_edges(g) == M);
+ BOOST_ASSERT(rng.first != rng.second);
+ BOOST_ASSERT(std::distance(rng.first, rng.second) == int(M));
+}
+//@}
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/test_properties.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,101 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef TEST_PROPERTIES_HPP
+#define TEST_PROPERTIES_HPP
+
+/** @name Test Vertex Bundle
+ * Exercise the vertex bundle. Note that this is expected to be of type
+ * VertexBundle.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_vertex_bundle(Graph& g, VertexSet const& verts,
boost::mpl::true_) {
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((GraphConcept<Graph>));
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ BOOST_CONCEPT_ASSERT((PropertyGraphConcept<Graph, Vertex,
vertex_bundle_t>));
+
+ std::cout << "...test_vertex_bundle\n";
+
+ // Test bundling via the graph object on the lollipop vertex.
+ Vertex v = verts[5];
+ VertexBundle& b = g[v];
+ b.value = 10;
+ BOOST_ASSERT(g[v].value == 10);
+
+ // Test bundling via the property map.
+ typedef typename property_map<Graph, int VertexBundle::*>::type
BundleMap;
+ BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<BundleMap, Vertex>));
+ BundleMap map = get(&VertexBundle::value, g);
+ put(map, v, 5);
+ BOOST_ASSERT(get(map, v) == 5);
+
+ typedef typename property_map<Graph, int VertexBundle::*>::const_type
ConstBundleMap;
+ BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<ConstBundleMap,
Vertex>));
+ ConstBundleMap cmap = get(&VertexBundle::value, (Graph const&)g);
+ BOOST_ASSERT(get(cmap, v) == 5);
+}
+
+template <typename Graph, typename VertexSet>
+void test_vertex_bundle(Graph&, VertexSet const&, boost::mpl::false_)
+{ }
+//@}
+
+/** @name Test Edge Bundle
+ * Exercise the edge bundle. Note that this is expected to be of type
+ * EdgeBundle.
+ */
+//@{
+template <typename Graph, typename VertexSet>
+void test_edge_bundle(Graph& g, VertexSet const& verts, boost::mpl::true_)
{
+ using namespace boost;
+ BOOST_CONCEPT_ASSERT((GraphConcept<Graph>));
+ typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
+ BOOST_CONCEPT_ASSERT((PropertyGraphConcept<Graph, Edge,
edge_bundle_t>));
+
+ std::cout << "...test_edge_bundle\n";
+
+ // Test bundling via the graph object on the lollipop edge.
+ Edge e = boost::edge(verts[5], verts[3], g).first;
+ EdgeBundle& b = g[e];
+ b.value = 10;
+ BOOST_ASSERT(g[e].value == 10);
+
+ // Test bundling via the property map.
+ typedef typename boost::property_map<Graph, int EdgeBundle::*>::type
BundleMap;
+ BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<BundleMap, Edge>));
+ BundleMap map = get(&EdgeBundle::value, g);
+ put(map, e, 5);
+ BOOST_ASSERT(get(map, e) == 5);
+
+ typedef typename boost::property_map<Graph, int
EdgeBundle::*>::const_type ConstBundleMap;
+ BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<BundleMap, Edge>));
+ ConstBundleMap cmap = get(&EdgeBundle::value, (Graph const&)g);
+ BOOST_ASSERT(get(cmap, e) == 5);
+}
+
+template <typename Graph, typename VertexSet>
+void test_edge_bundle(Graph&, VertexSet const&, boost::mpl::false_)
+{ }
+//@}
+
+/**
+ * Test the properties of a graph. Basically, we expect these to be one of
+ * bundled or not. This test could also be expanded to test non-bundled
+ * properties. This just bootstraps the tests.
+ */
+template <typename Graph, typename VertexSet>
+void test_properties(Graph& g, VertexSet const& verts) {
+ typename boost::has_bundled_vertex_property<Graph>::type
vertex_bundled;
+ typename boost::has_bundled_edge_property<Graph>::type edge_bundled;
+
+ test_vertex_bundle(g, verts, vertex_bundled);
+ test_edge_bundle(g, verts, edge_bundled);
+}
+//@}
+
+#endif
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/tiernan_all_cycles.cpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,79 @@
+// (C) Copyright 2007-2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+
+#include <boost/random/linear_congruential.hpp>
+
+using namespace std;
+using namespace boost;
+
+struct cycle_validator
+{
+ cycle_validator(size_t& c)
+ : cycles(c)
+ { }
+
+ template <typename Path, typename Graph>
+ void cycle(const Path& p, const Graph& g)
+ {
+ ++cycles;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+ // Check to make sure that each of the vertices in the path
+ // is truly connected and that the back is connected to the
+ // front - it's not validating that we find all paths, just
+ // that the paths are valid.
+ typename Path::const_iterator i, j, last = prior(p.end());
+ for(i = p.begin(); i != last; ++i) {
+ j = boost::next(i);
+ BOOST_ASSERT(edge(*i, *j, g).second);
+ }
+ BOOST_ASSERT(edge(p.back(), p.front(), g).second);
+ }
+
+ size_t& cycles;
+};
+
+template <typename Graph>
+void test()
+{
+ typedef erdos_renyi_iterator<boost::minstd_rand, Graph> er;
+
+ // Generate random graphs with 15 vertices and 15% probability
+ // of edge connection.
+ static const size_t N = 20;
+ static const double P = 0.1;
+ boost::minstd_rand rng;
+
+ Graph g(er(rng, N, P), er(), N);
+ renumber_indices(g);
+ print_edges(g, get(vertex_index, g));
+
+ size_t cycles = 0;
+ cycle_validator vis(cycles);
+ tiernan_all_cycles(g, vis);
+ cout << "# cycles: " << vis.cycles << "\n";
+}
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> DiGraph;
+
+ std::cout << "*** undirected ***\n";
+ test<Graph>();
+
+ std::cout << "*** directed ***\n";
+ test<DiGraph>();
+}
=======================================
--- /dev/null
+++ /trunk/libs/graph/test/typestr.hpp Mon Sep 7 09:29:57 2009
@@ -0,0 +1,46 @@
+// (C) Copyright 2009 Andrew Sutton
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef ORIGIN_TYPESTR_HPP
+#define ORIGIN_TYPESTR_HPP
+
+#include <string>
+#include <cstring>
+#include <typeinfo>
+
+#if defined(__GNUC__)
+#include <cxxabi.h>
+#endif
+
+/**
+ * Return a string that describes the type of the given template parameter.
+ * The type name depends on the results of the typeid operator.
+ *
+ * @todo Rewrite this so that demangle will dynamically allocate the
memory.
+ */
+template <typename T>
+std::string typestr()
+{
+#if defined(__GNUC__)
+ std::size_t const BUFSIZE = 8192;
+ std::size_t n = BUFSIZE;
+ char buf[BUFSIZE];
+ abi::__cxa_demangle(typeid(T).name(), buf, &n, 0);
+ return std::string(buf, ::strlen(buf));
+#else
+ return typeid(T).name();
+#endif
+}
+
+/**
+ * Return a string that describes the type of the given parameter. The type
+ * name depends on the results of the typeid operator.
+ */
+template <typename T>
+inline std::string typestr(T const&)
+{ return typestr<T>(); }
+
+#endif
=======================================
***Additional files exist in this changeset.***
Other related posts:
- » [boost-doc-zh] r324 committed - 转换至1.40.0，第7批，完成以下库：... - codesite-noreply
