GClasses::GShortcutPruner Class Reference

Detailed Description

This uses "betweeenness centrality" to find the shortcuts in a table of neighbors and replaces them with INVALID_INDEX.

#include <GNeighborFinder.h>

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. More...
	~GShortcutPruner ()
void	onDetectBigAtomicCycle (std::vector< size_t > &cycle)
	Internal method. More...
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. More...
void	setCycleThreshold (size_t cycleThresh)
	Sets the cycle-length threshold. (The default is 14.) More...
void	setSubGraphRange (size_t range)
	Sets the sub graph range. (The default is 6.) More...

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

Protected Member Functions
bool	isEveryNodeReachable ()

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

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_cuts

protected

size_t GClasses::GShortcutPruner::m_cycleThresh

protected

size_t GClasses::GShortcutPruner::m_k

protected

size_t GClasses::GShortcutPruner::m_n

protected

size_t* GClasses::GShortcutPruner::m_pNeighborhoods

protected

size_t GClasses::GShortcutPruner::m_subGraphRange

protected