evgenymarkov / pygraph Goto Github PK

Библиотека содержит такие структуры данных как неориентированный граф, ориентированный граф. Каждая вершина и ребро могут иметь атрибуты. Отдельно выделены 2 атрибута - вес и метка, а помимо них поддерживаются произвольные пользовательские.

Доступна следующая функциональность:

• добавление вершины
• добавление ребра
• удаление вершины
• удаление ребра
• получение списка вершин
• получение списка рёбер
• проверка наличия ребра
• проверка наличия вершины
• получение порядка(количества вершин)
• получение степени вершины неориентированного графа
• проверка на равенство с другим графом
• получение исходящей(выходящей) степени вершины ориентированного графа
• получение соседей вершины графа
• получение списка вершин, из которых есть рёбра в указанную вершину
• получшение графа, образованного сменой направления ребер
• получение дополнения графа до полного

Есть инструментарий для импорта и экспорта графов в формате dot. Реализована проверка связности, алгоритмы обхода графа в ширину и глубину, поиска кратчайшего пути, поиска всех путей, проверки является ли граф подграфом другого, а так же проверки 2-х графов на изоморфность.