Add a function to return the list of edges in a graph #17

MaybeJustJames · 2022-02-10T16:08:19Z

Adds an edges function and a corresponding Edge type.

Reasoning for the change:
I had implemented this badly in my own project. edges functionality is also necessary to implement an Eq instance for Graph if that should be considered (RE #1).

Checklist:

Added the change to the changelog's "Unreleased" section with a reference to this PR (e.g. "- Made a change (#0000)")
Linked any existing issues or proposals that this pull request should close
Updated or added relevant documentation
Added a test for the contribution (if applicable)

JordanMartinez · 2022-06-22T12:30:20Z

I think this shouldn't add a dependency on tailrec and that the topo-sort implementation could be reused for this.

* Also adds an Edge type

MaybeJustJames · 2022-06-23T10:29:14Z

@JordanMartinez that was significantly easier than I expected. I also exposed the Edge constructor which breaks the convention (#18 exposes a toMap rather than the Graph constructor). Shall I expose an edgeToTuple?

src/Data/Graph.purs

JordanMartinez · 2022-06-23T10:38:27Z

src/Data/Graph.purs

+unfoldGraph ks label theEdges =
  Graph (M.fromFoldable (map (\k ->
-            Tuple k (Tuple (label k) (L.fromFoldable (edges k)))) ks))
+            Tuple k (Tuple (label k) (L.fromFoldable (theEdges k)))) ks))


Could you revert these two changes since they're not relevant to this PR?

These 2 changes are to avoid shadowing the edges name

Ah! Makes sense. Ok.

JordanMartinez · 2022-06-23T10:57:43Z

src/Data/Graph.purs

+-- | List all edges in a graph
+edges :: forall k v. Graph k v -> List (Edge k)
+edges (Graph g) = go initialState
+  where
+    go :: EdgesState k v -> List (Edge k)
+    go { unvisited: Nil, result: res } = res
+    go { unvisited: (src /\ (_ /\ dests)) : ns, result: res } =
+      go
+        { unvisited: ns
+        , result: map (Edge <<< (src /\ _)) dests <> res
+        }
+
+    initialState :: EdgesState k v
+    initialState =
+      { unvisited: M.toUnfoldableUnordered g
+      , result: Nil
+      }
+


I'm pretty sure this is slow for a few reasons.

First, you're using List and you have at least two traversals over dests:

map (Edge <<< (src /\ _)) dests: 1 traversal to create a new version of the list

(map _ dests) <> res: 1 traversal appending the result of map _ dests to res. See https://github.com/JordanMartinez/purescript-jordans-reference/blob/latestRelease/21-Hello-World/05-Application-Structure/src/03-Free/01-What-Is-The-Free-Monad/04-The-Remorseless-Free-Monad.md#the-direction-matters for context.

A faster solution would to fold over dests and cons the src and destination onto res in one fold:

result: foldl (\acc dest -> Edge (src /\ dest) : acc) res dests

Second, for initialState, why convert the Map to a List in the first place via M.toUnfoldableUnordered? That traverses the map once and then you traverse the map a second time in go via the unvisited field. Since Graph is just a newtype around Map and Map has an instance for FoldableWithIndex, couldn't this same key-value information be obtained with foldlWithIndex using a single traversal rather than two as it currently does?

Wow! I did not notice that at all. Thank you for taking the time to explain this all to me so clearly :)

As you mentioned I've replaced the custom function with foldlWithIndex (which traverses the Map once) and a foldl for each list of edge endpoints. So I cannot see any redundant traversals now.

JordanMartinez · 2022-06-23T10:59:53Z

src/Data/Graph.purs

  sequence = traverse identity

+-- | An edge within a `Graph` referencing endpoint keys
+newtype Edge k = Edge (Tuple k k)


Rather than defining an edge, it may be more helpful to define a newtype indicating which value inside the Tuple is the source and which is the destination. For example:

-newtype Edge k = Edge (Tuple k k) +Tuple (Source k) (Destination k)

I'm not sure what the best API would be here.

I've implemented this. I don't think it's any less ergonomic and, as you say, prevents mixing up source and destination. What do you think? Is this what you meant?

@JordanMartinez

Thanks @JordanMartinez

JordanMartinez

LGTM besides the changelog issue.

JordanMartinez · 2022-06-23T17:13:21Z

CHANGELOG.md


 New features:
 - Added `Foldable` and `Traversable` instances for `Graph` (#16 by @MaybeJustJames)
- Added `toMap` to unwrap `Graph` (#18)


Could you put this back into the correct spot in the changelog?

I moved this because it hasn't been released. Would you prefer a separate PR?

Ah, my bad. No, let's just fix it here.

MaybeJustJames · 2022-07-20T08:29:19Z

Can this be merged?

JordanMartinez · 2022-07-23T13:50:57Z

@garyb Can this get an approval?

garyb · 2022-07-23T13:58:17Z

Another option here might be to use type Edge k = { start :: k, end :: k } (or source/destination terms if preferred)?

If we don't want to go that route, then I'd suggest including Eq/Ord/Show instances for the newtypes at least.

MaybeJustJames · 2022-07-29T07:51:45Z

Another option here might be to use type Edge k = { start :: k, end :: k }

I've just pushed this. It still has the advantage of not mixing up source and destination without needing Eq, Ord, Show instances.

JordanMartinez · 2022-07-30T00:15:26Z

🏓 @garyb

garyb

👍 Thanks for making the change!

MaybeJustJames changed the title ~~Add a function the return the list of edges in a graph~~ Add a function to return the list of edges in a graph Feb 11, 2022

MaybeJustJames added 4 commits June 23, 2022 11:59

Add a function to return the list of edges in a graph

43afb78

* Also adds an Edge type

Updated the CHANGELOG

3862b9e

CHANGELOG formatting

654d9bf

Remove dependency on purescript-tailrec

2f5dd86

JordanMartinez reviewed Jun 23, 2022

View reviewed changes

src/Data/Graph.purs Outdated Show resolved Hide resolved

JordanMartinez reviewed Jun 23, 2022

View reviewed changes

MaybeJustJames added 4 commits June 23, 2022 13:36

Remove unused toMap import in test/Main.purs

92560ca

Correctly export Edge constructor

4e5d0d5

Replace custom tail-recursive function with foldlWithIndex

c724eec

Thanks @JordanMartinez

Implement Edge suggestion from @JordanMartinez

029c360

MaybeJustJames requested a review from JordanMartinez June 23, 2022 12:48

JordanMartinez approved these changes Jun 23, 2022

View reviewed changes

Switch Edge type from a Tuple of newtypes to a record

1dbf1cf

JordanMartinez approved these changes Jul 30, 2022

View reviewed changes

garyb approved these changes Jul 30, 2022

View reviewed changes

garyb merged commit c0a9fe4 into purescript:master Jul 30, 2022

Add a function to return the list of edges in a graph #17

Add a function to return the list of edges in a graph #17

Conversation

MaybeJustJames commented Feb 10, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

JordanMartinez commented Jun 22, 2022

Uh oh!

MaybeJustJames commented Jun 23, 2022

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

JordanMartinez left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

MaybeJustJames commented Jul 20, 2022

Uh oh!

JordanMartinez commented Jul 23, 2022

Uh oh!

garyb commented Jul 23, 2022

Uh oh!

MaybeJustJames commented Jul 29, 2022

Uh oh!

JordanMartinez commented Jul 30, 2022

Uh oh!

garyb left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

MaybeJustJames commented Feb 10, 2022 •

edited

Loading