Example: 'Compute the bidirectional minimum spanning tree for the network'

Brief description

This algorithm computes the bidirectional minimum spanning tree (MST) for the given set of nodes, using the node distance as the cost measure for each link.

For a network of \(N\) nodes, the returned topology is a tree of \(N-1\) bidirectional links, so that no other topology is able to connect the \(N\) nodes with bidirectional links, at a lower cost (being the cost the sum of the lengths of the links). To compute the MST, the Prim algorithm is implemented.

Algorithm description table

Algorithm inputs

A set of nodes within the netPlan is required.

Algorithm parameters:

  • linkCapacities: The capacities (in Erlangs) to set in the links. Default: 100
  • initialNode: Initial node of the spanning tree. Default: 0
Algorithm outputsLinks and their respective capacity values are added to the netPlan object
Required librariesNone
KeywordsCapacity assignment (CA), Topology assignment (TA)
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeTCA_PrimMST.java

Detailed description

The algorithm performs the following steps:

  1. Create a tree containing a single vertex, chosen arbitrarily from the graph
  2. Create a set containing all the edges in the graph
  3. Loop until every edge in the set connects two vertices in the tree:
    • Remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
    • Add that edge to the tree