pygraph

A graph manipulation library in pure Python

Available on PyPI

Pygraph aims to be an easy-to-use and functional graph library that doesn't sacrifice advanced capabilities or usability in the process.

By implementing the library in pure Python, it can be installed without any dependencies aside from the Python core, enabling maximum ease of use.

Graph Types Supported:

Directed Graphs
Undirected Graphs

Common Algorithms Supported:

DFS
BFS
Minimum Spanning Tree
Connected Components
Biconnected Components
Articulation Vertices

Advanced algorithms supported will include:

Triconnected Components
Separation Pairs
Lipton-Tarjan Separator Theorem
Planarity Testing
Fully Dynamic Planarity Testing
Planar Embedding

Current Algorithm Support

Algorithm	Status
DFS	✅ Supported
BFS	✅ Supported
MST	✅ Supported
Connected Components	✅ Supported
Biconnected Components	✅ Supported
Triconnected Components	❌ Unsupported
Articulation Vertices	✅ Supported
Separation Pairs	❌ Unsupported
L-T Separator Theorem	❌ Unsupported
Planarity Testing	✅ Supported
Planar Embedding	❌ Unsupported
Fully-Dynamic Planarity Testing	❌ Unsupported

Installation && Usage

Installing the module is as easy as pip install pygraph

>>> import pygraph
>>> g = pygraph.build_chvatal_graph()
>>> pygraph.is_planar(g)
False

Running the Test Suite

The entire test suite is written using the standard library unittest module, so you should be able to run it with whichever framework you most prefer. We recommend nose.

With nose installed, navigate to the root of the project and run nosetests. It should recognize the tests subdirectory and run through the entire test suite.

All algorithm implementations should have test cases written and passing.

Contributions

Contributions are more than welcome! Algorithm suggestions, implementations, or even additional tests for existing algorithms are all great ways to contribute. Not a coder? That's fine too! This project is in dire need of documentation and examples.

Planarity Test Cases

The planarity testing algorithm is extremely complicated. As such, more tests with more graphs are desired. Good sources of known graphs are: