Инфраструктура Python. Графы

Библиотека networkx (входящая в Anaconda) умеет почти все, что можно сделать с графами. Для визуализации ей еще следует поставить программу graphviz http://www.graphviz.org/Download_windows.php и библиотеку pydotplus. Также может пригодиться программа Gephi https://gephi.org/ .

pip instlal pydotplus
pip install pygraphviz
In [1]:
%pylab inline
import networkx, IPython, itertools, delegator
from io import BytesIO
import PIL
Populating the interactive namespace from numpy and matplotlib

Создание графов

Графы в networkx можно задавать вызовами add_edge,

In [2]:
G = networkx.Graph()
v1 = [21,4,14,0,31,46,1,34,2,3,27,19,47,46,17,11,41,12,31,0,34,18,8,14,23,40,0,18,48,35,42,24,25,32,25,44,17,6,44,34,12,39,43,39,26,34,10,6,13,2,40,15,16,32,32,29,1,23,8,10,49,22,10,15,40,20,0,30,1,43,33,42,28,39,28,4,38,11,5,1,47,12,0,22,20,33,33,34,18,8,23,6]
v2 = [25,5,39,20,44,47,11,49,42,17,25,15,23,11,32,17,24,4,11,47,27,41,40,0,49,27,5,28,6,11,18,0,17,1,0,32,45,28,17,5,13,40,40,25,33,7,8,32,12,0,39,30,8,39,23,9,8,34,34,37,5,1,24,23,0,29,11,42,29,40,24,18,37,1,21,0,31,47,23,33,45,48,31,11,40,45,24,22,19,26,37,39]
for i in range(len(v1)):
    G.add_edge(v1[i], v2[i])
# или g.add_edges_from(zip(v1, v2))
pos=networkx.nx_pydot.graphviz_layout(G)
networkx.draw(G, pos, with_labels=True, font_color='w')

из списка смежности,

In [3]:
G = networkx.from_edgelist([(0, 1), (1, 2), (2, 3), (2, 4)])
networkx.draw(G, pos=networkx.nx_pydot.graphviz_layout(G), with_labels=True, font_color='w')

из словаря смежности,

In [4]:
G = networkx.from_dict_of_lists({0: [1, 2, 3], 1: [2, 4], 2: [5, 6]})
networkx.draw(G, with_labels=True, font_color='w')

из матрицы смежности.

