Topological sort with support for cyclic dependencies

Question

Consider the following dependencies (where A --> B means B depends on A, so effectively, A is the 'parent')

A --> B
A --> C
C --> D
C --> E

More graphically:

    A
    |
----------
|        |
B        C
         |
    -----------
    |         |
    D         E

A topological sort algorithm would return something like:

ABCDE

I have found code for this (exhibit A and exhibit B), but neither support cyclice dependencies. I am in the situtation that this could happen:

A --> B
B --> C
B --> D
C --> B
C --> E

Graphically:

A
|
B <--> C
|      |
D      E

This could return ABCDE or ACBDE. So because B and C are on the same 'level', the order between them is not important (likewise for D and E).

How could I accomplish such a thing. I realize this isn't exactly a topological sorting, but I'm not expert mathematician, so I don't really know where to start looking, let alone how to implement this.

Personally, I'm working in C#, but if you know how to do it in any other language, I'd be happy to study your code and translate it to C#.

update

I can also have the following situation:

A <--------
|         |
--> B --> C
    |     |
    D     E

So, important, this doesn't have to be a tree. I can have any arbitrary graph. In fact, not all nodes have to be connected to one another.

Answer 1

First off, it is conceptually easier if you have a graph such that you can ask "what do you depend on"? I'm going to assume that we have a graph where a directed edge from A to B means "A depends on B", which is the opposite of your statement.

I am somewhat confused by your question since a topo sort that ignores cycles is virtually the same as a regular topo sort. I'll develop the algorithm so that you can handle cycles as you see fit; perhaps that will help.

The idea of the sort is:

• A graph is a collection of nodes such that each node has a collection of neighbours. As I said, if a node A has a neighbour B then A depends on B, so B must happen before A.

• The sort takes a graph and produces a sorted list of nodes.

• During the operation of the sort a dictionary is maintained which maps every node onto one of three values: alive, dead and undead. An alive node has yet to be processed. A dead node is already processed. An undead node is being processed; it's no longer alive but not yet dead.

• If you encounter a dead node you can skip it; it's already in the output list.

• If you encounter a live node then you process it recursively.

• If you encounter an undead node then it is part of a cycle. Do what you like. (Produce an error if cycles are illegal, treat it as dead if cycles are legal, etc.)

---

function topoSort(graph) 
  state = []
  list = []
  for each node in graph
    state[node] = alive
  for each node in graph
    visit(graph, node, list, state)
  return list

function visit(graph, node, list, state)
  if state[node] == dead
    return // We've done this one already.
  if state[node] == undead
    return // We have a cycle; if you have special cycle handling code do it here.
  // It's alive. Mark it as undead.
  state[node] = undead
  for each neighbour in getNeighbours(graph, node)
    visit(graph, neighbour, list, state)
  state[node] = dead
  append(list, node);

Make sense?

Answer 2

edit 3 years later: I've occasionally come back to this since I first implemented this in 2014. I didn't really have a good understanding of it at the time when I first posted this answer, so that answer was overly complex. The sort is actually pretty straightforward to implement:

public class Node
{
    public int Data { get; set; }
    public List<Node> Children { get; set; }

    public Node()
    {
        Children = new List<Node>();
    }
}

public class Graph
{
    public List<Node> Nodes { get; set; }

    public Graph()
    {
        Nodes = new List<Node>();
    }

    public List<Node> TopologicSort()
    {
        var results = new List<Node>();
        var seen = new List<Node>();
        var pending = new List<Node>();

        Visit(Nodes, results, seen, pending);

        return results;
    }

    private void Visit(List<Node> graph, List<Node> results, List<Node> dead, List<Node> pending)
    {
        // Foreach node in the graph
        foreach (var n in graph)
        {
            // Skip if node has been visited
            if (!dead.Contains(n))
            {
                if (!pending.Contains(n))
                {
                    pending.Add(n);
                }
                else
                {
                    Console.WriteLine(String.Format("Cycle detected (node Data={0})", n.Data));
                    return;
                }

                // recursively call this function for every child of the current node
                Visit(n.Children, results, dead, pending);

                if (pending.Contains(n))
                {
                    pending.Remove(n);
                }

                dead.Add(n);

                // Made it past the recusion part, so there are no more dependents.
                // Therefore, append node to the output list.
                results.Add(n);
            }
        }
    }
}

Answer 3

In fact, you want a breadth-first printout of your graph

The linked wikipedia page list an algorithm to perform this.

There's also this question on SO

Answer 4

Start by thinking about the problem right. You don't have a tree. You have an arbitrary graph.

With that in mind, what you probably need to do first is to find cycles and break them by deleting an edge in the cycle (OK, marking the edge as "ignore this when doing topological sort").

With all the cycles removed, you can apply toplogical sort to the remaining nodes and arcs.