Home > Articles > Programming > C/C++

  • Print
  • + Share This
Like this article? We recommend

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.

  • + Share This
  • 🔖 Save To Your Account