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.

Public Member Functions
def	__init__ (self, scipy.sparse.spmatrix adj_mat, stag_internal.Graph internal_graph=None)
	Initialise the graph with an adjacency matrix.
scipy.sparse.csc_matrix	adjacency (self)
	Return the sparse adjacency matrix of the graph.
scipy.sparse.csc_matrix	laplacian (self)
	Construct the Laplacian matrix of the graph.
scipy.sparse.csc_matrix	normalised_laplacian (self)
	Construct the normalised Laplacian matrix of the graph.
scipy.sparse.csc_matrix	normalised_laplacian (self)
	Construct the normalised Laplacian matrix of the graph.
scipy.sparse.csc_matrix	signless_laplacian (self)
	Construct the signless Laplacian matrix of the graph.
scipy.sparse.csc_matrix	normalised_signless_laplacian (self)
	Construct the normalised signless Laplacian matrix of the graph.
scipy.sparse.csc_matrix	degree_matrix (self)
	The degree matrix of the graph.
scipy.sparse.csc_matrix	inverse_degree_matrix (self)
	The inverse degree matrix of the graph.
scipy.sparse.csc_matrix	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.
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.
List[int]	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.
Public Member Functions inherited from stag.graph.LocalGraph
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.
List[int]	neighbors_unweighted (self, int v)
	Given a vertex v, return a list of neighbors of v.
List[float]	degrees (self, List[int] vertices)
	Given a list of vertices, return a list of their weighted degrees.
List[int]	degrees_unweighted (self, List[int] 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,
		scipy.sparse.spmatrix	adj_mat,
		stag_internal.Graph	internal_graph = None
	)

Initialise the graph with an adjacency matrix.

For example:

>>> import stag.graph
>>> import scipy.sparse
>>>
>>> adj_mat = scipy.sparse.csc_matrix([[0, 1, 1, 1],
...                                    [1, 0, 1, 1],
...                                    [1, 1, 0, 1],
...                                    [1, 1, 1, 0]])
>>> g = stag.graph.Graph(adj_mat)

Parameters

adj_mat	A sparse scipy matrix, such as scipy.sparse.csc_matrix.
internal_graph	(optional) specify a STAG C++ graph object to initialise with. Use this only if you understand the internal workings of the STAG library.

Reimplemented from stag.graph.LocalGraph.

Member Function Documentation

adjacency()

scipy.sparse.csc_matrix stag.graph.Graph.adjacency

(

self

)

Return the sparse adjacency matrix of the graph.

Returns

a scipy.sparse.csc_matrix representing the graph adjacency matrix

laplacian()

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix representing the graph Laplacian

normalised_laplacian() [1/2]

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix representing the normalised Laplacian

normalised_laplacian() [2/2]

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix representing the normalised Laplacian

signless_laplacian()

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix representing the signless graph Laplacian

normalised_signless_laplacian()

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix representing the normalised signless Laplacian

degree_matrix()

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix representing the degree matrix

inverse_degree_matrix()

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix representing the inverse degree matrix

lazy_random_walk_matrix()

scipy.sparse.csc_matrix 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 scipy.sparse.csc_matrix 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.

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.

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()

List[int] 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

a list 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()