sgtl.graph.Graph#

class sgtl.graph.Graph(adj_mat)#

Bases: object

Represents a graph. We keep things very simple - a graph is represented by its sparse adjacency matrix.

In the general case, this allows for

  • directed and undirected graphs

  • self-loops

If you’d like to store meta-data about the graph, such as node or edge labels, you should implement a subclass of this one, and add that information yourself.

This graph cannot be dynamically updated. It must be initialised with the complete adjacency matrix.

Vertices are referred to by their index in the adjacency matrix.

__init__(adj_mat)#

Initialise the graph with an adjacency matrix.

Parameters:

adj_mat – A sparse scipy matrix.

Methods

__init__(adj_mat)

Initialise the graph with an adjacency matrix.

adjacency_matrix()

Return the Adjacency matrix of the graph.

bipartiteness(vertex_set_l, vertex_set_r)

Compute the bipartiteness of the two given vertex sets.

conductance(vertex_set_s)

Compute the conductance of the given set of vertices.

degree_matrix()

Construct the diagonal degree matrix of the graph.

draw()

Plot the graph, by first converting to a networkx graph.

from_networkx(netx_graph[, ...])

Given a networkx graph object, convert it to an SGTL graph object.

inverse_degree_matrix()

Construct the inverse of the diagonal degree matrix of the graph.

inverse_sqrt_degree_matrix()

Construct the square root of the inverse of the diagonal degree matrix of the graph.

laplacian_matrix()

Construct the Laplacian matrix of the graph.

normalised_adjacency_matrix()

Return the normalised adjacency matrix of the graph.

normalised_laplacian_matrix()

Construct the normalised Laplacian matrix of the graph.

number_of_edges()

The number of edges in the graph, ignoring any weights.

number_of_vertices()

The number of vertices in the graph.

random_walk_laplacian_matrix()

Construct the random walk Laplacian matrix of the graph.

tensor_product(other_graph)

Construct the tensor-product graph of this graph with another one.

to_networkx()

Construct a networkx graph which is equivalent to this SGTL graph.

total_volume()

The total volume of the graph.

volume(vertex_set)

Given a set of vertices, compute the volume of the set.

weight(vertex_set_l, vertex_set_r[, ...])

Compute the weight of all edges between the two given vertex sets.
adjacency_matrix()#

Return the Adjacency matrix of the graph.

bipartiteness(vertex_set_l, vertex_set_r)#

Compute the bipartiteness of the two given vertex sets. The bipartiteness is defined as

\[\beta(L, R) = 1 - \frac{2 w(L, R)}{vol(L \cup R)}\]
Parameters:

  • vertex_set_l – a collection of vertex indices corresponding to the set L

  • vertex_set_r – a collection of vertex indices corresponding to the set R

Returns:

The bipartiteness ratio \(\beta(L, R)\)

Raises:

ValueError – if both vertex sets are empty

conductance(vertex_set_s)#

Compute the conductance of the given set of vertices. The conductance is defined to be

\[\phi(S) = 1 - \frac{2 w(S, S)}{vol(S)}\]
Parameters:

vertex_set_s – a collection of vertex indices corresponding to the set S

Returns:

The conductance \(\phi(S)\)

Raises:

ValueError – if the vertex set is empty

degree_matrix()#

Construct the diagonal degree matrix of the graph.

draw()#

Plot the graph, by first converting to a networkx graph. This will use the default networkx plotting functionality. If you’d like to do something more fancy, then you should convert the graph to a networkx graph using the to_networkx method and use networkx directly.

static from_networkx(netx_graph: Graph, edge_weight_attribute='weight')#

Given a networkx graph object, convert it to an SGTL graph object. Unless otherwise specified, this method will use the ‘weight’ attribute on the networkx edges to assign the weight of the edges. If no such attribute is present, the edges will be added with weight 1.

Parameters:

  • netx_graph – The networkx graph object to be converted.

  • edge_weight_attribute – (default ‘weight’) the edge attribute to be used to generate the edge weights.

Returns:

An SGTL graph which is equivalent to the given networkx graph.

inverse_degree_matrix()#

Construct the inverse of the diagonal degree matrix of the graph.

inverse_sqrt_degree_matrix()#

Construct the square root of the inverse of the diagonal degree matrix of the graph.

laplacian_matrix()#

Construct the Laplacian matrix of the graph. The Laplacian matrix is defined to be

\[L = D - A\]

where D is the diagonal degree matrix and A is the adjacency matrix of the graph.

normalised_adjacency_matrix()#

Return the normalised adjacency matrix of the graph. The normalised adjacency matrix is defined to be

\[\mathcal{A} = D^{-1/2} A D^{-1/2}\]

where \(A\) is the unnormalised adjacency matrix and \(D\) is the diagonal degree matrix of the graph.

normalised_laplacian_matrix()#

Construct the normalised Laplacian matrix of the graph. The normalised Laplacian matrix is defined to be

\[\mathcal{L} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}\]

where I is the identity matrix and D is the diagonal degree matrix of the graph.

number_of_edges() → int#

The number of edges in the graph, ignoring any weights.

number_of_vertices() → int#

The number of vertices in the graph.

random_walk_laplacian_matrix()#

Construct the random walk Laplacian matrix of the graph. The random walk Laplacian matrix is defined to be

\[L_{\mathrm{RW}} = D^{-1} L = I - D^{-1} A\]

where I is the identity matrix and D is the diagonal degree matrix of the graph.

tensor_product(other_graph)#

Construct the tensor-product graph of this graph with another one.

The tensor product graph \(G_1 \otimes G_2\) has vertex set

\[V_3 = V_1 \times V_2\]

where \(V_1\) and \(V_2\) are the vertex sets of the two input graphs. Then, the edge set is

\[E_3 = \left\{ (v_{ab}, v_{ij}) : (a, i) \in E_1 \land (b, j) \in E_2 \right\}.\]

Notice that the tensor product is not symmetrical: graph1.tensor_product(graph2) is not the same as graph2.tensor_product(graph1).

Parameters:

other_graph – The other sgtl.Graph object to combine with this one.

Returns:

A new graph object which is the tensor product of the two input graphs.

Example:
>>> import sgtl.graph
>>> graph1 = sgtl.graph.complete_graph(4)
>>> graph2 = sgtl.graph.path_graph(3)
>>> graph1.tensor_product(graph2).adjacency_matrix().toarray()
array([[0., 0., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0.],
       [0., 0., 0., 1., 0., 1., 1., 0., 1., 1., 0., 1.],
       [0., 0., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0.],
       [0., 1., 0., 0., 0., 0., 0., 1., 0., 0., 1., 0.],
       [1., 0., 1., 0., 0., 0., 1., 0., 1., 1., 0., 1.],
       [0., 1., 0., 0., 0., 0., 0., 1., 0., 0., 1., 0.],
       [0., 1., 0., 0., 1., 0., 0., 0., 0., 0., 1., 0.],
       [1., 0., 1., 1., 0., 1., 0., 0., 0., 1., 0., 1.],
       [0., 1., 0., 0., 1., 0., 0., 0., 0., 0., 1., 0.],
       [0., 1., 0., 0., 1., 0., 0., 1., 0., 0., 0., 0.],
       [1., 0., 1., 1., 0., 1., 1., 0., 1., 0., 0., 0.],
       [0., 1., 0., 0., 1., 0., 0., 1., 0., 0., 0., 0.]])
>>> graph2.tensor_product(graph1).adjacency_matrix().toarray()
array([[0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1., 0., 1., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1., 1., 0., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1., 1., 1., 0., 0., 0., 0., 0.],
       [0., 1., 1., 1., 0., 0., 0., 0., 0., 1., 1., 1.],
       [1., 0., 1., 1., 0., 0., 0., 0., 1., 0., 1., 1.],
       [1., 1., 0., 1., 0., 0., 0., 0., 1., 1., 0., 1.],
       [1., 1., 1., 0., 0., 0., 0., 0., 1., 1., 1., 0.],
       [0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1., 0., 1., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1., 1., 0., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1., 1., 1., 0., 0., 0., 0., 0.]])
to_networkx() → Graph#

Construct a networkx graph which is equivalent to this SGTL graph.

total_volume() → float#

The total volume of the graph.

volume(vertex_set)#

Given a set of vertices, compute the volume of the set.

Parameters:

vertex_set – an iterable collection of vertex indices

Returns:

The volume of vertex_set

weight(vertex_set_l: List[int], vertex_set_r: List[int], check_for_overlap=True, sets_are_equal=False) → float#

Compute the weight of all edges between the two given vertex sets.

By default, this method needs to check whether the given two sets overlap, this is a somewhat expensive operation. There are two circumstances in which the caller can avoid this:

  • if the caller can guarantee that the sets do not overlap, then set check_for_overlap=False

  • if the caller can guarantee that the sets are equal, then set sets_are_equal=True

Parameters:

  • vertex_set_l – a collection of vertex indices corresponding to the set L

  • vertex_set_r – a collection of vertex indices corresponding to the set R

  • check_for_overlap – set to False if the given sets are guaranteed not to overlap

  • sets_are_equal – set to True if the given sets are guaranteed to be equal

Returns:

The weight w(L, R)