stag.graph.AdjacencyListLocalGraph Class Reference

Inheritance diagram for stag.graph.AdjacencyListLocalGraph:

Description

A local graph backed by an adjacency list file on disk.

The graph is loaded into memory in a local way only. That is, an adjacency list data structure is constructed in memory as node neighbours are queried. If a node is not found in the cached adjacency list, then the neighbours of the node are queried from the adjacency list on disk. This allows for local algorithms to be executed on very large graphs stored on disk without loading the whole graph into memory.

See Graph File Formats for more information about the adjacency list file format.

Note

It is important that the adjacency list on disk is stored with sorted node indices. This allows us to query the neighbours of a given node in \(O(\mathrm{log}(n))\) time using binary search.

Public Member Functions
def	__init__ (self, str filename)
	Construct a local graph backed by an adjacency list file.
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.
bool	vertex_exists (self, int v)
	Given a vertex ID, returns true or false to indicate whether the vertex exists in the graph.
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.
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.AdjacencyListLocalGraph.__init__	(		self,
		str	filename
	)

Construct a local graph backed by an adjacency list file.

The adjacency list file must not be modified externally while it is in use by this object.

Parameters

filename

the name of the adjacency list file which defines the graph.

Reimplemented from stag.graph.LocalGraph.

Member Function Documentation

degree()

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

Given a vertex v, return its weighted degree.

Reimplemented from stag.graph.LocalGraph.

degree_unweighted()

int stag.graph.AdjacencyListLocalGraph.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.AdjacencyListLocalGraph.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.AdjacencyListLocalGraph.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.AdjacencyListLocalGraph.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.

degrees()

np.ndarray stag.graph.AdjacencyListLocalGraph.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.AdjacencyListLocalGraph.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.