SinglePairShortestPath Class Reference
[Algorithms]

SinglePairShortestPath class. More...

Inheritance diagram for SinglePairShortestPath:

Inheritance graph
Collaboration diagram for SinglePairShortestPath:

Collaboration graph

List of all members.

Public Member Functions

virtual dex::gdb::OIDList * GetPathAsNodes ()=0
 Gets the shortest path between the source node and the destination node as an ordered set of nodes.
virtual dex::gdb::OIDList * GetPathAsEdges ()=0
 Gets the shortest path between the source node and the destination node as an ordered set of edges.
virtual dex::gdb::double64_t GetCost ()=0
 Gets the cost of the shortest path.
virtual dex::gdb::bool_t Exists ()
 Returns TRUE If a path exists or FALSE otherwise.
virtual ~SinglePairShortestPath ()
 Destructor.
void SetMaximumHops (dex::gdb::int32_t maxhops)
 Sets the maximum hops restriction.
virtual void AddEdgeType (dex::gdb::type_t t, dex::gdb::EdgesDirection d)
 Allows for traversing edges of the given type.
virtual void AddAllEdgeTypes (dex::gdb::EdgesDirection d)
 Allows for traversing all edge types of the graph.
virtual void AddNodeType (dex::gdb::type_t t)
 Allows for traversing nodes of the given type.
virtual void AddAllNodeTypes ()
 Allows for traversing all node types of the graph.
virtual void ExcludeNodes (dex::gdb::Objects &nodes)
 Set which nodes can't be used.
virtual void ExcludeEdges (dex::gdb::Objects &edges)
 Set which edges can't be used.
virtual void Run ()=0
 Runs the algorithm.

Protected Member Functions

 SinglePairShortestPath (dex::gdb::Session &s, dex::gdb::oid_t src, dex::gdb::oid_t dst)
 Creates a new instance.
void AssertEdgeType (dex::gdb::type_t edgetype)
 Check that the given edge type is valid.
void AssertAddedEdges ()
 Check that edges had been added.
void AssertAddedNodes ()
 Check that nodes had been added.
void AssertNodeType (dex::gdb::type_t nodetype)
 Check that the given node type is valid.
dex::gdb::bool_t IsNodeTypeAllowed (dex::gdb::oid_t nodeId)
 Check if the given node has an allowed type.
void AssertNotComputed ()
 Check that the shortest path had not been calculated yet.
void AssertComputed ()
 Check that the shortest path had been calculated.
dex::gdb::bool_t IsNodeExcluded (dex::gdb::oid_t node)
 Check if the given node is forbidden.
dex::gdb::bool_t IsEdgeExcluded (dex::gdb::oid_t edge)
 Check if the given edge is forbidden.

Protected Attributes

dex::gdb::oid_t source
 Source node.
dex::gdb::oid_t destination
 Destination node.
dex::gdb::OIDList * pathAsNodes
 Ordered set of node identifiers representing the shortest path.
dex::gdb::OIDList * pathAsEdges
 Ordered set of edge identifiers representing the shortest path.
dex::gdb::Session * sess
 Session.
dex::gdb::Graph * graph
 Graph.
std::map< dex::gdb::type_t,
dex::gdb::EdgesDirection
edgeTypes
 Allowed edge types.
std::vector< dex::gdb::type_tnodeTypes
 Allowed node types.
dex::gdb::int32_t maxHops
 Maximum hops restriction.
dex::gdb::bool_t computed
 True if the shortest path has been calculated.
dex::gdb::Objects * excludedNodes
 The set of excluded nodes.
dex::gdb::Objects * excludedEdges
 The set of excluded edges.


Detailed Description

SinglePairShortestPath class.

Classes implementing this abstract class solve the shortest path problem in a graph from a given source node and to a given destination node.

Author:
Sparsity Technologies http://www.sparsity-technologies.com

Constructor & Destructor Documentation

SinglePairShortestPath::SinglePairShortestPath ( dex::gdb::Session &  s,
dex::gdb::oid_t  src,
dex::gdb::oid_t  dst 
) [protected]

Creates a new instance.

Parameters:
s [in] Session to get the graph from and perform traversal.
src [in] Source node.
dst [dst] Destination node.


Member Function Documentation

virtual dex::gdb::OIDList* SinglePairShortestPath::GetPathAsNodes (  )  [pure virtual]

Gets the shortest path between the source node and the destination node as an ordered set of nodes.

Returns:
Ordered set of node identifiers.

Implemented in SinglePairShortestPathBFS, and SinglePairShortestPathDijkstra.

virtual dex::gdb::OIDList* SinglePairShortestPath::GetPathAsEdges (  )  [pure virtual]

Gets the shortest path between the source node and the destination node as an ordered set of edges.

Returns:
Ordered set of edge identifiers.

Implemented in SinglePairShortestPathBFS, and SinglePairShortestPathDijkstra.

virtual dex::gdb::double64_t SinglePairShortestPath::GetCost (  )  [pure virtual]

Gets the cost of the shortest path.

The cost for unweighted algorithms is the number of hops of the shortest path. For weighted algoritms, the cost is the sum of the costs of the edges of the shortest path.

Returns:
The cost of the shortest path.

Implemented in SinglePairShortestPathBFS, and SinglePairShortestPathDijkstra.

void ShortestPath::SetMaximumHops ( dex::gdb::int32_t  maxhops  )  [inherited]

Sets the maximum hops restriction.

All paths longer than the maximum hops restriction will be ignored.

Parameters:
m [in] The maximum hops restriction. It must be positive or zero. Zero, the default value, means unlimited.

virtual void ShortestPath::AddEdgeType ( dex::gdb::type_t  t,
dex::gdb::EdgesDirection  d 
) [virtual, inherited]

Allows for traversing edges of the given type.

Parameters:
t [in] Edge type.
d [in] Edge direction.

virtual void ShortestPath::AddAllEdgeTypes ( dex::gdb::EdgesDirection  d  )  [virtual, inherited]

Allows for traversing all edge types of the graph.

Parameters:
d [in] Edge direction.

virtual void ShortestPath::ExcludeNodes ( dex::gdb::Objects &  nodes  )  [virtual, inherited]

Set which nodes can't be used.

This will replace any previously specified set of excluded nodes. Should only be used to exclude the usage of specific nodes from allowed node types because it's less efficient than not allowing a node type.

Parameters:
nodes [in] A set of node identifiers that must be kept intact until the destruction of the class.

virtual void ShortestPath::ExcludeEdges ( dex::gdb::Objects &  edges  )  [virtual, inherited]

Set which edges can't be used.

This will replace any previously specified set of excluded edges. Should only be used to exclude the usage of specific edges from allowed edge types because it's less efficient than not allowing an edge type.

Parameters:
edges [in] A set of edge identifiers that must be kept intact until the destruction of the class.

virtual void ShortestPath::Run (  )  [pure virtual, inherited]

Runs the algorithm.

This method can only be called once.

Implemented in SinglePairShortestPathBFS, and SinglePairShortestPathDijkstra.


Member Data Documentation

dex::gdb::OIDList* SinglePairShortestPath::pathAsEdges [protected]

Ordered set of edge identifiers representing the shortest path.

May be computed lazily when requested from the pathAsNodes.

dex::gdb::int32_t ShortestPath::maxHops [protected, inherited]

Maximum hops restriction.

It must be positive or zero. Zero means unlimited.


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

Generated on Mon Oct 15 14:40:44 2012 for Dex by  doxygen 1.5.6