NOTES:
there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash.
the code provide in this post is
python3
on the premise that it lends itself to readability.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).
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?
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$