How to Represent a Graph Data Structure in Python
Graph is an important data structure studied in Computer Science. Graph theory is an equally important topic in both mathematics and Computer Science.
Representing a graph in a program means finding a way to store the graph in a computer’s memory. Which is a prerequisite to working with graphs in…
Отображение графа на Python с networkx
Граф — это форма визуализации, позволяющая показывать и анализировать отношения между сущностями. Например, рисунок ниже показывает вклад редакторов Википедии на различных языках энциклопедии в июле 2013 года:
Можно сделать несколько наблюдений:
- Английский (en) — основной язык, на который переводятся все остальные языки; в то же время многие англоязычные материалы переводятся на другие языки.
- Китайский (zh) переводится на японский (ja), но не наоборот.
- И китайский, и японский материалы переведены на английский, и наоборот.
Я же расскажу о том, как для отображения графов использовать пакет networkx.
Установка networkx
Чтобы установить этот пакет, используйте команду pip:
Терминология
Прежде чем начать отрисовку графа, полезно знать некоторые основы.
На рисунке ниже показывается направленный граф, также известный как диграф, ребра которого имеют обозначенные стрелками направления.
- Узел — фундаментальный элемент графа, общеизвестный под названием вершина.
- Ребро — соединение узлов графа.
- Неориентированный граф не имеет направления между узлами, то есть не имеет стрелок, а его ребра двунаправлены.
Создание графа
Давайте шаг за шагом создадим граф.
Во-первых, создадим объект класса networkx.classes.graph.Graph:
Класс nx.Craph() создает неориентированный граф. Если захочется создать ориентированный, используйте класс nx.DiGraph(directed=True), который возвращает объект networkx.classes.digraph.DiGraph.
В этой статье поговорим об ориентированных графах.
Добавим узлы
Фрагмент кода ниже добавляет три узла без ребер:
Помимо функции add_node() для добавления индивидуальных узлов, чтобы добавить множество узлов, можно воспользоваться функцией add_nodes_from():
Сейчас у графа 5 узлов.
Добавим ребра
Теперь, когда узлы определены, определим ребра, чтобы соединить их:
Как и узлы, ребра можно добавлять по одному, при помощи add_edge(), или группами — при помощи add_edges_from() со списком кортежей, представляющих каждый узел.
Рисуем граф
Я покажу основы отображения сетевых графов при помощи пакета networkx. Начнем:
Вы увидите что-то такое:
Вот другое изображение того же графа:
Отображение меток
Само собой, граф без меток не очень полезен, если вообще полезен, поэтому давайте отрисуем метки:
- nx.draw_networkx_nodes() — рисует все узлы графа;
- nx.draw_networkx_labels() — рисует метки на каждом узле;
- nx.draw_networkx_edges() — рисует ребра, соединяющие узлы.
И теперь мы видим метку каждого узла:
Применение макетов
Помните, что функция draw() каждый раз использует разные макеты? Так вот, для графа можно указать конкретный макет:
Узлы упорядочены так, что по ним можно очертить круг:
Кроме того, график с круговой компоновкой можно нарисовать с помощью nx.draw_circular(), а не nx.draw():
Можно попробовать другие макеты:
- nx.draw_kamada_kawai(G, with_labels = True);
- nx.draw_planar(G, with_labels = True);
- nx.draw_random(G, with_labels = True);
- nx.draw_spectral(G, with_labels = True);
- nx.draw_spring(G, with_labels = True);
- nx.draw_shell(G, with_labels = True);
Разметка ребер
Ребра можно отметить при помощи nx.draw_networkx_edge_labels(). Фрагмент кода ниже размечает два ребра трех узлов:
Ориентированный граф
Иногда полезно построить ориентированный граф. В нашем примере ребра могут представлять рейсы между двумя городами. Ориентированный граф позволяет увидеть, какие рейсы идут из одного города в другой. Следующий фрагмент кода показывает наш пример в виде ориентированного графа:
Теперь вы видите, что есть рейсы из Сингапура в Сан-Франциско и наоборот; с другой стороны, есть рейсы из Риги в Сан-Франциско, но не наоборот:
Настройка узлов
По умолчанию узлы имеют синий цвет и довольно маленький размер. Настроить узлы и цвет ребра можно, передав словарь в функцию draw():
Сейчас узлы желтые и они больше, а ребра синие:
Очерчивание узлов
Если вы хотите обозначить узлы, вам нужно сделать это вручную, используя matplotlib. Следующий фрагмент кода задает размер рисунка 10 на 10 дюймов (ширина и высота), а затем функцией set_edgecolor() рисует контур каждого узла:
Теперь каждый узел обведен черным:
Если не установить размер рисунка, граф будет выглядеть так:
Раскрашивание узлов
Чтобы раскрасить каждый узел разными цветами, можно определить цветовую палитру, такую как в bokeh, и установить значение ключу словаря node_color, затем передав его в draw():
И теперь узлы графа раскрашены разными цветами:
Если захочется указать свой цвет, установите его вручную:
Вот и все на сегодня. А на наших курсах — полезная теория и много практики:
Name already in use
Preprocessing / Networkx.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Графы (сети), библиотека networkx
С использованием материалов Оксаны Дерезы
Что такое графы?
Чтобы что-то научно исследовать, мы строим модель, то есть упрощённую схему, исследуемого предмета. Карта — модель пространства и того, что в нём находится, грамматическое описание — модель реальной грамматической системы языка, а глоссированный текст — модель текста настоящего, произнесённого. В модель мы берём какие-то важные для нас данные, а другие отбрасываем, считая их неважными. Например, физики часто пренебрегают таким свойством предмета, как его размер, принимая во внимание только массу, скорость и ряд других характеристик, а сам объект считая «материальной точкой», то есть своего рода абстракцией (в реальности не может существовать предмет без пространственных характеристик).
Частотный словарь — тоже модель, это модель реального текста, в которой мы важными параметрами, которые мы взяли в нашу модель, считаем сами слова и частоту их употребления. Но при этом мы отказываемся от ряда других характеристик, которые, на самом деле, даже важнее, чем частотность, — это связи между словами.
Кажется, что это касается не только текста, но и многих других объектов реальности: связи между элементами системы важнее количества этих элементов. Посмотрите на любой сложный механизм. Скажем, самолёт. Что лучше даст нам представление о том, как он устроен: список всех винтиков, панелей и шарниров с указанием, сколько раз каждый из них задействован в конструкциии, или точный чертёж, из которого будет ясно, акэти винтики и панели соединяются друг сдругом и соединяются в единую систему? Очевидно, что второе.
Модель, которая не только описывает элементы системы, но и фиксирует связи между ними, называется графом или сетью. В терминах графов может быть описана любая система, в которой можно выделить
- элементы (в графе они называются узлами = вершинами = nodes = vertices)
- связи между ними (они именуются рёбрами = связями = edges = relations).
Самый близкий нам пример — социальная сеть (не просто же так она сеть), где пользователи — узлы,а наличие «дружбы» между пользователями — ребро. Чуть менее очевидные графы, с которыми мы сталкиваемся каждый день — метро и интернет.
Зачем нужны графы?
Прежде всего, графы любят за то, что их можно визуализировать, и в результате получается красивая картинка. Действительно, визуальный анализ уже может дать довольно много, и рассматривание такой картинки в некотором смысле уже научная работа.
Но не только. Рассматриванием картинок дело не ограничивается. Граф — это математический объект, в котором мы можем довольно много всего посчитать, и таким образом установить разные закономерности, доказать гипотезу. Это называется сетевым анализом.
Для того, чтобы превращать данные (любые формализованные данные) в граф, можно использовать библиотеку networkx . Вот ее документация. Это не единственная библиотека для работы с графами в питоне (вот полный список), но, кажется, самая простая и удобная.
Мы можем пойти двумя путями, в зависимости от того, положения, в котором находимся. Первая ситуация: у нас есть какие-то данные, и нам нужно превратить их в граф. Тогда уместно создать сначала пустой объект графа и туда постепенно что-то добавлять.
Реализация Graph в Python
Реализуйте взвешенную и невзвешенную структуру данных ориентированного Graph в Python.
В представлении Graph списком смежности каждая вершина Graph хранит список соседних вершин. Ниже приведено графическое представление соответствующего списка смежности для приведенного выше Graph:
1. Реализация ориентированного Graph
Ниже приведена реализация Python ориентированного Graph с использованием списка смежности: