HOG2
Public Member Functions | Protected Attributes | Private Member Functions | List of all members
GraphAbstraction Class Referenceabstract

A generic class for basic operations on Graph abstractions. More...

#include <GraphAbstraction.h>

Inheritance diagram for GraphAbstraction:
Inheritance graph
[legend]

Public Member Functions

 GraphAbstraction ()
 
virtual ~GraphAbstraction ()
 
virtual bool Pathable (node *from, node *to)=0
 is there a legal path between these 2 nodes? More...
 
void GetNumAbstractGraphs (node *from, node *to, std::vector< node * > &fromChain, std::vector< node * > &toChain)
 given 2 nodes, find as much of their hierarchy that exists in the Graph More...
 
Graph * GetAbstractGraph (int level)
 return the abstract Graph at the given level More...
 
unsigned int getNumAbstractGraphs ()
 return the total number of graphs in the hierarchy More...
 
virtual double h (node *a, node *b)=0
 heuristic cost between any two nodes More...
 
double distance (path *p)
 length in distance of a path More...
 
node * GetNthParent (node *which, int n)
 return nth level parent of which or null if it doesn't exist More...
 
bool IsParentOf (node *parent, node *child)
 return true if the first node is a parent of or is equal two the second node More...
 
node * GetParent (node *which)
 
long GetNumChildren (node *which)
 
node * GetNthChild (node *which, int n)
 
node * GetRandomGroundNodeFromNode (node *n)
 
long GetAbstractionLevel (node *which)
 
Graph * GetAbstractGraph (node *which)
 
virtual void VerifyHierarchy ()=0
 verify that the hierarchy is consistent More...
 
void ClearMarkedNodes ()
 rebuild hierarchy from original domain *‍/ More...
 
virtual void RemoveNode (node *n)=0
 remove node from abstraction More...
 
virtual void RemoveEdge (edge *e, unsigned int absLevel)=0
 remove edge from abstraction More...
 
virtual void AddNode (node *n)=0
 add node to abstraction More...
 
virtual void AddEdge (edge *e, unsigned int absLevel)=0
 add edge to abstraction More...
 
virtual void RepairAbstraction ()=0
 This must be called after any of the above add/remove operations. More...
 
virtual int MeasureRepairHits ()
 
void MeasureAbstractionValues (int level, double &n, double &n_dev, double &c, double &c_dev)
 
double MeasureAverageNodeWidth (int level)
 
virtual void OpenGLDraw () const
 
virtual recVec GetNodeLoc (node *) const
 

Protected Attributes

std::vector< Graph * > abstractions
 

Private Member Functions

int ComputeWidth (node *n)
 
int WidthBFS (node *child, node *parent)
 
double MeasureExpectedNodeWidth (node *n)
 
int GetNumExternalEdges (node *n, node *p)
 
int CountEdgesAtDistance (node *child, node *parent, std::vector< int > &dists)
 

Detailed Description

A generic class for basic operations on Graph abstractions.

Definition at line 63 of file GraphAbstraction.h.

Constructor & Destructor Documentation

◆ GraphAbstraction()

GraphAbstraction::GraphAbstraction ( )
inline

Definition at line 65 of file GraphAbstraction.h.

◆ ~GraphAbstraction()

GraphAbstraction::~GraphAbstraction ( )
virtual

Definition at line 29 of file GraphAbstraction.cpp.

Member Function Documentation

◆ AddEdge()

virtual void GraphAbstraction::AddEdge ( edge *  e,
unsigned int  absLevel 
)
pure virtual

add edge to abstraction

Implemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

◆ AddNode()

virtual void GraphAbstraction::AddNode ( node *  n)
pure virtual

add node to abstraction

Implemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

◆ ClearMarkedNodes()

void GraphAbstraction::ClearMarkedNodes ( )

rebuild hierarchy from original domain *‍/

get current revision of hierarchy – indicates if changes have been made *‍/

Definition at line 89 of file GraphAbstraction.cpp.

References Graph::edgeIterNext(), and Graph::getEdgeIter().

◆ ComputeWidth()

int GraphAbstraction::ComputeWidth ( node *  n)
private

Definition at line 141 of file GraphAbstraction.cpp.

