GraphViz u SAGE-u

Pokazano je na nekoliko primjera korištenje GraphViz-a unutar SAGE-a. Detaljniji help o GraphViz-u možete pronaći na webu. GraphViz je napredni alat za automatsko crtanje grafova. Ovdje će biti pokazane samo neke od opcija. GraphViz ima puno opcija kojima se određuje izgled grafa i nemoguće je baš sve ih ovdje navesti.

In [1]:
import sage.misc.banner
banner()

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.2, Release Date: 2020-10-24                     │
│ Using Python 3.8.6. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘
In [2]:
from IPython.core.display import Image
In [3]:
graf1=Graph({0:[1,2,3],1:[1,1,1],2:[2,4,4],3:[4,4,4]})

SAGE

In [4]:
graf1.plot(graph_border=True)
Out[4]:

GraphViz

In [5]:
s1=graf1.graphviz_string()
print(s1)

graph {
  node_0  [label="0"];
  node_1  [label="1"];
  node_2  [label="2"];
  node_3  [label="3"];
  node_4  [label="4"];

  node_0 -- node_1;
  node_0 -- node_2;
  node_0 -- node_3;
  node_1 -- node_1;
  node_1 -- node_1;
  node_1 -- node_1;
  node_2 -- node_2;
  node_2 -- node_4;
  node_2 -- node_4;
  node_3 -- node_4;
  node_3 -- node_4;
  node_3 -- node_4;
}

različiti rasporedi vrhova pomoću opcija: neato, fdp, sfdp, twopi, circo.

In [6]:
os.system("echo '%s' | dot -Tpng > graf1.png" % s1)
Out[6]:
0
In [7]:
Image(filename="graf1.png")
Out[7]:
In [8]:
os.system("echo '%s' | dot -Kcirco -Tpng > graf2.png" % s1)
Out[8]:
0
In [9]:
Image(filename="graf2.png")
Out[9]:
In [10]:
os.system("echo '%s' | dot -Kneato -Tpng > graf3.png" % s1)
Out[10]:
0
In [11]:
Image(filename="graf3.png")
Out[11]:
In [12]:
os.system("echo '%s' | dot -Kfdp -Tpng > graf4.png" % s1)
Out[12]:
0
In [13]:
Image(filename="graf4.png")
Out[13]:
In [14]:
os.system("echo '%s' | dot -Ktwopi -Tpng > graf5.png" % s1)
Out[14]:
0
In [15]:
Image(filename="graf5.png")
Out[15]:

želimo li drukčiji izlaz od PNG-a

In [16]:
os.system("echo '%s' | dot -Teps > graf1.eps" % s1)
Out[16]:
0
In [17]:
os.system("echo '%s' | dot -Tpdf > graf1.pdf" % s1)
Out[17]:
0

možemo sami konstruirati direktno GraphViz graf dodajući još mnoge druge opcije (naravno, treba proučiti dot jezik; na webu postoje helpovi o tome).

neke opcije za prikaz vrhova grafa

možemo definirati globalno opcije koje će vrijediti za sve vrhove

In [18]:
s2="""graph {\n node[width=0.1,height=0.1,shape=circle, fontsize=10, fontcolor=red,fillcolor=yellow,style=filled,margin=0]\n
"0" [label="root"];\n  "1" [label="1"];\n  "2" [label="2"];\n  "3" [label="3"];\n  "4" [label="4"];\n  
"0" -- "1";\n  "0" -- "2";\n  "0" -- "3";\n  "1" -- "1";\n  "1" -- "1";\n  "1" -- "1";\n  "2" -- "2";\n  "2" -- "4";\n
"2" -- "4";\n  "3" -- "4";\n  "3" -- "4";\n  "3" -- "4";\n}"""
In [19]:
print(s2)

graph {
 node[width=0.1,height=0.1,shape=circle, fontsize=10, fontcolor=red,fillcolor=yellow,style=filled,margin=0]

"0" [label="root"];
  "1" [label="1"];
  "2" [label="2"];
  "3" [label="3"];
  "4" [label="4"];
  
"0" -- "1";
  "0" -- "2";
  "0" -- "3";
  "1" -- "1";
  "1" -- "1";
  "1" -- "1";
  "2" -- "2";
  "2" -- "4";

"2" -- "4";
  "3" -- "4";
  "3" -- "4";
  "3" -- "4";
}
In [20]:
os.system("echo '%s' | dot -Tpng > graf6.png" % s2)
Out[20]:
0
In [21]:
Image(filename="graf6.png")
Out[21]:
In [22]:
os.system("echo '%s' | dot -Kfdp -Tpng > graf7.png" % s2)
Out[22]:
0
In [23]:
Image(filename="graf7.png")
Out[23]:

