Pgrouting, pgr_dijkstra function error

Question

I'm starting to use the Pgrouting function on my database Postgresl. I have the table of links (id, source, target, cost) which contains the set of edges of my graph. I want to calculate the shortest path of a given node to another. The pgr_dijkstra function returns an error that I have not understood. Here is the table of edges:

When I'm trying to run this request:

SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra('SELECT id, source,target, cost FROM ubanlinks', 244225135, 598385915, false, false);

It returns this error:

ERREUR: Error computing path: Unknown exception caught! ********** Erreur ********** ERREUR: Error computing path: Unknown exception caught! État SQL :38001

Does anyone have an idea as to what is the problem of my request or my table?

Answer 1

This is a memory allocation problem.

Your source and target nodes have high id's and PgRouting tries to allocate the memory based on the highest node id it can find, even if there is only a few edges and nodes in the graph.

Dijkstra, drivingDistance and other functions have the same problem. IMHO this is a real problem since you can't select a subgraph from a huge graph without renumbering the edges and nodes, which renders unusable the query parameters of these functions.

A simple test case to reproduce the problem : Create a small graph with 1 edge and starting and ending nodes id of 2 000 000 000 and 2 000 000 001. You ll get an error running dijkstra on theses two nodes.

Technical analysis follows :

Looking at the C source code (PgRouting v2.0.0), in src\bd_dijkstra\src :

bdsp.c 

... line 271 : computing max node id

  for(z=0; z<total_tuples; z++) {
    if(edges[z].source<v_min_id) v_min_id=edges[z].source;
    if(edges[z].source>v_max_id) v_max_id=edges[z].source;
    if(edges[z].target<v_min_id) v_min_id=edges[z].target;
    if(edges[z].target>v_max_id) v_max_id=edges[z].target; 

then line 315, the v_max_id is used as parameter...

  ret = bidirsp_wrapper(edges, total_271tuples, v_max_id + 2, start_vertex, end_vertex,
                       directed, has_reverse_cost,
                       path, path_count, &err_msg);

in BiDirDijkstra.cpp ... line 281, v_max_id + 2 = maxNode

int BiDirDijkstra::bidir_dijkstra(edge_t *edges, unsigned int edge_count, int maxNode, int start_vertex, int end_vertex,
                path_element_t **path, int *path_count, char **err_msg)
{
    max_node_id = maxNode;
    max_edge_id = -1;

    // Allocate memory for local storage like cost and parent holder
    DBG("calling initall(maxNode=%d)\n", maxNode);
    initall(maxNode);

and then line 67, trying to allocate A LOT of memory :

void BiDirDijkstra::initall(int maxNode)
{
    int i;
    m_vecPath.clear();
    DBG("BiDirDijkstra::initall: allocating m_pFParent, m_pRParent maxNode: %d\n", maxNode+1);
    m_pFParent = new PARENT_PATH[maxNode + 1];
    m_pRParent = new PARENT_PATH[maxNode + 1];
    DBG("BiDirDijkstra::initall: allocated m_pFParent, m_pRParent\n");

    DBG("BiDirDijkstra::initall: allocating m_pFCost, m_pRCost maxNode: %d\n", maxNode+1);
    m_pFCost = new double[maxNode + 1];
    m_pRCost = new double[maxNode + 1];
...