Assign integers to the vertices of $G$

Question

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

Answer 1

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.

Answer 2

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.