ogdf::AdjacencyOracle Class Reference

Tells you in constant time if two nodes are adjacent. More...

#include <ogdf/basic/AdjacencyOracle.h>

Public Member Functions
	AdjacencyOracle (const Graph &G, int degreeThreshold=32)
	The constructor for the class, needs time O(n^2 + m) ∩ Ω(n). More...
	~AdjacencyOracle ()
	The destructor. More...
bool	adjacent (node v, node w) const
	Returns true iff vertices v and w are adjacent. More...

Private Member Functions
int	index (node v, node w) const
	Returns an index for m_adjacencies that corresponds to the entry of nodes v and w. More...

Private Attributes
std::vector< bool >	m_adjacencies
	An entry is true iff the corresponding nodes are adjacent. More...
NodeArray< int >	m_nodeNum
	The internal number given to each node. More...

Detailed Description

Tells you in constant time if two nodes are adjacent.

AdjacencyOracle is initialized with a graph and returns for any pair of nodes in constant time if they are adjacent.

Definition at line 48 of file AdjacencyOracle.h.

Constructor & Destructor Documentation

AdjacencyOracle()

ogdf::AdjacencyOracle::AdjacencyOracle ( const Graph &  G, int  degreeThreshold = 32  )

explicit

The constructor for the class, needs time O(n^2 + m) ∩ Ω(n).

Builds the bottom-left part of an adjacency matrix for the subset of nodes with degree above degreeThreshold.

~AdjacencyOracle()

ogdf::AdjacencyOracle::~AdjacencyOracle ( )

inline

The destructor.

Definition at line 59 of file AdjacencyOracle.h.

Member Function Documentation

adjacent()

bool ogdf::AdjacencyOracle::adjacent	(	node	v,
		node	w
	)		const

Returns true iff vertices v and w are adjacent.

index()

int ogdf::AdjacencyOracle::index ( node  v, node  w  ) const

private

Returns an index for m_adjacencies that corresponds to the entry of nodes v and w.

Member Data Documentation

m_adjacencies

std::vector<bool> ogdf::AdjacencyOracle::m_adjacencies

private

An entry is true iff the corresponding nodes are adjacent.

Definition at line 69 of file AdjacencyOracle.h.

m_nodeNum

NodeArray<int> ogdf::AdjacencyOracle::m_nodeNum

private

The internal number given to each node.

Definition at line 68 of file AdjacencyOracle.h.

---

The documentation for this class was generated from the following file:

• include/ogdf/basic/AdjacencyOracle.h