139 lines
3.5 KiB
ReStructuredText
139 lines
3.5 KiB
ReStructuredText
========
|
|
spqrtree
|
|
========
|
|
|
|
|
|
Description
|
|
===========
|
|
|
|
**spqrtree** is a pure Python implementation of the SPQR-tree data
|
|
structure for biconnected graphs. It decomposes a biconnected graph
|
|
into its triconnected components (S, P, Q, and R nodes) and organizes
|
|
them as a tree.
|
|
|
|
SPQR-trees are a classical tool in graph theory, widely used for
|
|
planarity testing, graph drawing, and network analysis.
|
|
|
|
The implementation is based on the Gutwenger & Mutzel (2001) linear-time
|
|
algorithm, with corrections to Hopcroft & Tarjan (1973), and follows the
|
|
SPQR-tree data structure defined by Di Battista & Tamassia (1996).
|
|
|
|
Features:
|
|
|
|
- Pure Python --- no compiled extensions or external dependencies.
|
|
- Handles multigraphs (parallel edges between the same vertex pair).
|
|
- Simple ``dict``-based input for quick prototyping.
|
|
- Typed package with PEP 561 support.
|
|
- Requires Python 3.10 or later.
|
|
|
|
|
|
Installation
|
|
============
|
|
|
|
You can install spqrtree with ``pip``:
|
|
|
|
::
|
|
|
|
pip install spqrtree
|
|
|
|
You may also install the latest source from the
|
|
`spqrtree GitHub repository`_.
|
|
|
|
::
|
|
|
|
pip install git+https://github.com/imacat/spqrtree.git
|
|
|
|
|
|
Quick Start
|
|
===========
|
|
|
|
.. code-block:: python
|
|
|
|
from spqrtree import SPQRTree, NodeType
|
|
|
|
# K4 complete graph
|
|
graph = {
|
|
1: [2, 3, 4],
|
|
2: [1, 3, 4],
|
|
3: [1, 2, 4],
|
|
4: [1, 2, 3],
|
|
}
|
|
tree = SPQRTree(graph)
|
|
print(tree.root.type) # NodeType.R
|
|
print(len(tree.nodes())) # number of SPQR-tree nodes
|
|
|
|
|
|
Documentation
|
|
=============
|
|
|
|
Refer to the `documentation on Read the Docs`_.
|
|
|
|
|
|
Change Log
|
|
==========
|
|
|
|
Refer to the `change log`_.
|
|
|
|
|
|
References
|
|
==========
|
|
|
|
- C. Gutwenger and P. Mutzel, "A Linear Time Implementation of
|
|
SPQR-Trees," *Graph Drawing (GD 2000)*, LNCS 1984, pp. 77--90,
|
|
2001. `doi:10.1007/3-540-44541-2_8`_
|
|
|
|
- J. E. Hopcroft and R. E. Tarjan, "Dividing a Graph into
|
|
Triconnected Components," *SIAM Journal on Computing*, 2(3),
|
|
pp. 135--158, 1973. `doi:10.1137/0202012`_
|
|
|
|
- G. Di Battista and R. Tamassia, "On-Line Planarity Testing,"
|
|
*SIAM Journal on Computing*, 25(5), pp. 956--997, 1996.
|
|
`doi:10.1137/S0097539794280736`_
|
|
|
|
|
|
Acknowledgments
|
|
===============
|
|
|
|
This project was written from scratch in pure Python but drew
|
|
inspiration from the `SageMath`_ project. The SPQR-tree
|
|
implementation in SageMath served as a valuable reference for
|
|
both its implementation approach and its comprehensive test
|
|
cases.
|
|
|
|
Development was assisted by `Claude Code`_ (Anthropic).
|
|
|
|
|
|
Copyright
|
|
=========
|
|
|
|
Copyright (c) 2026 imacat.
|
|
|
|
Licensed under the Apache License, Version 2.0 (the "License");
|
|
you may not use this file except in compliance with the License.
|
|
You may obtain a copy of the License at
|
|
|
|
http://www.apache.org/licenses/LICENSE-2.0
|
|
|
|
Unless required by applicable law or agreed to in writing, software
|
|
distributed under the License is distributed on an "AS IS" BASIS,
|
|
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
See the License for the specific language governing permissions and
|
|
limitations under the License.
|
|
|
|
|
|
Authors
|
|
=======
|
|
|
|
| imacat
|
|
| imacat@mail.imacat.idv.tw
|
|
| 2026/3/4
|
|
|
|
.. _spqrtree GitHub repository: https://github.com/imacat/spqrtree
|
|
.. _documentation on Read the Docs: https://spqrtree.readthedocs.io
|
|
.. _change log: https://spqrtree.readthedocs.io/en/latest/changelog.html
|
|
.. _doi\:10.1007/3-540-44541-2_8: https://doi.org/10.1007/3-540-44541-2_8
|
|
.. _doi\:10.1137/0202012: https://doi.org/10.1137/0202012
|
|
.. _doi\:10.1137/S0097539794280736: https://doi.org/10.1137/S0097539794280736
|
|
.. _SageMath: https://www.sagemath.org/
|
|
.. _Claude Code: https://claude.com/claude-code
|