COIN-OR::LEMON - Graph Library

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 Changed 6 years ago by 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)?

comment:2 in reply to:  1 Changed 6 years ago by 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)?

comment:3 Changed 6 years ago by 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.

comment:4 Changed 6 years ago by 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.

Last edited 6 years ago by Peter Kovacs (previous) (diff)

comment:5 in reply to:  4 Changed 5 years ago by Alpar Juttner

Resolution: fixed
Status: newclosed

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

Note: See TracTickets for help on using tickets.