2
$\begingroup$

The Problem

I have a set of edges (a, b), where a and b are nodes in a directed, acyclic graph (DAG).

The number of edges is guaranteed to be the number of nodes - 1.

I am looking for an algorithm that finds a sequence of nodes [n_1, ... n_n] so that the sequence contains all nodes in the graph, and that all edges (n_i, n_i+1) for 0 < i < n exist in edges. If that sequence is not possible because the given set of edges is not equal to the set of edges required, then I need an error to be thrown.

Edit: the graph may have an arbitrary number of disconnected components. I obviously don't consider a graph with multiple disconnected components as linear.

Ideas so far

Note that I am checking that the number of edges is exactly the number of edges required for such a sequence to exist. As a result, the algorithm can fail when there are two edges that share a source or a destination. However, I still need to get that sequence.

I realize that topological sort returns a linear order of a directed graph, which satisfies my requirements. However, I still want to fail when the graph is not exactly linear like that, instead of getting a linear order anyways.

Maybe I can validate, then do a topological sort. But that sounds inefficient. I am also not sure about the formal names of things in this problem, so it's hard to simply look up an algorithm. I feel like I am missing some simple connection or trick here.

Could you provide me with an algorithm that accomplishes this? I'll take pseudocode or any language of your choice.

$\endgroup$
1
  • 1
    $\begingroup$ Have you tried thinking of an algorithm using BFS or DFS? $\endgroup$ – D.W. May 3 '20 at 15:37
0
$\begingroup$

Here is a quite non-optimal algorithm, to get you started.

Go over all edges $(a,b)$. For each edge, go again over all edges, and check how many times $a$ appears. Stop once you discover $a$ that appears only once (if this never happens, reject). We will take $n_1 = a$.

Go over all edges again, looking for the unique edge $(n_1,b)$ in which $n_1$ appears. Take $n_2 = b$.

Go over all edges again, looking for an edge $(n_2,c)$ in which $n_2$ appears on the left (if there is no such edge, reject). Take $n_3 = c$.

Continue in this way, finding $n_4,\ldots,n_n$.

This algorithm runs in $O(n^2)$. Using hashing, you should be able to improve it to $O(n)$.

$\endgroup$
2
  • $\begingroup$ Are you sure this works? If there are any two edges (a, b) and (c, d) where a = c, then the graph is not linear. Every node should exist exactly once as a the source of an edge and once as a destination. Otherwise it should fail. $\endgroup$ – Dracam May 3 '20 at 15:46
  • $\begingroup$ You also need to check that the different $n_i$ that you find are distinct. $\endgroup$ – Yuval Filmus May 3 '20 at 15:47
0
$\begingroup$

I figured out an algorithm that at least passes my test cases:

let N = set of all nodes
let E = set of all edges

if (|E| != |N|-1) fail

let possibleStartNodes = new set containing all of N
let nexts = new dictionary from node -> node

foreach (prev, next) in E:
  if (next not in possibleStartNodes) fail 
  remove next from possibleStartNodes
  nexts[prev] = next
end foreach

if (|possibleStartNodes| != 1) fail

let currentNode = the one node in possibleStartNodes
let ordering = new list
ordering.push(currentNode)

while (nexts contains value for currentNode) 
  ordering.push(next)
  currentNode = next
end while

return ordering

$O(n)$ looks pretty reasonable to me. Are there any ways to improve?

Edit: I would appreciate any hints about the correct technical terms for the concepts I'm using

$\endgroup$

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.