stag.graph.Graph Class Reference

Inheritance diagram for stag.graph.Graph:

Description

The core object used to represent graphs for use with the library.

Graphs are always constructed from sparse matrices, and this is the internal representation used as well. Vertices of the graph are always referred to by their unique integer index. This index corresponds to the position of the vertex in the stored adjacency matrix of the graph.

This class supports graphs with positive edge weights. Self-loops are permitted.

Public Member Functions
def	__init__ (self, Union[scipy.sparse.spmatrix, stag.utility.SprsMat] mat)
	Initialise the graph with a sparse matrix.
stag.utility.SprsMat	adjacency (self)
	Return the sparse adjacency matrix of the graph.
stag.utility.SprsMat	laplacian (self)
	Construct the Laplacian matrix of the graph.
stag.utility.SprsMat	normalised_laplacian (self)
	Construct the normalised Laplacian matrix of the graph.
stag.utility.SprsMat	signless_laplacian (self)
	Construct the signless Laplacian matrix of the graph.
stag.utility.SprsMat	normalised_signless_laplacian (self)
	Construct the normalised signless Laplacian matrix of the graph.
stag.utility.SprsMat	degree_matrix (self)
	The degree matrix of the graph.
stag.utility.SprsMat	inverse_degree_matrix (self)
	The inverse degree matrix of the graph.
stag.utility.SprsMat	lazy_random_walk_matrix (self)
	The lazy random walk matrix of the graph.
float	total_volume (self)
	The volume of the graph.
float	average_degree (self)
	The average degree of the graph.
int	number_of_vertices (self)
	The number of vertices in the graph.
int	number_of_edges (self)
	The number of edges in the graph.
def	add_edge (self, int i, int j, float w)
	Add an edge to the graph.
def	remove_edge (self, int i, int j)
	Remove an edge from the graph.
bool	has_self_loops (self)
	Returns a boolean indicating whether this graph contains self loops.
bool	is_connected (self)
	Returns a boolean indicating whether the graph is connected.
'Graph'	subgraph (self, np.ndarray vertices)
	Construct and return a subgraph of this graph.
'Graph'	disjoint_union (self, 'Graph' other)
	Construct and return the disjoint union of this graph and another.
float	degree (self, int v)
	Given a vertex v, return its weighted degree.
int	degree_unweighted (self, int v)
	Given a vertex v, return its unweighted degree.
np.ndarray	degrees (self, np.ndarray vertices)
	Given a list of vertices, return a list of their weighted degrees.
np.ndarray	degrees_unweighted (self, np.ndarray vertices)
	Given a list of vertices, return a list of their unweighted degrees.
List[Edge]	neighbors (self, int v)
	Given a vertex v, return a list of edges representing the neighbors of v.
np.ndarray	neighbors_unweighted (self, int v)
	Given a vertex v, return a list of neighbors of v.
bool	vertex_exists (self, int v)
	Given a vertex ID, returns true or false to indicate whether the vertex exists in the graph.
networkx.Graph	to_networkx (self)
	Construct a networkx graph object which is equivalent to this STAG graph.
def	draw (self, **kwargs)
	Plot the graph with matplotlib.
def	__init__ (self)
	Default LocalGraph constructor.
float	degree (self, int v)
	Given a vertex v, return its weighted degree.
int	degree_unweighted (self, int v)
	Given a vertex v, return its unweighted degree.
List[Edge]	neighbors (self, int v)
	Given a vertex v, return a list of edges representing the neighbors of v.
np.ndarray	neighbors_unweighted (self, int v)
	Given a vertex v, return a list of neighbors of v.
np.ndarray	degrees (self, np.ndarray vertices)
	Given a list of vertices, return a list of their weighted degrees.
np.ndarray	degrees_unweighted (self, np.ndarray vertices)
	Given a list of vertices, return a list of their unweighted degrees.
bool	vertex_exists (self, int v)
	Given a vertex ID, returns true or false to indicate whether the vertex exists in the graph.

Constructor & Destructor Documentation

__init__()

def stag.graph.Graph.__init__	(		self,
		Union[scipy.sparse.spmatrix, stag.utility.SprsMat]	mat
	)

Initialise the graph with a sparse matrix.

The provided matrix should correspond either to the adjacency matrix or Laplacian matrix of the graph. STAG will automatically detect whether the provided matrix is an adjacency matrix or a Laplacian matrix.

For example:

>>> import stag.graph
>>> import stag.utility
>>>
>>> adj_mat = stag.utility.SprsMat([[0, 1, 1, 1],
...                                 [1, 0, 1, 1],
...                                 [1, 1, 0, 1],
...                                 [1, 1, 1, 0]])
>>> g = stag.graph.Graph(adj_mat)

