OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches

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).

The destructor.

bool adjacent (node v, node w) const
Returns true iff vertices v and w are adjacent.

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.

Private Attributes

An entry is true iff the corresponding nodes are adjacent.

NodeArray< intm_nodeNum
The internal number given to each node.

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 45 of file AdjacencyOracle.h.

Constructor & Destructor Documentation

 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.

inline

The destructor.

Definition at line 56 of file AdjacencyOracle.h.

Member Function Documentation

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

private

An entry is true iff the corresponding nodes are adjacent.

Definition at line 66 of file AdjacencyOracle.h.