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.2

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.2
File Size Uploaded Provenance Actions
graph_matrix_analysis-0.1.2.tar.gz 5.0 kB Without provenance Details for graph_matrix_analysis-0.1.2.tar.gz

Built distribution (wheel)

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

Total release size: 10.5 kB

Release files / graph_matrix_analysis-0.1.2.tar.gz

Download URL graph_matrix_analysis-0.1.2.tar.gz
Size 5.0 kB
Tags Source
SHA-256 checksum
How to use checksums
cc645a480ccb220a6bce807a9db9de186677bd338943c1ed8eb7a381110354e3
BLAKE2b-256 checksum
How to use checksums
056aec072032716004300ef726cab91e8057c9d1b8097b64d78f40188d32185a
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.2-py3-none-any.whl

Download URL graph_matrix_analysis-0.1.2-py3-none-any.whl
Size 5.5 kB
Tags Python 3
SHA-256 checksum
How to use checksums
2636af29a55800a99d60da2c3158e23ff84819faa96a8e0db85e46a96578215c
BLAKE2b-256 checksum
How to use checksums
db4b4684d273163892636de7f493229a45ecff934e1a1445224aa3b98b7f6b61
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.2

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