Parameters

mat	A sparse scipy matrix or a stag.utility.SprsMat object

Reimplemented from stag.graph.LocalGraph.

Member Function Documentation

adjacency()

stag.utility.SprsMat stag.graph.Graph.adjacency

(

self

)

Return the sparse adjacency matrix of the graph.

Returns

a stag.utility.SprsMat representing the graph adjacency matrix

laplacian()

stag.utility.SprsMat stag.graph.Graph.laplacian

(

self

)

Construct the Laplacian matrix of the graph.

The Laplacian matrix is defined by

\[ L = D - A \]

where \(D\) is the diagonal matrix of vertex degrees and \(A\) is the adjacency matrix of the graph.

Returns

a stag.utility.SprsMat representing the graph Laplacian

normalised_laplacian()

stag.utility.SprsMat stag.graph.Graph.normalised_laplacian

(

self

)

Construct the normalised Laplacian matrix of the graph.

The normalised Laplacian matrix is defined by

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

where \(D\) is the diagonal matrix of vertex degrees and \(L\) is the Laplacian matrix of the graph.

Returns

a stag.utility.SprsMat representing the normalised Laplacian

signless_laplacian()

stag.utility.SprsMat stag.graph.Graph.signless_laplacian

(

self

)

Construct the signless Laplacian matrix of the graph.

The signless Laplacian matrix is defined by

\[ J = D + A \]

where \(D\) is the diagonal matrix of vertex degrees and \(A\) is the adjacency matrix of the graph.

Returns

a stag.utility.SprsMat representing the signless graph Laplacian

normalised_signless_laplacian()

stag.utility.SprsMat stag.graph.Graph.normalised_signless_laplacian

(

self

)

Construct the normalised signless Laplacian matrix of the graph.

The normalised signless Laplacian matrix is defined by

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

where \(D\) is the diagonal matrix of vertex degrees and \(J\) is the signless Laplacian matrix of the graph.

Returns

a stag.utility.SprsMat representing the normalised signless Laplacian

degree_matrix()

stag.utility.SprsMat stag.graph.Graph.degree_matrix

(

self

)

The degree matrix of the graph.

The degree matrix \(D \in \mathbb{R}^{n \\times n}\) is a diagonal matrix such that \(D(i, i) = \mathrm{deg}(i)\) where \(\mathrm{deg}(i)\) is the degree of vertex \(i\) and \(n\) is the number of vertices in the graph.

Returns

a stag.utility.SprsMat representing the degree matrix

inverse_degree_matrix()

stag.utility.SprsMat stag.graph.Graph.inverse_degree_matrix

(

self

)

The inverse degree matrix of the graph.

The degree matrix \(D^{-1} \in \mathbb{R}^{n \times n}\) is a diagonal matrix such that

