Feature request: topological sorting support

[liach]

@jrtom suggests moving the topic of topological sorting to a separate issue.

Usage

The most outstanding usage of topological sorting is dependency management. For example, an order of executing tasks. (some depend on others)

Suggestion of implementation

Since topological sorting is from graph algorithm, I proposed to put it together with direct acyclic graphs in the previous issue. But the algorithm will be much slower once it involves with graphs.

Here are some ideas on implementation:

• Using graphs

• Using a hash map and a priority queue

[jrtom]

@liach: as @Bezier89 mentioned on the other issue, we have an internal implementation of topological sorting that we are considering releasing in a subsequent release.

We didn't do so in Guava 20.0 because there are some dependency issues (and related architectural issues) that we haven't worked out yet, but we are actively working on those issues.

[kashike]

Will this be making it into Guava in the near future?

[liach]

@kashike This sort is easy to understand. Each time you keep a collection of items without a prerequisite, and you then unlock more item when you add each of those in the collection to the sorted list. You can find a loop when you can no longer unlock but there are still entries left.

[jrtom]

@kashike It's still on our radar. I don't have a schedule for when we'll be able to get it out the door, though.

[kashike]

Any update on getting this into guava, @jrtom?

[jrtom]

@kashike No updates to share, sorry. It's still on our list, but there are other things in front of it. Unfortunately, common.graph is not anyone's full-time employment, so progress on these items like this is often slower than we'd like. :(

[liach]

Here is a side note: @ben-manes said in #3025 that

See #2641. I also implemented Kahn's algorithm on top of Guava's graph to order executions in a workflow. Simple code to write, but will gladly remove it when built in.

In the Kahn's algorithm, elements are enqueued and dequeued. Not only an array based queue but a priority queue can achieve this functionality, giving the elements another keyword to sort besides the graph-based ordering.

Use case: If a loader loads a list of plugins which specify both number priorities and load orders to other plugins, such a priority queue within topological sort may manage to sort quickly.

[kashike]

Thanks for the update - just wanted to make sure this wasn't lost. :dancer:

[lukeu]

Out of curiosity, what would the API look like? The word 'sort' makes me thing of modifying the graph, but I guess many use-cases would be met by a new Traverser - is that the idea here? And if not, would it be worth raising that as a separate issue?

[liach]

if this is part of the graph api, a predrcessor/successor function should suffice