Skip to main content

Python implementation of graph data structures and algorithms

Project description

graphtheory package

Python implementation of graph data structures and algorithms is presented. The minimal graph interface is defined together with several classes implementing this interface. Graph nodes can be any hashable Python objects. Directed edges are instances of the Edge class. Graphs are instances of the Graph class (several versions). Multigraphs are instances of the MultiGraph class. Many algorithms are implemented using a unified approach. There are separate classes and modules devoted to different algorithms.

Problems and algorithms

  • Connectivity: connected components, strongly connected components, cut nodes, cut edges (bridges)
  • Cycle detection, topological sorting (DFS, Kahn), transitive closure (matrix multiplication, Floyd-Warshall, BFS, DFS)
  • Bipartiteness: bipartite graphs detection (BFS, DFS), maximum-cardinality matching (Hopcroft-Karp, Ford-Fulkerson)
  • Matching: heuristics (greedy for a maximal cardinality matching, greedy for a minimum weight matching)
  • Vertex coloring: sequential (US, RS, CS), Brooks' theorem (Delta colors), m-coloring (backtracking, exact), counter method (exact), LF, SLF, RLF, SL, GIS
  • Edge coloring: with the line graph (using vertex coloring), sequential (US, RS, CS), NTL (using Delta or Delta+1 colors), complete graphs (exact), bipartite graphs (exact)
  • Independent sets: backtracking (exact), US, RS, LL, SF
  • Dominating sets: backtracking (exact), hybrid (exact), US, RS, LF
  • Vertex covers (heuristics): greedy, 2-approximation, LF
  • Minimum spanning trees (weighted undirected graphs): Boruvka, Prim, Kruskal
  • Single-source shortest paths (weighted directed graphs without negative cycles): Dijkstra (nonnegative weights), DAGs (using topological sorting), Bellman-Ford
  • All-pairs shortest paths (weighted directed graphs without negative cycles): Floyd-Warshall, Johnson, matrix multiplications
  • Eulerian graphs: DFS, Fleury, Hierholzer
  • Hamiltonian graphs: DFS, tournaments, TSP (DFS, with MST, NN, RNN, sorted edges)
  • Forests (exact algorithms): iset, dset, vertex cover, matching, tree center, longest path problem, plotting
  • Undirected series-parallel graphs (exact algorithms): recognition, generators, iset, dset, vertex cover, matching, chordal completion (PEO), vertex coloring
  • Directed series-parallel graphs: recognition, generators
  • Halin graphs (exact algorithms): recognition, generators, vertex coloring, chordal completion (PEO), tree decomposition, plotting
  • Chordal graphs (exact algorithms): recognition, generators, finding PEO (MCS), finding maximum clique (PEO, MDO), finding all maximal cliques (PEO), finding maximum independent set (PEO), finding tree decomposition (TD), finding minimum dominating set (TD), finding minimum node cover (TD)
  • Interval graphs: double perm representation, generators, traversing (BFS, DFS), finding path decomposition
  • Outerplanar graphs (exact algorithms): recognition, chordal completion (PEO), vertex coloring
  • Permutation graphs: generators, traversing (BFS, DFS) O(n^2), connectivity O(n)
  • Circle graphs: double perm representation, generators, traversing (BFS, DFS) O(n^2), connectivity O(n^2)
  • Clustering: Kruskal

Download

To install an official release do

python3 -m pip install graphtheory

To get the git version do

git clone https://github.com/ufkapano/graphtheory.git

Usage

See doc/quickstart.txt and other doc/*.txt files.

References

[1] A. Kapanowski and Ł. Gałuszka, Weighted graph algorithms with Python. http://arxiv.org/abs/1504.07828 [draft]

A. Kapanowski and Ł. Gałuszka, Weighted graph algorithms with Python. The Python Papers 11, 3 (2016). http://ojs.pythonpapers.org/index.php/tpp/article/view/270 [final version]

[2] A. Kapanowski and A. Krawczyk, Halin graphs are 3-vertex-colorable except even wheels. https://arxiv.org/abs/1903.02904

Contributors

Andrzej Kapanowski (project leader)

Łukasz Gałuszka (MST, shortest paths, flows)

Łukasz Malinowski (matching, Eulerian graphs, graph coloring, bipartite graphs)

Paweł Motyl (multigraphs, graph coloring, independent sets)

Piotr Szestało (Hamiltonian graphs, TSP, tournaments)

Kacper Dziubek (planarity testing)

Sandra Pażyniowska (graph drawing)

Wojciech Sarka (dominating sets)

Igor Samson (graph coloring)

Dariusz Zdybski (cliques)

Aleksander Krawczyk (Halin graphs, wheel graphs)

Małgorzata Olak (chordal graphs)

Krzysztof Niedzielski (matching)

Konrad Gałuszka (series-parallel graphs)

Maciej Niezabitowski (tree decomposition)

Piotr Wlazło (edge coloring)

Magdalena Stępień (planar graphs)

Sandra Rudnicka (outerplanar graphs)

Albert Surmacz (permutation graphs, circle graphs)

Maciej Mularski (interval graphs)

Angelika Siwek (AT-free graphs)

Honorata Zych (chordal completion)

EOF

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

graphtheory-1.0.3.tar.gz (138.7 kB view details)

Uploaded Source

Built Distribution

graphtheory-1.0.3-py3-none-any.whl (315.7 kB view details)

Uploaded Python 3

File details

Details for the file graphtheory-1.0.3.tar.gz.

File metadata

  • Download URL: graphtheory-1.0.3.tar.gz
  • Upload date:
  • Size: 138.7 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.7.3

File hashes

Hashes for graphtheory-1.0.3.tar.gz
Algorithm Hash digest
SHA256 bcc3db003a4a840ea023752ccc476c137832a3248e664f33bd8918b99b48c904
MD5 33678a28254bb57855b7475436ed5e6e
BLAKE2b-256 4bd108e86f08bdbbdc7326089254d94724de0b39f1395a863409e56f80e50ea0

See more details on using hashes here.

File details

Details for the file graphtheory-1.0.3-py3-none-any.whl.

File metadata

  • Download URL: graphtheory-1.0.3-py3-none-any.whl
  • Upload date:
  • Size: 315.7 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.2 CPython/3.7.3

File hashes

Hashes for graphtheory-1.0.3-py3-none-any.whl
Algorithm Hash digest
SHA256 12c6912f32b0ef30b876c70d4d6a5eb81052612ae91ab477cf69e5f0e91c79dc
MD5 afec197ea03b7fe5f75f82da74271662
BLAKE2b-256 5c072b58ff31445338f5ea2b2dc443e7c66fcf942d4301dca1686f7276912033

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page