\[ D(i, i) = \left\{ \begin{array}{lll} \mathrm{deg}(i) & \mbox{if } \mathrm{deg}(i) > 0 \\ 0 & \mbox{otherwise} \end{array} \right. \]

where \(\mathrm{deg}(i)\) is the degree of vertex \(i\) and \(n\) is the number of vertices in the graph.

Returns

a stag.utility.SprsMat representing the inverse degree matrix

lazy_random_walk_matrix()

stag.utility.SprsMat stag.graph.Graph.lazy_random_walk_matrix

(

self

)

The lazy random walk matrix of the graph.

The lazy random walk matrix is defined by

\[ W = \frac 1 2 I + \frac 1 2 A D^{-1} \]

where \(I\) is the identity matrix, \(A\) is the graph adjacency matrix and \(D\) is the degree matrix of the graph.

Returns

a stag.utility.SprsMat representing the lazy random walk matrix

total_volume()

float stag.graph.Graph.total_volume

(

self

)

The volume of the graph.

The volume of a graph \(G = (V, E, w)\) is defined by

\[ \mathrm{vol}(G) = \sum_{u \in V} \mathrm{deg}(u), \]

where \(\mathrm{deg}(u)\) is the degree of vertex \(u\).

Returns

the graph's volume, \(\mathrm{vol}(G)\)

average_degree()

float stag.graph.Graph.average_degree

(

self

)

The average degree of the graph.

This is defined as the sum of the node degrees divided by the number of nodes.

Returns

the graph's average degree.

number_of_vertices()

int stag.graph.Graph.number_of_vertices

(

self

)

The number of vertices in the graph.

number_of_edges()

int stag.graph.Graph.number_of_edges

(

self

)

The number of edges in the graph.

This method ignores the weights of the edges.

add_edge()

def stag.graph.Graph.add_edge	(		self,
		int	i,
		int	j,
		float	w
	)

Add an edge to the graph.

The edge goes from node \(i\) to node \(j\), and is added with weight \(w\). If there is already an edge from \(i\) to \(j\), then \(w\) is added to its weight.

If either of \(i\) of \(j\) are larger than the number of nodes in the graph, the graph is resized to have enough nodes.

remove_edge()

def stag.graph.Graph.remove_edge	(		self,
		int	i,
		int	j
	)

Remove an edge from the graph.

Remove any edge between nodes \(i\) and \(j\).

has_self_loops()

bool stag.graph.Graph.has_self_loops

(

self

)

Returns a boolean indicating whether this graph contains self loops.

is_connected()

bool stag.graph.Graph.is_connected

(

self

)

Returns a boolean indicating whether the graph is connected.

The running time of this method is \(O(m)\) where \(m\) is the number of edges in the graph.

subgraph()

'Graph' stag.graph.Graph.subgraph	(		self,
		np.ndarray	vertices
	)

Construct and return a subgraph of this graph.

Note that the vertex indices will be changed in the subgraph.

Parameters

vertices

the vertices in the induced subgraph

Returns

a new stag.graph.Graph object representing the subgraph induced by the given vertices

disjoint_union()

'Graph' stag.graph.Graph.disjoint_union	(		self,
		'Graph'	other
	)

Construct and return the disjoint union of this graph and another.

The disjoint union of two graphs \(G\) and \(H\) is a graph containing \(G\) and \(H\) as disconnected subgraphs.

Parameters

other

the other graph to be combined with this one

Returns

a new stag.graph.Graph object representing the union of this graph with the other one

degree()

float stag.graph.Graph.degree	(		self,
		int	v
	)

Given a vertex v, return its weighted degree.

Reimplemented from stag.graph.LocalGraph.

degree_unweighted()

int stag.graph.Graph.degree_unweighted	(		self,
		int	v
	)

Given a vertex v, return its unweighted degree.

That is, the number of neighbors of v, ignoring the edge weights.

Reimplemented from stag.graph.LocalGraph.

degrees()

np.ndarray stag.graph.Graph.degrees	(		self,
		np.ndarray	vertices
	)

Given a list of vertices, return a list of their weighted degrees.

When developing implementations of the stag.graph.LocalGraph class, providing an efficient method of returning a list of degrees will improve the performance of local clustering algorithms.

Parameters

vertices

a list of IDs representing the vertices to be queried

Returns

an array of degrees

Reimplemented from stag.graph.LocalGraph.

degrees_unweighted()

np.ndarray stag.graph.Graph.degrees_unweighted	(		self,
		np.ndarray	vertices
	)

Given a list of vertices, return a list of their unweighted degrees.

When developing implementations of the stag.graph.LocalGraph class, providing an efficient method of returning a list of degrees will improve the performance of local clustering algorithms.

Parameters

vertices

a list of IDs representing the vertices to be queried

Returns

an array of unweighted degrees

Reimplemented from stag.graph.LocalGraph.

neighbors()

List[Edge] stag.graph.Graph.neighbors	(		self,
		int	v
	)

Given a vertex v, return a list of edges representing the neighbors of v.

The returned edge objects will all have the ordering (v1, v2) such that edge.v1 = v.

Parameters

v	the ID of some vertex in the graph

Returns

a list of stag.graph.Edge objects containing the neighbourhood of v

Reimplemented from stag.graph.LocalGraph.

neighbors_unweighted()

np.ndarray stag.graph.Graph.neighbors_unweighted	(		self,
		int	v
	)

Given a vertex v, return a list of neighbors of v.

The weights of edges to the neighbors are not returned by this method.

Parameters

v	the ID of some vertex in the graph

Returns

an array of vertex IDs giving the neighbours of v

Reimplemented from stag.graph.LocalGraph.

vertex_exists()

bool stag.graph.Graph.vertex_exists	(		self,
		int	v
	)

Given a vertex ID, returns true or false to indicate whether the vertex exists in the graph.

Parameters

v	the vertex index to check

Returns

a boolean indicating whether there exists a vertex with the given index

Reimplemented from stag.graph.LocalGraph.

to_networkx()

networkx.Graph stag.graph.Graph.to_networkx

(

self

)

Construct a networkx graph object which is equivalent to this STAG graph.

See the networkx documentation.

draw()

def stag.graph.Graph.draw	(		self,
		**	kwargs
	)

Plot the graph with matplotlib.

This uses the networkx draw method and accepts any the keyword arguments will be passed through directly.

Example

import matplotlib.pyplot as plt
import stag.graph
myGraph = stag.graph.star_graph(10)
myGraph.draw()
plt.show()