0
$\begingroup$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less than $j$.

Could you give me some hints how to do that??

EDIT:

Is it maybe as followed??

L ← Set of integers
S ← Set of all nodes with no incoming edges
while S is non-empty do
    assign the lowest number i from L to first node n from S
    remove the node n from S
    remove the integer i from L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return G
$\endgroup$
2
  • 3
    $\begingroup$ You want an algorithm for topological sorting. $\endgroup$ – user193271 Nov 24 '14 at 2:34
  • $\begingroup$ @yyyyyyy I edited my post. Could you have a look to tell me if it is correct?? $\endgroup$ – Mary Star Nov 30 '14 at 21:47
2
$\begingroup$

If your graph is infinite you might not be able to do it. Consider $\mathbb N \cup \{\omega\} $ as a set with the graph generated by the natural order $<$ (the normal one on finite integers, plus every finite is less than $\omega$. You cannot map the set into $\mathbb N$ preserving order.

In the case of a finite set, just complete you order (by adding all the missing edges and assigning arbitrary directions) and map onto $\mathbb N$ one by one. The inverse of this mapping will give you the desired labelling.

To be more explicit on the "completion" algorithm, let's first have the transitive closure of your graph (add as edge all compositons of edges with a common direction). If you can label this new graph, the labelling will be valid for the original one too.

Now, take any two vertices without any edge between them. This means that it is consistent with DAG that you can add an edge in any direction. Choose one and take the transitive closure again.

This process must finish in a finite number of steps, because the max number of edges in a DAG over $n$ points is $n^2$ (not counting duplicate edges).

At the end you will get a complete order over a finite set, which is equivalente to a bounded interval of the natural numbers.

$\endgroup$
1
$\begingroup$

A simple solution for a finite graph is this is to repeatedly apply the following procedure:

Find a vertex that has no incoming directed edges from unlabeled vertices. Label it by the next unused natural numbers.

The fact that such a vertex always exists follows from the graph being acyclic, since if every vertex had an incoming edge, there would have to be a cycle, since that would mean we could have some function $f:V\rightarrow V$ where $f(i)$ had an edge to $i$ - and this function would have no fixed point, but being a mapping from a finite set to a finite set, would therefore have a cycle, which is a contradiction. We can, after the first iteration, view labeling a vertex as removing it from the graph for the next iteration and we can apply the argument again.

You could also label each vertex $i$ by the number of vertices $j$ such that there is a (forward directed) path from $j$ to $i$, which might not give each vertex a unique integer, but it certainly satisfies the desired property - and it'd be easy enough to jiggle the numbers about to give each vertex a unique integer, without changing the order meaningfully.

$\endgroup$
6
  • $\begingroup$ I see... I added a pseudocode at my initial post. Could you have a look to tell me if it is correct?? $\endgroup$ – Mary Star Nov 30 '14 at 21:46
  • 1
    $\begingroup$ That should work fine, yes (assuming you properly compute the initial value for $S$) $\endgroup$ – Milo Brandt Nov 30 '14 at 21:48
  • $\begingroup$ What do you mean by "computing properly compute the initial value for $S$" ?? $\endgroup$ – Mary Star Nov 30 '14 at 21:50
  • $\begingroup$ Do we have to write in the algorithm also how we find the nodes with no incoming edges ?? $\endgroup$ – Mary Star Nov 30 '14 at 21:51
  • 1
    $\begingroup$ Yes, precisely. (Though finding nodes with no incoming edges shouldn't be too hard) $\endgroup$ – Milo Brandt Nov 30 '14 at 21:59

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.