References node::GetLabelL(), GraphAbstractionConstants::kNumAbstractedNodes, max, and width.

◆ CountEdgesAtDistance()

int GraphAbstraction::CountEdgesAtDistance ( node *  child,
node *  parent,
std::vector< int > &  dists 
)
private

Definition at line 291 of file GraphAbstraction.cpp.

References Graph::GetNode(), node::GetNum(), graph_object::key, and GraphAbstractionConstants::kParent.

◆ distance()

double GraphAbstraction::distance ( path *  p)

length in distance of a path

Definition at line 102 of file GraphAbstraction.cpp.

References path::n, and path::next.

◆ GetAbstractGraph() [1/2]

Graph* GraphAbstraction::GetAbstractGraph ( int  level)
inline

return the abstract Graph at the given level

Definition at line 74 of file GraphAbstraction.h.

References abstractions.

Referenced by praStar::astar(), spreadPRAStar::buildNextAbstractPath(), praStar2::buildNextAbstractPath(), craStar::buildNextAbstractPath(), DoRandomPath(), craStar::doRefinement(), craStar::findGoalNode(), corridorAStar::getBestPath(), AbstractionSearchEnvironment::getNeighbors(), praStar::GetPath(), spreadPRAStar::GetPath(), praStar2::GetPath(), aStarOld::GetPath(), craStar::GetPath(), IRDijkstra::GetRealNode(), IRAStar::GetRealNode(), CFOptimalRefinement::GetRealNode(), GraphRefinementEnvironment::HCost(), AbstractionSearchEnvironment::heuristic(), FringeSearch::initializeSearch(), craStar::nextPathNode(), IRDijkstra::RefineNode(), IRAStar::RefineNode(), CFOptimalRefinement::RefineNode(), praStar2::selectTopAbstractionLevel(), spreadPRAStar::setupSearch(), craStar::setupSearch(), IRDijkstra::ShouldAddEdge(), IRAStar::ShouldAddEdge(), and CFOptimalRefinement::ShouldAddEdge().

◆ GetAbstractGraph() [2/2]

Graph* GraphAbstraction::GetAbstractGraph ( node *  which)
inline

Definition at line 93 of file GraphAbstraction.h.

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

◆ GetAbstractionLevel()

long GraphAbstraction::GetAbstractionLevel ( node *  which)
inline

Definition at line 92 of file GraphAbstraction.h.

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

Referenced by IRDijkstra::FindTopLevelNode(), IRAStar::FindTopLevelNode(), CFOptimalRefinement::FindTopLevelNode(), GetNthChild(), GetParent(), praStar::GetPath(), IRDijkstra::RefineNode(), IRAStar::RefineNode(), CFOptimalRefinement::RefineNode(), praStar2::selectTopAbstractionLevel(), IRDijkstra::SetInitialValues(), IRAStar::SetInitialValues(), CFOptimalRefinement::SetInitialValues(), IRDijkstra::ShouldAddEdge(), IRAStar::ShouldAddEdge(), and CFOptimalRefinement::ShouldAddEdge().

◆ GetNodeLoc()

virtual recVec GraphAbstraction::GetNodeLoc ( node *  ) const
inlinevirtual

Reimplemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

Definition at line 120 of file GraphAbstraction.h.

References recVec::x, recVec::y, and recVec::z.

Referenced by IRDijkstra::OpenGLDraw(), IRAStar::OpenGLDraw(), and CFOptimalRefinement::OpenGLDraw().

◆ GetNthChild()

node* GraphAbstraction::GetNthChild ( node *  which,
int  n 
)
inline

Definition at line 88 of file GraphAbstraction.h.

References abstractions, GetAbstractionLevel(), node::GetLabelL(), and GraphAbstractionConstants::kFirstData.

Referenced by IRDijkstra::RefineNode(), IRAStar::RefineNode(), and CFOptimalRefinement::RefineNode().

◆ GetNthParent()

node * GraphAbstraction::GetNthParent ( node *  which,
int  n 
)

return nth level parent of which or null if it doesn't exist

Definition at line 67 of file GraphAbstraction.cpp.

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

Referenced by aStar::ABSNode(), craStar::doRefinement(), corridorAStar::getBestPath(), craStar::getNextNode(), GraphRefinementEnvironment::GetSuccessors(), and GraphRefinementEnvironment::GoalTest().

