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 49 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 60 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 87 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 98 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:

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 66 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 73 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:

exploreNode__()

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

private

explore the neighborhood of a node belonging to the spanning tree

Definition at line 136 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:

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 80 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 96 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 99 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 93 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 108 of file spanningForestPrim.h.

spanning_tree__

UndiGraph gum::SpanningForestPrim::spanning_tree__

private

the computed spanning tree

Definition at line 102 of file spanningForestPrim.h.

spanning_tree_cost__

float gum::SpanningForestPrim::spanning_tree_cost__

private

the cost of the spanning tree

Definition at line 105 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