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

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

Built distribution (wheel)

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

Total release size: 10.4 kB

Release files / graph_matrix_analysis-0.1.1.tar.gz

Download URL graph_matrix_analysis-0.1.1.tar.gz
Size 5.0 kB
Tags Source
SHA-256 checksum
How to use checksums
d82f848ae0e9e5573b2fe62069daf47c26d058d9fd98f3e5c002f5c87fb95e35
BLAKE2b-256 checksum
How to use checksums
c2c475cd8539a7f5645b30445a41f9833c06ab1973a9368cf59dd6ad8cc3a370
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.1-py3-none-any.whl

Download URL graph_matrix_analysis-0.1.1-py3-none-any.whl
Size 5.5 kB
Tags Python 3
SHA-256 checksum
How to use checksums
955affabb35182319266cb48099f506360e3e07a9d3ce000c3dd176722632ba3
BLAKE2b-256 checksum
How to use checksums
f90db4bf75bbc4c6561bee49d7c7ec3817051736fa2df347dd7a1651a52d611a
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.1

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