◆ getNumAbstractGraphs()

unsigned int GraphAbstraction::getNumAbstractGraphs ( )
inline

return the total number of graphs in the hierarchy

Definition at line 76 of file GraphAbstraction.h.

References abstractions.

Referenced by IRDijkstra::FindTopLevelNode(), IRAStar::FindTopLevelNode(), and CFOptimalRefinement::FindTopLevelNode().

◆ GetNumAbstractGraphs()

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

given 2 nodes, find as much of their hierarchy that exists in the Graph

Definition at line 39 of file GraphAbstraction.cpp.

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

Referenced by praStar::GetPath(), spreadPRAStar::setupSearch(), praStar2::setupSearch(), and craStar::setupSearch().

◆ GetNumChildren()

long GraphAbstraction::GetNumChildren ( node *  which)
inline

Definition at line 87 of file GraphAbstraction.h.

References node::GetLabelL(), and GraphAbstractionConstants::kNumAbstractedNodes.

Referenced by IRDijkstra::RefineNode(), IRAStar::RefineNode(), and CFOptimalRefinement::RefineNode().

◆ GetNumExternalEdges()

int GraphAbstraction::GetNumExternalEdges ( node *  n,
node *  p 
)
private

Definition at line 275 of file GraphAbstraction.cpp.

References node::getNeighborIter(), Graph::GetNode(), and node::nodeNeighborNext().

◆ GetParent()

node* GraphAbstraction::GetParent ( node *  which)
inline

Definition at line 86 of file GraphAbstraction.h.

References abstractions, GetAbstractionLevel(), node::GetLabelL(), and GraphAbstractionConstants::kParent.

Referenced by IRDijkstra::FindTopLevelNode(), IRAStar::FindTopLevelNode(), and CFOptimalRefinement::FindTopLevelNode().

◆ GetRandomGroundNodeFromNode()

node * GraphAbstraction::GetRandomGroundNodeFromNode ( node *  n)

Definition at line 331 of file GraphAbstraction.cpp.

◆ h()

virtual double GraphAbstraction::h ( node *  a,
node *  b 
)
pure virtual

heuristic cost between any two nodes

Implemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

Referenced by praStar::astar(), DoRandomPath(), corridorAStar::getBestPath(), craStar::getNextNode(), aStarOld::GetPath(), FringeSearch::h(), GraphRefinementEnvironment::HCost(), AbstractionSearchEnvironment::heuristic(), aStarOld::relaxEdge(), corridorAStar::relaxEdge(), praStar::relaxEdge(), corridorAStar::relaxFinalEdge(), corridorAStar::relaxFirstEdge(), CFOptimalRefinement::UpdateG(), and CFOptimalRefinement::UpdateH().

◆ IsParentOf()

bool GraphAbstraction::IsParentOf ( node *  parent,
node *  child 
)

return true if the first node is a parent of or is equal two the second node

Definition at line 78 of file GraphAbstraction.cpp.

Referenced by IRDijkstra::SetInitialValues(), IRAStar::SetInitialValues(), CFOptimalRefinement::SetInitialValues(), IRDijkstra::ShouldAddEdge(), IRAStar::ShouldAddEdge(), and CFOptimalRefinement::ShouldAddEdge().

◆ MeasureAbstractionValues()

void GraphAbstraction::MeasureAbstractionValues ( int  level,
double &  n,
double &  n_dev,
double &  c,
double &  c_dev 
)

Definition at line 109 of file GraphAbstraction.cpp.

References Graph::getNodeIter(), GraphAbstractionConstants::kNumAbstractedNodes, and Graph::nodeIterNext().

◆ MeasureAverageNodeWidth()

double GraphAbstraction::MeasureAverageNodeWidth ( int  level)

Definition at line 186 of file GraphAbstraction.cpp.

References Graph::getNodeIter(), and Graph::nodeIterNext().

◆ MeasureExpectedNodeWidth()

double GraphAbstraction::MeasureExpectedNodeWidth ( node *  n)
private

Definition at line 212 of file GraphAbstraction.cpp.

References node::GetLabelL(), and GraphAbstractionConstants::kNumAbstractedNodes.

