Missing something about Boost.Graph
We have a graph of relational tables, with the foreign keys being the edges of the graph. We're using boost::topological_sort() to sort the graph, and have struggled in the past with Boost.Graph. Recently we had cycles appearing in our graph, so I'm revisiting this code, and I think I must be missing something fundamental about Boost.Graph, because I get what I consider incoherent results. Here are the relevant code snippets. typedef std::pair<std::size_t, std::size_t> IndexPair; std::vector<IndexPair> edges; // fill edges with pairs of integers, in range [0, 111] (at the moment) using namespace boost; typedef property<vertex_color_t, default_color_type> GraphProperty; typedef adjacency_list<vecS, vecS, directedS, GraphProperty> Graph; typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; Graph G(edges.begin(), edges.end(), edges.size()); size_t max_vrtx_index = 0; for (const auto& e : boost::make_iterator_range(boost::edges(G))) { size_t s = boost::source(e, G); size_t t = boost::target(e, G); max_vrtx_index = std::max(max_vrtx_index, s); max_vrtx_index = std::max(max_vrtx_index, t); } const auto G_vrtx_count = num_vertices(G); const auto G_edge_count = num_edges(G); if (G_vrtx_count != (max_vrtx_index + 1)) { std::cout << "Graph has " << G_vrtx_count << " vertices " "and " << G_edge_count << " edges, yet in reality " "our edges refer to at most " << max_vrtx_index << " vertices!" << std::endl; } This outputs: Graph has 1137 vertices and 1137 edges, yet in reality our edges refer to at most 111 vertices! How can num_vertices() and num_edges() return the same number? Why isn't num_vertices() returning 112 as I'd expect? I'm using 1.58. Thanks, --DD
________________________________ From: Dominique Devienne <ddevienne@gmail.com> To: boost-users <boost-users@lists.boost.org> Sent: Wednesday, October 28, 2015 2:52 AM Subject: [Boost-users] Missing something about Boost.Graph
We have a graph of relational tables, with the foreign keys being the edges of the graph. We're using boost::topological_sort() to sort the graph, and have struggled in the past with Boost.Graph.
Recently we had cycles appearing in our graph, so I'm revisiting this code, and I think I must be missing something fundamental about Boost.Graph, because I get what I consider incoherent results. Here are the relevant code snippets.
typedef std::pair<std::size_t, std::size_t> IndexPair; std::vector<IndexPair> edges;
// fill edges with pairs of integers, in range [0, 111] (at the moment)
using namespace boost; typedef property<vertex_color_t, default_color_type> GraphProperty; typedef adjacency_list<vecS, vecS, directedS, GraphProperty> Graph; typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
Graph G(edges.begin(), edges.end(), edges.size());
The third parameter to the constructor is the number of vertices, not the number of edges. If you want to give the edge count explicitly, that is placed as the fourth parameter, after the edge count. -- Jeremiah Willcock
On Wed, Oct 28, 2015 at 1:43 PM, Jeremiah Willcock <jewillco@yahoo.com> wrote:
From: Dominique Devienne <ddevienne@gmail.com> Graph G(edges.begin(), edges.end(), edges.size());
The third parameter to the constructor is the number of vertices, not the number of edges. If you want to give the edge count explicitly, that is placed as the fourth parameter, after the edge count.
Thanks a bunch Jeremiah. Silly mistake on my end... In the mean time (I'm on GMT+1), thanks to [1], I've completely changed the way I build the graph, working around the above mistake, and was able to make progress. I now get the much more sensical "Graph has 112 vertices and 1257 edges". But my graph is not a DAG. So thanks to [2] I found my back edges (4 of them). So next I tried to get a good report on the cycle using [3] and strong_components(), which yields these two questions: - Why do I get 106 strong components? Only 1 of them contains more than 1 vertex. All others have a single vertex. - In the 1 component with more than 1 vertex, which looks like my cycle, is there a way to know the edges of the cycle? Thanks, --DD [1] http://stackoverflow.com/questions/3100146 [2] http://www.boost.org/doc/libs/master/libs/graph/doc/file_dependency_example.... [3] http://www.boost.org/doc/libs/1_59_0/libs/graph/example/strong_components.cp...
participants (2)
-
Dominique Devienne
-
Jeremiah Willcock