A graph manipulation library in pure Python
Please note that this library is currently in legacy mode and not under active development. PRs are welcome to be submitted, but there's no guarantees about the time it'll take for them to get merged or an updated version released to PyPI. If someone else would like to take over as maintainer of the library, I'm more than willing to discuss that.
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
| 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 |
Installing the module is as easy as pip install pygraph
>>> import pygraph
>>> g = pygraph.build_chvatal_graph()
>>> pygraph.is_planar(g)
FalseThe 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 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.
The planarity testing algorithm is extremely complicated. As such, more tests with more graphs are desired. Good sources of known graphs are:
For non-planar graphs, priority should be given to ones that don't fall afoul of Euler's Formula, so that the actual planarity testing algorithm is tested.