graphviz: disposition circulaire tout en préservant l'ordre des nœuds

Question

Hey
Je veux tracer un graphique de 128 nœuds (numérotés de 1 à 128) dans graphviz en utilisant une disposition circulaire. Circo fait cela, mais je veux que les nœuds soient placés dans l'ordre de leur numéro d'étiquette au lieu de l'ordre créé par circo (basé sur les bords entre eux). En outre, il peut y avoir des nœuds sans bord entrant ou sortant, mais qui doivent toujours être placés dans l'ordre circulaire.

J'ai essayé de jouer avec le poids des carres, mais cela n'affecte rien. Je pourrais obtenir que les nœuds sans bord apparaissent dans le cercle de circo en utilisant des bords invisibles entre des nœuds adjacents (par exemple 1-> 2, 2-> 3, ..., 128-> 1). Mais l'ordre est toujours laissé à vouloir.

Y a-t-il un moyen d'y parvenir? J'apprécierais vraiment toute aide à cet égard. Voici mon code:

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

Je pense que la seule solution est d'utiliser un layout et l'attribut pos.

Pour faire ce que vous voulez, je commence par la création d'un petit script Ruby pour calculer toutes les positions des noeuds:

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 

Ensuite, je mets le résultat dans le script 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 
} 

ici est le résultat: http://dl.dropbox.com/u/72629/stackoverflow-4242949.png

Answer 2

La génération de vos propres positions de nœuds est la meilleure solution en dehors de l'élaboration d'un meilleur algorithme ou de l'ajout de la pondération à circo par modifier la source graphviz.

Cependant, cela ne va pas dans le but de générer des graphes arbitraires avec graphviz. Ce script utilisera graphviz lui-même pour générer un cercle de taille arbitraire avec un formatage défini par l'utilisateur, coder en dur la position, puis ajouter des arêtes au centre.

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

Voici un exemple de fichier.

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 

en cours

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

Résultats dans

Où normalement, la même disposition entraînerait