GClasses

GClasses::GShortcutPruner Class Reference

This finds the shortcuts in a table of neighbors and replaces them with INVALID_INDEX. More...

#include <GNeighborFinder.h>

List of all members.

Public Member Functions

 GShortcutPruner (size_t *pNeighborhoods, size_t n, size_t k)
 pNeighborMap is expected to be an array of size n*k, where n is the number of points, and k is the number of neighbors.
 ~GShortcutPruner ()
void setCycleThreshold (size_t cycleThresh)
 Sets the cycle-length threshold. (The default is 14.)
void setSubGraphRange (size_t range)
 Sets the sub graph range. (The default is 6.)
size_t prune ()
 Do the pruning. Returns the number of shortcuts that were removed. Any atomic cycles in the graph (where neighbors are treated as bi-directional) with a cycle-length of cycleThresh or bigger indicates the existence of a shortcut that must be cut. To determine which edge in the cycle is the shortcut, it will make a subgraph containing all nodes withing "subGraphRange" hops of any vertex in the cycle, and compute the betweenness centrality of every edge in the sub-graph. The edge on the cycle with the largest betweenness is determed to be the shortcut, and is replaced with INVALID_INDEX.
void onDetectBigAtomicCycle (std::vector< size_t > &cycle)
 Internal method.

Static Public Member Functions

static void test ()
 Performs unit tests for this class. Throws an exception if there is a failure.

Protected Member Functions

bool isEveryNodeReachable ()

Protected Attributes

size_t * m_pNeighborhoods
size_t m_n
size_t m_k
size_t m_cycleThresh
size_t m_subGraphRange
size_t m_cuts

Detailed Description

This finds the shortcuts in a table of neighbors and replaces them with INVALID_INDEX.


Constructor & Destructor Documentation

GClasses::GShortcutPruner::GShortcutPruner ( size_t *  pNeighborhoods,
size_t  n,
size_t  k 
)

pNeighborMap is expected to be an array of size n*k, where n is the number of points, and k is the number of neighbors.

GClasses::GShortcutPruner::~GShortcutPruner ( )

Member Function Documentation

bool GClasses::GShortcutPruner::isEveryNodeReachable ( ) [protected]
void GClasses::GShortcutPruner::onDetectBigAtomicCycle ( std::vector< size_t > &  cycle)

Internal method.

size_t GClasses::GShortcutPruner::prune ( )

Do the pruning. Returns the number of shortcuts that were removed. Any atomic cycles in the graph (where neighbors are treated as bi-directional) with a cycle-length of cycleThresh or bigger indicates the existence of a shortcut that must be cut. To determine which edge in the cycle is the shortcut, it will make a subgraph containing all nodes withing "subGraphRange" hops of any vertex in the cycle, and compute the betweenness centrality of every edge in the sub-graph. The edge on the cycle with the largest betweenness is determed to be the shortcut, and is replaced with INVALID_INDEX.

void GClasses::GShortcutPruner::setCycleThreshold ( size_t  cycleThresh) [inline]

Sets the cycle-length threshold. (The default is 14.)

void GClasses::GShortcutPruner::setSubGraphRange ( size_t  range) [inline]

Sets the sub graph range. (The default is 6.)

static void GClasses::GShortcutPruner::test ( ) [static]

Performs unit tests for this class. Throws an exception if there is a failure.


Member Data Documentation

size_t GClasses::GShortcutPruner::m_k [protected]
size_t GClasses::GShortcutPruner::m_n [protected]