možemo i lokalno urediti svaki pojedini vrh ukoliko želimo da izgleda drukčije od ostalih vrhova

In [24]:
s3="""graph {\n node [width=0.3,height=0.3 fontsize=10, fontcolor=red,fillcolor=yellow,style=filled,margin=0]\n 
"0" [label="root"];\n  "1" [label="1",shape=hexagon,fontsize=18,margin=0.2];\n  
"2" [label="2", fillcolor=mintcream, fontcolor=purple];\n  "3" [label="3",shape=house];\n  
"4" [label="4", shape=doublecircle];\n\n  "0" -- "1";\n  "0" -- "2";\n  "0" -- "3";\n  
"1" -- "1";\n  "1" -- "1";\n  "1" -- "1";\n  "2" -- "2";\n  "2" -- "4";\n  "2" -- "4";\n  
"3" -- "4";\n  "3" -- "4";\n  "3" -- "4";\n}"""
In [25]:
print(s3)

graph {
 node [width=0.3,height=0.3 fontsize=10, fontcolor=red,fillcolor=yellow,style=filled,margin=0]
 
"0" [label="root"];
  "1" [label="1",shape=hexagon,fontsize=18,margin=0.2];
  
"2" [label="2", fillcolor=mintcream, fontcolor=purple];
  "3" [label="3",shape=house];
  
"4" [label="4", shape=doublecircle];

  "0" -- "1";
  "0" -- "2";
  "0" -- "3";
  
"1" -- "1";
  "1" -- "1";
  "1" -- "1";
  "2" -- "2";
  "2" -- "4";
  "2" -- "4";
  
"3" -- "4";
  "3" -- "4";
  "3" -- "4";
}
In [26]:
os.system("echo '%s' | dot -Tpng > graf8.png" % s3)
Out[26]:
0
In [27]:
Image(filename="graf8.png")
Out[27]:
In [28]:
os.system("echo '%s' | dot -Kcirco -Tpng > graf9.png" % s3)
Out[28]:
0
In [29]:
Image(filename="graf9.png")
Out[29]:

neke opcije za prikaz bridova

In [30]:
s4="""graph {\n node [width=0.3,height=0.3 fontsize=10, fontcolor=red,fillcolor=yellow,style=filled, margin=0]\n 
edge [color=blue,style=bold,tailport=s,headport=n]\n "0" [label="root"];\n  
"1" [label="1",shape=hexagon,margin=0.2,fontsize=18];\n  
"2" [label="2", fillcolor=mintcream, fontcolor=purple];\n  "3" [label="3",shape=house];\n  
"4" [label="4", shape=doublecircle];\n\n  "0" -- "1";\n  "0" -- "2";\n  
"0" -- "3";\n  "1" -- "1";\n  "1" -- "1";\n  "1" -- "1";\n  "2" -- "2";\n  "2" -- "4";\n  "2" -- "4";\n  
"3" -- "4";\n  "3" -- "4";\n  "3" -- "4";\n}"""
In [31]:
print(s4)