◆ MeasureRepairHits()

virtual int GraphAbstraction::MeasureRepairHits ( )
inlinevirtual

Definition at line 115 of file GraphAbstraction.h.

◆ OpenGLDraw()

virtual void GraphAbstraction::OpenGLDraw ( ) const
inlinevirtual

Reimplemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

Definition at line 119 of file GraphAbstraction.h.

◆ Pathable()

virtual bool GraphAbstraction::Pathable ( node *  from,
node *  to 
)
pure virtual

is there a legal path between these 2 nodes?

Implemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

Referenced by DoRandomPath(), praStar::GetPath(), aStarOld::GetPath(), FringeSearch::GetPath(), aStar::GetPath(), spreadPRAStar::setupSearch(), praStar2::setupSearch(), and craStar::setupSearch().

◆ RemoveEdge()

virtual void GraphAbstraction::RemoveEdge ( edge *  e,
unsigned int  absLevel 
)
pure virtual

remove edge from abstraction

Implemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

◆ RemoveNode()

virtual void GraphAbstraction::RemoveNode ( node *  n)
pure virtual

remove node from abstraction

Implemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

◆ RepairAbstraction()

virtual void GraphAbstraction::RepairAbstraction ( )
pure virtual

This must be called after any of the above add/remove operations.

But the operations can be stacked followed by a single RepairAbstraction call.

Implemented in LoadedBBAbstraction, and LoadedCliqueAbstraction.

◆ VerifyHierarchy()

virtual void GraphAbstraction::VerifyHierarchy ( )
pure virtual

verify that the hierarchy is consistent

Implemented in LoadedCliqueAbstraction, and LoadedBBAbstraction.

◆ WidthBFS()

int GraphAbstraction::WidthBFS ( node *  child,
node *  parent 
)
private

Definition at line 152 of file GraphAbstraction.cpp.

References Graph::GetNode(), node::GetNum(), graph_object::key, and GraphAbstractionConstants::kParent.

Member Data Documentation

◆ abstractions

std::vector<Graph *> GraphAbstraction::abstractions
protected

Definition at line 122 of file GraphAbstraction.h.

Referenced by LoadedCliqueAbstraction::abstractUpEdge(), LoadedBBAbstraction::buildAbstractions(), LoadedCliqueAbstraction::buildAbstractions(), LoadedCliqueAbstraction::checkAndCreateParent(), LoadedCliqueAbstraction::checkNeighborClique(), LoadedBBAbstraction::cleanMemory(), LoadedCliqueAbstraction::cleanMemory(), LoadedBBAbstraction::DrawLevelConnections(), LoadedCliqueAbstraction::DrawLevelConnections(), LoadedCliqueAbstraction::extractGroupIntoNewNode(), LoadedCliqueAbstraction::findEdgeParent(), LoadedCliqueAbstraction::findNeighborCliques(), LoadedBBAbstraction::findNodeParent(), LoadedCliqueAbstraction::findNodeParent(), GetAbstractGraph(), LoadedCliqueAbstraction::getChildGroups(), LoadedCliqueAbstraction::getGroupSize(), LoadedCliqueAbstraction::getNodeInGroup(), LoadedBBAbstraction::GetNodeLoc(), LoadedCliqueAbstraction::GetNodeLoc(), GetNthChild(), getNumAbstractGraphs(), GetParent(), LoadedCliqueAbstraction::insertNodeIntoHierarchy(), LoadedCliqueAbstraction::mergeGroupIntoNeighbor(), LoadedBBAbstraction::OpenGLDraw(), LoadedCliqueAbstraction::OpenGLDraw(), LoadedBBAbstraction::Pathable(), LoadedCliqueAbstraction::Pathable(), LoadedCliqueAbstraction::RemoveEdge(), LoadedCliqueAbstraction::RemoveNode(), LoadedCliqueAbstraction::renameNodeInAbstraction(), LoadedCliqueAbstraction::resetLocationCache(), LoadedCliqueAbstraction::splitNode(), LoadedCliqueAbstraction::transferGroup(), LoadedBBAbstraction::VerifyHierarchy(), and LoadedCliqueAbstraction::VerifyHierarchy().

The documentation for this class was generated from the following files:
Generated by   doxygen 1.8.17