il2.inf.structure.minfill2
Class Util

Object
  extended by Util

public class Util
extends Object

Static utility routines.

We represent nodes as integers 0..N-1. We represent a graph as an array that maps each node to its adjacency list. We represent an adjacency as an int array containing one-hop neighbors in no particular order.

Internally, we work with a different graph representation. This representation is the same as the previous, except that the length of each adjacency list is not necessarily the same as the number of elements in the list. The second representation can be identified, because it is always be accompanied by an array that maps from each node to the size of its adjacency list.

Author:
Mark Chavira

Field Summary
static int BIGGEST_POSSIBLE_CLUSTER
          A constant for the largest cluster possible.
 
Constructor Summary
Util()
           
 
Method Summary
static void fillNeighborMap(int[][] adj, int[] adjSize, int n, boolean[][] map, boolean val)
          Fills the given map with the results of calling fillNeigbhorMap on each neighbor of the given node.
static void fillNeighborMap(int[][] adj, int[] adjSize, int n, boolean[] map, boolean val)
          Fills the given neighbor map for the given node.
static void initGraph(int[][] g, int[][] adj, int[] adjSize)
          Initializes a graph in the internal representation from a graph in the external representation.
static double[] logCardinalities(int[] cardinalities)
          Returns a map from each variable to the log base 2 of its cardinality.
static double logMaxClusterSize(int[] eo, int[] cardinalities, int[][] g)
          Returns the log base two of the maximum cluster size of the given elimination order when applied to the given graph.
static void prepareForUpdate(int[][] adj, int[] adjSize, int removed, boolean[] marked, boolean[][] marked2)
           
static void update(int[][] adj, int[] adjSize, int removed, boolean[] marked, boolean[][] marked2)
          Removes edges in one direction from each one-hop neighbor to the given node.
 
Methods inherited from class Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

BIGGEST_POSSIBLE_CLUSTER

public static final int BIGGEST_POSSIBLE_CLUSTER
A constant for the largest cluster possible. Minfill will fail if a variable is eliminated that has a cluster bigger.

See Also:
Constant Field Values
Constructor Detail

Util

public Util()
Method Detail

logCardinalities

public static double[] logCardinalities(int[] cardinalities)
Returns a map from each variable to the log base 2 of its cardinality.

Parameters:
cardinalities - a map from each variable to its cardinality.
Returns:
the map from each variable to the log of its cardinality.

logMaxClusterSize

public static double logMaxClusterSize(int[] eo,
                                       int[] cardinalities,
                                       int[][] g)
Returns the log base two of the maximum cluster size of the given elimination order when applied to the given graph.

Parameters:
eo - the given elimination order.
cardinalities - a map from each node to its cardinality.
g - the given graph.
Returns:
the log base two of the maximum cluster size.

fillNeighborMap

public static void fillNeighborMap(int[][] adj,
                                   int[] adjSize,
                                   int n,
                                   boolean[] map,
                                   boolean val)
Fills the given neighbor map for the given node.

Parameters:
adj - a map from each node to its adjacency list.
adjSize - a map from each node to the size of its adjacency list.
n - the given node.
map - the given neighbor map.
val - the given value.

fillNeighborMap

public static void fillNeighborMap(int[][] adj,
                                   int[] adjSize,
                                   int n,
                                   boolean[][] map,
                                   boolean val)
Fills the given map with the results of calling fillNeigbhorMap on each neighbor of the given node.

Parameters:
adj - a map from each node to its adjacency list.
adjSize - a map from each node to the size of its adjacency list.
n - the given node.
map - the given neighbor map.
val - the given value.

initGraph

public static void initGraph(int[][] g,
                             int[][] adj,
                             int[] adjSize)
Initializes a graph in the internal representation from a graph in the external representation.

Parameters:
g - the given external graph.
on - entry, an array of the same dimension as ext; on exit, a map from each node to its adjacency list.
adjSize - on entry, an array of the same dimension as ext; on exit, a map from each node to the size of its adjacency list.

prepareForUpdate

public static void prepareForUpdate(int[][] adj,
                                    int[] adjSize,
                                    int removed,
                                    boolean[] marked,
                                    boolean[][] marked2)

update

public static void update(int[][] adj,
                          int[] adjSize,
                          int removed,
                          boolean[] marked,
                          boolean[][] marked2)
Removes edges in one direction from each one-hop neighbor to the given node.

Parameters:
adj - a map from each node to its adjacency list.
adjSize - a map from each node to the size of its adjacency list.
removed - the given node.
marked2 - on entry, an int[BIGGEST_POSSIBLE_CLUSTER - 1][N] that is all false; on exit, marked2[i] maps each node to whether it is a neighbor of the former ith neigbhor of the removed node.


Copyright 2010 UCLA Automated Reasoning Group