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;

Answer 1

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

Answer 2

Here's the solution I found, though I'm not convinced I fully understand why the original method does not.

I have replaced the above code with

for(PathType::iterator pathIterator = path.begin(); pathIterator != path.end(); ++pathIterator){
    edge_t edge = *pathIterator;

    int sourceID = m_graph[boost::source(edge, m_graph)].id;
    int destID = m_graph[boost::target(edge, m_graph)].id;

    int lowerID, higherID;
    if (sourceID < destID){
        lowerID = sourceID;
        higherID = destID;
    } else {
        lowerID = destID;
        higherID = sourceID;
    }

    edge_t edge2 = m_edgeDescriptorsByEndpoints.at(make_pair(lowerID, higherID));
    RelationshipEdge rEdge = m_graph[edge2];

m_edgeDescriptorsByEndpoints is a map of pairs of vertex IDs to edge descriptors.

So I'm taking the edge descriptor, getting the IDs of the source and target vertices, finding the corresponding edge descriptor from the map and then getting the properties of that edge.

Not exactly a satisfying solution but it works, as far as I've been able to test so far.

EDIT

I substituted the call to my map with a call to boost::edge(u,v,g) as suggested by @sehe, so the code is now as follows:

for(PathType::iterator pathIterator = path.begin(); pathIterator != path.end(); ++pathIterator){
            edge_t edge = *pathIterator;

            vert_t sourceV = boost::source(edge, m_graph);
            vert_t targetV = boost::target(edge, m_graph);

            pair<edge_t, bool> edgePair = boost::edge(sourceV, targetV, m_graph);
            if (!edgePair.second){
                cerr << "Edge does not exist" << endl;
            }
            RelationshipEdge rEdge = m_graph[edgePair.first];

This code still results in rEdge containing the correct properties, which seems odd, since I'd think that querying the graph for the vertices of an edge, and then querying the graph for the edge that connects those vertices would always give you that exact same edge back.

Answer 3

Without further information, I can make the educated guess that you use vecS containers and the iterators/references have become invalidated.

This would happen on insertion/deletion of edges/vertices.