In [5]:
G = networkx.from_numpy_array(array(
[[0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
 [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
 [0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0],
 [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0]]))
networkx.draw(G, pos=networkx.nx_pydot.graphviz_layout(G), with_labels=True, font_color='w')

Библиотека networkx знает ряд именованых графов, умеет строить сетки, полные графы

In [6]:
def trydefault(fn, default=None):
    try:
        return fn()
    except:
        return default
In [7]:
named_graphs = {k: v() for k, v in networkx.__dict__.items()
    if k.endswith('_graph') and trydefault(v) and v().number_of_nodes() > 1}
figure(figsize=(16,16))
for i, (k, v) in enumerate(sorted(named_graphs.items())):
    subplot(5, (len(named_graphs) + 5 - 1) / 5, i + 1)
    title(k)
    networkx.draw(v, node_size=100)
In [8]:
figure(figsize=(16, 4))
subplot(151)
title('complete_graph(5)')
G = networkx.complete_graph(5)
networkx.draw(G)

subplot(152)
title('complete_bipartite_graph(3,3)')
G = networkx.complete_bipartite_graph(3, 3)
networkx.draw(G)

subplot(153)
title('grid_2d_graph(5,5)')
G = networkx.grid_2d_graph(5, 5)
networkx.draw(G, pos=networkx.nx_pydot.graphviz_layout(G))

subplot(154)
title('hexagonal_lattice_graph(3,3)')
G = networkx.hexagonal_lattice_graph(3, 3)
networkx.draw(G, pos=networkx.nx_pydot.graphviz_layout(G, prog='sfdp'))

subplot(155)
title('triangular_lattice_graph(3,3)')
G = networkx.triangular_lattice_graph(3, 3)
networkx.draw(G)

Умеет строить деревья по коду Прюфера

In [9]:
tree = networkx.algorithms.tree.coding.from_prufer_sequence([0,0,1,2,3,1,1,2,3,1])
print networkx.algorithms.tree.coding.to_prufer_sequence(tree)
networkx.draw(tree, pos=networkx.nx_pydot.graphviz_layout(tree), with_labels=True, node_color='r', font_color='w')
[0, 0, 1, 2, 3, 1, 1, 2, 3, 1]

Умеет перечислять неизоморфные деревья (существенно быстрее, чем с проверкой networkx.is_isomorphic)

In [10]:
figure(figsize=(16,8))
nonanes = [nonane for nonane in networkx.nonisomorphic_trees(9) if max(dict(nonane.degree()).values()) <= 4]
for i, nonane in enumerate(nonanes):
    subplot(5, 7, i + 1)
    networkx.draw(nonane, pos=networkx.nx_pydot.graphviz_layout(nonane), node_size=15)
print 'Isomeres count:', len(nonanes)
Isomeres count: 35

Свойства графов

In [11]:
G = networkx.house_x_graph()
networkx.draw(G, with_labels=True, font_color='w')
In [12]:
print G.number_of_edges(), G.edges()
print G.number_of_nodes(), G.nodes()
8 [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
5 [0, 1, 2, 3, 4]
In [13]:
print G.degree()
[(0, 3), (1, 3), (2, 4), (3, 4), (4, 2)]
In [14]:
print G.has_edge(1, 4)
print list(G.neighbors(1))
print list(networkx.common_neighbors(G, 1, 4))
False
[0, 2, 3]
[2, 3]
In [15]:
print networkx.adjacency_matrix(G).todense()
[[0 1 1 1 0]
 [1 0 1 1 0]
 [1 1 0 1 1]
 [1 1 1 0 1]
 [0 0 1 1 0]]
In [16]:
laplacian = networkx.laplacian_matrix(G).todense()
print laplacian
print 'Число остовных деревьев по теореме Кирхгофа', det(laplacian[1:,1:])
[[ 3 -1 -1 -1  0]
 [-1  3 -1 -1  0]
 [-1 -1  4 -1 -1]
 [-1 -1 -1  4 -1]
 [ 0  0 -1 -1  2]]
Число остовных деревьев по теореме Кирхгофа 40.0

Отображение графов

Можно отображать графы либо встроенным способом (networkx.draw), либо через graphviz (разными методами в каждом). DiGraph это орграф.

In [17]:
G = networkx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_node(5)

G.add_edge(1,2, color='red')
G.add_edge(1,3)
G.add_edge(2,4)
G.add_edge(1,5)

pos=networkx.nx_pydot.graphviz_layout(G, prog='dot')
networkx.draw(G, pos, node_size=800, with_labels=True, font_color='w', cmap='Dark2', node_color=range(len(G)))
In [18]:
G = networkx.pappus_graph()
figure(figsize=(16,8))
subplot(241); title('draw'); networkx.draw(G)
subplot(242); title('draw_circular'); networkx.draw_circular(G)
subplot(243); title('draw_networkx'); networkx.draw_networkx(G, font_color='w')
subplot(244); title('draw_random'); networkx.draw_random(G)
subplot(245); title('draw_shell'); networkx.draw_shell(G)
subplot(246); title('draw_spectral'); networkx.draw_spectral(G)
subplot(247); title('draw_spring'); networkx.draw_spring(G)
In [19]:
figure(figsize=(16,8))
for i, prog in enumerate('dot neato fdp sfdp twopi circo'.split()):
    subplot(2, 3, i + 1)
    title(prog)
    networkx.draw(
        G, pos=networkx.nx_pydot.graphviz_layout(G, prog=prog),
        node_size=400, cmap=cm.Spectral, node_color=range(len(G)), edge_color='gray'
    )