minimun_spanning_tree.cpp 3.99 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
/**
 * @file minimun_spanning_tree.cpp
 */

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2011 Jean-Pierre Charras
 * Copyright (C) 2004-2011 KiCad Developers, see change_log.txt for contributors.
 *
 * derived from this article:
 * http://compprog.wordpress.com/2007/11/09/minimal-spanning-trees-prims-algorithm
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

#include <limits.h>

#include <minimun_spanning_tree.h>
#include <class_pad.h>

/*
 * The class MIN_SPAN_TREE calculates the rectilinear minimum spanning tree
 * of a set of points (pads usually having the same net)
 * using the Prim's algorithm.
 */

/*
 *  Prim's Algorithm
 *   Step 0
 *   Pick any vertex as a starting vertex. (Call it S).
 *   Mark it with any given flag, say 1.
 *
 *   Step 1
 *   Find the nearest neighbour of S (call it P1).
 *   Mark both P1 and the edge SP1.
 *   cheapest unmarked edge in the graph that doesn't close a marked circuit.
 *   Mark this edge.
 *
 *   Step 2
 *   Find the nearest unmarked neighbour to the marked subgraph
 *   (i.e., the closest vertex to any marked vertex).
 *   Mark it and the edge connecting the vertex.
 *
 *   Step 3
 *   Repeat Step 2 until all vertices are marked.
 *   The marked subgraph is a minimum spanning tree.
 */
MIN_SPAN_TREE::MIN_SPAN_TREE()
{
    MSP_Init( 0 );
}


void MIN_SPAN_TREE::MSP_Init( int aNodesCount )
{
72
    m_Size = std::max( aNodesCount, 1 );
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
    inTree.clear();
    linkedTo.clear();
    distTo.clear();

    if( m_Size == 0 )
        return;

    // Reserve space in memory
    inTree.reserve( m_Size );
    linkedTo.reserve( m_Size );
    distTo.reserve( m_Size );

    // Initialize values:
    for( int ii = 0; ii < m_Size; ii++ )
    {
        // Initialise dist with infinity:
        distTo.push_back( INT_MAX );

        // Mark all nodes as NOT beeing in the minimum spanning tree:
        inTree.push_back( 0 );

        linkedTo.push_back( 0 );
    }
}


/* updateDistances(int target)
 *   should be called immediately after target is added to the tree;
 *   updates dist so that the values are correct (goes through target's
 *   neighbours making sure that the distances between them and the tree
 *   are indeed minimum)
 */
void MIN_SPAN_TREE::updateDistances( int target )
{
    for( int ii = 0; ii < m_Size; ++ii )
    {
        if( !inTree[ii] )   // no need to evaluate weight for already in tree items
        {
            int weight = GetWeight( target, ii );
            if( (weight > 0) && (distTo[ii] > weight ) )
            {
                distTo[ii]   = weight;
                linkedTo[ii] = target;
            }
        }
    }
}


void MIN_SPAN_TREE::BuildTree()
{
    /* Add the first node to the tree */
    inTree[0] = 1;
    updateDistances( 0 );

    for( int treeSize = 1; treeSize < m_Size; ++treeSize )
    {
        // Find the node with the smallest distance to the tree
        int min = -1;
        for( int ii = 0; ii < m_Size; ++ii )
        {
            if( !inTree[ii] )
            {
                if( (min == -1) || (distTo[min] > distTo[ii]) )
                    min = ii;
            }
        }

        inTree[min] = 1;
        updateDistances( min );
    }
}