edu.ksu.cis.kdd.util.graph
Class MaxCardinalitySearch

java.lang.Object
  edu.ksu.cis.kdd.util.graph.MaxCardinalitySearch

public class MaxCardinalitySearch

extends java.lang.Object

Perform maximal cardinality search. Actually a part of Clique tree construction, but refactored out because other modules may use this ordering as well.

Author:

Roby Joehanes

Constructor Summary

MaxCardinalitySearch(Graph g)

MaxCardinalitySearch(TableSet adjList)
Clique tree construction.

Method Summary

java.util.List	getOrder()
static void	main(java.lang.String[] args)
protected void	maxCardinalitySearch() Maximum Cardinality Search.
protected void	moralization() "Moralize" the graph.
protected void	toUndirectedGraph() Converting the adjacency list into undirected edges.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MaxCardinalitySearch

public MaxCardinalitySearch(Graph g)

MaxCardinalitySearch

public MaxCardinalitySearch(TableSet adjList)

Clique tree construction. Follows directly from Neapolitan's book.

Parameters:

adjList -

Method Detail

moralization

protected void moralization()

"Moralize" the graph. For every two parents of a particular node, add an undirected edge to it.

toUndirectedGraph

protected void toUndirectedGraph()

Converting the adjacency list into undirected edges. It simply add the reverse edge.

maxCardinalitySearch

protected void maxCardinalitySearch()

Maximum Cardinality Search. See Tarjan and Yannakakis.

For the pseudocode, see Neapolitan, R., Probabilistic Reasoning In Expert Systems, Theory and Algorithm, 1990, John Wiley and Sons, page 110.

getOrder

public java.util.List getOrder()

Returns:

List

main

public static void main(java.lang.String[] args)