Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

graphAbstraction Class Reference

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

#include <graphAbstraction.h>

Inheritance diagram for graphAbstraction:

Inheritance graph
[legend]
List of all members.

Public Member Functions

 graphAbstraction ()
virtual ~graphAbstraction ()
virtual bool pathable (node *from, node *to)=0
 is there a legal path between these 2 nodes?

void getParentHierarchy (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

graph * getAbstractGraph (int level)
 return the abstract graph at the given level

unsigned int getNumAbstractGraphs ()
 return the total number of graphs in the hierarchy

virtual double h (node *a, node *b)=0
 heuristic cost between any two nodes

double distance (path *p)
 length in distance of a path

node * getNthParent (node *which, int n)
 return nth level parent of which or null if it doesn't exist

node * getParent (node *which)
long getNumChildren (node *which)
node * getNthChild (node *which, int n)
long getAbstractionLevel (node *which)
graph * getAbstractGraph (node *which)
virtual void verifyHierarchy ()=0
 verify that the hierarchy is consistent

void clearMarkedNodes ()
 get current revision of hierarchy -- indicates if changes have been made */

virtual void removeNode (node *n)=0
 remove node from abstraction

virtual void removeEdge (edge *e, unsigned int absLevel)=0
 remove edge from abstraction

virtual void addNode (node *n)=0
 add node to abstraction

virtual void addEdge (edge *e, unsigned int absLevel)=0
 add edge to abstraction

virtual void repairAbstraction ()=0
 This must be called after any of the above add/remove operations.

virtual int measureRepairHits ()
void measureAbstractionValues (int level, double &n, double &n_dev, double &c, double &c_dev)
double measureAverageNodeWidth (int level)

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.

Constructor & Destructor Documentation

graphAbstraction::graphAbstraction (   )  [inline]
 

graphAbstraction::~graphAbstraction (   )  [virtual]
 

Member Function Documentation

virtual void graphAbstraction::addEdge (  edge *  e,
unsigned int  absLevel
)  [pure virtual]
 

add edge to abstraction

Implemented in clusterAbstraction, loadedCliqueAbstraction, mapCliqueAbstraction, mapFlatAbstraction, MapLineAbstraction, mapQuadTreeAbstraction, NodeLimitAbstraction, and radiusAbstraction.

virtual void graphAbstraction::addNode (  node *  n  )  [pure virtual]
 

add node to abstraction

Implemented in clusterAbstraction, loadedCliqueAbstraction, mapCliqueAbstraction, mapFlatAbstraction, MapLineAbstraction, mapQuadTreeAbstraction, NodeLimitAbstraction, and radiusAbstraction.

void graphAbstraction::clearMarkedNodes (   ) 
 

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

Reimplemented in mapAbstraction, and mapCliqueAbstraction.

int graphAbstraction::computeWidth (  node *  n  )  [private]
 

int graphAbstraction::countEdgesAtDistance (  node *  child,
node *  parent,
std::vector< int > &  dists
)  [private]
 

double graphAbstraction::distance (  path *  p  ) 
 

length in distance of a path

graph* graphAbstraction::getAbstractGraph (  node *  which  )  [inline]
 

graph* graphAbstraction::getAbstractGraph (  int  level  )  [inline]
 

return the abstract graph at the given level

long graphAbstraction::getAbstractionLevel (  node *  which  )  [inline]
 

node* graphAbstraction::getNthChild (  node *  which,
int  n
)  [inline]
 

node * graphAbstraction::getNthParent (  node *  which,
int  n
) 
 

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

unsigned int graphAbstraction::getNumAbstractGraphs (   )  [inline]
 

return the total number of graphs in the hierarchy

long graphAbstraction::getNumChildren (  node *  which  )  [inline]
 

int graphAbstraction::getNumExternalEdges (  node *  n,
node *  p
)  [private]
 

node* graphAbstraction::getParent (  node *  which  )  [inline]
 

void graphAbstraction::getParentHierarchy (  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

Reimplemented in loadedCliqueAbstraction, and mapCliqueAbstraction.

virtual double graphAbstraction::h (  node *  a,
node *  b
)  [pure virtual]
 

heuristic cost between any two nodes

Implemented in loadedCliqueAbstraction, and mapAbstraction.

void graphAbstraction::measureAbstractionValues (  int  level,
double &  n,
double &  n_dev,
double &  c,
double &  c_dev
) 
 

double graphAbstraction::measureAverageNodeWidth (  int  level  ) 
 

double graphAbstraction::measureExpectedNodeWidth (  node *  n  )  [private]
 

virtual int graphAbstraction::measureRepairHits (   )  [inline, virtual]
 

Reimplemented in mapCliqueAbstraction.

virtual bool graphAbstraction::pathable (  node *  from,
node *  to
)  [pure virtual]
 

is there a legal path between these 2 nodes?

Implemented in clusterAbstraction, loadedCliqueAbstraction, mapCliqueAbstraction, mapFlatAbstraction, MapLineAbstraction, mapQuadTreeAbstraction, NodeLimitAbstraction, and radiusAbstraction.

virtual void graphAbstraction::removeEdge (  edge *  e,
unsigned int  absLevel
)  [pure virtual]
 

remove edge from abstraction

Implemented in clusterAbstraction, loadedCliqueAbstraction, mapCliqueAbstraction, mapFlatAbstraction, MapLineAbstraction, mapQuadTreeAbstraction, NodeLimitAbstraction, and radiusAbstraction.

virtual void graphAbstraction::removeNode (  node *  n  )  [pure virtual]
 

remove node from abstraction

Implemented in clusterAbstraction, loadedCliqueAbstraction, mapCliqueAbstraction, mapFlatAbstraction, MapLineAbstraction, mapQuadTreeAbstraction, NodeLimitAbstraction, and radiusAbstraction.

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 clusterAbstraction, loadedCliqueAbstraction, mapCliqueAbstraction, mapFlatAbstraction, MapLineAbstraction, mapQuadTreeAbstraction, NodeLimitAbstraction, and radiusAbstraction.

virtual void graphAbstraction::verifyHierarchy (   )  [pure virtual]
 

verify that the hierarchy is consistent

Implemented in clusterAbstraction, loadedCliqueAbstraction, mapCliqueAbstraction, mapFlatAbstraction, MapLineAbstraction, mapQuadTreeAbstraction, NodeLimitAbstraction, and radiusAbstraction.

int graphAbstraction::widthBFS (  node *  child,
node *  parent
)  [private]
 

Member Data Documentation

std::vector<graph *> graphAbstraction::abstractions [protected]
 

The documentation for this class was generated from the following files:
Generated on Tue Aug 18 03:42:52 2009 for HOG by doxygen 1.3.4