graphviz: diseño circular conservando el orden de nodos

Question

Oye
Quiero trazar un gráfico de 128 nodos (etiquetados de 1 a 128) en graphviz usando el diseño circular. Circo hace esto, pero quiero que los nodos se coloquen en orden de su número de etiqueta en lugar del orden creado por circo (en función de los bordes entre ellos). Además, puede haber nodos sin bordes entrantes o salientes, pero aún deben colocarse en el orden circular.

He intentado juguetear con el peso del borde, pero no afectó nada. Pude hacer que aparecieran los nodos sin borde en el círculo circo utilizando bordes invisibles entre nodos adyacentes (por ejemplo, 1> 2, 2> 3, ..., 128> 1). Pero el orden todavía está faltando.

¿Hay alguna manera de lograr esto? Realmente agradecería cualquier ayuda en este sentido. Aquí está mi código:

digraph{ 
size="8,6" 
layout=circo 
node [shape=square,fontsize=300,penwidth=2] 
1->2 [style=invis] 
2->3 [style=invis] 
3->4 [style=invis] 
4->5 [style=invis] 
5->6 [style=invis] 
6->7 [style=invis] 
7->8 [style=invis] 
8->9 [style=invis] 
9->10 [style=invis] 
10->11 [style=invis] 
11->12 [style=invis] 
12->13 [style=invis] 
13->14 [style=invis] 
14->15 [style=invis] 
15->16 [style=invis] 
16->17 [style=invis] 
17->18 [style=invis] 
18->19 [style=invis] 
19->20 [style=invis] 
20->21 [style=invis] 
21->22 [style=invis] 
22->23 [style=invis] 
23->24 [style=invis] 
24->25 [style=invis] 
25->26 [style=invis] 
26->27 [style=invis] 
27->28 [style=invis] 
28->29 [style=invis] 
29->30 [style=invis] 
30->31 [style=invis] 
31->32 [style=invis] 
32->33 [style=invis] 
33->34 [style=invis] 
34->35 [style=invis] 
35->36 [style=invis] 
36->37 [style=invis] 
37->38 [style=invis] 
38->39 [style=invis] 
39->40 [style=invis] 
40->41 [style=invis] 
41->42 [style=invis] 
42->43 [style=invis] 
43->44 [style=invis] 
44->45 [style=invis] 
45->46 [style=invis] 
46->47 [style=invis] 
47->48 [style=invis] 
48->49 [style=invis] 
49->50 [style=invis] 
50->51 [style=invis] 
51->52 [style=invis] 
52->53 [style=invis] 
53->54 [style=invis] 
54->55 [style=invis] 
55->56 [style=invis] 
56->57 [style=invis] 
57->58 [style=invis] 
58->59 [style=invis] 
59->60 [style=invis] 
60->61 [style=invis] 
61->62 [style=invis] 
62->63 [style=invis] 
63->64 [style=invis] 
64->65 [style=invis] 
65->66 [style=invis] 
66->67 [style=invis] 
67->68 [style=invis] 
68->69 [style=invis] 
69->70 [style=invis] 
70->71 [style=invis] 
71->72 [style=invis] 
72->73 [style=invis] 
73->74 [style=invis] 
74->75 [style=invis] 
75->76 [style=invis] 
76->77 [style=invis] 
77->78 [style=invis] 
78->79 [style=invis] 
79->80 [style=invis] 
80->81 [style=invis] 
81->82 [style=invis] 
82->83 [style=invis] 
83->84 [style=invis] 
84->85 [style=invis] 
85->86 [style=invis] 
86->87 [style=invis] 
87->88 [style=invis] 
88->89 [style=invis] 
89->90 [style=invis] 
90->91 [style=invis] 
91->92 [style=invis] 
92->93 [style=invis] 
93->94 [style=invis] 
94->95 [style=invis] 
95->96 [style=invis] 
96->97 [style=invis] 
97->98 [style=invis] 
98->99 [style=invis] 
99->100 [style=invis] 
100->101 [style=invis] 
101->102 [style=invis] 
102->103 [style=invis] 
103->104 [style=invis] 
104->105 [style=invis] 
105->106 [style=invis] 
106->107 [style=invis] 
107->108 [style=invis] 
108->109 [style=invis] 
109->110 [style=invis] 
110->111 [style=invis] 
111->112 [style=invis] 
112->113 [style=invis] 
113->114 [style=invis] 
114->115 [style=invis] 
115->116 [style=invis] 
116->117 [style=invis] 
117->118 [style=invis] 
118->119 [style=invis] 
119->120 [style=invis] 
120->121 [style=invis] 
121->122 [style=invis] 
122->123 [style=invis] 
123->124 [style=invis] 
124->125 [style=invis] 
125->126 [style=invis] 
126->127 [style=invis] 
127->128 [style=invis] 
128->1 [style=invis] 
25->42 [penwidth=5] 
25->71 [penwidth=7] 
26->25 [penwidth=5] 
26->40 [penwidth=6] 
27->30 [penwidth=6] 
29->25 [penwidth=9] 
29->26 [penwidth=9] 
29->27 [penwidth=6] 
29->30 [penwidth=4] 
29->32 [penwidth=4] 
29->40 [penwidth=5] 
29->80 [penwidth=5] 
32->39 [penwidth=5] 
33->28 [penwidth=5] 
33->44 [penwidth=4] 
33->74 [penwidth=6] 
37->34 [penwidth=6] 
37->66 [penwidth=5] 
37->69 [penwidth=4] 
38->60 [penwidth=4] 
38->107 [penwidth=5] 
40->100 [penwidth=5] 
47->30 [penwidth=4] 
48->35 [penwidth=6] 
48->36 [penwidth=4] 
50->35 [penwidth=5] 
50->63 [penwidth=5] 
51->50 [penwidth=5] 
51->96 [penwidth=4] 
52->50 [penwidth=8] 
53->51 [penwidth=7] 
53->96 [penwidth=4] 
59->50 [penwidth=5] 
59->51 [penwidth=6] 
59->52 [penwidth=5] 
59->60 [penwidth=5] 
60->50 [penwidth=10] 
60->63 [penwidth=4] 
60->95 [penwidth=4] 
67->74 [penwidth=4] 
67->114 [penwidth=4] 
68->74 [penwidth=5] 
70->74 [penwidth=6] 
70->126 [penwidth=4] 
71->74 [penwidth=8] 
71->86 [penwidth=4] 
72->70 [penwidth=4] 
75->39 [penwidth=4] 
77->81 [penwidth=5] 
79->73 [penwidth=6] 
80->84 [penwidth=4] 
82->78 [penwidth=5] 
82->114 [penwidth=4] 
86->115 [penwidth=5] 
87->115 [penwidth=5] 
87->121 [penwidth=5] 
91->69 [penwidth=5] 
91->87 [penwidth=5] 
96->30 [penwidth=5] 
96->114 [penwidth=5] 
101->107 [penwidth=5] 
102->108 [penwidth=5] 
107->75 [penwidth=5] 
107->78 [penwidth=6] 
108->95 [penwidth=5] 
108->103 [penwidth=4] 
111->80 [penwidth=5] 
111->114 [penwidth=5] 
114->128 [penwidth=4] 
115->114 [penwidth=4] 
118->128 [penwidth=5] 
119->103 [penwidth=5] 
121->72 [penwidth=4] 
123->116 [penwidth=5] 
125->80 [penwidth=4] 
126->122 [penwidth=7] 
128->96 [penwidth=5] 
} 

Answer 1

Creo que la única solución es usar un diseño de neato y la postribución.

para hacer lo que quiere, comienzo mediante la creación de un pequeño script de Ruby para calcular todos los nodos posiciones:

radius = 20 

(1..128).each do |i| 
    x = Math.cos(((Math::PI*2)/128.0)*i.to_f)*radius 
    y = Math.sin(((Math::PI*2)/128.0)*i.to_f)*radius 
    puts " #{i}[label=\"#{i}\", pos=\"#{x},#{y}!\", shape = \"square\"];" 
end 

Entonces, puse el resultado en el guión graphviz:

digraph G { 
    layout="neato" 
    1[label="1", pos="19.9759091241034,0.98135348654836!", shape = "square"]; 
    2[label="2", pos="19.9036945334439,1.96034280659121!", shape = "square"]; 
    3[label="3", pos="19.7835301992956,2.93460948910723!", shape = "square"]; 
    4[label="4", pos="19.6157056080646,3.90180644032256!", shape = "square"]; 
    5[label="5", pos="19.4006250638909,4.85960359806528!", shape = "square"]; 
    6[label="6", pos="19.1388067146442,5.80569354508925!", shape = "square"]; 
    7[label="7", pos="18.8308813036604,6.7377970678444!", shape = "square"]; 
    8[label="8", pos="18.4775906502257,7.6536686473018!", shape = "square"]; 
    9[label="9", pos="18.0797858624689,8.55110186860564!", shape = "square"]; 
    10[label="10", pos="17.6384252869671,9.42793473651995!", shape = "square"]; 
    11[label="11", pos="17.1545722000054,10.2820548838644!", shape = "square"]; 
    12[label="12", pos="16.6293922460509,11.111404660392!", shape = "square"]; 
    13[label="13", pos="16.0641506296129,11.9139860898487!", shape = "square"]; 
    14[label="14", pos="15.4602090672547,12.6878656832729!", shape = "square"]; 
    15[label="15", pos="14.8190225070992,13.4311790969404!", shape = "square"]; 
    16[label="16", pos="14.142135623731,14.1421356237309!", shape = "square"]; 
    17[label="17", pos="13.4311790969404,14.8190225070992!", shape = "square"]; 
    18[label="18", pos="12.6878656832729,15.4602090672547!", shape = "square"]; 
    19[label="19", pos="11.9139860898487,16.0641506296129!", shape = "square"]; 
    20[label="20", pos="11.111404660392,16.6293922460509!", shape = "square"]; 
    21[label="21", pos="10.2820548838644,17.1545722000054!", shape = "square"]; 
    22[label="22", pos="9.42793473651996,17.6384252869671!", shape = "square"]; 
    23[label="23", pos="8.55110186860564,18.0797858624689!", shape = "square"]; 
    24[label="24", pos="7.6536686473018,18.4775906502257!", shape = "square"]; 
    25[label="25", pos="6.7377970678444,18.8308813036604!", shape = "square"]; 
    26[label="26", pos="5.80569354508925,19.1388067146442!", shape = "square"]; 
    27[label="27", pos="4.85960359806528,19.4006250638909!", shape = "square"]; 
    28[label="28", pos="3.90180644032257,19.6157056080646!", shape = "square"]; 
    29[label="29", pos="2.93460948910723,19.7835301992956!", shape = "square"]; 
    30[label="30", pos="1.96034280659122,19.9036945334439!", shape = "square"]; 
    31[label="31", pos="0.981353486548363,19.9759091241034!", shape = "square"]; 
    32[label="32", pos="1.22464679914735e-15,20.0!", shape = "square"]; 
    33[label="33", pos="-0.98135348654836,19.9759091241034!", shape = "square"]; 
    34[label="34", pos="-1.96034280659121,19.9036945334439!", shape = "square"]; 
    35[label="35", pos="-2.93460948910723,19.7835301992956!", shape = "square"]; 
    36[label="36", pos="-3.90180644032256,19.6157056080646!", shape = "square"]; 
    37[label="37", pos="-4.85960359806528,19.4006250638909!", shape = "square"]; 
    38[label="38", pos="-5.80569354508924,19.1388067146442!", shape = "square"]; 
    39[label="39", pos="-6.7377970678444,18.8308813036604!", shape = "square"]; 
    40[label="40", pos="-7.65366864730179,18.4775906502257!", shape = "square"]; 
    41[label="41", pos="-8.55110186860564,18.0797858624689!", shape = "square"]; 
    42[label="42", pos="-9.42793473651995,17.6384252869671!", shape = "square"]; 
    43[label="43", pos="-10.2820548838644,17.1545722000054!", shape = "square"]; 
    44[label="44", pos="-11.111404660392,16.6293922460509!", shape = "square"]; 
    45[label="45", pos="-11.9139860898487,16.0641506296129!", shape = "square"]; 
    46[label="46", pos="-12.6878656832729,15.4602090672547!", shape = "square"]; 
    47[label="47", pos="-13.4311790969404,14.8190225070992!", shape = "square"]; 
    48[label="48", pos="-14.1421356237309,14.142135623731!", shape = "square"]; 
    49[label="49", pos="-14.8190225070992,13.4311790969404!", shape = "square"]; 
    50[label="50", pos="-15.4602090672547,12.6878656832729!", shape = "square"]; 
    51[label="51", pos="-16.0641506296129,11.9139860898487!", shape = "square"]; 
    52[label="52", pos="-16.6293922460509,11.111404660392!", shape = "square"]; 
    53[label="53", pos="-17.1545722000054,10.2820548838644!", shape = "square"]; 
    54[label="54", pos="-17.6384252869671,9.42793473651996!", shape = "square"]; 
    55[label="55", pos="-18.0797858624689,8.55110186860564!", shape = "square"]; 
    56[label="56", pos="-18.4775906502257,7.6536686473018!", shape = "square"]; 
    57[label="57", pos="-18.8308813036604,6.73779706784441!", shape = "square"]; 
    58[label="58", pos="-19.1388067146442,5.80569354508925!", shape = "square"]; 
    59[label="59", pos="-19.4006250638909,4.85960359806528!", shape = "square"]; 
    60[label="60", pos="-19.6157056080646,3.90180644032257!", shape = "square"]; 
    61[label="61", pos="-19.7835301992956,2.93460948910724!", shape = "square"]; 
    62[label="62", pos="-19.9036945334439,1.96034280659122!", shape = "square"]; 
    63[label="63", pos="-19.9759091241034,0.98135348654836!", shape = "square"]; 
    64[label="64", pos="-20.0,2.44929359829471e-15!", shape = "square"]; 
    65[label="65", pos="-19.9759091241034,-0.981353486548354!", shape = "square"]; 
    66[label="66", pos="-19.9036945334439,-1.96034280659121!", shape = "square"]; 
    67[label="67", pos="-19.7835301992956,-2.93460948910723!", shape = "square"]; 
    68[label="68", pos="-19.6157056080646,-3.90180644032257!", shape = "square"]; 
    69[label="69", pos="-19.4006250638909,-4.85960359806528!", shape = "square"]; 
    70[label="70", pos="-19.1388067146442,-5.80569354508924!", shape = "square"]; 
    71[label="71", pos="-18.8308813036604,-6.7377970678444!", shape = "square"]; 
    72[label="72", pos="-18.4775906502257,-7.65366864730179!", shape = "square"]; 
    73[label="73", pos="-18.0797858624689,-8.55110186860564!", shape = "square"]; 
    74[label="74", pos="-17.6384252869671,-9.42793473651995!", shape = "square"]; 
    75[label="75", pos="-17.1545722000054,-10.2820548838644!", shape = "square"]; 
    76[label="76", pos="-16.6293922460509,-11.111404660392!", shape = "square"]; 
    77[label="77", pos="-16.0641506296129,-11.9139860898487!", shape = "square"]; 
    78[label="78", pos="-15.4602090672547,-12.6878656832729!", shape = "square"]; 
    79[label="79", pos="-14.8190225070992,-13.4311790969404!", shape = "square"]; 
    80[label="80", pos="-14.142135623731,-14.1421356237309!", shape = "square"]; 
    81[label="81", pos="-13.4311790969404,-14.8190225070992!", shape = "square"]; 
    82[label="82", pos="-12.6878656832729,-15.4602090672547!", shape = "square"]; 
    83[label="83", pos="-11.9139860898487,-16.0641506296129!", shape = "square"]; 
    84[label="84", pos="-11.111404660392,-16.6293922460509!", shape = "square"]; 
    85[label="85", pos="-10.2820548838644,-17.1545722000054!", shape = "square"]; 
    86[label="86", pos="-9.42793473651996,-17.6384252869671!", shape = "square"]; 
    87[label="87", pos="-8.55110186860565,-18.0797858624689!", shape = "square"]; 
    88[label="88", pos="-7.65366864730181,-18.4775906502257!", shape = "square"]; 
    89[label="89", pos="-6.7377970678444,-18.8308813036604!", shape = "square"]; 
    90[label="90", pos="-5.80569354508925,-19.1388067146442!", shape = "square"]; 
    91[label="91", pos="-4.85960359806528,-19.4006250638909!", shape = "square"]; 
    92[label="92", pos="-3.90180644032257,-19.6157056080646!", shape = "square"]; 
    93[label="93", pos="-2.93460948910725,-19.7835301992956!", shape = "square"]; 
    94[label="94", pos="-1.96034280659121,-19.9036945334439!", shape = "square"]; 
    95[label="95", pos="-0.981353486548361,-19.9759091241034!", shape = "square"]; 
    96[label="96", pos="-3.67394039744206e-15,-20.0!", shape = "square"]; 
    97[label="97", pos="0.981353486548353,-19.9759091241034!", shape = "square"]; 
    98[label="98", pos="1.9603428065912,-19.9036945334439!", shape = "square"]; 
    99[label="99", pos="2.93460948910724,-19.7835301992956!", shape = "square"]; 
    100[label="100", pos="3.90180644032257,-19.6157056080646!", shape = "square"]; 
    101[label="101", pos="4.85960359806528,-19.4006250638909!", shape = "square"]; 
    102[label="102", pos="5.80569354508924,-19.1388067146442!", shape = "square"]; 
    103[label="103", pos="6.73779706784439,-18.8308813036604!", shape = "square"]; 
    104[label="104", pos="7.6536686473018,-18.4775906502257!", shape = "square"]; 
    105[label="105", pos="8.55110186860564,-18.0797858624689!", shape = "square"]; 
    106[label="106", pos="9.42793473651995,-17.6384252869671!", shape = "square"]; 
    107[label="107", pos="10.2820548838644,-17.1545722000054!", shape = "square"]; 
    108[label="108", pos="11.111404660392,-16.6293922460509!", shape = "square"]; 
    109[label="109", pos="11.9139860898487,-16.0641506296129!", shape = "square"]; 
    110[label="110", pos="12.6878656832729,-15.4602090672547!", shape = "square"]; 
    111[label="111", pos="13.4311790969404,-14.8190225070992!", shape = "square"]; 
    112[label="112", pos="14.1421356237309,-14.142135623731!", shape = "square"]; 
    113[label="113", pos="14.8190225070992,-13.4311790969404!", shape = "square"]; 
    114[label="114", pos="15.4602090672547,-12.6878656832729!", shape = "square"]; 
    115[label="115", pos="16.0641506296129,-11.9139860898487!", shape = "square"]; 
    116[label="116", pos="16.6293922460509,-11.111404660392!", shape = "square"]; 
    117[label="117", pos="17.1545722000054,-10.2820548838644!", shape = "square"]; 
    118[label="118", pos="17.6384252869671,-9.42793473651996!", shape = "square"]; 
    119[label="119", pos="18.0797858624689,-8.55110186860565!", shape = "square"]; 
    120[label="120", pos="18.4775906502257,-7.65366864730181!", shape = "square"]; 
    121[label="121", pos="18.8308813036604,-6.7377970678444!", shape = "square"]; 
    122[label="122", pos="19.1388067146442,-5.80569354508925!", shape = "square"]; 
    123[label="123", pos="19.4006250638909,-4.85960359806528!", shape = "square"]; 
    124[label="124", pos="19.6157056080646,-3.90180644032257!", shape = "square"]; 
    125[label="125", pos="19.7835301992956,-2.93460948910725!", shape = "square"]; 
    126[label="126", pos="19.9036945334439,-1.96034280659121!", shape = "square"]; 
    127[label="127", pos="19.9759091241034,-0.981353486548362!", shape = "square"]; 
    128[label="128", pos="20.0,-4.89858719658941e-15!", shape = "square"]; 

    25->42 
    25->71 
    26->25 
    26->40 
    27->30 
    29->25 
    29->26 
    29->27 
    29->30 
    29->32 
    29->40 
    29->80 
    32->39 
    33->28 
    33->44 
    33->74 
    37->34 
    37->66 
    37->69 
    38->60 
    38->107 
    40->100 
    47->30 
    48->35 
    48->36 
    50->35 
    50->63 
    51->50 
    51->96 
    52->50 
    53->51 
    53->96 
    59->50 
    59->51 
    59->52 
    59->60 
    60->50 
    60->63 
    60->95 
    67->74 
    67->114 
    68->74 
    70->74 
    70->126 
    71->74 
    71->86 
    72->70 
    75->39 
    77->81 
    79->73 
    80->84 
    82->78 
    82->114 
    86->115 
    87->115 
    87->121 
    91->69 
    91->87 
    96->30 
    96->114 
    101->107 
    102->108 
    107->75 
    107->78 
    108->95 
    108->103 
    111->80 
    111->114 
    114->128 
    115->114 
    118->128 
    119->103 
    121->72 
    123->116 
    125->80 
    126->122 
    128->96 
} 

