Package edu.cmu.tetrad.bayes
Class GraphTools
java.lang.Object
edu.cmu.tetrad.bayes.GraphTools
A utility class containing graph function from graph theory. These implementations derived from Weka's
implementation.
Oct 7, 2019 2:56:07 PM
- Author:
- Kevin V. Bui (kvb2@pitt.edu)
- See Also:
-
Method Summary
Modifier and TypeMethodDescriptionstatic void
Apply Tarjan and Yannakakis (1984) fill in algorithm for graph triangulation.getCliques
(Node[] ordering, Graph graph) Get cliques in a decomposable graph.static Node[]
Perform Tarjan and Yannakakis (1984) maximum cardinality search (MCS) to get the maximum cardinality ordering.Calculate separator sets in clique tree.static Graph
Create a moral graph.
-
Method Details
-
getCliqueTree
public static Map<Node,Node> getCliqueTree(Node[] ordering, Map<Node, Set<Node>> cliques, Map<Node, Set<Node>> separators) - Parameters:
ordering
- maximum cardinality orderingcliques
- set of cliquesseparators
- set of separator sets- Returns:
- parent cliques
-
getSeparators
Calculate separator sets in clique tree. A separator (set) is the intersection of two adjacent nodes.- Parameters:
ordering
- maximum cardinality ordering of the graphcliques
- set of cliques- Returns:
- set of separator sets
-
getCliques
Get cliques in a decomposable graph. A clique is a fully-connected subgraph.- Parameters:
graph
- decomposable graphordering
- maximum cardinality ordering- Returns:
- set of cliques
-
fillIn
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 graphordering
- maximum cardinality ordering
-
getMaximumCardinalityOrdering
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
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
-