graph {
 node [width=0.3,height=0.3 fontsize=10, fontcolor=red,fillcolor=yellow,style=filled, margin=0]
 
edge [color=blue,style=bold,tailport=s,headport=n]
 "0" [label="root"];
  
"1" [label="1",shape=hexagon,margin=0.2,fontsize=18];
  
"2" [label="2", fillcolor=mintcream, fontcolor=purple];
  "3" [label="3",shape=house];
  
"4" [label="4", shape=doublecircle];

  "0" -- "1";
  "0" -- "2";
  
"0" -- "3";
  "1" -- "1";
  "1" -- "1";
  "1" -- "1";
  "2" -- "2";
  "2" -- "4";
  "2" -- "4";
  
"3" -- "4";
  "3" -- "4";
  "3" -- "4";
}
In [32]:
os.system("echo '%s' | dot -Tpng > graf10.png" % s4)
Out[32]:
0
In [33]:
Image(filename="graf10.png")
Out[33]:
In [34]:
s5="""graph {\n node [width=0.3,height=0.3 fontsize=10, fontcolor=red,fillcolor=yellow,style=filled, margin=0]\n 
edge [color=blue,fontsize=10]\n "0" [label="root"];\n  
"1" [label="1",shape=hexagon,margin=0.2,fontsize=18];\n  "2" [label="2", fillcolor=mintcream, fontcolor=purple];\n  
"3" [label="3",shape=house];\n  "4" [label="4", shape=doublecircle];\n\n  
"0" -- "1" [taillabel="tri",labelangle=10,labelfontcolor=red,labeldistance=4];\n  
"0" -- "2" [label="dva",decorate=true];\n  "0" -- "3";\n  "1" -- "1";\n  
"1" -- "1" [style=dotted];\n  "1" -- "1";\n  "2" -- "2";\n  "2" -- "4";\n  
"2" -- "4";\n  "3" -- "4";\n  "3" -- "4";\n  "3" -- "4";\n}"""
In [35]:
print(s5)

graph {
 node [width=0.3,height=0.3 fontsize=10, fontcolor=red,fillcolor=yellow,style=filled, margin=0]
 
edge [color=blue,fontsize=10]
 "0" [label="root"];
  
"1" [label="1",shape=hexagon,margin=0.2,fontsize=18];
  "2" [label="2", fillcolor=mintcream, fontcolor=purple];
  
"3" [label="3",shape=house];
  "4" [label="4", shape=doublecircle];

  
"0" -- "1" [taillabel="tri",labelangle=10,labelfontcolor=red,labeldistance=4];
  
"0" -- "2" [label="dva",decorate=true];
  "0" -- "3";
  "1" -- "1";
  
"1" -- "1" [style=dotted];
  "1" -- "1";
  "2" -- "2";
  "2" -- "4";
  
"2" -- "4";
  "3" -- "4";
  "3" -- "4";
  "3" -- "4";
}
In [36]:
os.system("echo '%s' | dot -Tpng > graf11.png" % s5)
Out[36]:
0
In [37]:
Image(filename="graf11.png")
Out[37]:

Usmjereni graf

In [38]:
digraf1=DiGraph({0:[1,2,3],1:[1,1,1],2:[2,4,4],3:[4,4,4]})
In [39]:
digraf1.plot(graph_border=True,vertex_size=300)
Out[39]:
In [40]:
s6=digraf1.graphviz_string()
print(s6)

digraph {
  node_0  [label="0"];
  node_1  [label="1"];
  node_2  [label="2"];
  node_3  [label="3"];
  node_4  [label="4"];

  node_0 -> node_1;
  node_0 -> node_2;
  node_0 -> node_3;
  node_1 -> node_1;
  node_1 -> node_1;
  node_1 -> node_1;
  node_2 -> node_2;
  node_2 -> node_4;
  node_2 -> node_4;
  node_3 -> node_4;
  node_3 -> node_4;
  node_3 -> node_4;
}
In [41]:
os.system("echo '%s' | dot -Tpng > digraf1.png" % s6)
Out[41]:
0
In [42]:
Image(filename="digraf1.png")
Out[42]:
In [43]:
s7="""digraph {\n edge [color=blue,fontsize=10,arrowhead=vee]\n 
"0" [label="0"];\n  "1" [label="1"];\n  "2" [label="2"];\n  "3" [label="3"];\n  
"4" [label="4"];\n "0" -> "1";\n  "0" -> "2";\n  
"0" -> "3" [dir=both,arrowhead=odiamond,arrowtail=dot,color=red];\n  
"1" -> "1";\n  "1" -> "1";\n  "1" -> "1";\n  "2" -> "2";\n  
"2" -> "4" [headlabel="2->4",labelangle=20,labeldistance=4];\n  
"2" -> "4";\n  "3" -> "4";\n "3" -> "4";\n  "3" -> "4";\n}"""
In [44]:
print(s7)

