Edge bundling

[LoLei]

Might not be worth it, but would be cool if it supported edge bundling. I know GraphViz is kinda broken in a lot of ways. concentrate=true definitely doesn't work. mingle could be used, although the dependency library ann is broken for compilation with GraphViz, I've just gotten it to work on Arch Linux.

I've tried a few combinations of mingle filters but I'm not sure which is the right one with your format. E.g.: twopi pacwall.gv | mingle | twopi -Tpng pacwall.png Also, it seems that mingle depends on the pos attribute of nodes, which is not used in your gv format at all, so it might be necessary to add these.

[Kharacternyk]

twopi pacwall.gv | mingle | twopi -Tpng pacwall.png

That should work. After the first run of twopi the source contains pos attributes. Does it produce the desired image?

I've read that mingle complains when it sees cycles. Dependency cycles between packages are possible, I'm not sure how we should handle it.

[LoLei]

It doesn't work: twopi -Nshape=point -Nheight=0.1 -Nwidth=0.1 pacwall.gv | mingle | twopi -Tpng -o pacwall.png

Disregarding mingle also often seems to color the edges blue for some reason.

Playing around with the parameters yields no better results: twopi -Nshape=point -Nheight=0.1 -Nwidth=0.1 pacwall.gv | mingle -a 0 -c 1 -i 10000 -r 10000 | twopi -Tpng -o pacwall.png

[Kharacternyk]

Can it be that mingle just gives up when detects at least one loop? An error message would be expected though.

[LoLei]

With the default method it just seems to stop intermittently as there is no more "improvement" to be found:

$ twopi -Nshape=point -Nheight=0.1 -Nwidth=0.1 pacwall.gv | mingle -a 0 -c 1 -i 10000 -r 10000 -v 2 | twopi -Tpng -o pacwall.png       
Mingle params:
  outer_iter = 10000
  method = 1
  compatibility_method = 1
  K = -1.00
  fmt = gv
  nneighbors = 10
  max_recursion = 10000
  angle_param = -1.00
  angle = 0.00
Process graph G in file <stdin>
n = 1616 nz = 4722
agglomerative_ink_bundling_internal, recurse level ------- 1
level ===================== 0, n = 4722
level 0->1, edges 4722 -> 2050, ink 1714789.522820->788601.420862 , gain = 926188.101958, or 926188.101958
level ===================== 1, n = 2050
level 1->2, edges 2050 -> 1047, ink 788601.420862->473300.460221 , gain = 315300.960640, or 315300.960640
level ===================== 2, n = 1047
level 2->3, edges 1047 -> 771, ink 473300.460221->403457.420845 , gain = 69843.039377, or 69843.039377
level ===================== 3, n = 771
level 3->4, edges 771 -> 740, ink 403457.420845->398950.024719 , gain = 4507.396126, or 4507.396126
level ===================== 4, n = 740
no more improvement, orig ink = 398950.024719, gain = 0.000000, stop and final bundling found
CPU for agglomerative bundling 0.039976
initial total ink = 1714789.522820
ink: 1714789.522820->398950.024719, edges: 4722->740, current ink = 398950.024719, percentage gain over original = 0.767348
agglomerative_ink_bundling_internal, recurse level ------- 2
level ===================== 0, n = 740
level 0->1, edges 740 -> 440, ink 147235.532759->92794.903488 , gain = 54440.629271, or 54440.629271
level ===================== 1, n = 440
level 1->2, edges 440 -> 393, ink 92794.903488->84653.817798 , gain = 8141.085689, or 8141.085689
level ===================== 2, n = 393
level 2->3, edges 393 -> 391, ink 84653.817798->84518.790471 , gain = 135.027328, or 135.027328
level ===================== 3, n = 391
no more improvement, orig ink = 84518.790471, gain = 0.000000, stop and final bundling found
CPU for agglomerative bundling 0.007952
ink: 147235.532759->84518.790471, edges: 740->391, current ink = 336233.282431, percentage gain over original = 0.036574
agglomerative_ink_bundling_internal, recurse level ------- 3
level ===================== 0, n = 391
level 0->1, edges 391 -> 342, ink 34498.530287->30759.011277 , gain = 3739.519010, or 3739.519010
level ===================== 1, n = 342
level 1->2, edges 342 -> 341, ink 30759.011277->30713.493131 , gain = 45.518146, or 45.518146
level ===================== 2, n = 341
no more improvement, orig ink = 30713.493131, gain = 0.000000, stop and final bundling found
CPU for agglomerative bundling 0.004049
ink: 34498.530287->30713.493131, edges: 391->341, current ink = 332448.245275, percentage gain over original = 0.002207
agglomerative_ink_bundling_internal, recurse level ------- 4
level ===================== 0, n = 341
level 0->1, edges 341 -> 336, ink 18234.107604->18177.313283 , gain = 56.794321, or 56.794321
level ===================== 1, n = 336
no more improvement, orig ink = 18177.313283, gain = 0.000000, stop and final bundling found
CPU for agglomerative bundling 0.002306
ink: 18234.107604->18177.313283, edges: 341->336, current ink = 332391.450954, percentage gain over original = 0.000033
agglomerative_ink_bundling_internal, recurse level ------- 5
level ===================== 0, n = 336
level 0->1, edges 336 -> 334, ink 17396.718085->17391.528177 , gain = 5.189908, or 5.189908
level ===================== 1, n = 334
no more improvement, orig ink = 17391.528177, gain = 0.000000, stop and final bundling found
CPU for agglomerative bundling 0.002311
ink: 17396.718085->17391.528177, edges: 336->334, current ink = 332386.261046, percentage gain over original = 0.000003
agglomerative_ink_bundling_internal, recurse level ------- 6
level ===================== 0, n = 334
no more improvement, orig ink = 17219.518968, gain = 0.000000, stop and final bundling found
CPU for agglomerative bundling 0.001106
ink: 17219.518968->17219.518968, edges: 334->334, current ink = 332386.261046, percentage gain over original = 0.000000
initial total ink = 1714789.522820, final total ink = 332386.261046, inksaving = 0.806165 percent, total ink_calc = 488527.000000, avg ink_calc per edge = 103.457645
total edge bundling cpu = 0.067290

