Generate every topological sort of a graph

user_5861265 0
Viewed 180

Consider this input array which represents a graph:

[
    {"id":1,"prev":["NaN"]},
    {"id":2,"prev":["NaN"]},
    {"id":3,"prev":[1]},
    {"id":4,"prev":[2]},
    {"id":5,"prev":[2]},
    {"id":6,"prev":[3,4]},
    {"id":7,"prev":[5,6]}
]

enter image description here

My task is to find each possible option of ordering the elements in the list.

The order of the elements depends on whether the element has a previous one or not. For example, no. 7 will always be the last since it has 2 previous elements and no followers.

I tried to implement as follows but without success:

var possibleSolutions = [];
recursiveCheck(tasks.slice(), tasks.length, []);

function recursiveCheck(array, noCalls, currentSolution) {
    var solution = currentSolution;
    array.forEach((task, index, object) => {
        if (task.prev.length <= 1 && isNaN(task.prev[0])) {
            var tmpTasks = array.slice();
            solution.push(task.id);
            tmpTasks.splice(index, 1);
            tmpTasks.forEach(el => {
                el.prev.forEach((prevEl, index, object) => {
                    if (prevEl == task.id) {
                        object.splice(index, 1)
                    }
                })
            })
            noCalls--;
            if (noCalls == 0) {
                possibleSolutions.push(solution)
                solution = [];
            } else {
                recursiveCheck(tmpTasks, noCalls, solution);
            }
        }
    });
}

This should be the output:

[
    [1,2,3,4,5,6,7],
    [1,2,3,4,6,5,7],
    [1,2,3,5,4,6,7],
    [1,2,4,3,5,6,7],
    [1,2,4,3,6,5,7],
    [1,2,4,5,3,6,7],
    [1,2,5,3,4,6,7],
    [1,2,5,4,3,6,7],
    [1,3,2,4,5,6,7],
    [1,3,2,4,6,5,7],
    [1,3,2,5,4,6,7],
    [2,1,3,4,5,6,7],
    [2,1,3,4,6,5,7],
    [2,1,3,5,4,6,7],
    [2,1,4,3,5,6,7],
    [2,1,4,3,6,5,7],
    [2,1,4,5,3,6,7],
    [2,1,5,3,4,6,7],
    [2,1,5,4,3,6,7],
    [2,4,1,3,5,6,7],
    [2,4,1,3,6,5,7],
    [2,4,1,5,3,6,7],
    [2,4,5,1,3,6,7],
    [2,5,1,3,4,6,7],
    [2,5,1,4,3,6,7],
    [2,5,4,1,3,6,7]
]

As another example, the array cannot be arranged like [1,3,6,...] because 6 has a previous element 4 and therefore element 4 must be before 6.

topological-sort graph-theory recursion javascript
1 Answers

Let's discuss this a bit more abstractly.

A directed graph is the data structure we're really taking as input here. We have a set V of vertices/nodes and a set E of edges. Each edge is an ordered pair (v1, v2), where v1 and v2 are both vertices, representing an arrow from v1 to v2. Here, we're representing the graph using the "adjacency list" representation.

The task is to find all the ways to topologically sort this graph.

We can describe the ways to topologically sort a graph as follows:

If we want to topologically sort the empty graph (the graph with no vertices), this is easy: the only way to do it is to output the empty sorting []. So the list of all ways to topologically sort the empty graph will be [[]].

Now, let's consider the problem of topologically sorting a non-empty graph. Consider a sequence s which is a topological sort of a non-empty graph G. We can consider the first element of s, which we will call x, and the sequence of all the rest of the elements, which we call s'.

We know that x must be a node in G, and we know that x cannot have any predecessors in G. In other words, there can be no node y such that (y, x) is an edge.

We also know that s' must be a topological sort of G'_x, which is G but with the node x (and all edges connecting to it) removed.

So to get all the topological sortings of G, we must find all sequences with initial element x and remaining elements s', such that x is an element of G with no predecessors and s' is a topological sorting of G'_x.

const remove_node = (g, x) => 
    g.flatMap((node) => node["id"] == x ? 
                        [] : 
                        {"id": node["id"], 
                         "prev": node["prev"].filter((id) => id != x)});

const topological_sorts = (g) => 
    g.length == 0 ?
    [[]] :
    g.filter((node) => node["prev"].length == 0)
     .map((node) => node["id"])
     .flatMap((id) => 
       topological_sorts(remove_node(g, id)).map((sorting) =>
         [id].concat(sorting)));

const remove_nan = (g) => g.map((node) => 
   ({ "id" : node.id, 
     "prev": node.prev.filter((predecessor) => 
       predecessor !== "NaN") } ));

const get_answer = (g) => topological_sorts(remove_nan(g));

Calling get_answer on your graph will result in the correct answer.

user_119123420
Related