0
$\begingroup$

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 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?

$\endgroup$
9
  • $\begingroup$ What problem is this algorithm trying to solve? Is your goal to find a longest path in the dag? Is it to label each node with its distance to a sink (i.e., "layer")? Let me check to see if I can understand what your question is. You are saying, you have an algorithm for finding the longest path in a dag, but it seems to fail if the dag is not (weakly) connected, and you want to know what the algorithm should do in that case. Is that right? Do you know what output you'd like to receive from the algorithm in that case? Or are you asking what the output should be? $\endgroup$
    – D.W.
    Mar 22, 2018 at 16:03
  • $\begingroup$ @D.W. I apologize if I was not clear. This algorithm layers a DAG for hierarchical graph drawing i.e. it solves the problem that hierarchical drawings require a layering ( a partition of the vertex set). This algorithm does this by following the longest-path so there should be at most len-longest-path layers. It fails when the graph it not weakly connected. I mention what it could do in that case, but I want to know what makes the most sense. I think reseting currentLayer to 1 and starting with the next component makes sense, but it changes some of the internal logic. $\endgroup$
    – SumNeuron
    Mar 22, 2018 at 17:06
  • $\begingroup$ I don't know what the hierarchical graph drawing problem is. What is the problem specification? I understand that you want the algorithm to output a layering, but what properties do you want the resulting layering to have? It should be possible to specify what the problem is, in a way that is independent of how the algorithm happens to achieve it -- what is the problem spec? I can't tell you what the algorithm should do operationally or what makes the most sense without knowing what properties you want the output to have. $\endgroup$
    – D.W.
    Mar 22, 2018 at 17:21
  • $\begingroup$ @D.W. "The longest-path algorithm (LPA) solves the static scheduling problem for m = ∞. Let π be the number of vertices (V) in the longest directed path in a DAG. The LPA builds the scheduling list by assigning priority π to the V without outgoing edges. If all immediate successors of a vertex (v) have been assigned a priority then that v is assigned the lowest of the priorities of its immediate successors minus one. This is repeated until all V are assigned a priority. The V with the same priority k form layer L_(π − k +1)." In this post, we reverse the direction. $\endgroup$
    – SumNeuron
    Mar 22, 2018 at 17:25
  • $\begingroup$ Again, you are describing what the algorithm is doing, not what problem it is solving. I don't care about how it achieves it; at this point I care about what you're trying to achieve. Do you see the difference? Do you see why we have to know what we're trying to achieve, before we can begin to discuss how to achieve it? Also, what's the definition of the static scheduling problem? What do you want the output to be, if the graph isn't connected? $\endgroup$
    – D.W.
    Mar 22, 2018 at 17:55

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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