Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Dijkstra distance between nodes are Infinity when using undirected graph #42

Open
ghost opened this issue May 31, 2015 · 3 comments · May be fixed by #92
Open

Dijkstra distance between nodes are Infinity when using undirected graph #42

ghost opened this issue May 31, 2015 · 3 comments · May be fixed by #92

Comments

@ghost
Copy link

ghost commented May 31, 2015

Hi!

I'm quite new to graphs, so this may not be a bug at all. Anyway, I noticed while i'm working on my network viewer(http://high5.io/network/), that the distance between nodes is quite randomly set to Infinity, instead of 1 or 2. When i type graphlib.alg.dijkstra(h5.network.graph, h5.id) in the console, I should see distance 0, 1 or anything but not Infinity I think. When I change the graph to directed and copy the edges, this problem seems to be gone. Any idea? Thanks by the way for creating this library!
@cpettitt
Copy link
Collaborator

The behavior is counter intuitive. The default edge traversal function is outEdges, regardless of whether the graph is directed or undirected. However, the behavior of outEdges is undefined for an undirected graph. The correct fix for this is to use outEdges for directed graphs and nodeEdges for undirected graphs.

To hold you over until I get the fix in, you can use:

graphlib.alg.dijkstra(h5.network.graph, h5.id, null, function(v) { return h5.network.graph.nodeEdges(v); })

@ghost
Copy link
Author

ghost commented Jun 1, 2015

Thanks! That worked perfectly.

@one-ideaed
Copy link

I faced the same issue as @jvanveen.
Suggested hotfix worked fine.

@cpettitt do you consider this issue to be a bug?

p.s. thx for the lib

@dionyziz dionyziz linked a pull request Aug 25, 2018 that will close this issue
Open
@assafsun assafsun mentioned this issue Apr 10, 2020
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Dijkstra undirected dionyziz/graphlib
2 participants
@cpettitt @one-ideaed