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

References GUM_ERROR.

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

SpanningForestPrim() [2/2]

gum::SpanningForestPrim::SpanningForestPrim

(

const SpanningForestPrim &

toCopy

)

Copy constructor.

Definition at line 50 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);
  }

~SpanningForestPrim()

gum::SpanningForestPrim::~SpanningForestPrim ( )

virtual

Destructor.

Definition at line 61 of file spanningForestPrim.cpp.

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

Member Function Documentation

__compute()

void gum::SpanningForestPrim::__compute ( )

private

Computes the spanning forest.

compute the spanning forest

Definition at line 88 of file spanningForestPrim.cpp.

References __computeInAComponent(), __graph, __require_computation, __spanning_tree, gum::NodeGraphPart::existsNode(), and gum::NodeGraphPart::nodes().

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

                                     {
    // 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:

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

References __costTable, __edgesToExplore, __exploreNode(), __spanning_tree, __spanning_tree_cost, gum::UndiGraph::addEdge(), gum::NodeGraphPart::addNodeWithId(), gum::NodeGraphPart::existsNode(), gum::Edge::first(), and gum::Edge::second().

Referenced by __compute().

                                                                {
    // 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:

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

References __costTable, __edgesToExplore, __graph, __spanning_tree, gum::NodeGraphPart::existsNode(), and gum::EdgeGraphPart::neighbours().

Referenced by __computeInAComponent().

                                                        {
    // 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:

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

References __compute(), __require_computation, and __spanning_tree_cost.

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

References __compute(), __require_computation, __spanning_tree, and gum::EdgeGraphPart::edges().

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

References __compute(), __require_computation, and __spanning_tree.

                                                      {
    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 97 of file spanningForestPrim.h.

Referenced by __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 100 of file spanningForestPrim.h.

Referenced by __computeInAComponent(), and __exploreNode().

__graph

const UndiGraph& gum::SpanningForestPrim::__graph

private

the graph the spanning tree of which we wish to compute

Definition at line 94 of file spanningForestPrim.h.

Referenced by __compute(), and __exploreNode().

__require_computation

bool gum::SpanningForestPrim::__require_computation

private

a Boolean indicating whether we need recompute the spanning tree

Definition at line 109 of file spanningForestPrim.h.

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

__spanning_tree

UndiGraph gum::SpanningForestPrim::__spanning_tree

private

the computed spanning tree

Definition at line 103 of file spanningForestPrim.h.

Referenced by __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 106 of file spanningForestPrim.h.

Referenced by __computeInAComponent(), and costOfSpanningForest().

---

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

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