The running time is O(e*log n) where e is the number of edges and n is the number of nodes in the graph.
It is also possible to change the underlying priority heap.
|
Public Types |
typedef TR::UGraph | UGraph |
| The type of the underlying graph.
|
typedef UGraph::Node | Node |
|
|
typedef UGraph::NodeIt | NodeIt |
|
|
typedef UGraph::UEdge | UEdge |
|
|
typedef UGraph::IncEdgeIt | IncEdgeIt |
|
|
typedef TR::CostMap::Value | Value |
| The type of the cost of the edges.
|
typedef TR::CostMap | CostMap |
| The type of the map that stores the edge costs.
|
typedef TR::PredMap | PredMap |
| The type of the map that stores the last predecessor edges of the spanning tree.
|
typedef TR::TreeMap | TreeMap |
| Edges of the spanning tree.
|
typedef TR::ProcessedMap | ProcessedMap |
| The type of the map indicating if a node is processed.
|
typedef TR::HeapCrossRef | HeapCrossRef |
| The cross reference type used for the current heap.
|
typedef TR::Heap | Heap |
| The heap type used by the prim algorithm.
|
Public Member Functions |
| Prim (const UGraph &_graph, const CostMap &_cost) |
| Constructor.
|
| ~Prim () |
| Destructor.
|
Prim & | costMap (const CostMap &m) |
| Sets the cost map.
|
Prim & | predMap (PredMap &m) |
| Sets the map storing the predecessor edges.
|
Prim & | treeMap (TreeMap &m) |
| Sets the map storing the tree edges.
|
Prim & | heap (Heap &heap, HeapCrossRef &crossRef) |
| Sets the heap and the cross reference used by algorithm.
|
|
The simplest way to execute the algorithm is to use one of the member functions called run (...).
If you need more control on the execution, first you must call init(), then you can add several source nodes with addSource(). Finally start() will perform the actual path computation.
|
void | init () |
| Initializes the internal data structures.
|
void | addSource (Node s) |
| Adds a new source node.
|
Node | processNextNode () |
| Processes the next node in the priority heap.
|
Node | nextNode () |
| Next node to be processed.
|
bool | emptyQueue () |
| Returns false if there are nodes to be processed in the priority heap.
|
int | queueSize () |
| Returns the number of the nodes to be processed in the priority heap.
|
void | start () |
| Executes the algorithm.
|
template<class NodeBoolMap> |
void | start (const NodeBoolMap &nm) |
| Executes the algorithm until a condition is met.
|
void | run () |
| Runs Prim algorithm.
|
void | run (Node s) |
| Runs Prim algorithm from node s .
|
|
The result of the Prim algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.
|
UEdge | predEdge (Node v) const |
| Returns the 'previous edge' of the minimum spanning tree.
|
Node | predNode (Node v) const |
| Returns the 'previous node' of the minimum spanning tree.
|
const PredMap & | predMap () const |
| Returns a reference to the NodeMap of the edges of the minimum spanning tree.
|
const TreeMap & | treeMap () const |
| Returns a reference to the tree edges map.
|
template<class TreeMap> |
void | quickTreeEdges (TreeMap &tree, const typename TreeMap::Value &tree_edge_value=true) const |
| Sets the tree edges map.
|
template<class TreeMap> |
void | treeEdges (TreeMap &tree, const typename TreeMap::Value &tree_edge_value=true, const typename TreeMap::Value &tree_default_value=false) const |
| Sets the tree edges map.
|
bool | reached (Node v) |
| Checks if a node is reachable from the starting node.
|
bool | processed (Node v) |
| Checks if a node is processed.
|
bool | tree (UEdge e) |
| Checks if an edge is in the spanning tree or not.
|
Classes |
struct | DefHeap |
struct | DefPredMap |
| Named parameter for setting PredMap type More...
|
struct | DefProcessedMap |
| Named parameter for setting ProcessedMap type More...
|
struct | DefStandardHeap |
struct | DefTreeMap |
| Named parameter for setting TreeMap More...
|
class | UninitializedParameter |
| Exception for uninitialized parameters. More...
|