MapCliqueAbstraction Class Reference

A map abstraction based on the reduction of cliques. More...

#include <MapCliqueAbstraction.h>

Inheritance diagram for MapCliqueAbstraction:

Collaboration diagram for MapCliqueAbstraction:

Public Member Functions
	MapCliqueAbstraction (Map *, bool uniform=true)
	Construct a new Graph hierarchy. More...
virtual	~MapCliqueAbstraction ()
virtual MapAbstraction *	Clone (Map *_m)
	return a new abstraction map of the same type as this map abstraction More...
virtual void	VerifyHierarchy ()
bool	Pathable (node *from, node *to)
bool	Pathable (unsigned int from, unsigned int to)
void	GetNumAbstractGraphs (node *from, node *to, std::vector< node * > &fromChain, std::vector< node * > &toChain)
void	ClearMarkedNodes ()
void	clearDisplayLists ()
virtual void	RemoveNode (node *n)
void	RemoveEdge (edge *e, unsigned int absLevel)
virtual void	AddNode (node *n)
virtual void	AddEdge (edge *e, unsigned int absLevel)
void	RepairAbstraction ()
node *	findNodeParent (node *n)
edge *	findEdgeParent (edge *e, unsigned int absLevel)
int	MeasureRepairHits ()
	MeasureRepairHits Measure the number of levels hit during repair. More...

Protected Member Functions
virtual Graph *	abstractGraph (Graph *g)
virtual Graph *	cliqueAbstractGraph (Graph *g)
void	addNodesToParent (Graph *g, node *n, node *parent, int width)
void	addTunnel (node *n, Graph *g, node *newNode)
void	renameNodeInAbstraction (node *which, unsigned int oldID)
int	getChildGroups (node *which)
void	splitNode (node *which, int numGroups)
void	addNodeToRepairQ (node *n)
void	removeNodeFromRepairQ (node *n)
void	resetLocationCache (node *n)
void	checkAndCreateParent (node *which)
void	insertNodeIntoHierarchy (node *newNode)
void	transferGroup (int group, node *oldParent, node *newParent)
void	abstractUpEdge (unsigned int absLevel, edge *e)
void	extractGroupIntoNewNode (node *parent, int group)
void	mergeGroupIntoNeighbor (node *parent, int group, node *neighbor=0)
bool	checkNeighborClique (node *child, node *neighbor)
node *	findNeighborCliques (node *parent, int group)
node *	findNeighborCliques (node *)
int	getGroupSize (node *parent, int group)
node *	getNodeInGroup (node *parent, int group)

Private Member Functions
void	buildAbstractions ()
void	cleanMemory ()

Private Attributes
std::vector< GLuint >	displayLists
std::vector< node * >	modifiedNodeQ
bool	abstractUniformly

Detailed Description

A map abstraction based on the reduction of cliques.

Definition at line 21 of file MapCliqueAbstraction.h.

Constructor & Destructor Documentation

MapCliqueAbstraction()

MapCliqueAbstraction::MapCliqueAbstraction	(	Map *	_m,
		bool	uniform = true
	)

Construct a new Graph hierarchy.

Constructions a new Graph abstraction hierarchy from the Graph using the designated abstraction method.

Definition at line 36 of file MapCliqueAbstraction.cpp.

References buildAbstractions().

Referenced by Clone().

~MapCliqueAbstraction()

MapCliqueAbstraction::~MapCliqueAbstraction ( )

virtual

Definition at line 46 of file MapCliqueAbstraction.cpp.

References cleanMemory().

Member Function Documentation

abstractGraph()

Graph * MapCliqueAbstraction::abstractGraph ( Graph *  g )

protectedvirtual

Definition at line 217 of file MapCliqueAbstraction.cpp.

References cliqueAbstractGraph().

Referenced by buildAbstractions().

abstractUpEdge()

void MapCliqueAbstraction::abstractUpEdge ( unsigned int  absLevel, edge *  e  )

protected

Definition at line 1682 of file MapCliqueAbstraction.cpp.

References Graph::AddEdge(), Graph::FindEdge(), edge::getFrom(), edge::GetLabelL(), node::GetLabelL(), Graph::GetNode(), node::GetNumEdges(), edge::getTo(), GraphAbstractionConstants::kEdgeCapacity, GraphAbstractionConstants::kParent, kRepairGraph, edge::SetLabelL(), and verbose.

Referenced by insertNodeIntoHierarchy(), and transferGroup().

AddEdge()

void MapCliqueAbstraction::AddEdge ( edge *  e, unsigned int  absLevel  )

virtual

Definition at line 972 of file MapCliqueAbstraction.cpp.

AddNode()

void MapCliqueAbstraction::AddNode ( node *  n )