digraph {
 edge [color=blue,fontsize=10,arrowhead=vee]
 
"0" [label="0"];
  "1" [label="1"];
  "2" [label="2"];
  "3" [label="3"];
  
"4" [label="4"];
 "0" -> "1";
  "0" -> "2";
  
"0" -> "3" [dir=both,arrowhead=odiamond,arrowtail=dot,color=red];
  
"1" -> "1";
  "1" -> "1";
  "1" -> "1";
  "2" -> "2";
  
"2" -> "4" [headlabel="2->4",labelangle=20,labeldistance=4];
  
"2" -> "4";
  "3" -> "4";
 "3" -> "4";
  "3" -> "4";
}
In [45]:
os.system("echo '%s' | dot -Tpng > digraf2.png" % s7)
Out[45]:
0
In [46]:
Image(filename="digraf2.png")
Out[46]:
In [47]:
s8="""digraph {\n node [style=filled,fillcolor=yellow] edge [color=blue,fontsize=10,arrowhead=vee]\n 
"0" [label="0"];\n  "1" [label="1"];\n  "2" [label="2"];\n  "3" [label="3"];\n  "4" [label="4"];\n 
"0" -> "1"[weight=2];\n  "0" -> "2";\n  "0" -> "3" [dir=both,arrowhead=odiamond,arrowtail=dot,color=red];\n  
"1" -> "1";\n  "1" -> "1";\n  "1" -> "1";\n  "2" -> "2";\n  
"2" -> "4" [headlabel="2->4",labelangle=35,labeldistance=5];\n  
"2" -> "4";\n  "3" -> "4";\n "3" -> "4";\n  "3" -> "4";\n}"""
In [48]:
print(s8)

digraph {
 node [style=filled,fillcolor=yellow] edge [color=blue,fontsize=10,arrowhead=vee]
 
"0" [label="0"];
  "1" [label="1"];
  "2" [label="2"];
  "3" [label="3"];
  "4" [label="4"];
 
"0" -> "1"[weight=2];
  "0" -> "2";
  "0" -> "3" [dir=both,arrowhead=odiamond,arrowtail=dot,color=red];
  
"1" -> "1";
  "1" -> "1";
  "1" -> "1";
  "2" -> "2";
  
"2" -> "4" [headlabel="2->4",labelangle=35,labeldistance=5];
  
"2" -> "4";
  "3" -> "4";
 "3" -> "4";
  "3" -> "4";
}
In [49]:
os.system("echo '%s' | dot -Kcirco -Tpng > digraf3.png" % s8)
Out[49]:
0
In [50]:
Image(filename="digraf3.png")
Out[50]:

Petersenov graf

In [51]:
P=graphs.PetersenGraph()
P.plot(graph_border=True,figsize=[4,4])
Out[51]:
In [52]:
Pstr=P.graphviz_string()
print(Pstr)

graph {
  node_0  [label="0"];
  node_1  [label="1"];
  node_2  [label="2"];
  node_3  [label="3"];
  node_4  [label="4"];
  node_5  [label="5"];
  node_6  [label="6"];
  node_7  [label="7"];
  node_8  [label="8"];
  node_9  [label="9"];

  node_0 -- node_1;
  node_0 -- node_4;
  node_0 -- node_5;
  node_1 -- node_2;
  node_1 -- node_6;
  node_2 -- node_3;
  node_2 -- node_7;
  node_3 -- node_4;
  node_3 -- node_8;
  node_4 -- node_9;
  node_5 -- node_7;
  node_5 -- node_8;
  node_6 -- node_8;
  node_6 -- node_9;
  node_7 -- node_9;
}
In [53]:
os.system("echo '%s' | dot -Tpng > petersen.png" % Pstr)
Out[53]:
0
In [54]:
Image(filename="petersen.png")
Out[54]:
In [55]:
Pstr2="""graph {\n  "0" [label="0"];\n  "1" [label="1",shape=box,style=filled];\n  "2" [label="2"];\n  "3" [label="3"];\n 
"4" [label="4"];\n  "5" [label="5"];\n  "6" [label="6"];\n  "7" [label="7"];\n  "8" [label="8"];\n  "9" [label="9"];\n\n  
"0" -- "1";\n  "0" -- "4";\n  "0" -- "5";\n  "1" -- "2";\n  "1" -- "6";\n  "2" -- "3";\n  "2" -- "7";\n  "3" -- "4";\n  
"3" -- "8";\n  "4" -- "9";\n  "5" -- "7";\n  "5" -- "8";\n "6" -- "8";\n  "6" -- "9";\n  
"7" -- "9";\n {rank=same; "0" "1" "2" "3" "4"}\n {rank=same; "5" "6" "7" "8" "9"}}"""
In [56]:
print(Pstr2)

