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.
	SpanningForestPrim (const SpanningForestPrim &toCopy)
	Copy constructor.
	SpanningForestPrim (SpanningForestPrim &&from)
	Move constructor.
	~SpanningForestPrim () override
	Destructor.
Accessors / Modifiers
const EdgeSet &	edgesInSpanningForest () override
	Returns the edges in a min cost spanning forest.
const UndiGraph &	spanningForest () override
	Construct the spanning forest.
float	costOfSpanningForest () override
	Returns the cost of the spanning forest.

Private Member Functions
void	_compute_ ()
	Computes the spanning forest.
void	_computeInAComponent_ (const NodeId id)
	compute a spanning tree in a given connected component of graph
void	_exploreNode_ (const NodeId id)
	explore the neighborhood of a node belonging to the spanning tree
SpanningForestPrim &	operator= (const SpanningForestPrim &toCopy)
	Copy operator: private to prevent using it.

Private Attributes
const UndiGraph &	_graph_
	the graph the spanning tree of which we wish to compute
const EdgeProperty< float > &	_costTable_
	the costs of the edges
PriorityQueue< Edge, float >	_edgesToExplore_
	the next edges that may be added to the spanning tree
UndiGraph	_spanning_tree_
	the computed spanning tree
float	_spanning_tree_cost_
	the cost of the spanning tree
bool	_require_computation_
	a Boolean indicating whether we need recompute the spanning tree

Detailed Description

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

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

Definition at line 63 of file spanningForestPrim.h.

Constructor & Destructor Documentation

SpanningForestPrim() [1/3]

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 55 of file spanningForestPrim.cpp.

                                                                            :
      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);
  }

References gum::SpanningForest::SpanningForest(), SpanningForestPrim(), _costTable_, _graph_, _require_computation_, _spanning_tree_cost_, and GUM_ERROR.

Referenced by SpanningForestPrim(), SpanningForestPrim(), SpanningForestPrim(), ~SpanningForestPrim(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

SpanningForestPrim() [2/3]

gum::SpanningForestPrim::SpanningForestPrim

(

const SpanningForestPrim &

toCopy

)

Copy constructor.

Definition at line 66 of file spanningForestPrim.cpp.

                                                                       :
      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);
  }

References gum::SpanningForest::SpanningForest(), SpanningForestPrim(), _costTable_, _edgesToExplore_, _graph_, _require_computation_, _spanning_tree_, and _spanning_tree_cost_.

Here is the call graph for this function:

SpanningForestPrim() [3/3]

gum::SpanningForestPrim::SpanningForestPrim

(

SpanningForestPrim &&

from

)

Move constructor.

Definition at line 75 of file spanningForestPrim.cpp.

                                                                  :
      SpanningForest(), _graph_(from._graph_), _costTable_(from._costTable_),
      _edgesToExplore_(std::move(from._edgesToExplore_)),
      _spanning_tree_(std::move(from._spanning_tree_)),
      _spanning_tree_cost_(from._spanning_tree_cost_),
      _require_computation_(from._require_computation_) {
    GUM_CONS_MOV(SpanningForestPrim);
  }

References gum::SpanningForest::SpanningForest(), SpanningForestPrim(), _costTable_, _edgesToExplore_, _graph_, _require_computation_, _spanning_tree_, and _spanning_tree_cost_.

Here is the call graph for this function:

~SpanningForestPrim()

gum::SpanningForestPrim::~SpanningForestPrim ( )

override

Destructor.

Definition at line 85 of file spanningForestPrim.cpp.

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

References 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 112 of file spanningForestPrim.cpp.

                                     {
    _spanning_tree_.clear();
    _edgesToExplore_.clear();
    _spanning_tree_cost_ = 0;
 
    // 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;
  }

References _computeInAComponent_(), _edgesToExplore_, _graph_, _require_computation_, _spanning_tree_, and _spanning_tree_cost_.

Referenced by costOfSpanningForest(), edgesInSpanningForest(), and spanningForest().

Here is the call graph for this function:

Here is the caller 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 127 of file spanningForestPrim.cpp.

                                                                {
    // 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);
      }
    }
  }

References _costTable_, _edgesToExplore_, _exploreNode_(), _spanning_tree_, _spanning_tree_cost_, gum::Edge::first(), and gum::Edge::second().

