SinglePairShortestPathDijkstra Class Reference
[Algorithms]

SinglePairShortestPathDijkstra class. More...

Inheritance diagram for SinglePairShortestPathDijkstra:

Inheritance graph
Collaboration diagram for SinglePairShortestPathDijkstra:

Collaboration graph

List of all members.

Public Member Functions

virtual ~SinglePairShortestPathDijkstra ()
 Destructor.
virtual void Run ()
 Executes the algorithm.
virtual sparksee::gdb::OIDList * GetPathAsNodes ()
 Gets the shortest path between the source node and the destination node as an ordered set of nodes.
virtual sparksee::gdb::OIDList * GetPathAsEdges ()
 Gets the shortest path between the source node and the destination node as an ordered set of edges.
virtual sparksee::gdb::double64_t GetCost ()
 Gets the cost of the shortest path.
 SinglePairShortestPathDijkstra (sparksee::gdb::Session &s, sparksee::gdb::oid_t src, sparksee::gdb::oid_t dst)
 Creates a new instance.
virtual void AddWeightedEdgeType (sparksee::gdb::type_t t, sparksee::gdb::EdgesDirection d, sparksee::gdb::attr_t attr)
 Allows for traversing edges of the given type using the given attribute as the weight.
virtual void SetUnweightedEdgeCost (sparksee::gdb::double64_t weight)
 Sets the weight assigned to the unweighted edges.
virtual sparksee::gdb::bool_t Exists ()
 Returns TRUE If a path exists or FALSE otherwise.
void SetMaximumHops (sparksee::gdb::int32_t maxhops)
 Sets the maximum hops restriction.
virtual void AddEdgeType (sparksee::gdb::type_t t, sparksee::gdb::EdgesDirection d)
 Allows for traversing edges of the given type.
virtual void AddAllEdgeTypes (sparksee::gdb::EdgesDirection d)
 Allows for traversing all edge types of the graph.
virtual void AddNodeType (sparksee::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 (sparksee::gdb::Objects &nodes)
 Set which nodes can't be used.
virtual void ExcludeEdges (sparksee::gdb::Objects &edges)
 Set which edges can't be used.

Protected Member Functions

void AssertEdgeType (sparksee::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 (sparksee::gdb::type_t nodetype)
 Check that the given node type is valid.
sparksee::gdb::bool_t IsNodeTypeAllowed (sparksee::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.
sparksee::gdb::bool_t IsNodeExcluded (sparksee::gdb::oid_t node)
 Check if the given node is forbidden.
sparksee::gdb::bool_t IsEdgeExcluded (sparksee::gdb::oid_t edge)
 Check if the given edge is forbidden.

Protected Attributes

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

Classes

class  FibonacciHeap


Detailed Description

SinglePairShortestPathDijkstra class.

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

It is a weighted algorithm, so it takes into account the cost of the edges to compute a minimum-cost shortest path. That is, the user may set for each edge type which attribute should be used to retrieve the cost of the edge. If no attribute is given for an edge type, this will assume the edge has a fixed cost (the default is 1). Only numerical attribute can be set as weight attributes (that is Long, Integer or Double attributes are allowed).

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

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

Constructor & Destructor Documentation

SinglePairShortestPathDijkstra::SinglePairShortestPathDijkstra ( sparksee::gdb::Session &  s,
sparksee::gdb::oid_t  src,
sparksee::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 sparksee::gdb::OIDList* SinglePairShortestPathDijkstra::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 sparksee::gdb::OIDList* SinglePairShortestPathDijkstra::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 sparksee::gdb::double64_t SinglePairShortestPathDijkstra::GetCost (  )  [virtual]

Gets the cost of the shortest path.

The cost is the sum of the weights of the edges in the shortest path.

Returns:
The cost of the shortest path.

Implements SinglePairShortestPath.

virtual void SinglePairShortestPathDijkstra::AddWeightedEdgeType ( sparksee::gdb::type_t  t,
sparksee::gdb::EdgesDirection  d,
sparksee::gdb::attr_t  attr 
) [virtual]

Allows for traversing edges of the given type using the given attribute as the weight.

Parameters:
t [in] Edge type.
d [in] Edge direction.
attr [in] Attribute to be used as the weight. It must be a global attribute or an attribute of the given edge type.

virtual void SinglePairShortestPathDijkstra::SetUnweightedEdgeCost ( sparksee::gdb::double64_t  weight  )  [virtual]

Sets the weight assigned to the unweighted edges.

All the edges from the types added without an explicit weight attribute will get this weight. The default weight for this edges is 1.

void ShortestPath::SetMaximumHops ( sparksee::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 ( sparksee::gdb::type_t  t,
sparksee::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 ( sparksee::gdb::EdgesDirection  d  )  [virtual, inherited]

Allows for traversing all edge types of the graph.

Parameters:
d [in] Edge direction.

virtual void ShortestPath::ExcludeNodes ( sparksee::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 ( sparksee::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

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

Ordered set of edge identifiers representing the shortest path.

May be computed lazily when requested from the pathAsNodes.

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 Fri Feb 7 13:10:05 2014 for Sparksee by  doxygen 1.5.6