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;
}

score 1 · Answer 1 · edited May 23 '17 at 12:03

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.

score 0 · Answer 2 · answered Sep 11 '15 at 09:30

0

(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.

answered Sep 11 '15 at 09:30

Ziezi

6,375
3
39
49

Hmm I get these errors like this if I do that: test.cpp:35:17: error: indirection requires pointer operand ('reference' (aka 'unsigned long') invalid) cout << **vi.first << endl; ^~~~~~~~~~ – Paradox Sep 11 '15 at 10:21
1

@user2520385 OK, try access operator after the the element, i.e. something like: `*vi.first.` or `*vi.first->`. – Ziezi Sep 11 '15 at 10:29
1

Ok so I think I know the problem now. When storing vertices/edges in a List container, they simply don't have an 'index'. You need to either assign an index map or use a struct workaround. I will edit my main post. – Paradox Sep 13 '15 at 08:03
@user2520385 you can formulate it as an answer and then accept it, it's a valid action – Ziezi Sep 13 '15 at 09:32

How to view vertices/edges from boost graph list containers

2 Answers2