Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

◆ m_nodeNum

NodeArray<int> ogdf::AdjacencyOracle::m_nodeNum
private

The internal number given to each node.

Definition at line 65 of file AdjacencyOracle.h.


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