Opened 6 years ago
Closed 5 years ago
#623 closed defect (fixed)
Different ids assigned to the same edge in an undirected graph
Reported by: | Francesco Carrabs | Owned by: | Alpar Juttner |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.4 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
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).
Change History (5)
comment:1 follow-up: 2 Changed 6 years ago by
comment:2 Changed 6 years ago by
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=0If 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)?
comment:3 Changed 6 years ago by
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.
comment:4 follow-up: 5 Changed 6 years ago by
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.
comment:5 Changed 5 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
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].
I could not reproduce this issue, I got the following output with the exact same code:
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)?