virtual

Definition at line 968 of file MapCliqueAbstraction.cpp.

addNodesToParent()

void MapCliqueAbstraction::addNodesToParent ( Graph *  g, node *  n, node *  parent, int  width  )

protected

Definition at line 265 of file MapCliqueAbstraction.cpp.

References node::edgeIterNext(), node::getEdgeIter(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, node::SetLabelL(), and width.

addNodeToRepairQ()

void MapCliqueAbstraction::addNodeToRepairQ ( node *  n )

protected

Definition at line 1006 of file MapCliqueAbstraction.cpp.

References graph_object::key, kRepairGraph, modifiedNodeQ, and verbose.

Referenced by RemoveEdge(), and RemoveNode().

addTunnel()

void MapCliqueAbstraction::addTunnel ( node *  n, Graph *  g, node *  newNode  )

protected

Definition at line 921 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), node::getNeighborIter(), Graph::GetNode(), node::GetNum(), node::GetNumEdges(), kBuildGraph, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, node::nodeNeighborNext(), node::SetLabelL(), and verbose.

buildAbstractions()

void MapCliqueAbstraction::buildAbstractions ( )

private

Definition at line 188 of file MapCliqueAbstraction.cpp.

References abstractGraph(), cleanMemory(), displayLists, GetMapGraph(), Graph::GetNumEdges(), Graph::GetNumNodes(), kMiscMessages, Graph::printStats(), and verbose.

Referenced by MapCliqueAbstraction().

checkAndCreateParent()

void MapCliqueAbstraction::checkAndCreateParent ( node *  which )

protected

Definition at line 1578 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNodeBlocked, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, GraphAbstractionConstants::kUnknownPosition, GraphAbstractionConstants::kXCoordinate, node::SetLabelF(), and node::SetLabelL().

Referenced by insertNodeIntoHierarchy().

checkNeighborClique()

bool MapCliqueAbstraction::checkNeighborClique ( node *  child, node *  neighbor  )

protected

Definition at line 1381 of file MapCliqueAbstraction.cpp.

