undirectedmodel.java

这是一个matlab的java实现。里面有许多内容。请大家慢慢捉摸。

/* Copyright (C) 2003 Univ. of Massachusetts Amherst, Computer Science Dept.
   This file is part of "MALLET" (MAchine Learning for LanguagE Toolkit).
   http://www.cs.umass.edu/~mccallum/mallet
   This software is provided under the terms of the Common Public License,
   version 1.0, as published by http://www.opensource.org.  For further
   information, see the file `LICENSE' included with this distribution. */

package edu.umass.cs.mallet.grmm;

import edu.umass.cs.mallet.base.types.Alphabet;
import gnu.trove.TIntObjectHashMap;
import gnu.trove.TObjectObjectProcedure;
import salvo.jesus.graph.Edge;
import salvo.jesus.graph.GraphAddVertexEvent;
import salvo.jesus.graph.GraphImpl;
import salvo.jesus.graph.Vertex;
import salvo.jesus.graph.listener.NullGraphListener;

import java.util.*;
import gnu.trove.THashMap;



/**
 * Class for undirected graphical models.
 *
 * Created: Mon Sep 15 15:18:30 2003
 *
 * @author <a href="mailto:[e-mail]">Charles Sutton</a>
 * @version $Id: UndirectedModel.java,v 1.2 2004/07/22 00:37:38 casutton Exp $
 */
public class UndirectedModel extends GraphImpl implements GraphicalModel {

	/**
	 * Set of clique potential for this graph.
	 *   Ordinarily will map Cliques to DiscretePotentials.
	 */
	final private THashMap potentials = new THashMap ();

	private Alphabet variableAlphabet;

	/**
	 * Duplicate indexing of potentials for vertices and edges.  These
	 *  arrays are indexed by their Variable's index (see @link{Variable#index})
	 */
	private DiscretePotential[] vertexPots;

	private TIntObjectHashMap edgePots;

	int numNodes;

	public UndirectedModel() {
		super();
		numNodes = 0;
		setCachesCapacity (0);
		variableAlphabet = new Alphabet ();
		addListener (new NullGraphListener () {
				public void afterVertexAdded (GraphAddVertexEvent event) {
					Variable var = (Variable) event.getVertex ();
					variableAlphabet.lookupIndex (var);
					numNodes++;
					updatePotentialsCaches ();
				}
			});
	} 

	/** 
	 * Create a model with the variables given.  This is much faster
	 * than adding the variables one at a time.
	 */
	public UndirectedModel (Variable[] vars) {
		this();
		setCachesCapacity (vars.length);
		for (int i = 0; i < vars.length; i++) {
			add (vars [i]);
		}
	}
		
	/**
	 * Create a model with the given capacity.  It can expand later, but
	 *  declaring the capacity in advance if you know it makes things
	 *  more efficient.
	 */
	public UndirectedModel (int capacity)
	{
		this ();
		setCachesCapacity (capacity);
	}

	/**
	 * Returns collection that contains potentials in this model.
	 */
	public Collection potentials () {
		return potentials.values ();
	}

	/**
	 * Returns an iterator of all the potentials in the graph.
	 */
 	public Iterator potentialsIterator () 
	{
		return potentials.values().iterator();
	}

	/**
	 * Returns an iterator over all assignments to all variables of this
	 *  graphical model.
	 * @see Assignment
	 */
	public Iterator assignmentIterator ()
	{
		return new AssignmentIterator
			(Arrays.asList (variableAlphabet.toArray()));
	}

	/**
	 * Returns an iterator of all the cliques in the graph
	 *  for which there are potentials.
	 */
	public Iterator cliquesIterator () 
	{
		return potentials.keySet().iterator();
	}

	private void setCachesCapacity (int n)
	{
		vertexPots = new DiscretePotential [n];
    if (edgePots == null) edgePots = new TIntObjectHashMap(n);
	}
	
	private void removePotentialsOfVariable (final Variable var)
	{
		potentials.retainEntries(new TObjectObjectProcedure () {
			public boolean execute (Object clique, Object ptl) {
				return !((Clique) clique).contains (var);
			}
		});
	}
	
	private void renumberNodes ()
	{
		Alphabet dict = new Alphabet ();
		for (Iterator it = getVerticesIterator(); it.hasNext();) {
			dict.lookupIndex (it.next ());
		}
		variableAlphabet = dict;
	}
	
	private void recachePotentials ()
	{
		potentials.forEachEntry (new TObjectObjectProcedure () {
			public boolean execute (Object clique, Object ptl) {
				cachePotential ((Clique) clique, (DiscretePotential) ptl);
        		return true;
			}
		});
	}

	private void regenerateCaches () 
	{
		setCachesCapacity (numNodes);
		renumberNodes();
		recachePotentials ();
	}
	
	private void updatePotentialsCaches () 
	{
		assert numNodes == getVerticesCount ();
		if (vertexPots == null) {
			setCachesCapacity (numNodes);
		} else if (numNodes > vertexPots.length) {
			DiscretePotential[] oldVertexPots = vertexPots;
		  TIntObjectHashMap oldEdgePots = edgePots;
			setCachesCapacity (numNodes);
			if (oldVertexPots != null) {
				assert (oldEdgePots != null);
				for (int i = 0; i < oldVertexPots.length; i++) {
					vertexPots [i] = oldVertexPots [i];
				}
			}
		}
	}

