il2.inf.structure.minfill2
Class EliminationOrderEngine

Object
  extended by EliminationOrderEngine
Direct Known Subclasses:
MinfillEoe

public abstract class EliminationOrderEngine
extends Object

A base class for algorithms that produce an elimination order. See class Util for some definitions.

Author:
Mark Chavira

Constructor Summary
EliminationOrderEngine()
           
 
Method Summary
 int[] order(Random r, int[] cardinalities, int[][] g, int[][] nodes)
          Computes a "restricted" elimination order for a subset of nodes.
 int[] safeOrder(int[] cardinalities, int[][] g, int[][] nodes, double low)
           
 
Methods inherited from class Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

EliminationOrderEngine

public EliminationOrderEngine()
Method Detail

order

public int[] order(Random r,
                   int[] cardinalities,
                   int[][] g,
                   int[][] nodes)
            throws Exception
Computes a "restricted" elimination order for a subset of nodes. The parameter nodes specifies an ordered partition of the subset. It must have dimension >0. Variables in nodes[0] appear first in the order, in nodes[1] second, etc. Nodes within an element of the partition are ordered in a way dictated by the subclass. For a normal elimination order, nodes will have only one dimension. For MAP, it will have two dimensions. When constructing an ordering on clauses from an ordering on bn variables in the context of AC inference, the nodes representing clauses will be partitioned according to the bn variables wherein they derive, and the partitions will be ordered according to the bn variable ordering. Other uses for this feature abound. The method allows the client to specifies a random generator. This generator is used to shuffle the nodes in the parameter named nodes, which has the effect of breaking ties differently. The random generator may be specified as null, in which case no shuffling occurs.

Parameters:
r - a random generator used to shuffle the order of the nodes; may be null, in which case the nodes are not shuffled. Shuffling has the effect of breaking ties differently.
cardinalities - maps each node to its cardinality.
maps - each node to its adjacency list.
nodes - an ordered partition of the nodes to order.
Returns:
the order.
Throws:
Exception

safeOrder

public int[] safeOrder(int[] cardinalities,
                       int[][] g,
                       int[][] nodes,
                       double low)
                throws Exception
Throws:
Exception


Copyright 2010 UCLA Automated Reasoning Group