Node ID names affect Dijkstra algorithm

[rgcook]

Hi,

Just trying to make sense of this library, and I'm getting some confusing results that I don't quite understand. Hopefully I've not missed something important in the documentation.

It seems like for the Dijkstra algorithm to run properly, the node IDs must be all strings or all numbers, but never a mixture of the two. Additionally, all strings must be the same case and not contain a number within them. If these rules are not followed then the Dijkstra algorithm returns infinity for certain distances. For example:
g = new graphlib.Graph({directed:false,compound:true,multigraph:true});
g.setNode(0)
g.setNode('a')
g.setNode(3)
g.setNode(4)
g.setEdge(0,'a')
g.setEdge('a',3)
g.setEdge(3,0)
g.setEdge(4,'a')
In this example, the distance from node 0 to 3 and 0 to 'a' is 1, but from 0 to node 4 is reported as infinity, when it should be 2. If I change 'a' to a number, then it's fine. This isn't a problem, but I don't see any documentation that explicitly mentions rules about node names.

In the main example that I'm trying to work with, I have around 40,000 nodes and 60,000 edges, with each node having its own unique ID number allocated from an external application which are made up of numbers and letters. I originally used these ID numbers for consistency in graphlib, but Dijkstra was returning all infinities. I thought I had gotten to the bottom of it when I noticed the issue with mixed cases/letters/numbers - however, even if I replace these mixed ID names/numbers with unique integers, I still get some nodes that are infinite distance which shouldn't be.

I read the comment in a few bug reports where for undirected graphs we are supposed to use nodeEdges rather than outEdges, but this only returns an error for me if I follow the example fixes (TypeError: Cannot read property 'g' of undefined). I'm not sure if this is still necessary to do or whether it was changed since those bug reports, since it seems to work fine on small examples (like the one posted above) without it. I was wondering whether the number of nodes is a problem, or is there is still some issue with node naming that I am not aware of. I can't seem to find any issues when I'm debugging due to an error on how I'm inputting the data.

[chriscamplin]

@rgcook Did you ever solve this? i'm randomly getting Infinity too on a directed graph

[vladpuz]

I have the same problem. The strange thing is that the number of nodes with a distance of infinity still depends on the length of the name of the nodes.

I generate node IDs via nanoid and if the name length is 2, then the nodes to which there is no route are approximately 5%. But if the name length is 4 or more, then the number of nodes to which there is no route immediately becomes about 95%.

At the same time, I am sure that all the nodes can be reached. This is very strange

UPDATE:
My problem with the undirected graph was that I didn't pass the edgeFn

const route = alg.dijkstra(graph, terminalNode, (edge) => {
  const label = graph.edge(edge.v, edge.w) as EdgeLabelType;
  return label.weight;
}, (edge) => graph.nodeEdges(edge) as Edge[]);