Custom Query (545 matches)

is there any graph structure in lemon library which supports getting an arc from its two nodes in O(1) times? I check ListDigraph?, by iterating all arcs connected with one node, I can achieve this purpose but it could be O(n).

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

Found in version: 1.3.1

The call to findArc in the bellow program yields segmentation fault on Ubuntu 16.04:

int main() {

ListGraph? g; ListGraph::Node n = g.addNode(); ListGraph::Arc a = findArc(g, INVALID, n); return 0;

}

I expect to get INVALID back from findArc in this case.