graph {
  "0" [label="0"];
  "1" [label="1",shape=box,style=filled];
  "2" [label="2"];
  "3" [label="3"];
 
"4" [label="4"];
  "5" [label="5"];
  "6" [label="6"];
  "7" [label="7"];
  "8" [label="8"];
  "9" [label="9"];

  
"0" -- "1";
  "0" -- "4";
  "0" -- "5";
  "1" -- "2";
  "1" -- "6";
  "2" -- "3";
  "2" -- "7";
  "3" -- "4";
  
"3" -- "8";
  "4" -- "9";
  "5" -- "7";
  "5" -- "8";
 "6" -- "8";
  "6" -- "9";
  
"7" -- "9";
 {rank=same; "0" "1" "2" "3" "4"}
 {rank=same; "5" "6" "7" "8" "9"}}
In [57]:
os.system("echo '%s' | dot -Tpng > petersen2.png" % Pstr2)
Out[57]:
0
In [58]:
Image(filename="petersen2.png")
Out[58]:
In [59]:
os.system("echo '%s' | dot -Kcirco -Tpng > petersen3.png" % Pstr2)
Out[59]:
0
In [60]:
Image(filename="petersen3.png")
Out[60]:
In [61]:
Pstr3="""graph {\n splines=true\n node [width=0.3,height=0.2,margin=0]\n 
"0" [label="0"];\n  "1" [label="1",shape=box,style=filled];\n  "2" [label="2"];\n  
"3" [label="3"];\n  "4" [label="4"];\n  "5" [label="5"];\n  "6" [label="6"];\n  
"7" [label="7"];\n  "8" [label="8"];\n  "9" [label="9"];\n\n  "0" -- "1";\n  
"0" -- "4";\n  "0" -- "5";\n  "1" -- "2";\n  "1" -- "6";\n  "2" -- "3";\n  
"2" -- "7";\n  "3" -- "4";\n  "3" -- "8";\n  "4" -- "9";\n  "5" -- "7";\n  
"5" -- "8";\n "6" -- "8";\n  "6" -- "9";\n  "7" -- "9";}"""
In [62]:
print(Pstr3)

graph {
 splines=true
 node [width=0.3,height=0.2,margin=0]
 
"0" [label="0"];
  "1" [label="1",shape=box,style=filled];
  "2" [label="2"];
  
"3" [label="3"];
  "4" [label="4"];
  "5" [label="5"];
  "6" [label="6"];
  
"7" [label="7"];
  "8" [label="8"];
  "9" [label="9"];

  "0" -- "1";
  
"0" -- "4";
  "0" -- "5";
  "1" -- "2";
  "1" -- "6";
  "2" -- "3";
  
"2" -- "7";
  "3" -- "4";
  "3" -- "8";
  "4" -- "9";
  "5" -- "7";
  
"5" -- "8";
 "6" -- "8";
  "6" -- "9";
  "7" -- "9";}
In [63]:
os.system("echo '%s' | dot -Ktwopi -Tpng > petersen4.png" % Pstr2)
Out[63]:
0
In [64]:
Image(filename="petersen4.png")
Out[64]:
In [65]:
os.system("echo '%s' | dot -Ktwopi -Tpng > petersen5.png" % Pstr3)
Out[65]:
0
In [66]:
Image(filename="petersen5.png")
Out[66]:

Graf s puno vrhova i bridova

random graf sa 200 vrhova i 500 bridova

In [67]:
graf2=graphs.RandomGNM(200,500)
In [68]:
graf2.plot(graph_border=True)
Out[68]:
In [69]:
graf2.plot(graph_border=True,vertex_labels=False,vertex_size=10)
Out[69]:

Graphviz-u je ipak jako stalo da se svi vrhovi i bridovi čim jasnije vide pa je zato i konačna slika većih dimenzija

In [70]:
os.system("echo '%s' | dot -Tpng > graf_random.png" % graf2.graphviz_string())
Out[70]:
0
In [71]:
Image(filename="graf_random.png")
Out[71]:

