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

Author:
Kevin V. Bui (kvb2@pitt.edu)
See Also:
  • 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 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:
      graph - decomposable graph
      ordering - maximum cardinality ordering
      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