search

bitwalker / libgraph

A graph data structure library for Elixir projects
MIT License
524 stars 75 forks source link

failing test case for preorder dft with int vertices #10

Open jlgeering opened 6 years ago

jlgeering commented 6 years ago

not sure what is happening, but something weird is going on when vertices are integers.

I did not dig super deep, but it looks like the order of the vertices in the underlying MapSet determines the first vertex to be traversed.

I think that for BFT you sort the vertices first, which you don't do for DFT.

Also, this only fails for certain values, e.g. {1,9000} is fine

coveralls commented 6 years ago

Coverage Status

Coverage remained the same at 94.955% when pulling 47c190b06d3a400280f46e7e8543d4f4b2d0934d on jlgeering:first-node-integer-vertices into e94b118e168ffda1f127af0b890aaa831c548e89 on bitwalker:master.

jlgeering commented 6 years ago

actually, this has nothing to do with int vertices, as my second test cases shows: a graph with only 1 edge {:b, :a} will be traversed [:a, :b] (like the graph with edge {:a, :b}) instead of [:b, :a]

=> the "sorting" of the underling MapSet seems to be / could be what determines the order

coveralls commented 6 years ago

Coverage Status

Coverage remained the same at 94.955% when pulling 47c190b06d3a400280f46e7e8543d4f4b2d0934d on jlgeering:first-node-integer-vertices into e94b118e168ffda1f127af0b890aaa831c548e89 on bitwalker:master.

bitwalker commented 6 years ago

You're correct in that currently the order we visit edges/vertices is based on the order of the underlying map/mapset. If we follow any order at all, it should be insertion order, which implies we need to store that information in an ordered datastructure, or store extra information with each vertex so that we can sort the map/mapset. I'll have to think this over, since the solution will have an impact on either performance or space overhead, perhaps both.