Skip to main content

graph_matrix_analysis

Python library to analyze graphs from their adjacency matrix.

With a matrix you can:

  • check whether the graph is simple, complete, a multigraph, a pseudograph or directed,
  • check whether it is Eulerian or semi-Eulerian,
  • check whether it is connected (using the connectivity matrix C = A + A² + … + Aⁿ⁻¹),
  • compute the shortest path between two vertices with Bellman-Ford and draw the graph,
  • check whether two matrices represent isomorphic graphs.

Installation

pip install graph_matrix_analysis

It also installs networkx and matplotlib, which are used to draw the graph.

The matrix

The matrix is a square list of lists. A[i][j] is the number of edges from vertex i to vertex j, and vertices are numbered starting at 0. If the matrix is not square, InvalidMatrixError is raised.

Usage

from graph_matrix_analysis import Properties, Connectivity, WeightedGraph, Isomorphism

A = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0],
]

Properties (Properties)

p = Properties(A)

p.count_vertex()   # 4
p.count_edges()    # 5
p.simple()         # True
p.complete()       # False
p.pseudograph()    # False
p.multigraph()     # False
p.digraph()        # False
p.eulerian()       # False
p.semieulerian()   # True
Method Returns True if...
simple() it has no loops or multiple edges
complete() there is an edge between every pair of vertices
pseudograph() it has at least one loop
multigraph() it has multiple edges between distinct vertices
digraph() the matrix is not symmetric (directed graph)
eulerian() all vertices have even degree
semieulerian() exactly two vertices have odd degree

Connectivity (Connectivity)

c = Connectivity(A)

c.connected()            # True
c.connectivity_matrix()  # [[4, 7, 7, 4], [7, 7, 8, 7], [7, 8, 7, 7], [4, 7, 7, 4]]

connectivity_matrix() computes C = A + A² + … + Aⁿ⁻¹. The graph is connected if all off-diagonal entries of C are non-zero.

Shortest path (WeightedGraph)

W = [
    [0, 4, 5, 0],
    [0, 0, -3, 6],
    [0, 0, 0, 2],
    [0, 0, 0, 0],
]
g = WeightedGraph(W)

g.bellman_ford(0, 3)   # ([0, 1, 2, 3], 3)  -> (path, distance)
g.bellman_ford(3, 0)   # 'No path exists'
g.plot_graph()         # draws the graph with its weights

Here the matrix is a weight matrix: W[i][j] is the weight of the edge from i to j, and 0 means there is no edge. Negative weights are allowed; if there is a negative cycle, it returns 'Negative cycle detected'.

Isomorphism (Isomorphism)

B = [
    [0, 1, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 1, 0],
]

Isomorphism(A, B).isomorphic()   # True

It tries every permutation of the vertices, so it is only practical for small graphs.

Development

git clone https://github.com/tuusuario/graph_matrix_analysis
cd grafomatriz
pip install -e .
pip install pytest
pytest

License

MIT

Metadata

Release files for graph-matrix-analysis 0.1.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for graph-matrix-analysis 0.1.0
File Size Uploaded Provenance Actions
graph_matrix_analysis-0.1.0.tar.gz 5.0 kB Without provenance Details for graph_matrix_analysis-0.1.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for graph-matrix-analysis 0.1.0
File Interpreter ABI Platform Actions
graph_matrix_analysis-0.1.0-py3-none-any.whl Python 3 none any Details for graph_matrix_analysis-0.1.0-py3-none-any.whl

Total release size: 10.4 kB

Release files / graph_matrix_analysis-0.1.0.tar.gz

Download URL graph_matrix_analysis-0.1.0.tar.gz
Size 5.0 kB
Tags Source
SHA-256 checksum
How to use checksums
469536ae527673bbc63b0c2587468aa5acc408c05cc79c52bfed7d2b863fe0ec
BLAKE2b-256 checksum
How to use checksums
ad1cc38270ae2c686f5c160c068472e0058cf77de0a95a06576634f8d941ddc6
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.14.7

Release files / graph_matrix_analysis-0.1.0-py3-none-any.whl

Download URL graph_matrix_analysis-0.1.0-py3-none-any.whl
Size 5.5 kB
Tags Python 3
SHA-256 checksum
How to use checksums
0b0daa512a15a86570d16ca316f9c0cc1ce6293d06d42e0fd76046c7e6049b94
BLAKE2b-256 checksum
How to use checksums
638fe3d62331234f8baae8033e7faaf273b47ccaa9e1ae7702c2791d94565761
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.14.7

Security for graph-matrix-analysis 0.1.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page