stag.graph.LocalGraph Class Reference

Inheritance diagram for stag.graph.LocalGraph:

Description

An abstract class which defines methods for exploring the local neighborhood of vertices in a graph.

To maximise the performance of the local algorithms using this class, subclasses should cache the results of expensive queries. For example, if querying the neighbors of a vertex requires accessing the disk, then the result should be cached.

Public Member Functions
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.LocalGraph.__init__

(

self

)

Default LocalGraph constructor.

The constructor of any classes inheriting from this base class should call this constructor. For example:

import stag.graph
class MyLocalGraph(stag.graph.LocalGraph):
  def __init__(self):
  super().__init__()
 
  # Add custom initialisation for MyLocalGraph

Reimplemented in stag.graph.Graph, stag.graph.AdjacencyListLocalGraph, and stag.neo4j.Neo4jGraph.

Member Function Documentation

degree()

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

Given a vertex v, return its weighted degree.

Reimplemented in stag.graph.AdjacencyListLocalGraph, stag.graph.Graph, and stag.neo4j.Neo4jGraph.

degree_unweighted()

int stag.graph.LocalGraph.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 in stag.graph.AdjacencyListLocalGraph, stag.graph.Graph, and stag.neo4j.Neo4jGraph.

neighbors()

List[Edge] stag.graph.LocalGraph.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 in stag.graph.AdjacencyListLocalGraph, stag.graph.Graph, and stag.neo4j.Neo4jGraph.

neighbors_unweighted()

List[int] stag.graph.LocalGraph.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 in stag.graph.AdjacencyListLocalGraph, stag.graph.Graph, and stag.neo4j.Neo4jGraph.

degrees()

List[float] stag.graph.LocalGraph.degrees	(		self,
		List[int]	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

a list of degrees

degrees_unweighted()

List[int] stag.graph.LocalGraph.degrees_unweighted	(		self,
		List[int]	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

a list of unweighted degrees

vertex_exists()

bool stag.graph.LocalGraph.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 in stag.graph.AdjacencyListLocalGraph, stag.graph.Graph, and stag.neo4j.Neo4jGraph.