stag::LocalGraph Class Reference

#include <graph.h>

Inheritance diagram for stag::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
virtual StagReal	degree (StagInt v)=0
virtual StagInt	degree_unweighted (StagInt v)=0
virtual std::vector< edge >	neighbors (StagInt v)=0
virtual std::vector< StagInt >	neighbors_unweighted (StagInt v)=0
virtual std::vector< StagReal >	degrees (std::vector< StagInt > vertices)=0
virtual std::vector< StagInt >	degrees_unweighted (std::vector< StagInt > vertices)=0
virtual bool	vertex_exists (StagInt v)=0
virtual	~LocalGraph ()=default

Constructor & Destructor Documentation

~LocalGraph()

virtual stag::LocalGraph::~LocalGraph ( )

virtualdefault

Destructor for the LocalGraph object.

Member Function Documentation

degree()

virtual StagReal stag::LocalGraph::degree ( StagInt  v )

pure virtual

Given a vertex v, return its weighted degree.

A self-loop of weight \(1\) contributes \(2\) to the vertex's degree.

Implemented in stag::Graph, and stag::AdjacencyListLocalGraph.

degree_unweighted()

virtual StagInt stag::LocalGraph::degree_unweighted ( StagInt  v )

pure virtual

Given a vertex v, return its unweighted degree. That is, the number of neighbors of v, ignoring the edge weights.

Implemented in stag::Graph, and stag::AdjacencyListLocalGraph.

neighbors()

virtual std::vector< edge > stag::LocalGraph::neighbors ( StagInt  v )

pure virtual

Given a vertex v, return a vector of edges representing the neighborhood of v.

The returned edges will all have the ordering (v, x) such that edge.v = v.

Parameters

v	an int representing some vertex in the graph

Returns

an edge vector containing the neighborhood information

Implemented in stag::Graph, and stag::AdjacencyListLocalGraph.

neighbors_unweighted()

virtual std::vector< StagInt > stag::LocalGraph::neighbors_unweighted ( StagInt  v )

pure virtual

Given a vertex v, return a vector containing the neighbors of v.

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

Parameters

v	an int representing some vertex in the graph

Returns

an int vector giving the neighbors of v

Implemented in stag::Graph, and stag::AdjacencyListLocalGraph.

degrees()

virtual std::vector< StagReal > stag::LocalGraph::degrees ( std::vector< StagInt >  vertices )

pure virtual

Given a list of vertices, return the degrees of each vertex in the list.

Providing a method for computing the degrees 'in bulk' increases the efficiency of algorithms on graphs which are not stored directly in memory.

Parameters

vertices

a vector of ints representing the vertices to be queried.

Returns

a vector of degrees

Implemented in stag::Graph, and stag::AdjacencyListLocalGraph.

degrees_unweighted()

virtual std::vector< StagInt > stag::LocalGraph::degrees_unweighted ( std::vector< StagInt >  vertices )

pure virtual

Given a list of vertices, return their unweighted degrees.

Parameters

vertices

a vector of ints representing the vertices to be queried.

Returns

a vector of integer degrees

Implemented in stag::Graph, and stag::AdjacencyListLocalGraph.

vertex_exists()

virtual bool stag::LocalGraph::vertex_exists ( StagInt  v )

pure virtual

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

Implemented in stag::Graph, and stag::AdjacencyListLocalGraph.