SinglePairShortestPathBFS Class Reference
[Algorithms]

SinglePairShortestPathBFS class. More...

Inheritance diagram for SinglePairShortestPathBFS:

Inheritance graph
Collaboration diagram for SinglePairShortestPathBFS:

Collaboration graph

List of all members.

Public Member Functions

virtual ~SinglePairShortestPathBFS ()
 Destructor.
virtual void Run ()
 Executes the algorithm.
virtual dex::gdb::OIDList * GetPathAsNodes ()
 Gets the shortest path between the source node and the destination node as an ordered set of nodes.
virtual dex::gdb::OIDList * GetPathAsEdges ()
 Gets the shortest path between the source node and the destination node as an ordered set of edges.
virtual dex::gdb::double64_t GetCost ()
 Gets the cost of the shortest path.
 SinglePairShortestPathBFS (dex::gdb::Session &s, dex::gdb::oid_t src, dex::gdb::oid_t dst)
 Creates a new instance.
virtual void CheckOnlyExistence ()
 Set that only the path existence must be calculated and not the path itself.
virtual dex::gdb::bool_t Exists ()
 Returns TRUE If a path exists or FALSE otherwise.
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.

Protected Member Functions

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.
dex::gdb::bool_t areAllNodeTypesAllowed
 True if all the node types are allowed.


Detailed Description

SinglePairShortestPathBFS class.

It solves the single-pair shortest path problem using a BFS-based implementation.

It is a unweighted algorithm, that is it assumes all edges have the same cost.

Check out the 'Algorithms' section in the DEX User Manual for more details on this.

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

Constructor & Destructor Documentation

SinglePairShortestPathBFS::SinglePairShortestPathBFS ( dex::gdb::Session &  s,
dex::gdb::oid_t  src,
dex::gdb::oid_t  dst 
)

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* SinglePairShortestPathBFS::GetPathAsNodes (  )  [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.

Implements SinglePairShortestPath.

virtual dex::gdb::OIDList* SinglePairShortestPathBFS::GetPathAsEdges (  )  [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.

Implements SinglePairShortestPath.

virtual dex::gdb::double64_t SinglePairShortestPathBFS::GetCost (  )  [virtual]

Gets the cost of the shortest path.

The cost is the number of hops of the shortest path.

Returns:
The cost of the shortest path.

Implements SinglePairShortestPath.

virtual void SinglePairShortestPathBFS::CheckOnlyExistence (  )  [virtual]

Set that only the path existence must be calculated and not the path itself.

That method should improve the performance of the algorithm, but a call to GetPathAsNodes or GetPathAsEdges will generate an exception even if the path exists.

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.


Member Data Documentation

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

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 Tue Jul 16 12:10:28 2013 for Dex by  doxygen 1.5.6