Ring Graph

wpm edited this page Sep 14, 2010 · 8 revisions
Clone this wiki locally

A ring graph is an undirected graph whose vertices are arranged in a ring so that each vertex has exactly two neighbors. Vertices in the ring graph are indexed by unsigned integer and arranged sequentially so that each vertex i is adjacent to i-1 for i>0 and i+1 for i<n-1. The first vertex is also adjacent to the last one. For example, here is a ring graph with five nodes.

Ring graph with five nodes

Edges are indexed by pairs of vertex indices. Each edge has a weight equal to the average of the indices of its endpoint vertices. For example, edge (2,3) has weight 2.5 and edge (0,4) has weight 2. A ring graph with two vertices has a single edge between them. A ring graph with one vertex contains a single self-loop.

Various aspects of the graph are modeled by the following classes:

Class Decription
ring_graph The graph class instantiated by a client. This defines types for the concepts that this graph models and keeps track of the number of vertices in the graph.
ring_incident_edge_iterator This is an iterator that ranges over edges incident on a given vertex. The behavior of this iterator defines the ring topology. Other iterators that make reference to the graph structure are defined in terms of this one.
edge_weight_map This defines a property map between edges and weights and calculates the weight for each edge.
boost::property_map<ring_graph,boost::edge_weight_t> This tells Boost to associate the edges of the ring graph with the edge weight map.

Along with these classes, the graph concepts are modeled by various valid expression functions. This example also defines a get(boost::vertex_index_t, const ring_graph&) function which is not part of a graph concept, but is used for Dijkstra search.

Apart from ring_graph, client code should not instantiate the model classes directly. Instead it should access them and their properties via graph_traits<...> and property_traits<...> lookups. For convenience, the example defines short names for all these properties that client code can use.

The main function is an example of how client code could use a ring graph. The concept checking code at the top of this function is there to demonstrate how concept checking works, and is not required for a working program.