HyperDijkstra

Dijkstra's shortest-path algorithm on a HyperGraph. More...

Collaboration diagram for HyperDijkstra:

Classes
struct	AdjacencyMapEntry
	Entry in the adjacency map storing parent, child, edge, distance, and children set. More...
struct	CostFunction
	Abstract cost function for weighting edges during traversal. More...
struct	TreeAction
	Action interface executed when visiting the shortest-path tree. More...

Public Types
typedef Dictionary< HyperGraph::HGVertex *, AdjacencyMapEntry >	AdjacencyMap
	Map from vertex to its adjacency entry.

Public Member Functions
	HyperDijkstra (HyperGraph *g)
	Constructs a HyperDijkstra for the given graph.
AdjacencyMap &	adjacencyMap ()
	Returns the adjacency map.
HyperGraph *	graph ()
	Returns the underlying graph.
void	shortestPaths (HyperGraph::HGVertex *v, HyperDijkstra::CostFunction *cost, g_type maxDistance=std::numeric_limits< g_type >::max(), g_type comparisonConditioner=1e-3, bool directed=false, g_type maxEdgeCost=std::numeric_limits< g_type >::max())
	Computes shortest paths from a single source vertex.
void	shortestPaths (Set< HyperGraph::HGVertex * > &vset, HyperDijkstra::CostFunction *cost, g_type maxDistance=std::numeric_limits< g_type >::max(), g_type comparisonConditioner=1e-3, bool directed=false, g_type maxEdgeCost=std::numeric_limits< g_type >::max())
	Computes shortest paths from a set of source vertices.
Set< HyperGraph::HGVertex * > &	visited ()
	Returns the set of visited vertices.

Static Public Member Functions
static void	computeTree (AdjacencyMap &amap)
	Builds the tree structure from the adjacency map.
static void	connectedSubset (Set< HyperGraph::HGVertex * > &connected, Set< HyperGraph::HGVertex * > &visited, Set< HyperGraph::HGVertex * > &startingSet, HyperGraph *g, HyperGraph::HGVertex *v, HyperDijkstra::CostFunction *cost, g_type distance, g_type comparisonConditioner, g_type maxEdgeCost=std::numeric_limits< g_type >::max())
	Finds the connected subset of vertices reachable from a given vertex within a distance.
static void	visitAdjacencyMap (AdjacencyMap &amap, TreeAction *action, bool useDistance=false)
	Visits all entries in the adjacency map using the given tree action.

Protected Member Functions
void	reset ()
	Resets the adjacency map and visited set.

Protected Attributes
AdjacencyMap	_adjacencyMap
	Map from vertex to adjacency entry.
HyperGraph *	_graph
	The graph being searched.
Set< HyperGraph::HGVertex * >	_visited
	Set of visited vertices.

Detailed Description

Dijkstra's shortest-path algorithm on a HyperGraph.

Definition at line 38 of file hyper_dijkstra.h.

Constructor & Destructor Documentation

HyperDijkstra()

HyperDijkstra::HyperDijkstra

(

HyperGraph *

g

)

Constructs a HyperDijkstra for the given graph.

Parameters

[in]

g

The hyper graph to operate on.

Member Function Documentation

computeTree()

void HyperDijkstra::computeTree ( AdjacencyMap & amap )

static

Builds the tree structure from the adjacency map.

Parameters

[in]

amap

The adjacency map to process.

connectedSubset()

void HyperDijkstra::connectedSubset ( Set< HyperGraph::HGVertex * > & connected, Set< HyperGraph::HGVertex * > & visited, Set< HyperGraph::HGVertex * > & startingSet, HyperGraph * g, HyperGraph::HGVertex * v, HyperDijkstra::CostFunction * cost, g_type distance, g_type comparisonConditioner, g_type maxEdgeCost = std::numeric_limits< g_type >::max() )

static

Finds the connected subset of vertices reachable from a given vertex within a distance.

Parameters

[out]	connected	The resulting connected vertex set.
[in,out]	visited	Set of already-visited vertices.
[in]	startingSet	Initial set of candidate vertices.
[in]	g	The hyper graph.
[in]	v	The starting vertex.
[in]	cost	The cost function.
[in]	distance	Maximum distance threshold.
[in]	comparisonConditioner	Conditioning factor for comparison.
[in]	maxEdgeCost	Maximum cost for a single edge.

References visited().

shortestPaths() [1/2]

void HyperDijkstra::shortestPaths	(	HyperGraph::HGVertex *	v,
		HyperDijkstra::CostFunction *	cost,
		g_type	maxDistance = std::numeric_limits< g_type >::max(),
		g_type	comparisonConditioner = 1e-3,
		bool	directed = false,
		g_type	maxEdgeCost = std::numeric_limits< g_type >::max() )

Computes shortest paths from a single source vertex.

Parameters

[in]	v	The source vertex.
[in]	cost	The cost function for edge traversal.
[in]	maxDistance	Maximum distance threshold.
[in]	comparisonConditioner	Conditioning factor for distance comparison.
[in]	directed	Whether to consider edge direction.
[in]	maxEdgeCost	Maximum cost for a single edge.

shortestPaths() [2/2]

void HyperDijkstra::shortestPaths	(	Set< HyperGraph::HGVertex * > &	vset,
		HyperDijkstra::CostFunction *	cost,
		g_type	maxDistance = std::numeric_limits< g_type >::max(),
		g_type	comparisonConditioner = 1e-3,
		bool	directed = false,
		g_type	maxEdgeCost = std::numeric_limits< g_type >::max() )

Computes shortest paths from a set of source vertices.

Parameters

[in]	vset	The set of source vertices.
[in]	cost	The cost function for edge traversal.
[in]	maxDistance	Maximum distance threshold.
[in]	comparisonConditioner	Conditioning factor for distance comparison.
[in]	directed	Whether to consider edge direction.
[in]	maxEdgeCost	Maximum cost for a single edge.

visitAdjacencyMap()

void HyperDijkstra::visitAdjacencyMap ( AdjacencyMap & amap, TreeAction * action, bool useDistance = false )

static

Visits all entries in the adjacency map using the given tree action.

Parameters

[in]	amap	The adjacency map to traverse.
[in]	action	The action to perform at each vertex.
[in]	useDistance	Whether to pass accumulated distance to the action.

---

The documentation for this struct was generated from the following file:

• GraphOptimization/Headers/hyper_dijkstra.h