In [4]:
printmaze(makemaze(10,10))
printmaze(makemaze(10,10))
import numpy as np
import random as rn
import networkx as nx
Több lehetőség is van, mindnek megvannak az előnyei és hátrányai.
G = nx.erdos_renyi_graph(20, 0.3)
nx.draw(G)
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)
'b'
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)
'c'
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
array([[0, 0, 1, 1],
[0, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 1, 0]])
def maxfok3(A):
return A.sum(axis=0).argmax()
maxfok3(graphszom)
3
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
graph = { "a" : ["c"],
"b" : ["c", "e","f"],
"c" : ["a", "b", "d", "e"],
"d" : ["c"],
"e" : ["c", "b"],
"f" : ["b"]
}
G = nx.from_dict_of_lists(graph)
nx.draw(G,with_labels=True,font_color='white',font_size=20,node_size=500)
visited = set() # Meglátogatott csúcsok.
queue = [] #Egy sor adatszerkezet, őket még fel kell dolgozni
def bfs(visited, graph, node):
visited.add(node)
queue.append(node)
while queue:
s = queue.pop(0)
print (s, end = " ")
for neighbour in graph[s]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
# Driver Code
bfs(visited, graph, 'e')
e c b a d f
G = nx.from_dict_of_lists(graph)
nx.draw(G,with_labels=True,font_color='white',font_size=20,node_size=500)
visited = set() # Meglátogatott csúcsok
def dfs(visited, graph, node):
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
dfs(visited, graph, 'a')
a c b e f d
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
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("a") # 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_color='white',font_size=20,node_size=500)
G.remove_edge(1,2)
nx.draw(G,with_labels=True,font_color= 'white',font_size=20,node_size=500)
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',col="white")
G.nodes["x"]
{'time': '5pm', 'col': 'white'}
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.
EdgeView([(3, 1), (3, 2), ('a', 'b'), ('a', 'c'), (1, 4), (1, 5), (2, 7), ('b', 'c'), ('c', 'd')])
G.nodes()
NodeView((3, 'a', 1, 2, 4, 5, 'x', 7, 'b', 'c', 'd'))
G.number_of_nodes()
11
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"])
{1: {}, 2: {'weight': 0.9}}
{'weight': 0.9}
0.9
4
for e in G.edges.items():
print(e)
((3, 1), {})
((3, 2), {'weight': 0.9})
(('a', 'b'), {'weight': 5.0})
(('a', 'c'), {'weight': 1.0})
((1, 4), {'weight': 4})
((1, 5), {})
((2, 7), {'color': 'green'})
(('b', 'c'), {'weight': 3.0})
(('c', 'd'), {'weight': 7.3})
for u, v, weight in G.edges.data('weight'):
if weight is not None:
print(u,v)
pass
3 2 a b a c 1 4 b c c d
G = nx.petersen_graph()
plt.subplot(121)
nx.draw(G, with_labels=True,font_weight='bold',font_color='white',font_size=12,node_size=200)
plt.subplot(122)
nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold',font_color='white',font_size=12,node_size=200)
G.degree()
DegreeView({0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3, 7: 3, 8: 3, 9: 3})
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))
Number of nodes : 10 Number of edges : 15 Maximum degree : 3 Minimum degree : 3 Average degree : 3.0 Median degree : 3.0
nx.shortest_path(G)
{0: {0: [0],
1: [0, 1],
4: [0, 4],
5: [0, 5],
2: [0, 1, 2],
6: [0, 1, 6],
3: [0, 4, 3],
9: [0, 4, 9],
7: [0, 5, 7],
8: [0, 5, 8]},
1: {1: [1],
0: [1, 0],
2: [1, 2],
6: [1, 6],
4: [1, 0, 4],
5: [1, 0, 5],
3: [1, 2, 3],
7: [1, 2, 7],
8: [1, 6, 8],
9: [1, 6, 9]},
2: {2: [2],
1: [2, 1],
3: [2, 3],
7: [2, 7],
0: [2, 1, 0],
6: [2, 1, 6],
4: [2, 3, 4],
8: [2, 3, 8],
5: [2, 7, 5],
9: [2, 7, 9]},
3: {3: [3],
2: [3, 2],
4: [3, 4],
8: [3, 8],
1: [3, 2, 1],
7: [3, 2, 7],
0: [3, 4, 0],
9: [3, 4, 9],
5: [3, 8, 5],
6: [3, 8, 6]},
4: {4: [4],
0: [4, 0],
3: [4, 3],
9: [4, 9],
1: [4, 0, 1],
5: [4, 0, 5],
2: [4, 3, 2],
8: [4, 3, 8],
6: [4, 9, 6],
7: [4, 9, 7]},
5: {5: [5],
0: [5, 0],
7: [5, 7],
8: [5, 8],
1: [5, 0, 1],
4: [5, 0, 4],
2: [5, 7, 2],
9: [5, 7, 9],
3: [5, 8, 3],
6: [5, 8, 6]},
6: {6: [6],
1: [6, 1],
8: [6, 8],
9: [6, 9],
0: [6, 1, 0],
2: [6, 1, 2],
3: [6, 8, 3],
5: [6, 8, 5],
4: [6, 9, 4],
7: [6, 9, 7]},
7: {7: [7],
2: [7, 2],
5: [7, 5],
9: [7, 9],
1: [7, 2, 1],
3: [7, 2, 3],
0: [7, 5, 0],
8: [7, 5, 8],
4: [7, 9, 4],
6: [7, 9, 6]},
8: {8: [8],
3: [8, 3],
5: [8, 5],
6: [8, 6],
2: [8, 3, 2],
4: [8, 3, 4],
0: [8, 5, 0],
7: [8, 5, 7],
1: [8, 6, 1],
9: [8, 6, 9]},
9: {9: [9],
4: [9, 4],
6: [9, 6],
7: [9, 7],
0: [9, 4, 0],
3: [9, 4, 3],
1: [9, 6, 1],
8: [9, 6, 8],
2: [9, 7, 2],
5: [9, 7, 5]}}
for l in nx.enumerate_all_cliques(G):
print(l)
[0] [1] [2] [3] [4] [5] [6] [7] [8] [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]
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, font_weight='bold',font_color='white',font_size=12,node_size=600)
nx.to_prufer_sequence(T)
[1, 2, 4, 1, 2, 0, 1, 0]
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.from_dict_of_lists(usa)
print(nx.check_planarity(g))
plt.figure(1,figsize=(12,12))
nx.draw_planar(g, with_labels=True, width=1 ,font_weight='bold',font_color='white',font_size=12,node_size=500)
plt.show()
(True, <networkx.algorithms.planarity.PlanarEmbedding object at 0x000001E0B098B688>)
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 ,font_weight='bold',font_color='white',font_size=12,node_size=500)