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.

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

Add some basic graph functionality #172

Closed
dolio opened this issue Aug 18, 2023 · 1 comment
Closed

Add some basic graph functionality #172

dolio opened this issue Aug 18, 2023 · 1 comment
Assignees
Labels
pull-request A pull request discussion ticket

Comments

@dolio
Copy link

dolio commented Aug 18, 2023

This PR adds some graph functionality similar to Haskell's Data.Graph. The code is at @unison/base/@dolio/graphs

Added are types for graphs and strongly connected components. There are functions for building, topologically sorting and finding the SCCs of a graph, as well as some miscellaneous functionality that was useful for that and for creating tests. I also made some simple random graph generators for the tests (one generates DAGs, because topSort will fail on graphs with cycles).

@dolio dolio added the pull-request A pull request discussion ticket label Aug 18, 2023
@pchiusano
Copy link
Member

pchiusano commented Aug 18, 2023

@runarorama - I merged this while you're out, hope that is okay. All the definitions are under data.Graph if you want to shuffle things around.

@unison/base/main> merge /@dolio/graphs

  Here's what's changed in the current namespace after the merge:
  
  Added definitions:
  
    1.  structural type data.Graph v (+2 metadata)
    2.  structural type data.Graph.SCC v (+2 metadata)
    3.  data.Graph.SCC.Acyclic                     : v -> SCC v
    4.  data.Graph.AdjLists                        : data.Array.Raw [Nat]
                                                   -> data.Array.Raw v
                                                   -> data.Graph v
    5.  data.Graph.SCC.Cyclic                      : [v] -> SCC v
    6.  data.graph.SCC.add                         : a -> SCC a -> SCC a (+2 metadata)
    7.  data.graph.SCC.augment                     : Boolean
                                                   -> a
                                                   -> Optional (SCC a)
                                                   -> SCC a (+2 metadata)
    8.  data.Graph.build                           : [(v, k, [k])] -> data.Graph v (+2 metadata)
    9.  data.Graph.tests.build                     : [test.Result] (+3 metadata)
    10. data.Graph.tests.checkAcyclic              : data.Graph v
                                                   -> Nat
                                                   ->{Exception} Boolean (+2 metadata)
    11. data.Graph.tests.checkCyclic               : data.Graph v
                                                   -> [Nat]
                                                   ->{Exception} Boolean (+2 metadata)
    12. data.Graph.tests.checkTopOrder             : data.Graph v
                                                   -> [v]
                                                   ->{Exception} () (+2 metadata)
    13. data.Graph.sccs.classifies                 : data.Graph v
                                                   -> Nat
                                                   -> (data.NatSet, NatMap (SCC v))
                                                   -> [Nat]
                                                   ->{Exception} (data.NatSet, NatMap (SCC v)) (+2 metadata)
    14. data.Graph.sccs.classify                   : data.Graph v
                                                   -> Nat
                                                   -> data.NatSet
                                                   -> NatMap (SCC v)
                                                   -> Nat
                                                   ->{Exception} (data.NatSet, NatMap (SCC v)) (+2 metadata)
    15. data.graph.sccs.crawl                      : data.Graph v
                                                   -> data.NatSet
                                                   -> [Nat]
                                                   -> Nat
                                                   ->{Exception} (data.NatSet, [Nat]) (+2 metadata)
    16. data.Graph.topSort.crawl                   : data.Graph v
                                                   -> data.NatSet
                                                   -> (data.NatSet, [v])
                                                   -> Nat
                                                   ->{Exception, Abort} (data.NatSet, [v]) (+2 metadata)
    17. data.Graph.sccs.crawls                     : data.Graph v
                                                   -> (data.NatSet, [Nat])
                                                   -> [Nat]
                                                   ->{Exception} (data.NatSet, [Nat]) (+2 metadata)
    18. data.Graph.topSort.crawls                  : data.Graph v
                                                   -> data.NatSet
                                                   -> (data.NatSet, [v])
                                                   -> [Nat]
                                                   ->{Exception, Abort} (data.NatSet, [v]) (+2 metadata)
    19. data.Graph.doc                             : Doc (+2 metadata)
    20. data.Graph.SCC.doc                         : Doc (+2 metadata)
    21. data.graph.SCC.add.doc                     : Doc (+2 metadata)
    22. data.graph.SCC.augment.doc                 : Doc (+2 metadata)
    23. data.Graph.build.doc                       : Doc (+2 metadata)
    24. data.Graph.tests.checkTopOrder.doc         : Doc (+2 metadata)
    25. data.Graph.sccs.classifies.doc             : Doc (+2 metadata)
    26. data.Graph.sccs.classify.doc               : Doc (+2 metadata)
    27. data.graph.sccs.crawl.doc                  : Doc (+2 metadata)
    28. data.Graph.topSort.crawl.doc               : Doc (+2 metadata)
    29. data.Graph.sccs.crawls.doc                 : Doc (+2 metadata)
    30. data.Graph.edgeCount.doc                   : Doc (+2 metadata)
    31. data.Graph.edges.doc                       : Doc (+2 metadata)
    32. data.Graph.isReachable.doc                 : Doc (+2 metadata)
    33. data.graph.SCC.map.doc                     : Doc (+2 metadata)
    34. data.Graph.tests.reverse.matchEdges.doc    : Doc (+2 metadata)
    35. data.Graph.tests.randomGraph.doc           : Doc (+2 metadata)
    36. data.Graph.reverse.doc                     : Doc (+2 metadata)
    37. data.Graph.sccs.doc                        : Doc (+2 metadata)
    38. data.Graph.stronglyConnectedComponents.doc : Doc (+2 metadata)
    39. data.Graph.topSort.doc                     : Doc (+2 metadata)
    40. data.Graph.vertex.doc                      : Doc (+2 metadata)
    41. data.Graph.vertexCount.doc                 : Doc (+2 metadata)
    42. data.Graph.vertexNum.doc                   : Doc (+2 metadata)
    43. data.Graph.edgeCount                       : data.Graph v -> Nat (+2 metadata)
    44. data.Graph.edges                           : data.Graph v
                                                   -> Nat
                                                   ->{Exception} [Nat] (+2 metadata)
    45. data.Graph.isReachable                     : data.Graph v
                                                   -> Nat
                                                   -> Nat
                                                   ->{Exception} Boolean (+2 metadata)
    46. data.graph.SCC.map                         : (a ->{g} b) -> SCC a ->{g} SCC b (+2 metadata)
    47. data.Graph.tests.reverse.matchEdges        : ∀ v1 v.
                                                     data.Graph v1 -> data.Graph v ->{Exception} () (+2 metadata)
    48. data.Graph.tests.randomDAG                 : (Nat -> a)
                                                   ->{Random} data.Graph a (+2 metadata)
    49. data.Graph.tests.randomGraph               : (Nat -> a)
                                                   ->{Random} data.Graph a (+2 metadata)
    50. data.Graph.reverse                         : data.Graph v
                                                   ->{Exception} data.Graph v (+2 metadata)
    51. data.Graph.tests.reverse                   : [test.Result] (+3 metadata)
    52. data.Graph.sccs                            : data.Graph v -> [SCC v] (+2 metadata)
    53. data.Graph.tests.sccs                      : [test.Result] (+3 metadata)
    54. data.Graph.stronglyConnectedComponents     : [(v, k, [k])] -> [SCC v] (+2 metadata)
    55. data.Graph.topSort                         : data.Graph v ->{Abort} [v] (+2 metadata)
    56. data.Graph.tests.topSort                   : [test.Result] (+3 metadata)
    57. data.Graph.vertex                          : data.Graph v
                                                   -> Nat
                                                   ->{Exception} v (+2 metadata)
    58. data.Graph.vertexCount                     : data.Graph v -> Nat (+2 metadata)
    59. data.Graph.vertexNum                       : data.Graph v
                                                   -> v
                                                   ->{Exception} Optional Nat (+2 metadata)
  
  Tip: You can use `todo` to see if this generated any work to do in this namespace and `test` to
       run the tests. Or you can use `undo` or `reflog` to undo the results of this merge.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
pull-request A pull request discussion ticket
Projects
None yet
Development

No branches or pull requests

3 participants