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);
            }
        }
    }
}