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 support for acyclic graphs and associated operations #154

Open
michaelpj opened this Issue Dec 4, 2018 · 3 comments

Comments

Projects
None yet
2 participants
@michaelpj
Copy link

michaelpj commented Dec 4, 2018

"Topological sorting" is under-specified wrt the ordering of the independent vertices at each "level" of the sort. We could reflect this in the output type, by returning something like [Set Vertex], where each set is an independent set. You can then recover the current sort by flattening the inner sets in any order.

This has two advantages:

  • We don't make a choice about how to sort the independent sets (the user might have an opinion).
  • Sometimes it's useful to know what the independent sets are (e.g. you can process all things whose dependencies have been satisfied in a "batch", but you need to know where the batch starts and ends).
@snowleopard

This comment has been minimized.

Copy link
Owner

snowleopard commented Dec 4, 2018

This is related to this issue: #85, where a possible implementation of batch function was provided (it is no longer compatible with the new scc type though).

One problem with deriving such "level vertex sets" is that the solution is not unique, as demonstrated by this simple example: 1 + 2 * 3. Here there are two possible answers: [[1,2], 3] and [2, [1,3]], i.e. 1 can be batched with either 2 or 3. Making an arbitrary decision, e.g. picking the lexicographically first solution, makes me uneasy.

In an ideal world, I'd like to have the following signature of scc (see also #152):

scc :: Graph a -> Acyclic.Graph (NonEmpty.Graph a)

Now we could write functions like this:

topSort            :: Acyclic.Graph a        -> [a]
batchLexicographic :: Acyclic.Graph a        -> [Set a]
batchWeighted      :: Acyclic.Graph (a, Int) -> [Set a]

Where the latter does an optimal batching that aims to minimise the overall "execution time" of tasks associated with vertices. There are other interesting batching strategies, including dynamic ones.

To sum up: I'd like to have this functionality, but I think it shouldn't be a part of scc's API. It belongs to the API of the (yet non-existing) Acyclic.Graph data type.

@michaelpj

This comment has been minimized.

Copy link
Author

michaelpj commented Dec 4, 2018

Ah, of course it's not unique, my mistake! Then we can't give a "best" most general type for topSort indeed.

So yes, this should be some kind of additional "batching" functionality, which might not even belong in this package.

Not sure if you want to keep this open for future reference, happy to close and I'll just implement my own thing.

@snowleopard

This comment has been minimized.

Copy link
Owner

snowleopard commented Dec 4, 2018

Let's keep this issue open, but I'll give it a more general title.

@snowleopard snowleopard changed the title Enrich the output of `topSort` to be a list of independent sets Add support for acyclic graphs and associated operations Dec 4, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment