graphviz: układ kolisty z zachowaniem kolejności węzłów

Question

Hej
Chcę wykreślić wykres 128 węzłów (oznaczonych od 1 do 128) w graphviz przy użyciu układu kołowego. Circo robi to, ale chcę, aby węzły zostały umieszczone w kolejności ich numeru etykiety zamiast zamówienia utworzonego przez circo (w oparciu o krawędzie między nimi). Ponadto mogą istnieć węzły bez krawędzi przychodzących lub wychodzących, ale wciąż muszą być umieszczone w porządku cyklicznym.

Próbowałem gryźć z wagą krawędzi, ale nic nie wpłynęło. Mogłem uzyskać węzły bez krawędzi, które pojawiłyby się w okręgu cyrku, używając niewidocznych krawędzi między sąsiednimi węzłami (np. 1-> 2, 2> 3, ..., 128-> 1). Ale kolejność wciąż jest niewystarczająca.

Czy jest jakiś sposób, aby to osiągnąć? Naprawdę doceniam każdą pomoc w tym zakresie. Oto mój kod:

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

Myślę, że jedynym rozwiązaniem jest użycie układu neato i pos attribut.

Aby zrobić to, co chcesz, zacznę tworząc mały skrypt Ruby, aby obliczyć wszystkie węzły pozycje:

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 

Następnie umieścić wynik w skrypcie 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 
} 

Tutaj jest wynikiem: http://dl.dropbox.com/u/72629/stackoverflow-4242949.png

Answer 2

Generowanie własnych pozycji węzłów jest najlepszym rozwiązaniem poza wymyślaniem lepszego algorytmu lub dodawania wagi do circo przez zmiana źródła grafviz.

Jednak nie jest to cel generowania dowolnych wykresów za pomocą graphviz. Ten skrypt użyje samego graphviz do wygenerowania okręgu o dowolnym rozmiarze z formatowaniem zdefiniowanym przez użytkownika, zakodowaniu pozycji, a następnie dodaniu krawędzi na środku.

#!/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 

Oto przykładowy plik.

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 

przebiegu

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

Wyniki w

Gdzie zwykle ten sam układ spowodowałoby