Metadata-Version: 2.4
Name: graph_matrix_analysis
Version: 0.1.2
Summary: Library for analyzing graphs based on their adjacency matrix
Author-email: "Aitor Merino, Xabier Labraga" <aitor.merinol@alumni.mondragon.edu>
License-Expression: MIT
Keywords: graphs,adjacency matrix,euler,dijkstra,bellman-ford,isomorphism
Classifier: Programming Language :: Python :: 3
Classifier: Operating System :: OS Independent
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx
Requires-Dist: matplotlib
Dynamic: license-file

# 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

```bash
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

```python
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`)

```python
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`)

```python
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`)

```python
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`)

```python
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

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

## License

MIT
