printmaze(makemaze(10,10))
import numpy as np
import random as rn
Több lehetőség is van, mindnek megvannak az előnyei és hátrányai.
Egy listában tároljuk a gráf éleit.
graph_ellista=[("a","b"),("b","c"),("c","d"),("d","b"),("b","e")]
def maxfok1(l):
d={}
for el in l:
if el[0] in d:
d[el[0]]=d[el[0]]+1
else:
d[el[0]]=1
if el[1] in d:
d[el[1]]=d[el[1]]+1
else:
d[el[1]]=1
return max(d,key=lambda x:d[x])
maxfok1(graph_ellista)
Minden csúcshoz felírjuk a szomszédait.
graph = { "a" : ["c"],
"b" : ["c", "e"],
"c" : ["a", "b", "d", "e"],
"d" : ["c"],
"e" : ["c", "b"],
"f" : []
}
def maxfok2(l):
return max(l,key=lambda x: len(l[x]) )
maxfok2(graph)
usa={"AL" : [ "FL", "GA", "TN", "MS" ],
"AK" : [ ],
"AZ" : [ "NM", "UT", "NV", "CA" ],
"AR" : [ "LA", "MS", "TN", "MO", "OK", "TX" ],
"CA" : [ "AZ", "NV", "OR" ],
"CO" : [ "NM", "OK", "KS", "NE", "WY", "UT" ],
"CT" : [ "RI", "MA", "NY" ],
"DE" : [ "NJ", "PA", "MD" ],
"DC" : [ "MD", "VA" ],
"FL" : [ "GA", "AL" ],
"GA" : [ "SC", "NC", "TN", "AL", "FL" ],
"HI" : [ ],
"ID" : [ "WA", "OR", "NV", "UT", "WY", "MT" ],
"IL" : [ "WI", "IA", "MO", "KY", "IN" ],
"IN" : [ "IL", "KY", "OH", "MI" ],
"IA" : [ "MN", "SD", "NE", "MO", "IL", "WI" ],
"KS" : [ "OK", "MO", "NE", "CO" ],
"KY" : [ "TN", "VA", "WV", "OH", "IN", "IL", "MO" ],
"LA" : [ "MS", "AR", "TX" ],
"ME" : [ "NH" ],
"MD" : [ "DE", "PA", "WV", "VA", "DC" ],
"MA" : [ "NH", "VT", "NY", "CT", "RI" ],
"MI" : [ "WI", "IN", "OH" ],
"MN" : [ "ND", "SD", "IA", "WI" ],
"MS" : [ "AL", "TN", "AR", "LA" ],
"MO" : [ "AR", "TN", "KY", "IL", "IA", "NE", "KS", "OK" ],
"MT" : [ "ID", "WY", "SD", "ND" ],
"NE" : [ "KS", "MO", "IA", "SD", "WY", "CO" ],
"NV" : [ "AZ", "UT", "ID", "OR", "CA" ],
"NH" : [ "VT", "MA", "ME" ],
"NJ" : [ "NY", "PA", "DE" ],
"NM" : [ "TX", "OK", "CO", "AZ" ],
"NY" : [ "PA", "NJ", "CT", "MA", "VT" ],
"NC" : [ "VA", "TN", "GA", "SC" ],
"ND" : [ "MT", "SD", "MN" ],
"OH" : [ "MI", "IN", "KY", "WV", "PA" ],
"OK" : [ "TX", "AR", "MO", "KS", "CO", "NM" ],
"OR" : [ "CA", "NV", "ID", "WA" ],
"PA" : [ "OH", "WV", "MD", "DE", "NJ", "NY" ],
"RI" : [ "MA", "CT" ],
"SC" : [ "NC", "GA" ],
"SD" : [ "NE", "IA", "MN", "ND", "MT", "WY" ],
"TN" : [ "AL", "GA", "NC", "VA", "KY", "MO", "AR", "MS" ],
"TX" : [ "LA", "AR", "OK", "NM" ],
"UT" : [ "AZ", "CO", "WY", "ID", "NV", "" ],
"VT" : [ "NY", "MA", "NH" ],
"VA" : [ "MD", "DC", "WV", "KY", "TN", "NC" ],
"WA" : [ "OR", "ID" ],
"WV" : [ "VA", "MD", "PA", "OH", "KY" ],
"WI" : [ "MN", "IA", "IL", "MI" ],
"WY" : [ "CO", "NE", "SD", "MT", "ID", "UT" ]}
maxfok2(usa)
graphszom=np.array([[0,0,1,1],[0,0,0,1],[1,0,0,1],[1,1,1,0]])
graphszom
def maxfok3(A):
return A.sum(axis=0).argmax()
maxfok3(graphszom)
Mint mindig a helyzettől függ, mindegyiknek van előnye is és hátránya is.
Szomszédsági mátrix
Szomszédsági lista
Több modul van, ami kifejezetten a gráfok kezelésére készült, ebből nézünk meg most egyet.
NetworkX a háttérben szomszédsági listákkal reprezentálja a gráfot:
"The graph internal data structures are based on an adjacency list representation and implemented using Python dictionary datastructures. The graph adjacency structure is implemented as a Python dictionary of dictionaries; the outer dictionary is keyed by nodes to values that are themselves dictionaries keyed by neighboring node to the edge attributes associated with that edge. This “dict-of-dicts” structure allows fast addition, deletion, and lookup of nodes and neighbors in large graphs. The underlying datastructure is accessed directly by methods (the programming interface “API”) in the class definitions. All functions, on the other hand, manipulate graph-like objects solely via those API methods and not by acting directly on the datastructure. This design allows for possible replacement of the ‘dicts-of-dicts’-based datastructure with an alternative datastructure that implements the same methods."
import networkx as nx # Gráfokhoz
import matplotlib.pyplot as plt # Rajzokhoz
import warnings # Valami okból a networkx kép rajzoló függvénye olyan kódot használ, ami elavult. Emiatt
warnings.simplefilter('ignore') # folyamatosan figyelmeztetéseket kapunk. Mivel ez minket nem igazán érdekel,
# ezért blokkoljuk őket.
Négy gráf adatszerkezet:
Graph
irányítatlan, nincsenek párhuzamost élek DiGraph
irányított, nincsenek párhuzamost élekMultiGraph
irányítatlan, vannak párhuzamost élekMultiDiGraph
irányított, vannak párhuzamost élekG=nx.Graph()
G.add_node(3) # Bármilyen hashelhető típus lehet node.
G.add_node("almafa") # Bármilyen hashelhető típus lehet node.
G.add_edge(1,2)
G.add_edges_from([(1,4),(1,3)])
G.add_edge(1,5)
nx.draw(G, with_labels=True, font_weight='bold')
G.remove_edge(1,2)
nx.draw(G, with_labels=True, font_weight='bold')
Bármilyen gráfhoz, élhez és csúcshoz tudunk attribútumokat rendelni. Ez sokszor hasznos, például, amikor súlyozott gráfokkal dolgozunk.
G.add_node("x", time='5pm')
G.nodes["x"]
G.add_edge(2, 3, weight=0.9) # specify edge data
G.add_edge(2, 7, color="green")
elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]
G.add_weighted_edges_from(elist)
G.edges() #Ezzel a függvénnyel elérjük az éleket, de nem tudjuk megváltoztatni őket.
G.nodes()
G.number_of_nodes()
print(G[3])
print(G.edges[2,3])
print(G.edges[2,3]["weight"])
G.edges[1, 4]['weight'] = 4
print(G.edges[1,4]["weight"])
for e in G.edges.items():
print(e)
for u, v, weight in G.edges.data('weight'):
if weight is not None:
print(u,v)
pass
G = nx.petersen_graph()
plt.subplot(121)
nx.draw(G, with_labels=True, font_weight='bold')
plt.subplot(122)
nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold')
G.degree()
degree_sequence = list(G.degree())
nb_nodes = len(degree_sequence)
nb_arr = len(G.edges())
avg_degree = np.mean(np.array(degree_sequence)[:,1])
med_degree = np.median(np.array(degree_sequence)[:,1])
max_degree = max(np.array(degree_sequence)[:,1])
min_degree = np.min(np.array(degree_sequence)[:,1])
print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))
print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))
print("Average degree : " + str(avg_degree))
print("Median degree : " + str(med_degree))
nx.shortest_path(G)
for l in nx.enumerate_all_cliques(G):
print(l)
n=10
T=nx.Graph()
T.add_nodes_from(range(n))
for i in range(1,n):
T.add_edge(i,rn.randrange(i))
nx.draw_planar(T, with_labels=True, width=1 )
nx.to_prufer_sequence(T)
nx.check_planarity(G)
draw(G, keywrds)
raw_circular(G, keywrds)
draw_planar(G, keywrds)
draw_random(G, keywrds)
draw_spectral(G, keywrds)
draw_spring(G, keywrds)
draw_shell(G, keywrds)
g = nx.Graph()
g.add_nodes_from(usa.keys())
for k, v in usa.items():
g.add_edges_from(([(k, t) for t in v]))
nx.draw_planar(g, with_labels=True, width=1 )
G = nx.erdos_renyi_graph(20, 0.3)
color_map = []
edge_map = []
for edge in G.edges():
if rn.randrange(2)%2==0:
edge_map.append('blue')
else:
edge_map.append('green')
for node in G:
if rn.randrange(2)%2==0:
color_map.append('blue')
else:
color_map.append('green')
nx.draw(G, node_color=color_map,edge_color=edge_map, with_labels=True)
Sokszor nem éri meg külön felépíteni egy gráfot, végrehajthatjuk az algoritmust magán az adatokon. Példaképpen most készítünk egy labirintust mélységi bejárás segítségével.
# labirintus rajzoló. Egy 0/1/2 numpy tömböt vár. 0-semmi, 1-fal, 2-pozíció
def printmaze(a):
def selector(c):
if c==0:
return ' '
if c==1:
return chr(0x2588)
if c==2:
return "x"
for row in a:
print("".join([selector(c) for c in row]))
# print("".join([" " if c==0 else chr(0x2B1B) for c in row]))
printmaze(np.array([[1,1,1],[1,0,1],[1,1,1]]))
#Labirintus
def makemaze(w=16,h=8):
maze=np.ones((2*w+1,2*h+1))
vis=np.zeros((2*w+1,2*h+1))
def walk(x, y):
vis[x][y] = 1
maze[x,y]=0
d = [(x - 2, y), (x, y + 2), (x + 2, y), (x, y - 2)]
rn.shuffle(d)
for (xx, yy) in d:
if (not xx in range(2*w+1)) or (not yy in range(2*h+1)) or vis[xx][yy]:
continue
if xx == x:
maze[x][max(y, yy)-1] = 0
if yy == y:
maze[max(x, xx)-1][y] = 0
walk(xx, yy)
walk(2*rn.randrange(w)+1, 2*rn.randrange(h)+1)
return maze
printmaze(makemaze(4,40))
def makemaze2(w=16,h=8,entry=0,inner=0):
maze=np.ones((2*w+1,2*h+1))
vis=np.zeros((2*w+1,2*h+1))
def walk(x, y):
vis[x][y] = 1
maze[x,y]=0
d = [(x - 2, y), (x, y + 2), (x + 2, y), (x, y - 2)]
rn.shuffle(d)
for (xx, yy) in d:
if (not xx in range(2*w+1)) or (not yy in range(2*h+1)) or vis[xx][yy]:
continue
if xx == x:
maze[x][max(y, yy)-1] = 0
if yy == y:
maze[max(x, xx)-1][y] = 0
walk(xx, yy)
walk(2*rn.randrange(w)+1, 2*rn.randrange(h)+1)
### bejáratok
for i in range(entry):
if rn.randrange(2)==0:
pos=rn.randrange(h)
if rn.randrange(2)==0:
maze[2*pos+1,0]=0
else:
maze[2*pos+1,-1]=0
else:
pos=rn.randrange(w)
if rn.randrange(2)==0:
maze[0,2*pos+1]=0
else:
maze[-1,2*pos+1]=0
### belső körökhöz fal törlés
for i in range(inner):
if rn.randrange(2)==0:
maze[2*rn.randrange(h-1)+2,2*rn.randrange(w)+1]=0
else:
maze[2*rn.randrange(h)+1,2*rn.randrange(w-1)+2]=0
return maze
printmaze(makemaze2(10,10,2,3))