Добрый день, уважаемые читатели. Наверняка все слышали о такой «отрасли» математики, как теория графов. Так вот сегодня мы займемся введением в программирование графов на Python.

Сам по себе граф — множество точек, некоторые из которых (или все) соединены рёбрами. Да, вот так всё просто. Теория графов занимается изучением различных свойств графов.

Подпишись на группу Вконтакте и Телеграм-канал. Там еще больше полезного контента для программистов.

А на YouTube-канале ты найдешь обучающие видео по программированию. Подписывайся!

Установка NetworkX

NetworkX — библиотека, специально предназначена для работы с графами. Установить её можно с помощью команды:

pip/conda install networkx

Введение

Теперь перейдём к списку того, чем мы будем заниматься.

Сегодня в статье:

  • создание простого графа
  • визуализация графа
  • полносвязный граф
  • граф Эрдьёша-Реньи
  • проверка на полносвязность

Создание простого графа

Для начала импортируем все необходимые нам инструменты:

In[1]:
import itertools

import networkx as nx
import numpy.random as rnd
import matplotlib.pyplot as plt

Создадим экземпляр класса nx.Graph (именно он будет являться рабочим классом):

In[2]:
graph = nx.Graph()

graph

Out[2]:
networkx.classes.graph.Graph at 0x8ad1518>

Чтобы добавить вершину, используем метод add_node().

In[3]:
graph.add_node('A')
graph.add_node('B')
graph.add_node('C')

graph.nodes()

Out[3]:
NodeView(('A', 'B', 'C', 'D', 'E'))

Т.к. метод add_edge, забегая наперёд, соединяет первую вершину со второй, но не наоборот, напишем свою функцию для добавления рёбер.

In[5]:
def add_edge(f_item, s_item, graph=None):
  graph.add_edge(f_item, s_item)
  graph.add_edge(s_item, f_item) 

И теперь добавим несколько рёбер, а также визуализируем граф:

In[6]:
add_edge('A', 'B', graph=graph)
add_edge('B', 'C', graph=graph)
add_edge('B', 'D', graph=graph)
add_edge('D', 'E', graph=graph)

nx.draw_circular(graph,
         node_color='red',
         node_size=1000,
         with_labels=True)

Out[6]:

Также мы можем создать вершины графа, воспользовавшись методом add_nodes_from(), передав туда итерируемый объект. Также работает и с методом add_edges_from(), где аргумент должен содержать кортежи с вершинами.

In[7]:
cities = {'A':(0, 20),
     'B':(15, 24),
     'C':(16, 41),
     'D':(10, 40)}

graph = nx.Graph()
graph.add_nodes_from(cities)

Теперь добавим рёбра с весами (в нашем случае это расстояние между городами А, В, С и D):

In[8]:
kilometres = {('A', 'B', 15),
              ('B', 'C', 16),
              ('B', 'D', 25),
              ('C', 'D', 14),
              ('D', 'A', 18)}

graph.add_weighted_edges_from(kilometres)

Теперь изобразим этот граф.

Примечание. Для визуализации графа вам необходимо импортировать Matplotlib либо GraphDot.

In[9]:
nx.draw_circular(graph,
         node_color='red',
         node_size=1000,
         with_labels=True)

Out[9]:

Создание полносвязного графа

Полносвязный граф — граф, где каждая вершина соединена с каждой другой. Свойства полносвязного графа мы разберём попозже, а тем временем реализуем функцию для его построения.

In[10]:
def complete_graph(N: int) -> nx.Graph:
  graph = nx.Graph()
   
  N_range = range(N)
   
  all_pairs = itertools.permutations(N_range, 2)
   
  graph.add_nodes_from(N_range)
  graph.add_edges_from(all_pairs)
   
  return graph

itertools.permutations(arr[, len], n) — возвращает все возможные перестановки элементов arr длиной n.

Визуализируем полносвязный граф с 15-ю вершинами:

In[11]:
graph = complete_graph(15)

nx.draw_circular(graph, 
         node_color='y',
         node_size=750,
         with_labels=True)

Out[11]:

Граф Эрдьёша-Реньи

Граф Эрдьёша-Реньи — граф, который построен моделью Эрдьёша-Реньи, которых существует два вида — G(n, p) и G(n, m), где n — кол-во вершин графа, p — вероятность того, что две вершины соединены, а m — кол-во рёбер графа.

Сегодня мы рассмотрим первый случай, а именно модель G(n, p).

In[12]:
def random_graph(n:int, p:double) -> nx.Graph:
  graph = nx.Graph()
   
  N_range = range(n)
  graph.add_nodes_from(N_range)
   
  for pair in itertools.permutations(N_range, 2):
    if rnd.random() < p:
      graph.add_edge(*pair)
   
  return graph

Мы опять воспользовались генерацией всех возможных пар, а также использовали генератор случайных чисел для отбора рёбер в зависимости от вероятности их соединения.

Теперь посмотрим, как работает функция генерации:

In[13]:
graph = random_graph(7, 0.5)

nx.draw_circular(graph,
         node_color='y',
         node_size=1000,
         with_labels=True)

Out[13]:

Примечание. Попробуйте поиграть с кол-вом вершин и вероятностью попарного соединения.

Определение полноты графа

Теперь определим критерий, когда граф является полным.

В полном графе 𝑛(𝑛−1)/2 рёбер, т.к. каждая вершина соединена с каждой, а при таком подсчёте одно ребро считается дважды.

Мы уже знаем о методах nodes() и edges(), возвращающие список вершин и рёбер. Поэтому с помощью функции len() мы можем узнать кол-во вершин и рёбер.

In[14]:
def is_complete(graph:nx.Graph) -> bool:
  edges = len(graph.edges())
  nodes = len(graph.nodes())
   
  return edges == nodes * (nodes - 1) / 2

Помните функцию для построения полного графа? Давайте используем её, дабы протестировать нашу булеву функцию.

In[15]:
is_complete(complete_graph(5))

Out[15]:
True
In[16]:
is_complete(random_graph(10, 0.7))

Out[16]:
False

Заключение

Вот так мы и познакомились с азами работы с библиотекой NetworkX. Если вы поддержите эту статью оценками и комментариями, то будем развивать эту тему :)

Документ с кодом из статьи находится по ссылке.

Также рекомендую прочитать статью Алгоритм Евклида и линейное представление НОД. А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.

Рубрики: Python