HDX/Visualization: idea for additional graph traversals

[jteresco]

We could replace the stack/queue with other structures that would show different traversals. Some possibilities:

• Replace the stack/queue with a priority queue and base the priorities on things such as longest edge, shortest edge, or even northernmost edge (to have a bias toward searching northward first).
• Replace the stack/queue with a structure that chooses an element randomly to consider next.

[razieh]

Professor Teresco,

I think based on any Algorithm that's not too bad to change the items considered in that row of table.

On Thu, Aug 18, 2016 at 4:24 PM, Jim Teresco notifications@github.com wrote:

We could replace the stack/queue with other structures that would show different traversals. Some possibilities:

-

Replace the stack/queue with a priority queue and base the priorities on things such as longest edge, shortest edge, or even northernmost edge (to have a bias toward searching northward first).

Replace the stack/queue with a structure that chooses an element randomly to consider next.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/TravelMapping/EduTools/issues/32, or mute the thread https://github.com/notifications/unsubscribe-auth/ABbTSxcKC76yuFKUFUjz6lyHbDDnSNUqks5qhL-PgaJpZM4Jn4R4 .

[jteresco]

The reimplementation of the graph traversals with the action-based framework will make adding these pretty straightforward, hopefully.

[jteresco]

What we have now in the common graph traversal implementation by changing the behavior of the list of discovered vertices (LDV):

• breadth-first, LDV as a queue
• depth-first, LDV as a stack
• random-first, LDV selects an edge to remove randomly
• Dijkstra's algorithm, LDV is a priority queue based on shortest cumulative distance to the vertex via the edge
• Prim's algorithm, LDV is a priority queue based on shortest edge length

Dijkstra's and Prim's implementations use the common implementation, but are available in HDX as their own AVs. They could be added as options in the general graph traversals AV. Others that could be added:

• LDV is a priority queue based on longest edge length (kind of opposite of Prim's)
• LDV is a priority queue based on largest/smallest latitude/longitide, corresponding to creating a spanning tree first in one of the cardinal directions
• LDV bases priority on some pattern in edge labels, possibly giving priority to edges with an "I-" in the label which represent U.S. interstate highways
• LDV bases priority on some future supplemental data such as elevations or speed limits