# Graphs

## Contents

# Graphs#

## Theory#

A **graph** \(G\) of order \(o\) will be fully described by a square **adjacency matrix** \(\mathcal{A}\in\mathbb{M}_{o\times o}(\mathbb{R})\) and a **state vector** \(\mathcal{S}\in\mathbb{R}^{o}\).

The **adjacency matrix** contains the weights \(w(e_{i,j})\) of the edges (from the vertex \(v_i\) to \(v_j\) in this case). The particular case of \(w(e_{i,j})=0\) indicates that their is no edge going from \(v_i\) to \(v_j\).

The **state vector** contains the states \(s(v_i)\) of the vertices \(v_i\).

The **neighborhood** \(N(v)\) of a **vertex** \(v\) is the set of vertices which are adjacent to it. Thanks to the linear algebra description of graphs, there is a simple way to obtain a vector containing the weighted sum of the states present in the neighborhood of every vertex of a graph.

We can also define the **n-th neighborhood** \(N_n(v)\) of a vertex as the set of vertices which are at a distance \(n\) of \(v\).

## Examples#

The `Graph`

class can be instantiated with two inputs: an **adjacency matrix** and a **state vector** both in the form of nested arrays.

```
import gra
graph = gra.Graph([ # adjacency matrix
[0, 1, 1, 1],
[1, 0, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 0]
],[ # state vector
[1],
[0],
[0],
[0]
])
```

**Graph** objects have three atributes:

`adjacency_matrix`

( an instance of the SparseTensor class of TensorFlow )`state_vector`

( an instance of the Tensor class of TensorFlow )`dtype`

( a numpy data type object: np.int32 or np.float32 )

and eight methods:

`.plot()`

: plots the graph`.evolve(rule)`

: evolves the graph according the`rule`

`.order()`

: returns the order of the graph`.diameter()`

: returns the diameter of the graph`.clone()`

: returns a copy of the graph, this allows to use rules without modifying the original graph`.to_igraph()`

: returns an igraph object`.to_networkx()`

: returns a networkx object`.to_mathematica()`

: returns a string corresponding to a Mathematica compatible version of the graph

In the case of binary graphs \([s(v)\in \{0,1\}\;\forall v]\), plots are such that:

“alive” vertices \([s(v)=1]\) are colored

*purple*,“dead” vertices \([s(v)=0]\) are colored

*orange*.

```
graph.plot()
```

Graphs with a different ordering of vertices are equivalent. This equivalence can be checked with `==`

.

```
graph == gra.Graph([ # adjacency matrix
[0, 1, 1, 1],
[1, 0, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 0]
],[ # state vector
[0],
[0],
[1],
[0]
])
```

```
True
```