- Grasping Graph Theory
- Old and Famous Problems
- Graphs, Computers, and Popular Culture
- Constructing a Simple Graph with Boost
- Adding Values to Vertices and Edges
- Manipulating Property Values
- Adding Vertices and Edges
- Iterating Through the Edges and Vertices
- Solving Problems with Graphs and Boost
Adding Vertices and Edges
After you’ve specified your property types and defined the graph type, you’re ready to create an instance of the graph and add vertices and edges to the graph, along with values for the properties associated with the vertices and edges.
Let’s start with a fresh graph, define some properties, and then add the edges and vertices along with their properties. I’ll list all the code here so you don’t have to piece together the fragments I’ve given you so far.
// Property types typedef property<edge_weight_t, int> EdgeWeightProperty; typedef property<vertex_name_t, std::string, property<vertex_index2_t, int> > VertexProperties; // Graph type typedef adjacency_list<vecS, vecS, undirectedS, VertexProperties, EdgeWeightProperty> Graph; // Graph instance Graph g; // Property accessors property_map<Graph, vertex_name_t>::type city_name = get(vertex_name, g); property_map<Graph, vertex_index2_t>::type city_index2 = get(vertex_index2, g); property_map<Graph, edge_weight_t>::type edge_distance = get(edge_weight, g); // Create the vertices typedef graph_traits<Graph>::vertex_descriptor Vertex; Vertex u1; u1 = add_vertex(g); city_name[u1] = "Los Angeles"; city_index2[u1] = 3; Vertex u2; u2 = add_vertex(g); city_name[u2] = "Bakersfield"; city_index2[u2] = 2; Vertex u3; u3 = add_vertex(g); city_name[u3] = "New York"; city_index2[u3] = 1; // Create the edges typedef graph_traits<Graph>::edge_descriptor Edge; Edge e1; e1 = (add_edge(u1, u2, g)).first; edge_distance[e1] = 100; Edge e2; e2 = add_edge(u1, u3, g).first; edge_distance[e2] = 2500;
In the first section I define the property types, followed by the graph type. Then I create the instance, g, of the graph. Next, I obtain the property access objects that I talked about.
Then I start adding the vertices and edges. To add the vertices, I create my own type called Vertex from the vertex_descriptor, just to simplify the code a bit. I add the vertex by calling the helper function add_vertex, passing in g.
The graph adds the vertex and returns a vertex descriptor. Then I use the property access objects to assign the two properties for the vertex: city_name and city_index2. Setting the properties is easy; I just use the vertex as an index into the map by putting the vertex name in brackets ().
Creating the edges is similar, except that the add_edge function returns a pair type rather than an edge type. So I just grab the .first member of the pair to get the edge itself. I save that in a variable; then I use that variable as an index to set the properties. Since mathematically an edge is really nothing more than a set of two vertices, that’s all I have to pass to add_edge, along with the graph.