How to view vertices/edges from boost graph list containers

Question

I'm trying to use listS as the vertex/edge container so that I can remove edges safely. However, I'm running into a problem - I don't know how to see my vertices or edges! When I try to iterate through them and print them out, it only prints out their address for some reason.

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <utility>

using namespace std;

typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits <Graph>::edge_iterator edgeIt;
typedef boost::graph_traits<Graph>::vertex_iterator vertexIt;
typedef map<vertex_t,size_t> IndexMap;

int main(int argc, const char * argv[]) {

    Graph g;

    IndexMap mapIndex;

    vertex_t v0 = boost::add_vertex(g);
    vertex_t v1 = boost::add_vertex(g);
    vertex_t v2 = boost::add_vertex(g);
    vertex_t v3 = boost::add_vertex(g);
    mapIndex[v0] = 0;
    mapIndex[v1] = 1;
    mapIndex[v2] = 2;
    mapIndex[v3] = 3;
    boost::add_edge(v0,v2,g);
    boost::add_edge(v1,v3,g);
    boost::add_edge(v1,v0,g);


    for(pair<vertexIt,vertexIt> vi = boost::vertices(g); vi.first != vi.second; ++vi.first) {
        cout << *vi.first << endl;
    }

    for(pair<edgeIt,edgeIt> ei = boost::edges(g); ei.first != ei.second; ++ei.first) {
        cout << source(*ei.first, g) << " -> " << target(*ei.first, g) << endl;
        cout << *ei.first << endl;
    }
}

The output is:

0x7f9409404b10
0x7f9409404b70
0x7f9409404c00
0x7f9409404c40
0x7f9409404b10 -> 0x7f9409404c00
(0x7f9409404b10,0x7f9409404c00)
0x7f9409404b70 -> 0x7f9409404c40
(0x7f9409404b70,0x7f9409404c40)
0x7f9409404b70 -> 0x7f9409404b10
(0x7f9409404b70,0x7f9409404b10)

If I use vecS instead of listS, it works fine, but then I run into trouble when removing vertices. So how can I view edges/vertices with listS?

EDIT: SOLUTIONS

SOLUTION 1:

Use a struct to store a property:

struct vertex {
    int id;
}

typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, vertex> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits <Graph>::edge_iterator edgeIt;
typedef boost::graph_traits<Graph>::vertex_iterator vertexIt;
typedef map<vertex_t,size_t> IndexMap;

//MAKE YOUR GRAPH
...
//

//Assign vertex IDs
int currentID = 0;
for(pair<vertexIt,vertexIt> it = boost::vertices(g); it.first != it.second; ++it.first) {
    g[*it.first].id = currentID++;
}

//Access them when displaying edges:
for(pair<vertexIt,vertexIt> it = boost::vertices(g); it.first != it.second; ++it.first) {
    cout << g[*it.first].id << endl;
}

//Access them when displaying vertices:
for(pair<edgeIt,edgeIt> it = boost::edges(g); it.first != it.second; ++it.first) {
    cout << g[source(*it.first,g)].id << " " << g[target(*it.first,g)].id << endl;
}

SOLUTION 2:

Use property maps (continuing on from my first code)

for(pair<vertexIt,vertexIt> vi = boost::vertices(g); vi.first != vi.second; ++vi.first) {
    cout << mapIndex[*vi.first] << endl;
}

for(IndexMap::iterator it = mapIndex.begin(); it != mapIndex.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

Answer 1

The vertex and edge data types in Boost are abstracted as descriptors. They are more or less pointers.

When using vecS, the descriptors are size_t indexes and their corresponding vertex and edge index map is available by default. If you want an integer index for your edges and vertices with listS you have to create it yourself.

I think a good method of doing this in a Boost-like way is this.

typedef std::map<vertex_descriptor,size_t> StdVertexIndexMap;
StdVertexIndexMap viMap;
typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap;
VertexIndexMap v_index(viMap);
vertex_iterator vi,ve;
size_t i = 0;
for(boost::tie(vi,ve) = boost::vertices(g); vi != ve; ++vi){
    boost::put(v_index,*vi,i);
    ++i;
}

Similarly for Edges. See my old question for context. Wrapping it in a boost::associative_property_map or something similar is the Boost way so that the algorithms that use boost::get and boost::put will work correctly.

If you don't plan on using it in a boost algorithm you could just use a simple std::map.

Answer 2

(Speculation) One possibility is that you are returning value of a pointer, i.e. address.

Try and use the dereference operator twice ** to test what is on these addresses and see if the returned values is reasonable.