Generation depth partition
From InterSciWiki
See also: Alternating generation depth partition
DAGwuad, Directed Asymmetric Graph (with under-ancestor display), pronounced "Dagwood" after the cartoon character, offers a third Pajek/Network/Partition/ that modifies the Acyclic partition to bring descendants to the level just below the depth of their least ancestor and in this sense is far superior to the current Genealogical depth partition which creates arbitrary supernumerary levels. This pseudocode is by Douglas R. White and is proposed as an additional option for Pajek.
Say a network *.net obeys the Pajek/Net/Partition/Depth/Acyclic command, and a *.clu file is generated for hierarchical depths 1-M. N is known by the length of this file. The *.net file must also be read, with NARCS<NxN. Here is pseudocode for changing these depths, D the maximum depth, after reading the DAG.clu depths: in Matlab or R
[edit] USED IN
[edit] Algorithm
THIS ALGORITHM IS SUBQUADRATIC << O(N+Narcs+(D-1)*Narcs) and was programmed in Pajek by Andrej Mrvar 2008 as "Generation partition"
[edit] ARCS FROM PARENT TO CHILD AND LOWER TO HIGHER PARTITION NUMBERS
Do i=1=,N #clu file read lvl(i) enddo
Do Reps=1,D-1 #several repetitions will do or the algorithm could stop when no further changes are made.
Do i=1=,N #clu file minarc(i)=0 enddo
Do k=1,Narcs #for each arc until last. read i,j arc(k,1)=i #Parent arc(k,2)=j #Child if lvl(i)>minarc(j) then minarc(j)=lvl(i) #lowest ancestor if ancestors are higher than descendants enddo
Do k=1=,Narcs #for each arc until last. i=arc(k,1) #Parent j=arc(k,2) #Child if lvl(j)>minarc(j) then lvl(j)=minarc(j)+1 #bring low ego levels higher under min ancestor enddo enddo