References Graph::FindEdge(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), node::GetNumEdges(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, and GraphAbstractionConstants::kParent.

Referenced by findNeighborCliques().

cleanMemory()

void MapCliqueAbstraction::cleanMemory ( )

private

Definition at line 172 of file MapCliqueAbstraction.cpp.

References clearDisplayLists(), and displayLists.

Referenced by buildAbstractions(), and ~MapCliqueAbstraction().

clearDisplayLists()

void MapCliqueAbstraction::clearDisplayLists

(

)

Definition at line 179 of file MapCliqueAbstraction.cpp.

References displayLists.

Referenced by cleanMemory().

ClearMarkedNodes()

void MapCliqueAbstraction::ClearMarkedNodes

(

)

cliqueAbstractGraph()

Graph * MapCliqueAbstraction::cliqueAbstractGraph ( Graph *  g )

protectedvirtual

Definition at line 289 of file MapCliqueAbstraction.cpp.

References abstractUniformly, Graph::AddEdge(), Graph::AddNode(), d, Graph::edgeIterNext(), node::edgeIterNext(), Graph::FindEdge(), Graph::getEdgeIter(), node::getEdgeIter(), edge::getFrom(), edge::GetLabelL(), node::GetLabelL(), Graph::GetNode(), Graph::getNodeIter(), node::GetNum(), node::GetNumEdges(), node::getNumIncomingEdges(), node::getNumOutgoingEdges(), edge::getTo(), GraphAbstractionConstants::kAbstractionLevel, kBuildGraph, GraphAbstractionConstants::kEdgeCapacity, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNodeBlocked, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, GraphAbstractionConstants::kUnknownPosition, GraphAbstractionConstants::kXCoordinate, Graph::nodeIterNext(), node::SetLabelF(), edge::SetLabelL(), node::SetLabelL(), and verbose.

Referenced by abstractGraph().

Clone()

virtual MapAbstraction* MapCliqueAbstraction::Clone ( Map *  _m )

inlinevirtual

return a new abstraction map of the same type as this map abstraction

Definition at line 26 of file MapCliqueAbstraction.h.

References MapCliqueAbstraction().

extractGroupIntoNewNode()

void MapCliqueAbstraction::extractGroupIntoNewNode ( node *  parent, int  group  )

protected

Definition at line 1469 of file MapCliqueAbstraction.cpp.

References Graph::AddNode(), node::GetLabelL(), insertNodeIntoHierarchy(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kNodeBlocked, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, GraphAbstractionConstants::kUnknownPosition, GraphAbstractionConstants::kXCoordinate, node::SetLabelF(), node::SetLabelL(), and transferGroup().

Referenced by splitNode().

findEdgeParent()

edge * MapCliqueAbstraction::findEdgeParent	(	edge *	e,
		unsigned int	absLevel
	)

Definition at line 1776 of file MapCliqueAbstraction.cpp.

References Graph::FindEdge(), edge::getFrom(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), edge::getTo(), and GraphAbstractionConstants::kParent.

Referenced by RemoveEdge(), RemoveNode(), and transferGroup().

findNeighborCliques() [1/2]

node * MapCliqueAbstraction::findNeighborCliques ( node *  child )

protected

Definition at line 1360 of file MapCliqueAbstraction.cpp.

References checkNeighborClique(), node::edgeIterNext(), node::getEdgeIter(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), and GraphAbstractionConstants::kAbstractionLevel.

findNeighborCliques() [2/2]

node * MapCliqueAbstraction::findNeighborCliques ( node *  parent, int  group  )

protected

Definition at line 1335 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), Graph::GetNode(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, and GraphAbstractionConstants::kTemporaryLabel.

Referenced by insertNodeIntoHierarchy(), and splitNode().

findNodeParent()

node * MapCliqueAbstraction::findNodeParent

(

node *

n

)

Definition at line 1759 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), GraphAbstractionConstants::kAbstractionLevel, and GraphAbstractionConstants::kParent.

Referenced by RemoveNode(), and VerifyHierarchy().

getChildGroups()

int MapCliqueAbstraction::getChildGroups ( node *  which )

protected

Definition at line 1146 of file MapCliqueAbstraction.cpp.

References node::edgeIterNext(), node::getEdgeIter(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, kRepairGraph, GraphAbstractionConstants::kTemporaryLabel, node::SetLabelL(), and verbose.

Referenced by RepairAbstraction().

getGroupSize()

int MapCliqueAbstraction::getGroupSize ( node *  parent, int  group  )

protected

Definition at line 1314 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), Graph::GetNode(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, and GraphAbstractionConstants::kTemporaryLabel.

Referenced by splitNode().

getNodeInGroup()

node * MapCliqueAbstraction::getNodeInGroup ( node *  parent, int  group  )

protected

Definition at line 1295 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), Graph::GetNode(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, and GraphAbstractionConstants::kTemporaryLabel.

Referenced by splitNode().

GetNumAbstractGraphs()

void MapCliqueAbstraction::GetNumAbstractGraphs	(	node *	from,
		node *	to,
		std::vector< node * > &	fromChain,
		std::vector< node * > &	toChain
	)

insertNodeIntoHierarchy()

void MapCliqueAbstraction::insertNodeIntoHierarchy ( node *  newNode )

protected

Definition at line 1496 of file MapCliqueAbstraction.cpp.

References abstractUpEdge(), checkAndCreateParent(), node::edgeIterNext(), findNeighborCliques(), node::getEdge(), node::getEdgeIter(), edge::getFrom(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), node::GetNumEdges(), edge::getTo(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, kRepairGraph, resetLocationCache(), node::SetLabelL(), and verbose.

Referenced by extractGroupIntoNewNode().

MeasureRepairHits()

int MapCliqueAbstraction::MeasureRepairHits

(

)

MeasureRepairHits Measure the number of levels hit during repair.

Always returns 0 unless compiled with -D INSTRUMENT_REPAIR

Definition at line 1842 of file MapCliqueAbstraction.cpp.

mergeGroupIntoNeighbor()

void MapCliqueAbstraction::mergeGroupIntoNeighbor ( node *  parent, int  group, node *  neighbor = 0  )

protected

Definition at line 1415 of file MapCliqueAbstraction.cpp.

References node::edgeIterNext(), node::getEdgeIter(), edge::getFrom(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), edge::getTo(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, kRepairGraph, GraphAbstractionConstants::kTemporaryLabel, transferGroup(), and verbose.

Referenced by splitNode().

Pathable() [1/2]

bool MapCliqueAbstraction::Pathable	(	node *	from,
		node *	to
	)

Definition at line 949 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), GraphAbstractionConstants::kAbstractionLevel, and GraphAbstractionConstants::kParent.

Referenced by Pathable().

Pathable() [2/2]

bool MapCliqueAbstraction::Pathable	(	unsigned int	from,
		unsigned int	to
	)

Definition at line 944 of file MapCliqueAbstraction.cpp.

References Pathable().

RemoveEdge()

void MapCliqueAbstraction::RemoveEdge	(	edge *	e,
		unsigned int	absLevel
	)

Definition at line 978 of file MapCliqueAbstraction.cpp.

References addNodeToRepairQ(), findEdgeParent(), edge::getFrom(), edge::GetLabelL(), GraphAbstractionConstants::kEdgeCapacity, GraphAbstractionConstants::kParent, and edge::SetLabelL().

Referenced by RemoveNode(), and transferGroup().

RemoveNode()

void MapCliqueAbstraction::RemoveNode ( node *  n )

virtual

Definition at line 1037 of file MapCliqueAbstraction.cpp.

References addNodeToRepairQ(), node::edgeIterNext(), findEdgeParent(), findNodeParent(), node::getEdgeIter(), edge::GetLabelL(), node::GetLabelL(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kEdgeCapacity, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, kRepairGraph, RemoveEdge(), removeNodeFromRepairQ(), renameNodeInAbstraction(), resetLocationCache(), edge::SetLabelL(), node::SetLabelL(), and verbose.

removeNodeFromRepairQ()

void MapCliqueAbstraction::removeNodeFromRepairQ ( node *  n )

protected

Definition at line 1024 of file MapCliqueAbstraction.cpp.

References graph_object::key, and modifiedNodeQ.

Referenced by RemoveNode().

renameNodeInAbstraction()

void MapCliqueAbstraction::renameNodeInAbstraction ( node *  which, unsigned int  oldID  )

protected

Definition at line 1801 of file MapCliqueAbstraction.cpp.

References node::GetLabelL(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, and node::SetLabelL().

Referenced by RemoveNode().

RepairAbstraction()

void MapCliqueAbstraction::RepairAbstraction

(

)

Definition at line 1109 of file MapCliqueAbstraction.cpp.

References getChildGroups(), node::GetLabelL(), GraphAbstractionConstants::kAbstractionLevel, graph_object::key, kRepairGraph, modifiedNodeQ, splitNode(), and verbose.

resetLocationCache()

void MapCliqueAbstraction::resetLocationCache ( node *  n )

protected

Definition at line 1726 of file MapCliqueAbstraction.cpp.

References node::edgeIterNext(), node::getEdgeIter(), node::GetLabelL(), Graph::GetNode(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kParent, GraphAbstractionConstants::kUnknownPosition, GraphAbstractionConstants::kXCoordinate, and node::SetLabelF().

Referenced by insertNodeIntoHierarchy(), RemoveNode(), and transferGroup().

splitNode()

void MapCliqueAbstraction::splitNode ( node *  which, int  numGroups  )

protected

Definition at line 1204 of file MapCliqueAbstraction.cpp.

References extractGroupIntoNewNode(), findNeighborCliques(), getGroupSize(), node::GetLabelL(), getNodeInGroup(), node::GetNumEdges(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, kRepairGraph, mergeGroupIntoNeighbor(), and verbose.

Referenced by RepairAbstraction().

transferGroup()

void MapCliqueAbstraction::transferGroup ( int  group, node *  oldParent, node *  newParent  )

protected

Definition at line 1607 of file MapCliqueAbstraction.cpp.

References abstractUpEdge(), node::edgeIterNext(), findEdgeParent(), node::getEdgeIter(), edge::GetLabelL(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kEdgeCapacity, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, kRepairGraph, GraphAbstractionConstants::kTemporaryLabel, RemoveEdge(), resetLocationCache(), edge::SetLabelL(), node::SetLabelL(), and verbose.

Referenced by extractGroupIntoNewNode(), and mergeGroupIntoNeighbor().

VerifyHierarchy()

void MapCliqueAbstraction::VerifyHierarchy ( )

virtual

Definition at line 51 of file MapCliqueAbstraction.cpp.

References fequal(), findNodeParent(), node::GetLabelF(), node::GetLabelL(), Graph::GetNode(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kEdgeCapacity, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, GraphAbstractionConstants::kXCoordinate, GraphAbstractionConstants::kYCoordinate, and GraphAbstractionConstants::kZCoordinate.

Member Data Documentation

abstractUniformly

bool MapCliqueAbstraction::abstractUniformly

private

Definition at line 92 of file MapCliqueAbstraction.h.

Referenced by cliqueAbstractGraph().

displayLists

std::vector<GLuint> MapCliqueAbstraction::displayLists

private

Definition at line 88 of file MapCliqueAbstraction.h.

Referenced by buildAbstractions(), cleanMemory(), and clearDisplayLists().

modifiedNodeQ

std::vector<node *> MapCliqueAbstraction::modifiedNodeQ

private

Definition at line 91 of file MapCliqueAbstraction.h.

Referenced by addNodeToRepairQ(), removeNodeFromRepairQ(), and RepairAbstraction().

---

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

• /home/sturtevant/nightly/hog2/abstraction/MapCliqueAbstraction.h
• /home/sturtevant/nightly/hog2/abstraction/MapCliqueAbstraction.cpp