|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
ObjectUtil
public class Util
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.
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 |
---|
public static final int BIGGEST_POSSIBLE_CLUSTER
Constructor Detail |
---|
public Util()
Method Detail |
---|
public static double[] logCardinalities(int[] cardinalities)
cardinalities
- a map from each variable to its cardinality.
public static double logMaxClusterSize(int[] eo, int[] cardinalities, int[][] g)
eo
- the given elimination order.cardinalities
- a map from each node to its cardinality.g
- the given graph.
public static void fillNeighborMap(int[][] adj, int[] adjSize, int n, boolean[] map, boolean val)
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.public static void fillNeighborMap(int[][] adj, int[] adjSize, int n, boolean[][] map, boolean val)
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.public static void initGraph(int[][] g, int[][] adj, int[] adjSize)
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.public static void prepareForUpdate(int[][] adj, int[] adjSize, int removed, boolean[] marked, boolean[][] marked2)
public static void update(int[][] adj, int[] adjSize, int removed, boolean[] marked, boolean[][] marked2)
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.
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |