daheath / optic-graph Goto Github PK

At the moment, a shortest path traversal between two indices is implemented, which is handy. However, there is a generalization of this which is the shortest path to all other indices.

What's the best way to present this? A map of traversals?

This generalization should be applied for

• Unweighted edges (using Dijkstra)
• Positive weight edges (Dijkstra)
• Arbitrary weight edges (Bellman-Ford)

Write Strongly Connected Components algorithm. What's the correct way to present it? Just the sets of indices? Something more flexible?

With the following stack.yaml contents:

flags: {}
extra-package-dbs: []
packages:
- location:
    git: https://github.com/DAHeath/optic-graph
    commit: ce4eed2403c24a6c2189b7dd74e001d59d74869d
  extra-dep: true
resolver: lts-9.0

Using the following stack command: stack install optic-graph

The build fails on Ubuntu 16.04.3 with the following error:

    Preprocessing library optic-graph-0.1.0.0...
    Cabal-simple_mPHDZzAJ_1.24.2.0_ghc-8.0.2: can't find source for
    Data/Optic/Undirected/HyperGraph in src,
    .stack-work/dist/x86_64-linux/Cabal-1.24.2.0/build/autogen

I believe this is caused by incorrect naming of src/Data/Optic/Undirected/Hypergraph.hs, which should be named HyperGraph.hs. This is confirmed by the error not being present in Windows, which uses a case-insensitive filesystem.

Pretty much every traversal in the library makes sense as an underscore variant and also an edge or vertex specific variant.

So for example, there's ipath and path. These are all possibilities as well:

• ipathVert
• ipathEdge
• pathVert
• pathEdge
• ipath_
• path_
• ipathVert_
• ipathEdge_
• pathVert_
• pathEdge_

This is obviously a crazy number of variants (12 per traversal), but they all make sense to have. Maybe there's some way to generate them cleanly?

I'm not super fond of the name "ord-graph". optic-graph?

Write a minimum-spanning-tree traversal.

Perhaps Gabow, Galil, Spencer, and Tarjan?

A lot of traversals pass through the graph in a tree. It might be cool to have an abstraction for this concept and a way to get an actual Tree (Data.Tree?) out of anything under the abstraction.

Along these lines, there should be versions of DFS and BFS which only perform the tree traversal on edges, rather than hitting every edge.