Package edu.cmu.tetrad.bayes

Class GraphTools

java.lang.Object

edu.cmu.tetrad.bayes.GraphTools

public final class GraphTools
extends Object

A utility class containing graph function from graph theory. These implementations derived from Weka's implementation.

Oct 7, 2019 2:56:07 PM

Version:

$Id: $Id

Author:

Kevin V. Bui (kvb2@pitt.edu)

See Also:

• MarginCalculator.java

Method Summary

Modifier and Type	Method	Description
static void	fillIn(Graph graph, Node[] ordering)	Apply Tarjan and Yannakakis (1984) fill in algorithm for graph triangulation.
static Map<Node,Set<Node>>	getCliques(Node[] ordering, Graph graph)	Get cliques in a decomposable graph.
static Map<Node,Node>	getCliqueTree(Node[] ordering, Map<Node,Set<Node>> cliques, Map<Node,Set<Node>> separators)	getCliqueTree.
static Node[]	getMaximumCardinalityOrdering(Graph graph)	Perform Tarjan and Yannakakis (1984) maximum cardinality search (MCS) to get the maximum cardinality ordering.
static Map<Node,Set<Node>>	getSeparators(Node[] ordering, Map<Node,Set<Node>> cliques)	Calculate separator sets in clique tree.
static Graph	moralize(Graph graph)	Create a moral graph.

Methods inherited from class java.lang.Object

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

Method Details

getCliqueTree

public static Map<Node,Node> getCliqueTree(Node[] ordering,
 Map<Node,Set<Node>> cliques,
 Map<Node,Set<Node>> separators)

getCliqueTree.

Parameters:

ordering - maximum cardinality ordering

cliques - set of cliques

separators - set of separator sets

Returns:

parent cliques

getSeparators

public static Map<Node,Set<Node>> getSeparators(Node[] ordering,
 Map<Node,Set<Node>> cliques)

Calculate separator sets in clique tree. A separator (set) is the intersection of two adjacent nodes.

Parameters:

ordering - maximum cardinality ordering of the graph

cliques - set of cliques

Returns:

set of separator sets

getCliques

public static Map<Node,Set<Node>> getCliques(Node[] ordering,
 Graph graph)

Get cliques in a decomposable graph. A clique is a fully-connected subgraph.

Parameters:

ordering - maximum cardinality ordering

graph - decomposable graph

Returns:

set of cliques

fillIn

public static void fillIn(Graph graph,
 Node[] ordering)

Apply Tarjan and Yannakakis (1984) fill in algorithm for graph triangulation. An undirected graph is triangulated if every cycle of length greater than 4 has a chord.

Parameters:

graph - moral graph

ordering - maximum cardinality ordering

getMaximumCardinalityOrdering

public static Node[] getMaximumCardinalityOrdering(Graph graph)

Perform Tarjan and Yannakakis (1984) maximum cardinality search (MCS) to get the maximum cardinality ordering.

Parameters:

graph - moral graph

Returns:

maximum cardinality ordering of the graph

moralize

public static Graph moralize(Graph graph)

Create a moral graph. A graph is moralized if an edge is added between two parents with common a child and the edge orientation is removed, making an undirected graph.

Parameters:

graph - to moralized

Returns:

a moral graph