With force-directed bundling the process seems to be killed due to too much CPU/memory usage, but the output looked more promising:

$ twopi -Nshape=point -Nheight=0.1 -Nwidth=0.1 pacwall.gv | mingle -m 0 -a 0 -c 1 -i 10000 -r 10000 -v 2 | twopi -Tpng -o pacwall.png
Mingle params:
  outer_iter = 10000
  method = 0
  compatibility_method = 1
  K = -1.00
  fmt = gv
  nneighbors = 10
  max_recursion = 10000
  angle_param = -1.00
  angle = 0.00
Process graph G in file <stdin>
n = 1616 nz = 4722
edge compatibilitu time = 0.005640
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
iter ==== 1 cpu = 0.000808 npoints = 1
iter ==== 2 cpu = 0.000766 npoints = 1
iter ==== 3 cpu = 0.000762 npoints = 1
iter ==== 4 cpu = 0.000761 npoints = 1
iter ==== 5 cpu = 0.000761 npoints = 1
iter ==== 6 cpu = 0.000762 npoints = 1
iter ==== 7 cpu = 0.000761 npoints = 1
iter ==== 8 cpu = 0.000761 npoints = 1
iter ==== 9 cpu = 0.000762 npoints = 1
iter ==== 10 cpu = 0.000764 npoints = 1
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
iter ==== 1 cpu = 0.001397 npoints = 3
iter ==== 2 cpu = 0.001397 npoints = 3
iter ==== 3 cpu = 0.001396 npoints = 3
iter ==== 4 cpu = 0.001378 npoints = 3
iter ==== 5 cpu = 0.001436 npoints = 3
iter ==== 6 cpu = 0.001400 npoints = 3
iter ==== 7 cpu = 0.001461 npoints = 3
iter ==== 8 cpu = 0.001396 npoints = 3
iter ==== 9 cpu = 0.001503 npoints = 3
iter ==== 10 cpu = 0.001399 npoints = 3
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
iter ==== 1 cpu = 0.002726 npoints = 7
iter ==== 2 cpu = 0.002708 npoints = 7
iter ==== 3 cpu = 0.002789 npoints = 7
iter ==== 4 cpu = 0.002708 npoints = 7
iter ==== 5 cpu = 0.002762 npoints = 7
iter ==== 6 cpu = 0.002799 npoints = 7
iter ==== 7 cpu = 0.002716 npoints = 7
iter ==== 8 cpu = 0.002705 npoints = 7
iter ==== 9 cpu = 0.002804 npoints = 7
iter ==== 10 cpu = 0.002717 npoints = 7
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
iter ==== 1 cpu = 0.005138 npoints = 15
iter ==== 2 cpu = 0.005163 npoints = 15
iter ==== 3 cpu = 0.005340 npoints = 15
iter ==== 4 cpu = 0.005082 npoints = 15
iter ==== 5 cpu = 0.005217 npoints = 15
iter ==== 6 cpu = 0.005469 npoints = 15
iter ==== 7 cpu = 0.005064 npoints = 15
iter ==== 8 cpu = 0.005055 npoints = 15
iter ==== 9 cpu = 0.005222 npoints = 15
iter ==== 10 cpu = 0.005059 npoints = 15
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
iter ==== 1 cpu = 0.009961 npoints = 31
iter ==== 2 cpu = 0.010073 npoints = 31
iter ==== 3 cpu = 0.009889 npoints = 31
iter ==== 4 cpu = 0.009942 npoints = 31
iter ==== 5 cpu = 0.010164 npoints = 31
iter ==== 6 cpu = 0.009930 npoints = 31
iter ==== 7 cpu = 0.009843 npoints = 31
iter ==== 8 cpu = 0.010128 npoints = 31
iter ==== 9 cpu = 0.009921 npoints = 31
iter ==== 10 cpu = 0.010278 npoints = 31
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
iter ==== 1 cpu = 0.020250 npoints = 63
iter ==== 2 cpu = 0.020834 npoints = 63
iter ==== 3 cpu = 0.020693 npoints = 63
iter ==== 4 cpu = 0.020795 npoints = 63
iter ==== 5 cpu = 0.020153 npoints = 63
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
total interaction pairs = 56806 out of 22297284, avg neighbors per edge = 12.030072
[1]    106240 done       twopi -Nshape=point -Nheight=0.1 -Nwidth=0.1 pacwall.gv | 
       106241 killed     mingle -m 0 -a 0 -c 1 -i 10000 -r 10000 -v 2 | 
       106242 done       twopi -Tpng -o pacwall.png

