gum::SpanningForestPrim Class Reference

The Prim algorithm for computing min cost spanning trees or forests. More...

#include <spanningForestPrim.h>

Inheritance diagram for gum::SpanningForestPrim:

Collaboration diagram for gum::SpanningForestPrim:

Public Member Functions
Constructors / Destructors
	SpanningForestPrim (const UndiGraph *graph, const EdgeProperty< float > *costTable)
	Default constructor. More...
	SpanningForestPrim (const SpanningForestPrim &toCopy)
	Copy constructor. More...
virtual	~SpanningForestPrim ()
	Destructor. More...
Accessors / Modifiers
const EdgeSet &	edgesInSpanningForest ()
	Returns the edges in a min cost spanning forest. More...
const UndiGraph &	spanningForest ()
	Construct the spanning forest. More...
float	costOfSpanningForest ()
	Returns the cost of the spanning forest. More...

Detailed Description

The Prim algorithm for computing min cost spanning trees or forests.

Binary heap implementation : O(E log(V))

Definition at line 43 of file spanningForestPrim.h.

Constructor & Destructor Documentation

SpanningForestPrim() [1/2]

gum::SpanningForestPrim::SpanningForestPrim	(	const UndiGraph *	graph,
		const EdgeProperty< float > *	costTable
	)

Default constructor.

Note that this algorithm takes into account the fact that the graph given in input is not connected (that, is, it may contain several connected components)

Parameters

graph	the graph the spanning forest of which we look for
costTable	the cost for each edge of graph

Warning

note that, by aGrUM's rule, the graph and the costs are not copied but only referenced by the elimination sequence algorithm.

Exceptions

GraphError

if the grand and/or the cost table are null pointers

Definition at line 35 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                            :
      SpanningForest(),
      _graph_(*graph), _costTable_(*cost), _spanning_tree_cost_(0), _require_computation_(true) {
    if (!graph || !cost) { GUM_ERROR(GraphError, "invalid null graph or edge cost pointer") }

    // for debugging purposes
    GUM_CONSTRUCTOR(SpanningForestPrim);
  }

Here is the call graph for this function:

SpanningForestPrim() [2/2]

gum::SpanningForestPrim::SpanningForestPrim

(

const SpanningForestPrim &

toCopy

)

Copy constructor.

Definition at line 46 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                       :
      SpanningForest(), _graph_(from._graph_), _costTable_(from._costTable_),
      _edgesToExplore_(from._edgesToExplore_), _spanning_tree_(from._spanning_tree_),
      _spanning_tree_cost_(from._spanning_tree_cost_),
      _require_computation_(from._require_computation_) {
    // for debugging purposes
    GUM_CONS_CPY(SpanningForestPrim);
  }

Here is the call graph for this function:

~SpanningForestPrim()

gum::SpanningForestPrim::~SpanningForestPrim ( )

virtual

Destructor.

Definition at line 56 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                          {
    // for debugging purposes
    GUM_DESTRUCTOR(SpanningForestPrim);
  }

Here is the call graph for this function:

Member Function Documentation

_compute_()

void gum::SpanningForestPrim::_compute_ ( )

private

Computes the spanning forest.

compute the spanning forest

Definition at line 83 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                     {
    // compute a spanning tree in every connected component
    for (const auto node: _graph_.nodes()) {
      if (!_spanning_tree_.existsNode(node)) { _computeInAComponent_(node); }
    }

    // indicate that everything was computed
    _require_computation_ = false;
  }

Here is the call graph for this function:

_computeInAComponent_()

void gum::SpanningForestPrim::_computeInAComponent_ ( const NodeId  id )

private

compute a spanning tree in a given connected component of graph

compute a spanning tree

