#include <vector>
#include <map>
#include <iostream>

#include <boost/next_prior.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace std;
using namespace boost;

struct Prop
{
    Prop() : index(-1) { }
    Prop(int x) : index(x) { }
    int index;
};

typedef adjacency_list<listS, listS, bidirectionalS, Prop> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::vertex_iterator VertexIterator;

template <typename Graph> void external_indices(Graph& g);
template <typename Graph> void internal_indices(Graph& g);

int main()
{
    Graph g;

    // Put some vertices in the graph.
    for(int i = 0; i < 1000; ++i) {
        Vertex v = add_vertex(g);
        g[v].index = i;
    }

    // Demonstrate an external vertex map.
    external_indices(g);

    // Demonstrate internal indices
    internal_indices(g);
}

template <typename Graph>
void external_indices(Graph& g)
{
    typedef map<Vertex, int> IndexContainer;
    typedef associative_property_map<IndexContainer> IndexMap;

    // Build an external mapping
    IndexContainer indices;
    IndexMap im(indices);
    VertexIterator i, end;
    int n = 0;
    for(tie(i, end) = vertices(g); i != end; ++i, ++n) {
        indices[*i] = n;
    }

    // Create a predecessor map over the indices.
    vector<Vertex> preds(num_vertices(g));

    // Set the predecessor of the first vertex to the second.
    preds[get(im, *vertices(g).first)] = *next(vertices(g).first);
}

template <typename Graph>
void internal_indices(Graph& g)
{
    typedef typename property_map<Graph, int Prop::*>::type IndexMap;

    // Build the property map over the Prop::index member.
    IndexMap im = get(&Prop::index, g);

    // Create a predecessor map over the indices.
    vector<Vertex> preds(num_vertices(g));

    // Set the predecessor of the first vertex to the second.
    preds[get(im, *vertices(g).first)] = *next(vertices(g).first);
}