Different ids assigned to the same edge in an undirected graph

[Francesco Carrabs]

Dear LEMON developers, I would like to report a problem regarding multiple ids associated with the same edge in an undirected graph. Let us consider the following code in which I define a complete undirected graph with 3 nodes:

#include <iostream>
#include <lemon/list_graph.h>

using lemon::INVALID;
using namespace std;

int main() {

    lemon::ListGraph g;
    for(int i=0;i<3;i++){
        g.addNode();
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(i<j)
                g.addEdge(g.nodeFromId(i),g.nodeFromId(j));
        }
    }

    cout<<"Edge of the graph: "<<endl;
    for(lemon::ListGraph::EdgeIt e(g); e!=INVALID;++e){
        cout<<"Edge {"<<g.id(g.u(e))<<","<<g.id(g.v(e))<<"}: id= "<<g.id(e) << endl;
    }

    cout<<"IncEdge of the graph: "<<endl;
    for(lemon::ListGraph::NodeIt i(g); i!=INVALID; ++i){
        for(lemon::ListGraph::IncEdgeIt e(g, i); e != INVALID; ++e)
            cout<<"Edge {"<<g.id(g.baseNode(e))<<","<<g.id(g.runningNode(e))<<"}: id= "<<g.id(e)<<endl;
    }
}

Notice that I ask to print the id in two different ways: by iterating on all the edges of the graph and by iterating on the nodes of the graph and, for each node, by considering its incident edges. The output of the previous code is:

Edge of the graph: Edge {1,2}: id= 2 Edge {0,2}: id= 1 Edge {0,1}: id= 0

IncEdge? of the graph: Edge {2,1}: id= 4 Edge {2,0}: id= 2 Edge {1,2}: id= 5 Edge {1,0}: id= 0 Edge {0,2}: id= 3 Edge {0,1}: id= 1

You can notice that to the edge {0,1} are assigned the id 0 (loop on the edges) and 1 (loop on the incident edges).

[Balazs Dezso]

I could not reproduce this issue, I got the following output with the exact same code:

Edge of the graph: 
Edge {1,2}: id=2
Edge {0,2}: id=1
Edge {0,1}: id=0
IncEdge of the graph: 
Edge {2,1}: id=2
Edge {2,0}: id=1
Edge {1,2}: id=2
Edge {1,0}: id=0
Edge {0,2}: id=1
Edge {0,1}: id=0

If you iterate over the Arcs instead of Edges, then it's expected to get back different ids.

Could you check that your bug report is valid, and if yes, could you give us more information, e.g. compiler, compiler version, OS, lemon version (hg id)?

[Francesco Carrabs]

I am using a macbook pro with osx "El capitan". I tried the g++ 4.2.1 compiler (the default), the g++ version 8.2 (installed with homebrew) and clang 3.14.2 and with all of them, the problem arises. I am using the lemon library 1.3.1.

The problem arises only with the Edges while with the Arcs everything is ok. I do not know if it can be useful but I notice that the id of edge {1,2}, in the first loop, is equal to the floor of the id divided by 2 of the same edge, in the second for loop. The same occurs for the edge {0,2}.

Replying to Balazs Dezso:

I could not reproduce this issue, I got the following output with the exact same code:

Edge of the graph: 
Edge {1,2}: id=2
Edge {0,2}: id=1
Edge {0,1}: id=0
IncEdge of the graph: 
Edge {2,1}: id=2
Edge {2,0}: id=1
Edge {1,2}: id=2
Edge {1,0}: id=0
Edge {0,2}: id=1
Edge {0,1}: id=0

If you iterate over the Arcs instead of Edges, then it's expected to get back different ids.

Could you check that your bug report is valid, and if yes, could you give us more information, e.g. compiler, compiler version, OS, lemon version (hg id)?

[Balazs Dezso]

This problem looks to be solved in a previous changeset: ​https://lemon.cs.elte.hu/trac/lemon/changeset/4add05447ca00f659a054e88a7e0842a66f8b041/lemon

I recommend to use the developer version of lemon.

[Peter Kovacs]

I suggest to merge the relevant bug fix part of this changeset (i.e. fixing the IncEdgeIt typedefs) to be merged into release branches, at least to 1.3, and release 1.3.2.

[Alpar Juttner]

Replying to Peter Kovacs:

I suggest to merge the relevant bug fix part of this changeset (i.e. fixing the IncEdgeIt typedefs) to be merged into release branches, at least to 1.3, and release 1.3.2.

It's done, both to lemon-1.2 and to lemon-1.3 , see chgsets [7edc220d6244] and [ed2c21cbd6ef].