Definition at line 94 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                                {
    // add the node to the spanning tree
    _spanning_tree_.addNodeWithId(id);

    // explore its neighborhood
    _exploreNode_(id);

    // get the next nodes to link to the current spanning tree nodes

    while (!_edgesToExplore_.empty()) {
      const Edge   edge   = _edgesToExplore_.pop();
      const NodeId first  = edge.first();
      const NodeId second = edge.second();

      // consider only the edges that have one extremal node not in the spanning
      // tree as those that can be added to the tree

      if (!_spanning_tree_.existsNode(first)) {
        // add the edge to the spanning tree
        _spanning_tree_.addNodeWithId(first);
        _spanning_tree_.addEdge(first, second);
        _spanning_tree_cost_ += _costTable_[edge];

        // We must explore the first node's neighborhood
        _exploreNode_(first);
      } else if (!_spanning_tree_.existsNode(second)) {
        // add the edge to the spanning tree
        _spanning_tree_.addNodeWithId(second);
        _spanning_tree_.addEdge(first, second);
        _spanning_tree_cost_ += _costTable_[edge];

        // We must explore the second node
        _exploreNode_(second);
      }
    }
  }

Here is the call graph for this function:

_exploreNode_()

void gum::SpanningForestPrim::_exploreNode_ ( const NodeId  id )

private

explore the neighborhood of a node belonging to the spanning tree

Definition at line 132 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                        {
    // add its neighbors  _edgesToExplore_ to indicate that they are
    // potential next nodes to explore
    for (const auto node: _graph_.neighbours(id)) {
      if (!_spanning_tree_.existsNode(node)) {
        Edge edge(node, id);
        _edgesToExplore_.insert(edge, _costTable_[edge]);
      }
    }
  }

Here is the call graph for this function:

costOfSpanningForest()

float gum::SpanningForestPrim::costOfSpanningForest ( )

virtual

Returns the cost of the spanning forest.

Returns

cost of the spanning forest

Implements gum::SpanningForest.

Definition at line 62 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                 {
    if (_require_computation_) _compute_();

    return _spanning_tree_cost_;
  }

Here is the call graph for this function:

edgesInSpanningForest()

const EdgeSet & gum::SpanningForestPrim::edgesInSpanningForest ( )

virtual

Returns the edges in a min cost spanning forest.

Returns

edges in the spanning forest

Implements gum::SpanningForest.

Definition at line 69 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                           {
    if (_require_computation_) _compute_();

    return _spanning_tree_.edges();
  }

Here is the call graph for this function:

operator=()

SpanningForestPrim& gum::SpanningForestPrim::operator= ( const SpanningForestPrim &  toCopy )

private

Copy operator: private to prevent using it.

spanningForest()

const UndiGraph & gum::SpanningForestPrim::spanningForest ( )

virtual

Construct the spanning forest.

Returns

the spanning forest

Implements gum::SpanningForest.

Definition at line 76 of file spanningForestPrim.cpp.

References gum::Set< Key, Alloc >::emplace().

                                                      {
    if (_require_computation_) _compute_();

    return _spanning_tree_;
  }

Here is the call graph for this function:

Member Data Documentation

_costTable_

const EdgeProperty< float >& gum::SpanningForestPrim::_costTable_

private

the costs of the edges

Definition at line 95 of file spanningForestPrim.h.

_edgesToExplore_

PriorityQueue< Edge, float > gum::SpanningForestPrim::_edgesToExplore_

private

the next edges that may be added to the spanning tree

Definition at line 98 of file spanningForestPrim.h.

_graph_

const UndiGraph& gum::SpanningForestPrim::_graph_

private

the graph the spanning tree of which we wish to compute

Definition at line 92 of file spanningForestPrim.h.

_require_computation_

bool gum::SpanningForestPrim::_require_computation_

private

a Boolean indicating whether we need recompute the spanning tree

Definition at line 107 of file spanningForestPrim.h.

_spanning_tree_

UndiGraph gum::SpanningForestPrim::_spanning_tree_

private

the computed spanning tree

Definition at line 101 of file spanningForestPrim.h.

_spanning_tree_cost_

float gum::SpanningForestPrim::_spanning_tree_cost_

private

the cost of the spanning tree

Definition at line 104 of file spanningForestPrim.h.

---

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

• agrum/tools/graphs/algorithms/spanningForestPrim.h
• agrum/tools/graphs/algorithms/spanningForestPrim.cpp