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

java.lang.Object
  salvo.jesus.graph.GraphImpl
      salvo.jesus.graph.DirectedGraphImpl
          salvo.jesus.graph.DirectedAcyclicGraphImpl
              edu.ksu.cis.kdd.util.graph.Graph
                  edu.ksu.cis.kdd.util.graph.CliqueTree

All Implemented Interfaces:

salvo.jesus.graph.DirectedAcyclicGraph, salvo.jesus.graph.DirectedGraph, salvo.jesus.graph.Graph, HasProperty, java.io.Serializable

public class CliqueTree

extends Graph

Author:

Roby Joehanes

See Also:

Serialized Form

Field Summary

protected TableSet	adjList
protected java.util.LinkedList	cliques
protected java.util.Hashtable	nodeOrdering
protected TableSet	origList
protected java.lang.Object[]	reverseOrdering

Fields inherited from class edu.ksu.cis.kdd.util.graph.Graph

name, nodeTable, property

Fields inherited from class salvo.jesus.graph.GraphImpl

factory, traversal

Constructor Summary

CliqueTree()

CliqueTree(Graph g)

CliqueTree(java.util.Set[] adjList)

CliqueTree(TableSet adjList)
Clique tree construction.

Method Summary

void	buildCliqueTree()
protected void	buildEdges() Compute S for each clique (i.e. the separator set).
protected void	findCliques() Find cliques.
java.util.List	getOrderedCliques()
static void	main(java.lang.String[] args)
protected void	printAdjList() For debugging only
protected void	triangulation() Triangulation.

Methods inherited from class edu.ksu.cis.kdd.util.graph.Graph

add, addEdge, addNode, addNodes, containsNode, equals, getAdjacencyList, getEdges, getError, getName, getNode, getNodeList, getNodeNames, getNodes, getProperty, getProperty, getReverseAdjacencyList, hashCode, putProperty, remove, removeEdge, removeNode, removeProperty, setName, setProperty, toString

Methods inherited from class salvo.jesus.graph.DirectedAcyclicGraphImpl

getRoot, reverseTopologicalSort, reverseTopologicalSort, topologicalSort, topologicalSort

Methods inherited from class salvo.jesus.graph.DirectedGraphImpl

getEdge, getIncomingAdjacentVertices, getIncomingEdges, getOutgoingAdjacentVertices, getOutgoingEdges, isCycle, isPath

Methods inherited from class salvo.jesus.graph.GraphImpl

addEdge, addGraphAddEdgeListener, addGraphAddVertexListener, addGraphRemoveEdgeListener, addGraphRemoveVertexListener, addListener, cloneVertices, containsEdge, containsVertex, forgetConnectedSets, getAdjacentVertices, getAdjacentVertices, getConnectedSet, getConnectedSet, getDegree, getDegree, getEdges, getEdgesCount, getEdgeSet, getGraphFactory, getTraversal, getVertexSet, getVertices, getVerticesCount, getVerticesIterator, isConnected, removeEdge, removeEdges, removeGraphAddEdgeListener, removeGraphAddVertexListener, removeGraphRemoveEdgeListener, removeGraphRemoveVertexListener, removeListener, setGraphFactory, setTraversal, traverse

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface salvo.jesus.graph.DirectedGraph

getEdge, getIncomingAdjacentVertices, getIncomingEdges, getOutgoingAdjacentVertices, getOutgoingEdges, isCycle, isPath

Methods inherited from interface salvo.jesus.graph.Graph

addEdge, addGraphAddEdgeListener, addGraphAddVertexListener, addGraphRemoveEdgeListener, addGraphRemoveVertexListener, addListener, cloneVertices, getAdjacentVertices, getAdjacentVertices, getConnectedSet, getConnectedSet, getDegree, getDegree, getEdges, getEdgesCount, getEdgeSet, getGraphFactory, getTraversal, getVertexSet, getVertices, getVerticesCount, getVerticesIterator, isConnected, removeEdge, removeEdges, removeGraphAddEdgeListener, removeGraphAddVertexListener, removeGraphRemoveEdgeListener, removeGraphRemoveVertexListener, removeListener, setGraphFactory, setTraversal, traverse

Field Detail

adjList

protected TableSet adjList

origList

protected TableSet origList

reverseOrdering

protected java.lang.Object[] reverseOrdering

nodeOrdering

protected java.util.Hashtable nodeOrdering

cliques

protected java.util.LinkedList cliques

Constructor Detail

CliqueTree

public CliqueTree()

CliqueTree

public CliqueTree(Graph g)

CliqueTree

public CliqueTree(java.util.Set[] adjList)

CliqueTree

public CliqueTree(TableSet adjList)

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

Parameters:

adjList -

Method Detail

buildCliqueTree

public void buildCliqueTree()

triangulation

protected void triangulation()

Triangulation.

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

findCliques

protected void findCliques()

Find cliques. It simply follows the reverse order of the cardinality ordering. Then search on its parents that has ordering number less than itself. After that, we must check whether the clique is already contained in the previous search. If not, then we can safely add the clique.

buildEdges

protected void buildEdges()

Compute S for each clique (i.e. the separator set). We don't need to compute R, because it is inferred. Here, we also build edges

getOrderedCliques

public java.util.List getOrderedCliques()

printAdjList

protected void printAdjList()

For debugging only

main

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