0
$\begingroup$

I have a DAG which I want to traverse in a topological order. Wikipedia describes two algorithms for topological sorting, which both work in theory but seem impractical to me from a design point of view: Kahn's algorithm modifies the graph (by removing edges) and the DFS-based one marks nodes, which would require me to modify my node classes (by adding a boolean field) and is furthermore not thread safe.

Are there more practical approaches, that preserve the asymptotic runtime but do not interfere with my business logic so much?

$\endgroup$
  • $\begingroup$ This is not really a computer science question, I feel. $\endgroup$ – adrianN Jul 28 '16 at 13:05
  • 1
    $\begingroup$ You might be right. I was expecting an alternative algorithm, so I posted it here. Steve's answer is more a technical solution, though. $\endgroup$ – jederik Jul 28 '16 at 16:11
  • $\begingroup$ Precisely why do you think they are impractical? Can you edit the question to clarify why you think Kahn's algorithm is impractical? Why do you think that it's problematic to remove edges? Have you forgotten that you can make a copy of the graph or represent the "supposedly deleted" edges in some other way? Also, what is a "design point of view"? $\endgroup$ – D.W. Jul 28 '16 at 19:09
  • 1
    $\begingroup$ @D.W. What I meant is that my nodes are actually business objects that should not be aware that they are traversed over. They thus should not have any features (like a "marked" flag) solely meant for traversal. Furthermore the graph might be a "const" reference, which prevents it from being modified. $\endgroup$ – jederik Jul 29 '16 at 18:24
2
$\begingroup$

Instead of seting a 'mark' flag;

 node.Marked = true;

You can maintain a set of marked nodes in a hashtable or similar;

 hashTable[node] = true;

You now have to pass the hash table around, but it's O(n) for space and O(1) to check if a node is marked.

$\endgroup$
1
$\begingroup$

You can do a topological sort with a DFS and retrieve the nodes order by pushing the node on a stack just before the recursive call ends. This implies extra memory to mark a node as visited though, anyway to transverse a graph you almost always will need extra memory to keep account of visited nodes.

That visited marks can be implemented with a hash table as mentioned before without modify your business logic.

A quick pseudocode:

topSortRec(currentNode, graph):
  for neighbor in graph.neighbors(currentNode):
    if neighbor is not visited:
      topSortRec(neighbor, graph)    

  S.push(currentNode)

topsort(graph):
  for each node in graph:
    mark node as not visited

  S = init as empty stack
  for each node in graph:
    if not is not visited:
      topSortRec(node,graph)

  path = init as empty list
  while S is not empty:
    node = S.pop()
    path.append(node)

  return path
$\endgroup$
1
$\begingroup$

Kahn's algorithm is practical. When the algorithm says "delete an edge", what you actually do is mark the edge and remember to treat marked edges as if they were deleted. It's easy to figure out how to go from there. You can keep a set (hashtable) of marked edges.

Or, you can make a copy of the graph, and then delete edges in the copy. That's even easier to implement, and a quite reasonable implementation strategy.

$\endgroup$
  • $\begingroup$ I thought about your first approach, but what bothered me was that the check if "m has no other incoming edges" now takes $O(\deg m)$ instead of $O(1)$ and I have nodes with lots of predecessors in my graph. I didn't really follow the idea through to copy the whole graph because it seemed so impractical to me, but thinking about it it's actually not. Still, after lifting my reservations towards hash tables ;) I think I'll go with Steve Cooper's solution. $\endgroup$ – jederik Jul 29 '16 at 18:03
  • $\begingroup$ @jederik, You can be smarter about that. For example, it suffices to keep a counter for each vertex that counts its indegree. The counter can be stored in a separate hashtable if you don't want to store it in the object. $\endgroup$ – D.W. Jul 29 '16 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.