radijalni raspored vrhova ipak nije u ovom slučaju najbolje rješenje

In [72]:
os.system("echo '%s' | dot -Ktwopi -Tpng > graf_random2.png" % graf2.graphviz_string())
Out[72]:
0
In [73]:
Image(filename="graf_random2.png")
Out[73]:
In [74]:
os.system("echo '%s' | dot -Kfdp -Tpng > graf_random3.png" % graf2.graphviz_string())
Out[74]:
0
In [75]:
Image(filename="graf_random3.png")
Out[75]:

možemo pomoću opcije splines=true dobiti ljepšu sliku. Crtanje slike može malo dulje trajati u ovom slučaju pa budite strpljivi.

In [76]:
string3=graf2.graphviz_string()[0:10]+'splines=true\n '+graf2.graphviz_string()[10:]
In [77]:
os.system("echo '%s' | dot -Kfdp -Tpng > graf_random4.png" % string3)
Out[77]:
0
In [78]:
Image(filename="graf_random4.png")
Out[78]:

NetworkX

Navest ćemo nekoliko primjera korištenja NetworkX modula za crtanje grafova unutar SAGE-a. Taj pythonov modul smo već ranije koristili i koristit ćemo ga i kasnije na puno mjesta za razne druge probleme iz teorije grafova.

In [79]:
import networkx as nx
from pylab import *
In [80]:
papus=nx.pappus_graph()
In [81]:
papus.edges()
Out[81]:
EdgeView([(0, 1), (0, 17), (0, 5), (1, 2), (1, 8), (2, 3), (2, 13), (3, 4), (3, 10), (4, 5), (4, 15), (5, 6), (6, 7), (6, 11), (7, 8), (7, 14), (8, 9), (9, 10), (9, 16), (10, 11), (11, 12), (12, 13), (12, 17), (13, 14), (14, 15), (15, 16), (16, 17)])
In [82]:
nx.draw(papus,with_labels=True,node_color='y')

postoji također puno dodatnih opcija za šminkanje grafa. Napišite help(nx.draw), help(nx.draw_networkx) za popis dodatnih opcija ili pogledajte na web stranicama help o matplotlib i networkx modulima.

In [83]:
figure(figsize=(5,5))
nx.draw_circular(papus,node_color="yellow",node_shape='v',node_size=700,edge_cmap=cm.Spectral, 
                 edge_color=range(papus.number_of_edges()),edgecolors='k',with_labels=True)
In [84]:
figure(figsize=(5,5))
nx.draw_spring(papus,with_labels=True,node_color='y')

primjeri grafova s puno vrhova i bridova

In [85]:
geom=nx.random_geometric_graph(200,0.14)
In [86]:
geom.number_of_nodes(),geom.number_of_edges()
Out[86]:
(200, 1086)
In [87]:
figure(figsize=(8,8))
nx.draw_random(geom,node_size=10)

Pregledniju sliku dobijemo pomoću Graphviz-a.

In [88]:
geomSage=Graph(Matrix(nx.to_numpy_matrix(geom,dtype=int)))
In [89]:
os.system("echo '%s' | dot -Tpng > geom.png" % geomSage.graphviz_string())
Out[89]:
0
In [90]:
Image(filename="geom.png")
Out[90]:
In [91]:
gr=nx.Graph()
bridovi=[(randint(k+1),k+2) for k in range(1000)]
figure(figsize=(8,8))
gr.add_edges_from(bridovi)
nx.draw_random(gr,node_size=15,edgecolors='k')
In [92]:
gr.number_of_nodes(),gr.number_of_edges()
Out[92]:
(1002, 1000)
In [93]:
figure(figsize=(8,8))
gr.add_edges_from(bridovi)
nx.draw_circular(gr,node_size=15,node_color="yellow",edgecolors='k')

Pregledniju sliku dobijemo ponovo pomoću Pygraphviz-a.

In [94]:
grSage=Graph(Matrix(nx.to_numpy_matrix(gr)))
In [95]:
os.system("echo '%s' | dot -Tpng > GRgeom.png" % grSage.graphviz_string())
Out[95]:
0
In [96]:
Image(filename='GRgeom.png')
Out[96]:
In [ ]: