Longest-Path Layering algorithm

Question

NOTES:

1. there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash.

2. the code provide in this post is python3 on the premise that it lends itself to readability.

3. this post was not posted to SE code review as:

   a. there are not sufficient tags for graphs (just graphs and graphics)

   b. the underlying issue is one concerning the algorithm, not the implementation (I think).

4. this post uses the graph-traversal tag as it deals with finding the longest-path - although that is not necessarily the aim of the algorithm or this question.

---

This question deals with implementing the longest-path layering algorithm outlined in Chapter 13 of the Handbook of Graph Drawing and Visualization edited by Dr. Robert Tamassia and penned by Healy and Nikolov. It, and its explanation, can be found on pages 420-1 of the linked PDF. As I am seeking your help, I am writing the algorithm as they provide there, here:

The Longest-Path Algorithm(G)

Requires: DAG G=(V,E)

$ U \leftarrow \phi $

$ Z \leftarrow \phi $

$ currentLayer \leftarrow 1 $

while $ U \neq V $ do

$\quad$Select vertex $ v \in V \backslash U $ with $N^+_G(v)\subseteq Z$

$\quad$if $ v $ has been selected then

$\quad$ $\quad$ Assign $v$ to the layer with a number $ currentLayer $

$\quad$$\quad$$ U \leftarrow U \cup \{v\} $

$\quad$endif

$\quad$if no vertex has been selected then

$\quad$$\quad$$ currentLayer \leftarrow currentLayer+1 $

$\quad$$\quad$$ Z \leftarrow Z \cup U $

$\quad$endif

end while

Some things to note about this (and many) graph drawing algorithms. They often have stringent assumptions that need to be upheld. In this case, we assume that our graph is a directed acyclic graph (DAG) - not too big of a deal, but this should be kept in mind (see Tarjan's method for making acyclic graphs).

The implementation looks almost verbatim to the pseudo-code (a perk of python).

def longest_path_layering(vertex_set):
    """
    See page 420-1 of Chapter 13: Hierarchical Graph Drawing by Healy and Nikolov.
    Modified to switch layering (e.g. layer 0 is up top instead of at the bottom)
    U = vertices assigned to any layer
    Z = all vertices assigned to a layer above the current
    V = Vertex Set
    v is selected from v in V \ U
    """
    U = set()
    Z = set()
    V = set(vertex_set.keys())

    current_layer = 0 # layer 0 is 'top most'
    while U != V:

        choices = set(filter(lambda v: set(vertex_set[v]['p']).issubset(Z), V - U))

        if choices:
            selected = choices.pop()
            vertex_set[selected]['layer'] = current_layer
            U.add(selected)

        else:
            current_layer += 1
            Z = Z.union(U)

        if current_layer > len(V):
            # This algorithm will NEVER produce a graph with more layers than vertices.
            # So this is sensible for debugging
            break

    return current_layer + 1

In my experience, this has worked very well for me (using the aforementioned Tarjan method based on finding strongly connected components (SCC) to remove cycles via the feedback arc set (FAS)).

Until... this graph:

V = list(range(0, 24+1))
E = [[0, 1],
 [1, 2],
 [1, 5],
 [1, 14],
 [1, 19],
 [1, 21],
 [5, 3],
 [5, 20],
 [8, 9],
 [8, 10],
 [9, 0],
 [10, 0],
 [12, 15],
 [13, 1],
 [14, 12],
 [15, 16],
 [15, 17],
 [15, 18],
 [16, 0],
 [17, 0],
 [18, 0],
 [19, 20],
 [21, 20],
 [22, 13],
 [22, 23],
 [22, 24],
 [23, 0],
 [24, 0]]
VS = {v: {'s': set(), 'p': set()} for v in V} # s is short for successors (i.e. v --> s) and p for predecessors (p --> s)
for s, t in E: # for source target
    VS[t]['p'].add(s) # target <-- source
    VS[s]['s'].add(t) # source --> target

This graph has already been per-processed to be acyclic. I am fairly confident that my implementation to remove cycles is correct and functioning. If this graph is cyclic, I do not see it at the moment.

If we run the layering algorithm:

longest_path_layering(VS)
# returns 27, showing that we hit our sensible break to prevent the endless while loop

and then print out only the vertices that were layered:

for v in sorted([v for v in VS if 'layer' in VS[v]], key=lambda v: VS[v]['layer']):
    if 'layer' in VS[v]:
        print(v, VS[v]['p'], VS[v]['s'], VS[v]['layer'])

we get

vertex    predecessors    successors   layer
# layer 0
4 set() set() 0
6 set() set() 0
7 set() set() 0
8 set() {9, 10} 0
11 set() set() 0
22 set() {24, 13, 23} 0

# layer 1
9 {8} {0} 1
10 {8} {0} 1
13 {22} {1} 1
23 {22} {0} 1
24 {22} {0} 1

If this does not explain why the algorithm fails, then perhaps the following code might:

layer_1 = [8, 9, 10, 13, 23, 24]
for v in [v for v in VS if VS[v]['p'] in layer_1 or VS[v]['s'] in layer_1]:
    print(v, VS[v]['p'], VS[v]['s'])
# prints nothing

i.e. there are no vertices connected to layer 1 that are not already in layer 0. So it seems that the issue is that this algorithm has another requirement. The components of the graph must have a connection - albeit an acyclic one.

My question is thus what is the most sensible error handling for this scenario. Should I pick an un-assinged vertex with the minimal number of predecessors? This seems reasonable as the algorithm starts with a random root of the graph. However, given that we now have chosen one, it feels that it matters which vertex we choose. Also, should $currentLayer$ be reset to 0?

Answer 1

It looks like three vertices n6, n7 and n11 are orphans never included in any edges, also more importantly, the edges described creates a cyclic graph. Longest-Path Algorithm assumes an acyclic graph. There are preprocesses to make a cyclic graph acyclic using algorithms such as greedy cycle removal.