[LoLei]

Anyone else wanna try this out with mingle? Maybe my graph is just messed up.

[Kharacternyk]

I'll test it one day, my current priority is debtree support though.

[LoLei]

Repo rename incoming?

[Kharacternyk]

Nah, it would be packages wallpaper ;)

[LoLei]

Genius!

[Kharacternyk]

@LoLei, I've tried it. mingle does work by itself, the problem lies in post processing the output. When you did twopi | mingle | twopi, the second invocation of twopi just overwrote the positions that mingle calculated. An obvious fix would be to do twopi | mingle -Tpng, but (from the manual of mingle):

-T fmt specifies the output format. At present, the output is  always  in  the  DOT
       format. If fmt is "simple", the output is a simple, schematic representation
       of the drawing. Only the node positions and  edges  are  retained  from  the
       original  graph.  If fmt is "gv", the drawing information is attached to the
       input graph.

So, if I understand correctly, the situation is like this: mingle doesn't do -Tpng and filters that do -Tpng don't respect the positions that mingle suggests. Seems too dumb to be true, how am I supposed to render a graph that mingle created?

BTW, you have a typo in the instructions you posted on GitLab: ann.pac should be ann.pc.

[LoLei]

Thanks for still trying! And for the notice about the typo on GitLab, I've corrected it.

Still, it must be possible somehow. I just found this survey paper again from a previous year of a class I've taken, where a group does essentially the same thing. (See Section 3.1.) This is what led me to the manual compilation of GraphViz. They show some working mingle output. Unfortunately no exact replication instructions are included. They might have used different configurations.

I'm past the point of caring if this will ever work, but if you want I could reach out to the authors and get some more information.

[Kharacternyk]

The paper is a good read. They pass an undirected graph to mingle, so I have played with undirected graphs of various sizes. Still no luck. mingle outputs some fancy colors, but no edge bundling.

I could reach out to the authors and get some more information.

I would like to hear more from the authors, but it could be not worth your efforts. I'm OK if you would rather do something else.

[LoLei]

If I do get into contact with them I'll let you know!

[Kharacternyk]

Thanks!