Referenced by _compute_().

Here is the call graph for this function:

Here is the caller 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 165 of file spanningForestPrim.cpp.

                                                        {
    // add its neighbors  _edgesToExplore_ to indicate that they are
    // tensor next nodes to explore
    for (const auto node: _graph_.neighbours(id)) {
      if (!_spanning_tree_.existsNode(node)) {
        Edge edge(node, id);
        if (!_costTable_.exists(edge)) {
          GUM_ERROR(NotFound,
                    "no cost defined for edge (" << edge.first() << "," << edge.second() << ")")
        }
        _edgesToExplore_.insert(edge, _costTable_[edge]);
      }
    }
  }

References _costTable_, _edgesToExplore_, _graph_, _spanning_tree_, gum::Edge::first(), GUM_ERROR, and gum::Edge::second().

Referenced by _computeInAComponent_().

Here is the call graph for this function:

Here is the caller graph for this function:

costOfSpanningForest()

float gum::SpanningForestPrim::costOfSpanningForest ( )

overridevirtual

Returns the cost of the spanning forest.

Returns

cost of the spanning forest

Implements gum::SpanningForest.

Definition at line 91 of file spanningForestPrim.cpp.

                                                 {
    if (_require_computation_) _compute_();
 
    return _spanning_tree_cost_;
  }

References _compute_(), _require_computation_, and _spanning_tree_cost_.

Here is the call graph for this function:

edgesInSpanningForest()

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

overridevirtual

Returns the edges in a min cost spanning forest.

Returns

edges in the spanning forest

Implements gum::SpanningForest.

Definition at line 98 of file spanningForestPrim.cpp.

                                                           {
    if (_require_computation_) _compute_();
 
    return _spanning_tree_.edges();
  }

References _compute_(), _require_computation_, and _spanning_tree_.

Here is the call graph for this function:

operator=()

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

private

Copy operator: private to prevent using it.

References SpanningForestPrim().

Here is the call graph for this function:

spanningForest()

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

overridevirtual

Construct the spanning forest.

Returns

the spanning forest

Implements gum::SpanningForest.

Definition at line 105 of file spanningForestPrim.cpp.

                                                      {
    if (_require_computation_) _compute_();
 
    return _spanning_tree_;
  }

References _compute_(), _require_computation_, and _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 118 of file spanningForestPrim.h.

Referenced by SpanningForestPrim(), SpanningForestPrim(), SpanningForestPrim(), _computeInAComponent_(), and _exploreNode_().

_edgesToExplore_

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

private

the next edges that may be added to the spanning tree

Definition at line 121 of file spanningForestPrim.h.

Referenced by SpanningForestPrim(), SpanningForestPrim(), _compute_(), _computeInAComponent_(), and _exploreNode_().

_graph_

const UndiGraph& gum::SpanningForestPrim::_graph_

private

the graph the spanning tree of which we wish to compute

Definition at line 115 of file spanningForestPrim.h.

Referenced by SpanningForestPrim(), SpanningForestPrim(), SpanningForestPrim(), _compute_(), and _exploreNode_().

_require_computation_

bool gum::SpanningForestPrim::_require_computation_

private

a Boolean indicating whether we need recompute the spanning tree

Definition at line 130 of file spanningForestPrim.h.

Referenced by SpanningForestPrim(), SpanningForestPrim(), SpanningForestPrim(), _compute_(), costOfSpanningForest(), edgesInSpanningForest(), and spanningForest().

_spanning_tree_

UndiGraph gum::SpanningForestPrim::_spanning_tree_

private

the computed spanning tree

Definition at line 124 of file spanningForestPrim.h.

Referenced by SpanningForestPrim(), SpanningForestPrim(), _compute_(), _computeInAComponent_(), _exploreNode_(), edgesInSpanningForest(), and spanningForest().

_spanning_tree_cost_

float gum::SpanningForestPrim::_spanning_tree_cost_

private

the cost of the spanning tree

Definition at line 127 of file spanningForestPrim.h.

Referenced by SpanningForestPrim(), SpanningForestPrim(), SpanningForestPrim(), _compute_(), _computeInAComponent_(), and costOfSpanningForest().

---

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

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