minspantree.java

bayes network classifier toolbox 贝叶斯网络分类工具箱

/**
 *  JBNC - Bayesian Network Classifiers Toolbox <p>
 *
 *  Latest release available at http://sourceforge.net/projects/jbnc/ <p>
 *
 *  Copyright (C) 1999-2003 Jarek Sacha <p>
 *
 *  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. <p>
 *
 *  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. <p>
 *
 *  You should have received a copy of the GNU General Public License along with
 *  this program; if not, write to the Free Software Foundation, Inc., 59 Temple
 *  Place - Suite 330, Boston, MA 02111-1307, USA. <br>
 *  http://www.fsf.org/licenses/gpl.txt
 */
package jbnc.graphs;

import jbnc.util.Timer;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Vector;

// used im main() for testing.

/**
 *  Minimum Spanning Tree algorithm. <br>
 *  Assumes that edges are undirected and there is only at most one edge between
 *  any two nodes.
 *
 * @author     Jarek Sacha
 * @since      June 1, 1999
 */
public class MinSpanTree {

  /**
   *  Test the class.
   *
   * @param  argv  The command line arguments
   */
  public static void main(String[] argv) {
    try {

      Timer t = new Timer();
      System.out.println("\nTesting MinSpanTree\n");

      // Create a simple graph
      //
      //      0
      //  (0)---(1)
      //   |    /
      //  2|   / 1
      //   |  /
      //   (2)
      //

      Vertex v0 = new Vertex("0", 0);
      Vertex v1 = new Vertex("1", 1);
      Vertex v2 = new Vertex("2", 2);

      EdgeWithWeight e01 = new EdgeWithWeight(v0, v1, 0);
      EdgeWithWeight e02 = new EdgeWithWeight(v0, v2, 2);
      EdgeWithWeight e12 = new EdgeWithWeight(v1, v2, 1);

      Graph graph1 = new Graph();

      graph1.addEdge(e01);
      graph1.addEdge(e02);
      graph1.addEdge(e12);

      System.out.println("Initial graph1:");
      graph1.dump();

      // Find min spanning tree
      MinSpanTree tree1 = new MinSpanTree();
      Graph minGraph1 = tree1.run(graph1, v0);
      System.out.println("Min span tree graph1:");
      minGraph1.dump();

      //
      // Example from "Introduction to Algorithms", p.499
      //
      Vertex vA = new Vertex("a", 0);
      Vertex vB = new Vertex("b", 1);
      Vertex vC = new Vertex("c", 2);
      Vertex vD = new Vertex("d", 3);
      Vertex vE = new Vertex("e", 4);
      Vertex vF = new Vertex("f", 5);
      Vertex vG = new Vertex("g", 6);
      Vertex vH = new Vertex("h", 7);
      Vertex vI = new Vertex("i", 8);

      Graph graph2 = new Graph();
      graph2.addEdge(new EdgeWithWeight(vA, vB, 4));
      graph2.addEdge(new EdgeWithWeight(vA, vH, 8));
      graph2.addEdge(new EdgeWithWeight(vB, vC, 8));
      graph2.addEdge(new EdgeWithWeight(vB, vH, 11));
      graph2.addEdge(new EdgeWithWeight(vC, vD, 7));
      graph2.addEdge(new EdgeWithWeight(vC, vF, 4));
      graph2.addEdge(new EdgeWithWeight(vC, vI, 2));
      graph2.addEdge(new EdgeWithWeight(vD, vE, 9));
      graph2.addEdge(new EdgeWithWeight(vD, vF, 14));
      graph2.addEdge(new EdgeWithWeight(vE, vF, 10));
      graph2.addEdge(new EdgeWithWeight(vF, vG, 2));
      graph2.addEdge(new EdgeWithWeight(vG, vH, 1));
      graph2.addEdge(new EdgeWithWeight(vG, vI, 6));
      graph2.addEdge(new EdgeWithWeight(vH, vI, 7));
      System.out.println("\nInitial graph2:");
      graph2.dump();

      // Find min spanning tree
      MinSpanTree tree2 = new MinSpanTree();
      Graph minGraph2 = tree2.run(graph2, vA);
      System.out.println("Min span tree graph2:");
      minGraph2.dump();

      t.println("\nTotal time = ");
    } catch (Exception e) {
      e.printStackTrace();
    }

  }


