Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>I made a couple minor changes to the example you pointed too. Specifically setting the 4th &amp; fifth template parameters on the adjacency_list to be the a type containing any additional vertex and edge properties. See docs here: <a href="http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/adjacency_list.html" rel="nofollow">http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/adjacency_list.html</a></p> <pre><code>struct point { int x; int y; int z; }; typedef adjacency_list &lt;vecS, vecS, undirectedS, point &gt; Graph; </code></pre> <p>After nodes &amp; vertices the additional point data can be set like this: </p> <pre><code>graph[0].x = 42; </code></pre> <p>And retrieved at the end after the components have been computed: </p> <pre><code>std::cout &lt;&lt; child_index &lt;&lt; " " &lt;&lt; "x=" &lt;&lt; graph[current_index].x &lt;&lt; " "; </code></pre> <p>Full code: </p> <pre><code>//======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2009 Trustees of Indiana University. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, 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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;boost/foreach.hpp&gt; #include &lt;boost/graph/adjacency_list.hpp&gt; #include &lt;boost/graph/graph_utility.hpp&gt; #include &lt;boost/graph/incremental_components.hpp&gt; #include &lt;boost/pending/disjoint_sets.hpp&gt; /* This example shows how to use the disjoint set data structure to compute the connected components of an undirected, changing graph. Sample output: An undirected graph: 0 &lt;--&gt; 1 4 1 &lt;--&gt; 0 4 2 &lt;--&gt; 5 3 &lt;--&gt; 4 &lt;--&gt; 1 0 5 &lt;--&gt; 2 representative[0] = 1 representative[1] = 1 representative[2] = 5 representative[3] = 3 representative[4] = 1 representative[5] = 5 component 0 contains: 4 1 0 component 1 contains: 3 component 2 contains: 5 2 */ using namespace boost; struct point { point() : x(0), y(0), z(0) {} int x; int y; int z; }; int main(int argc, char* argv[]) { typedef adjacency_list &lt;vecS, vecS, undirectedS, point &gt; Graph; typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex; typedef graph_traits&lt;Graph&gt;::vertices_size_type VertexIndex; const int VERTEX_COUNT = 6; Graph graph(VERTEX_COUNT); std::vector&lt;VertexIndex&gt; rank(num_vertices(graph)); std::vector&lt;Vertex&gt; parent(num_vertices(graph)); typedef VertexIndex* Rank; typedef Vertex* Parent; disjoint_sets&lt;Rank, Parent&gt; ds(&amp;rank[0], &amp;parent[0]); initialize_incremental_components(graph, ds); incremental_components(graph, ds); graph_traits&lt;Graph&gt;::edge_descriptor edge; bool flag; boost::tie(edge, flag) = add_edge(0, 1, graph); ds.union_set(0,1); boost::tie(edge, flag) = add_edge(1, 4, graph); ds.union_set(1,4); boost::tie(edge, flag) = add_edge(4, 0, graph); ds.union_set(4,0); boost::tie(edge, flag) = add_edge(2, 5, graph); ds.union_set(2,5); graph[0].x = 42; std::cout &lt;&lt; "An undirected graph:" &lt;&lt; std::endl; print_graph(graph, get(boost::vertex_index, graph)); std::cout &lt;&lt; std::endl; BOOST_FOREACH(Vertex current_vertex, vertices(graph)) { std::cout &lt;&lt; "representative[" &lt;&lt; current_vertex &lt;&lt; "] = " &lt;&lt; ds.find_set(current_vertex) &lt;&lt; std::endl; } std::cout &lt;&lt; std::endl; typedef component_index&lt;VertexIndex&gt; Components; // NOTE: Because we're using vecS for the graph type, we're // effectively using identity_property_map for a vertex index map. // If we were to use listS instead, the index map would need to be // explicitly passed to the component_index constructor. Components components(parent.begin(), parent.end()); // Iterate through the component indices BOOST_FOREACH(VertexIndex current_index, components) { std::cout &lt;&lt; "component " &lt;&lt; current_index &lt;&lt; " contains: "; // Iterate through the child vertex indices for [current_index] BOOST_FOREACH(VertexIndex child_index, components[current_index]) { std::cout &lt;&lt; child_index &lt;&lt; " {" &lt;&lt; graph[child_index].x &lt;&lt; "," &lt;&lt; graph[child_index].y &lt;&lt; "," &lt;&lt; graph[child_index].z &lt;&lt; "} "; } std::cout &lt;&lt; std::endl; } return (0); } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload