如何在Boost图库中从边迭代器构造adjacency_list？

Hey there! Let's walk through how to correctly use that edge-iterator-based constructor for boost::adjacency_list you're working with. First, let's recap what each parameter does, then jump into a complete working example to make it concrete.

Parameter Breakdown #

Let's break down the constructor signature you mentioned:

template <class EdgeIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
               vertices_size_type n, edges_size_type m = 0,
               const GraphProperty& p = GraphProperty())

• first/last: Iterators defining a range of edge objects. These objects need to represent a pair of vertices (start and end), typically as std::pair<vertex_descriptor, vertex_descriptor> (or any type that can implicitly convert to this).
• n: Total number of vertices in the graph. Critical note: This value must be at least one greater than the highest vertex index used in your edges (since Boost's default vertex descriptors are 0-indexed integers).
• m: Optional estimate of the total number of edges, used to pre-allocate memory and optimize performance. Defaults to 0 if you don't specify it.
• p: Optional graph property object (like custom graph-level attributes). Uses the default constructor if omitted.

Complete Working Example #

Here's a straightforward implementation that uses this constructor correctly:

#include <boost/graph/adjacency_list.hpp>
#include <vector>
#include <iostream>

using namespace boost;

// Define our graph type: default is directed, integer vertices, no edge/vertex properties
using Graph = adjacency_list<>;

int main() {
    // Create a list of edges: each entry is (source vertex, target vertex)
    std::vector<std::pair<int, int>> edges = {
        {0, 1},
        {1, 2},
        {2, 0},
        {1, 3}
    };

    // Total vertices: our highest vertex index is 3, so we need 4 vertices (0-3)
    const int total_vertices = 4;

    // Initialize the graph using the edge iterator constructor
    Graph my_graph(edges.begin(), edges.end(), total_vertices);

    // Verify the graph was built correctly
    std::cout << "Total vertices in graph: " << num_vertices(my_graph) << "\n";
    std::cout << "Total edges in graph: " << num_edges(my_graph) << "\n";

    return 0;
}

Common Pitfalls to Avoid #

• Underestimating vertex count: If your edges include a vertex with index 5, you must set n to at least 6 (since vertices are 0-indexed). Setting a smaller value will lead to undefined behavior.
• Mismatched edge types: If your graph uses edge properties (like weights), your iterator range should point to objects that include those properties. For example, if you define a graph with weighted edges:

  using WeightedGraph = adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int>>;
  

  Your edges should be std::tuple<int, int, int> (source, target, weight) or a custom struct that can be converted to the edge type.
• Undirected graphs: If you're building an undirected graph (specify undirectedS as the third template parameter), you don't need to pass both (u,v) and (v,u) edges unless you want duplicate edges. The constructor will treat each edge as undirected automatically.

内容的提问来源于stack exchange，提问作者MaxPlankton