  /**
   *  Returns edges of a minimum spanning tree of a graph. Edges of the graph
   *  contain weights. Implements Kruskal's algorithm.
   *
   * @param  graph          graph to span with a tree.
   * @param  root           vertex designated as the root of the full tree.
   * @return                list of directed edges. Edges are listed from
   *      strongest to weakest.
   * @exception  Exception
   */
  public Edge[] getDirectedEdges(Graph graph, Vertex root) throws Exception {

    // Create a set for each of the vertices
    Vertex[] vertices = graph.getVertices();
    DisjointSets dSet = new DisjointSets(vertices);

    // Sort the edges in the graph by nondecreasing weight
    Edge[] edges = (Edge[]) graph.getEdges();
    if (edges == null) {
      return null;
    }

    LinkedList sortedEdges = new LinkedList();
    for (int i = 0; i < edges.length; ++i) {
      sortedEdges.add(edges[i]);
    }

    Collections.sort(sortedEdges, new EdgeWeightComparator());

    // Build min span tree
    Vector newEdges = new Vector();
    Iterator e = sortedEdges.iterator();
    while (e.hasNext()) {
      Edge thisEdge = (Edge) e.next();
      Vertex u = thisEdge.getInVertex();
      Vertex v = thisEdge.getOutVertex();

      Object set_u = dSet.findSet(u);
      Object set_v = dSet.findSet(v);
      if (set_u != set_v) {
        newEdges.add(new Edge(u, v));
        dSet.union(set_u, set_v);
      }
    }

    Edge[] minTreeEdges = new Edge[newEdges.size()];
    for (int i = 0; i < newEdges.size(); ++i) {
      minTreeEdges[i] = (Edge) newEdges.get(i);
    }

    orientEdges(minTreeEdges, root);

    return minTreeEdges;
  }


  /**
   *  Return a minimum spanning tree for a graph. Implements Kruskal's
   *  algorithm.
   *
   * @param  graph          Description of Parameter
   * @param  root           Description of Parameter
   * @return                Description of the Returned Value
   * @exception  Exception  Description of Exception
   */
  public Graph run(Graph graph, Vertex root) throws Exception {
    Edge[] edges = getDirectedEdges(graph, root);
    if (edges == null) {
      return null;
    }

    Graph minTree = new Graph();
    for (int i = 0; i < edges.length; ++i) {
      minTree.addEdge(edges[i]);
    }

    return minTree;
  }


  /**
   *  LOCAL
   *
   * @param  edges          Description of Parameter
   * @param  root           Description of Parameter
   * @exception  Exception  Description of Exception
   */

  /**
   *  Make sure that graph represents a directed tree (each vertex has at most
   *  one parent
   *
   * @param  root           Vertex that should be treated as root of the
   *      directed tree.
   * @param  edges          Description of Parameter
   * @exception  Exception  Description of Exception
   */
  /*
   *  protected void normalize(Graph tree, Vertex root) throws Exception
   *  {
   *  / Add reversed edges
   *  Edge[] edges = tree.getEdges();
   *  for(int i=0; i<edges.length; ++i)
   *  tree.addEdge(edges[i].getOutVertex(), edges[i].getInVertex());
   *  / Move from the root toward other nodes destroying edges that are aginst
   *  / the direction of the move.
   *  LinkedList vQueue = new LinkedList();
   *  vQueue.addLast(root);
   *  while(vQueue.size() > 0)
   *  {
   *  Vertex v = (Vertex)vQueue.removeFirst();
   *  Vertex[] children = tree.getChildrenOf(v);
   *  for(int c=0; c<children.length; ++c)
   *  {
   *  tree.removeEdge(children[c],v);
   *  vQueue.addLast(children[c]);
   *  }
   *  }
   *  }
   */
  /**
   *  Make sure that graph represents a directed tree (each vertex has at most
   *  one parent
   *
   * @param  root           Vertex that should be treated as root of the
   *      directed tree.
   * @param  edges          Description of Parameter
   * @exception  Exception  Description of Exception
   */
  protected void orientEdges(Edge[] edges, Vertex root) throws Exception {
    LinkedList q = new LinkedList();
    q.addLast(root);
    boolean[] oriented = new boolean[edges.length];
    while (q.size() > 0) {
      Vertex thisVertex = (Vertex) q.removeFirst();
      for (int i = 0; i < edges.length; ++i) {
        if (!oriented[i]) {
          Edge thisEdge = edges[i];
          if (thisEdge.getInVertex() == thisVertex) {
            oriented[i] = true;
            q.addLast(thisEdge.getOutVertex());
          } else if (thisEdge.getOutVertex() == thisVertex) {
            thisEdge.invert();
            oriented[i] = true;
            q.addLast(thisEdge.getOutVertex());
          }
        }
      }
    }

    // Sanity cheack
    for (int i = 0; i < oriented.length; ++i) {
      if (!oriented[i]) {
        throw new Exception("Unable to orient all of the edges");
      }
    }
  }
}