	/**
	 *  Returns a unique numeric index for a variable in this model.
	 *   Every UndirectedModel <tt>mdl</tt> maintains a mapping between its
	 *   variables and the integers 0...size(mdl)-1 , which is suitable
	 *   for caching the variables in an array.
	 *  <p>
	 *  <tt>getIndex</tt> and <tt>get</tt> are inverses.  That is, if
	 *  <tt>idx == getIndex (var)</tt>, then <tt>get(idx)</tt> will 
	 *  return <tt>var</tt>.
	 * @param var A variable contained in this graphical model
	 * @return The numeric index of var 
	 * @see #get(int)
	 */
	public int getIndex (Variable var)
	{
		return variableAlphabet.lookupIndex (var, false);
	}

	/**
	 *  Returns a variable from this model with a given index. 
	 *   Every UndirectedModel <tt>mdl</tt> maintains a mapping between its
	 *   variables and the integers 0...size(mdl)-1 , which is suitable
	 *   for caching the variables in an array.
	 *  <P>
	 *  <tt>getIndex</tt> and <tt>get</tt> are inverses.  That is, if
	 *  <tt>idx == getIndex (var)</tt>, then <tt>get(idx)</tt> will 
	 *  return <tt>var</tt>.
	 *  @see #getIndex(Variable)
	 */
	public Variable get (int index)
	{
		// xxx Should use a map index => Variable
		for (Iterator it = getVerticesIterator(); it.hasNext();) {
			Variable var = (Variable) it.next();
			if (getIndex (var) == index) {
				return var;
			}
		}
		return null;
	}

	/**
	 *  Searches this model for a variable with a given name.
	 *  @param name Name to find.
	 *  @return A variable <tt>var</tt> such that <tt>var.getLabel().equals (name)</tt>  
	 */
	public Variable findVariable (String name)
	{
		Iterator it = getVerticesIterator();
		while (it.hasNext()) {
			Variable var = (Variable) it.next();
			if (var.getLabel().equals(name)) {
				return var;
			}
		}
		return null;
	}

	/**
	 *  Adds a variable to this graphical model.
	 *  @param newVertex Variable to add.
	 */
	/* Work around broken OpenJGraph API that declares
		 java.lang.Exception to be thrown (!!!) */
	public void add (Vertex newVertex) 
	{
		try {
			super.add (newVertex);
		} catch (ClassCastException e) {
			throw new RuntimeException ("Attempt to add non-Variable to undirected model!");
		} catch (Exception e) {
			e.printStackTrace ();
			throw new RuntimeException (e);
		}
	}

	/**
	 * Removes a variable from this model.
	 * <p>
	 * This method is not completely supported.  In particular,
	 *  potentials on the variable are not removed.  This should
	 *  be fixed.
	 *
	 */
	 // xxx What
	// Work around nuisance OpenJGraph exception
	public void remove (Variable var)
	{
		try {
			super.remove (var);
		} catch (Exception e) {
			e.printStackTrace ();
			throw new RuntimeException (e);
		}
	
		numNodes--;
		removePotentialsOfVariable (var);
		regenerateCaches ();		
	}

	public void remove (Collection vars)
	{
		for (Iterator it = vars.iterator (); it.hasNext();) {
			Variable var = (Variable) it.next ();
			removePotentialsOfVariable (var);
			try {
				super.remove (var);
			} catch (Exception e) {
				e.printStackTrace ();
				throw new RuntimeException (e);
			}
		}
		
		numNodes -= vars.size ();
		regenerateCaches ();
	}
	
	/**
	 * Returns whether two variables are adjacent in the model's graph. 
	 *  @param v1 A variable in this model
	 *  @param v2 Another variable in this model
	 *  @return Whether there is an edge connecting them
	 */
	public boolean isAdjacent (Vertex v1, Vertex v2)
	{
		List edges = getEdges (v1);
		Iterator it = edges.iterator ();
		while (it.hasNext()) {
			Edge e = (Edge) it.next();
			if ((e.getVertexA() == v2) || (e.getVertexB() == v2)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Returns whether this variable is part of the model.
	 *  @param v1 Any Variable object 
	 *  @return true if this variable is contained in the moel.
	 */
	public boolean contains (Vertex v1)
	{
		return getVertexSet().contains (v1);
	}

		
	/* Work around broken OpenJGraph API that declares
		 java.lang.Exception to be thrown (!!!) */
	/**
	 * Adds an edge to the model.  No potential is added on the edge
	 *  @param v1 One variable in the edge
	 *  @param v2 Andother variable of the edge
	 * @see #addEdgeWithPotential(Vertex,Vertex,DiscretePotential)
	 */
	public Edge addEdge (Vertex v1, Vertex v2) {
		try {
			// Don't allow multigraph
			if (!contains(v1) || !contains (v2) || !isAdjacent (v1, v2)) {
				return super.addEdge (v1, v2);
			} else {
				return null;
			}
		} catch (Exception e) {
			e.printStackTrace ();
			throw new RuntimeException (e);
		}
	}
	
// {{{ ADDING AND REMOVING POTENTIALS

	/**
	 * Adds an undirected edge with an associated edge potential.
	 * @param var1 One variable of the edge
	 * @param var2 The other variable of the edge
	 * @param pot Potential for the new edge.  The potential must be
	 * over the variables <tt>var1</tt> and <tt>var1</tt>.
	 */
	public void addEdgeWithPotential (Vertex var1, Vertex var2, DiscretePotential pot)
	{
		try {
			/* This is broken.  salvo,jesus.graph.Graph.addEdge() should *not*
			 *  declare itself as throwing java.lang.Exception.  Come on!
			 */
			Edge e = addEdge (var1, var2);
			Clique c = new HashClique (e);
			addPotential (c, pot);