Aquí es el resultado: http://dl.dropbox.com/u/72629/stackoverflow-4242949.png

Answer 2

Generar sus propias posiciones de nodo es la mejor solución aparte de encontrar un mejor algoritmo o agregar ponderación a circo por alterando la fuente graphviz.

Sin embargo, no tiene el objetivo de generar gráficos arbitrarios con graphviz. Este script utilizará graphviz para generar un círculo de tamaño arbitrario con un formato definido por el usuario, codificar la posición y luego agregar bordes en el centro.

#!/bin/bash 
# loopgen.sh- generates a plain graphviz loop then hardcodes it and adds to it 
# input file format - 
# num of nodes 
# prefixes for the generated file (format information, labels) 
# (blank) 
# postfixes for the final file (extra connections, inputscale) 
# output - graph with nodes0 to nodex 
file=$(<$1) 
# trim filename to function name 
fun=${1##*/} 
fun=${fun%%.*} 
# gen is generation function 
gen="digraph $fun 
{ 
    layout=circo;" 
# fin is final function 
fin="" 
# get the number of inputs 
num=$(head -n 1 <<< "$file") 
if [ $num -lt 2 ]; then 
    echo "Bad number of inputs." 
    exit -1 
fi 
# increment the lines of the file 
file=$(tail -n +2 <<< "$file") 
# add all lines up to the first blank line 
gen="$gen 
    $(printf "$file" | awk '!p;/^$/{p=1}')" 
# remove all lines before the first blank line 
file=$(printf "$file" | awk '/^$/{p=1}p') 
# begin producing character-based nodes 
i=1 
gen="$gen 
    node0 " 
while [ $i -lt $num ]; do 
    gen="$gen -> node$i" 
    let i=i+1 
done 
#finish the loop 
gen="$gen -> node0; 
}" 
# generate, replace circo layout reference, make positions absolute 
gen=$(printf "$gen" | dot | 
sed -e 's/layout=circo/layout=neato/' -e 's/\(pos=".*\)"/\1!"/g') 
# remove trailing brace 
gen=$(printf "$gen" | head -n -1) 

fin="/* generated with loopgen.sh */ 
    $gen 
    $file 
}" 

printf "$fin" 
exit 0 

Aquí hay un archivo de ejemplo.

6 
node0 [label="bop it"]; 
node1 [label="twist it"]; 
node2 [label="pull it"]; 
node3 [label="flick it"]; 
node4 [label="spin it"]; 
node5 [label="throw it away"]; 

node2 -> node5 [constraint=false,weight=0]; 
// this keeps the program from running out of memory 
inputscale=72 

Operando

loopgen.sh input | neato -Tpng > output.png 

Resultados en

Donde normalmente, el mismo diseño se traduciría en