graphviz: circular layout while preserving node or

问题:

Hey
I want to plot a graph of 128 nodes (labeled 1 to 128) in graphviz using circular layout. Circo does this, but I want the nodes to be placed in order of their label number instead of the order created by circo (based on the edges between them). Also, there may be nodes with no incoming or outgoing edges, but still have to be placed in the circular order.

I have tried fiddling with edge weight but it didn't affect anything. I could get the no-edge nodes to appear in the circo circle using invisible edges between adjacent nodes (e.g. 1->2, 2->3, ..., 128->1). But the order is still left wanting.

Is there any way to achieve this? I would really appreciate any help in this regard. Here is my 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] 
}

回答1:

I think, the only solution is to use a neato' layout and the pos attribut.

To do what you want, I start by creating a small Ruby script to calculate all nodes positions :

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

Then, I put the result in the graphviz script :

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 
}

Here is the result : http://dl.dropbox.com/u/72629/stackoverflow-4242949.png

回答2:

Generating your own node positions is the best solution outside of coming up with a better algorithm or adding weighting to circo by altering the graphviz source.

However, it does defeat the purpose of generating arbitrary graphs with graphviz. This script will use graphviz itself to generate a circle of arbitrary size with user defined formatting, hardcode the position, and then add edges across the center.

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

Here is an example file.

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

Running

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

Results in

Where normally, the same layout would result in