stag::AdjacencyListLocalGraph Class Reference

#include <graph.h>

Inheritance diagram for stag::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(log(n))\) time using binary search.

Public Member Functions
	AdjacencyListLocalGraph (const std::string &filename)
StagReal	degree (StagInt v) override
StagInt	degree_unweighted (StagInt v) override
std::vector< edge >	neighbors (StagInt v) override
std::vector< StagInt >	neighbors_unweighted (StagInt v) override
std::vector< StagReal >	degrees (std::vector< StagInt > vertices) override
std::vector< StagInt >	degrees_unweighted (std::vector< StagInt > vertices) override
bool	vertex_exists (StagInt v) override
Public Member Functions inherited from stag::LocalGraph
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

AdjacencyListLocalGraph()

stag::AdjacencyListLocalGraph::AdjacencyListLocalGraph

(

const std::string &

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 adjacencylist file which defines the graph

Member Function Documentation

degree()

StagReal stag::AdjacencyListLocalGraph::degree ( StagInt  v )

overridevirtual

Given a vertex v, return its weighted degree.

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

Implements stag::LocalGraph.

degree_unweighted()

StagInt stag::AdjacencyListLocalGraph::degree_unweighted ( StagInt  v )

overridevirtual

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

Implements stag::LocalGraph.

neighbors()

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

overridevirtual

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

Implements stag::LocalGraph.

neighbors_unweighted()

std::vector< StagInt > stag::AdjacencyListLocalGraph::neighbors_unweighted ( StagInt  v )

overridevirtual

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

Implements stag::LocalGraph.

degrees()

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

overridevirtual

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

Implements stag::LocalGraph.

degrees_unweighted()

std::vector< StagInt > stag::AdjacencyListLocalGraph::degrees_unweighted ( std::vector< StagInt >  vertices )

overridevirtual

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

Implements stag::LocalGraph.

vertex_exists()

bool stag::AdjacencyListLocalGraph::vertex_exists ( StagInt  v )

overridevirtual

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

Implements stag::LocalGraph.