Incorrect A* pathfinding with undirected graph

[Langhaarzombie]

Hi there, I am just getting started with libgraph but I have noticed that I seem to be getting wrong results for the a_star function.

What I am doing basically:

g = Graph.new(type: :undirected)
|> Graph.add_edges([{:dp1, :dp2, [weight: 3]}, {:dp2, :dp3, [weight: 6]}, {:dp3, :dp4, [weight: 5]}])
|> Graph.add_edges([{:dp4, :dp5, [weight: 4]}, {:dp4, :dp6, [weight: 5]}, {:dp5, :dp6, [weight: 6]}])
|> Graph.add_edges([{:dp6, :dp7, [weight: 5]}, {:dp7, :dp8, [weight: 4]}, {:dp8, :dp9, [weight: 2]}])
|> Graph.add_edges([{:dp9, :dp10, [weight: 6]}, {:dp3, :dp5, [weight: 3]}, {:dp5, :dp1, [weight: 7]}])
|> Graph.add_edges([{:dp6, :dp3, [weight: 7]}])

iex(1)> Graph.a_star(g, :dp1, :dp6, fn v -> 0 end)

The result I get is:

[:dp1, :dp2, :dp3, :dp4, :dp6]

However, the correct result would be:

[:dp1, :dp2, :dp3, :dp6]

Thanks in advance.

PS.: If you need a picture of the graph created above just ask.

[bitwalker]

Looks like the problem here is that the pathfinding code is written around directed graphs (which is what this library focused on initially) - I'm working on rewriting the code to fix it for undirected graphs and will update this issue when that is done. Sorry for the trouble!

[willricketts]

Is this still in the pipeline?

[robindaumann]

The problem with the modelling of undirected graphs is that you have to check for the type everywhere. A proper (but perhaps not the most memory efficient) solution would be to implement everything only for directed graphs. When you want to add an undirected edge you just add two directed edges between the vertices.

[sgessa]

ping :)

[bitwalker]

Hey all, I have been swamped and not been able to revisit this in some time, but I'd like to get it addressed. If there is anyone interested in tackling the problem via PR, I'm happy to lend a hand in terms of review and suggestions, but not sure when I'll have enough time to sit down and address it myself.