CODEWITHSUNDEEP
javagraph-theoryjgrapht
Przemysław Różycki
Przemysław Różycki

Reputation: 838

Topological sort with detecting vertices that have equal priorities with JGraphT

I introduced JGraphT library to my project and I'm constructing a directed graph of some resources to create with their dependencies. I'm going to use topological sort to determine an order of creation to pass it to other component. I'd like to determine resources that could be created in parallel as they don't have dependencies (direct or indirect) to each other (I'm interpreting it as resources having equal priorities of creation). TopologicalOrderIterator just returns vertices in order but doesn't seem to handle a case of equal priorities.

For example, for graph as below:

enter image description here

The valid orders are A, B, D, C or for example A, D, B, C or even D, A, B, C. I'd like to determine the fact, that resources D and A or D and B can be created in parallel and have something like {D, A}, B, C.

Is it possible to achieve it with JGraphT using topological sort or any other mechanism? Or if not, then maybe some recommendation of other graph library?

Upvotes: 4

Views: 542

Answers (1)

Joris Kinable
Joris Kinable

Reputation: 2411

All processes without dependencies can be executed in parallel. A simple algorithm would be to:

  1. Find all processes without dependencies (vertices without incoming arcs). These processes can be executed in parallel.
  2. Remove the vertices found in the previous step from the graph, and repeat steps 1 and 2 for the remaining graph, until all vertices have been eliminated from the graph.

Note that the above algorithm only works if your graph does not contain cycles! You can use JGraphT to verify that the graph does not have cycles if you are uncertain about this.

An alternative approach is to start a breath-first-search (BFS) from a vertex without outgoing arcs (the BFS goes into the opposite direction of the arcs). Using BFS, you can assign a number to each vertex, where the number corresponds to the layer of the vertex in the BFS graph. So in your example, C would be the root of the BFS graph, and hence gets assigned to layer 0. In the next BFS layer (layer 1) we would have vertices B and D, finally, in the 3rd layer, we would have vertex A. By definition, all vertices in the same layer, can be executed in parallel.

Upvotes: 2

Related Questions