BGL: adjacency list returns wrong edge property for descriptor

Question

I have a graph stored as an adjacency list. The vertex property holds an int ID, and the edge property holds a 4x4 matrix and a weight;

In a test case, the graph is a 3-vertex graph with an edge connecting each pair of vertices (a complete graph).

I have a vector of edges descriptors PathType, representing a path, and I am iterating through it and accessing each edge and its property, RelationshipEdge, as follows.

for(PathType::iterator pathIterator = path.begin(); pathIterator != path.end(); ++pathIterator){
        edge_t edge = *pathIterator;
        RelationshipEdge rEdge = m_graph[edge];
        int sourceID = m_graph[boost::source(edge, m_graph)].id;
        int destID = m_graph[boost::target(edge, m_graph)].id;

However sometimes when this is performed, the RelationshipEdge returned contains the data for the wrong edge.

As an example, inspecting edge shows an m_source of 1 and m_target of 2. If I inspect the graph and find the edge with source 1 and target 2, the weight is 3 and the matrix is as entered. However rEdge has a weight of 1, and a different matrix. Those values actually correspond with the edge with source 0 and target 1.

Am I accessing the edge properties correctly?

The definition of my graph type is:

typedef boost::adjacency_list< 
boost::vecS, boost::vecS, boost::undirectedS, MarkerVertex, RelationshipEdge>
CorrelationAdjacencyList;

Where is your graph type definition, @Joe (consider a SSCCE since your prose suggests you can reproduce the issue with a small set of data) — sehe
I've now added that. When calling other edges in the same path, and even calling the same edge in a different path, I get the correct properties returned. This is as small an example as I can create, in terms of it still testing all the functionality. — Joe
Sorry, my crystal ball is failing to think of the reason why it fails for you. Try posting a SSCCE — sehe

pbible pbible · Accepted Answer · 2015-05-23T20:47:40

I believe your error is coming from somewhere else in the code base.

I put together this simple code to test out edge access and order on a similar graph and everything works as expected.

Culprits could be manually maintained edge_descriptors or vertex_descriptors as sehe mentioned. Or perhaps your path vector initialization or construction.

#include <iostream>
#include <algorithm>
#include <vector>

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

using namespace std;

enum edge_t {A,B};

struct MarkerVertex{
    std::string id;
};

struct RelationshipEdge{
    std::string id;
};


typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
    MarkerVertex, RelationshipEdge> CorrelationAdjacencyList;


typedef boost::graph_traits<CorrelationAdjacencyList>::edge_descriptor   Edge;
typedef boost::graph_traits<CorrelationAdjacencyList>::vertex_descriptor Vertex;

typedef vector<Edge> PathType;


void printPath(PathType &p, CorrelationAdjacencyList &g){
    cout << "print path" << endl;

    for(PathType::iterator pi = p.begin(); pi != p.end(); ++pi){
        Edge e = *pi;

        Vertex s = boost::source(e,g);
        Vertex t = boost::target(e,g);

        cout << g[s].id << "\t" 
             << g[e].id << "\t"
             << g[t].id << endl;

        bool isFound;
        Edge eForward;
        boost::tie(eForward,isFound) = boost::edge(s,t,g);
        cout << "forward  " << g[eForward].id << "\t" << isFound << endl;

        Edge eBackward;
        boost::tie(eBackward,isFound) = boost::edge(t,s,g);
        cout << "backward " << g[eBackward].id << "\t" << isFound << endl;
    }
}


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

    CorrelationAdjacencyList graph;

    Vertex a = boost::add_vertex(graph); graph[a].id = "a";
    Vertex b = boost::add_vertex(graph); graph[b].id = "b";
    Vertex c = boost::add_vertex(graph); graph[c].id = "c";

    Edge e1 = boost::add_edge(a,b,graph).first; graph[e1].id = "e1";
    Edge e2 = boost::add_edge(b,c,graph).first; graph[e2].id = "e2";
    Edge e3 = boost::add_edge(c,a,graph).first; graph[e3].id = "e3";

    PathType path1,path2,path3;

    path1.push_back(e1);
    path1.push_back(e2);
    path1.push_back(e3);

    path2.push_back(e2);
    path2.push_back(e3);
    path2.push_back(e1);

    path3.push_back(e3);
    path3.push_back(e2);
    path3.push_back(e1);

    printPath(path1,graph);
    cout << endl;
    printPath(path2,graph);
    cout << endl;
    printPath(path3,graph);


    cin.get();
}

BGL: adjacency list returns wrong edge property for descriptor

3 Answers