class_docstr: Base class for Markov Model.
  
  A MarkovNetwork stores nodes and edges with potentials
  
  MarkovNetwork holds undirected edges.
  
  Parameters
  ----------
  data : input graph
      Data to initialize graph.  If data=None (default) an empty
      graph is created.  The data can be an edge list, or any
      NetworkX graph object.
  
  Examples
  --------
  Create an empty Markov Model with no nodes and no edges.
  
  >>> from pgmpy.models import MarkovNetwork
  >>> G = MarkovNetwork()
  
  G can be grown in several ways.
  
  **Nodes:**
  
  Add one node at a time:
  
  >>> G.add_node('a')
  
  Add the nodes from any container (a list, set or tuple or the nodes
  from another graph).
  
  >>> G.add_nodes_from(['a', 'b'])
  
  **Edges:**
  
  G can also be grown by adding edges.
  
  Add one edge,
  
  >>> G.add_edge('a', 'b')
  
  a list of edges,
  
  >>> G.add_edges_from([('a', 'b'), ('b', 'c')])
  
  If some edges connect nodes not yet in the model, the nodes
  are added automatically.  There are no errors when adding
  nodes or edges that already exist.
  
  **Shortcuts:**
  
  Many common graph features allow python syntax for speed reporting.
  
  >>> 'a' in G     # check if node in graph
  True
  >>> len(G)  # number of nodes in graph
  3
class_docstr_tok: ["Base","class","for","Markov","Model",".","A","MarkovNetwork","stores","nodes","and","edges","with","potentials","MarkovNetwork","holds","undirected","edges",".","Parameters","--","--","--","--","--","data",":","input","graph","Data","to","initialize","graph",".","If","data=None","(","default",")","an","empty","graph","is","created",".","The","data","can","be","an","edge","list",",","or","any","NetworkX","graph","object",".","Examples","--","--","--","--","Create","an","empty","Markov","Model","with","no","nodes","and","no","edges",".",">",">",">","from","pgmpy.models","import","MarkovNetwork",">",">",">","G","=","MarkovNetwork","(",")","G","can","be","grown","in","several","ways",".","*","*","Nodes",":","*","*","Add","one","node","at","a","time",":",">",">",">","G.add_node","(","'","a","'",")","Add","the","nodes","from","any","container","(","a","list",",","set","or","tuple","or","the","nodes","from","another","graph",")",".",">",">",">","G.add_nodes_from","(","[","'","a","'",",","'","b","'","]",")","*","*","Edges",":","*","*","G","can","also","be","grown","by","adding","edges",".","Add","one","edge",",",">",">",">","G.add_edge","(","'","a","'",",","'","b","'",")","a","list","of","edges",",",">",">",">","G.add_edges_from","(","[","(","'","a","'",",","'","b","'",")",",","(","'","b","'",",","'","c","'",")","]",")","If","some","edges","connect","nodes","not","yet","in","the","model",",","the","nodes","are","added","automatically",".","There","are","no","errors","when","adding","nodes","or","edges","that","already","exist",".","*","*","Shortcuts",":","*","*","Many","common","graph","features","allow","python","syntax","for","speed","reporting",".",">",">",">","'","a","'","in","G","#","check","if","node","in","graph","True",">",">",">","len","(","G",")","#","number","of","nodes","in","graph","3"]
docstr: Triangulate the graph.
  
  If order of deletion is given heuristic algorithm will not be used.
  
  Parameters
  ----------
  heuristic: H1 | H2 | H3 | H4 | H5 | H6
      The heuristic algorithm to use to decide the deletion order of
      the variables to compute the triangulated graph.
      Let X be the set of variables and X(i) denotes the i-th variable.
  
      * S(i) - The size of the clique created by deleting the variable.
      * E(i) - Cardinality of variable X(i).
      * M(i) - Maximum size of cliques given by X(i) and its adjacent nodes.
      * C(i) - Sum of size of cliques given by X(i) and its adjacent nodes.
  
      The heuristic algorithm decide the deletion order if this way:
  
      * H1 - Delete the variable with minimal S(i).
      * H2 - Delete the variable with minimal S(i)/E(i).
      * H3 - Delete the variable with minimal S(i) - M(i).
      * H4 - Delete the variable with minimal S(i) - C(i).
      * H5 - Delete the variable with minimal S(i)/M(i).
      * H6 - Delete the variable with minimal S(i)/C(i).
  
  order: list, tuple (array-like)
      The order of deletion of the variables to compute the triagulated
      graph. If order is given heuristic algorithm will not be used.
  
  inplace: True | False
      if inplace is true then adds the edges to the object from
      which it is called else returns a new object.
  
  References
  ----------
  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.3607
  
  Examples
  --------
  >>> from pgmpy.models import MarkovNetwork
  >>> from pgmpy.factors.discrete import DiscreteFactor
  >>> G = MarkovNetwork()
  >>> G.add_nodes_from(['x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7'])
  >>> G.add_edges_from([('x1', 'x3'), ('x1', 'x4'), ('x2', 'x4'),
  ...                   ('x2', 'x5'), ('x3', 'x6'), ('x4', 'x6'),
  ...                   ('x4', 'x7'), ('x5', 'x7')])
  >>> phi = [DiscreteFactor(edge, [2, 2], np.random.rand(4)) for edge in G.edges()]
  >>> G.add_factors(*phi)
  >>> G_chordal = G.triangulate()
docstr_tok: ["Triangulate","the","graph",".","If","order","of","deletion","is","given","heuristic","algorithm","will","not","be","used",".","Parameters","--","--","--","--","--","heuristic",":","H1","|","H2","|","H3","|","H4","|","H5","|","H6","The","heuristic","algorithm","to","use","to","decide","the","deletion","order","of","the","variables","to","compute","the","triangulated","graph",".","Let","X","be","the","set","of","variables","and","X","(","i",")","denotes","the","i-th","variable",".","*","S","(","i",")","-","The","size","of","the","clique","created","by","deleting","the","variable",".","*","E","(","i",")","-","Cardinality","of","variable","X","(","i",")",".","*","M","(","i",")","-","Maximum","size","of","cliques","given","by","X","(","i",")","and","its","adjacent","nodes",".","*","C","(","i",")","-","Sum","of","size","of","cliques","given","by","X","(","i",")","and","its","adjacent","nodes",".","The","heuristic","algorithm","decide","the","deletion","order","if","this","way",":","*","H1","-","Delete","the","variable","with","minimal","S","(","i",")",".","*","H2","-","Delete","the","variable","with","minimal","S","(","i",")","\/E","(","i",")",".","*","H3","-","Delete","the","variable","with","minimal","S","(","i",")","-","M","(","i",")",".","*","H4","-","Delete","the","variable","with","minimal","S","(","i",")","-","C","(","i",")",".","*","H5","-","Delete","the","variable","with","minimal","S","(","i",")","\/M","(","i",")",".","*","H6","-","Delete","the","variable","with","minimal","S","(","i",")","\/C","(","i",")",".","order",":","list",",","tuple","(","array-like",")","The","order","of","deletion","of","the","variables","to","compute","the","triagulated","graph",".","If","order","is","given","heuristic","algorithm","will","not","be","used",".","inplace",":","True","|","False","if","inplace","is","true","then","adds","the","edges","to","the","object","from","which","it","is","called","else","returns","a","new","object",".","References","--","--","--","--","--","http",":","\/\/citeseerx.ist.psu.edu\/viewdoc\/summary","?","doi=10.1.1.56.3607","Examples","--","--","--","--",">",">",">","from","pgmpy.models","import","MarkovNetwork",">",">",">","from","pgmpy.factors.discrete","import","DiscreteFactor",">",">",">","G","=","MarkovNetwork","(",")",">",">",">","G.add_nodes_from","(","[","'x1","'",",","'x2","'",",","'x3","'",",","'x4","'",",","'x5","'",",","'x6","'",",","'x7","'","]",")",">",">",">","G.add_edges_from","(","[","(","'x1","'",",","'x3","'",")",",","(","'x1","'",",","'x4","'",")",",","(","'x2","'",",","'x4","'",")",",","...","(","'x2","'",",","'x5","'",")",",","(","'x3","'",",","'x6","'",")",",","(","'x4","'",",","'x6","'",")",",","...","(","'x4","'",",","'x7","'",")",",","(","'x5","'",",","'x7","'",")","]",")",">",">",">","phi","=","[","DiscreteFactor","(","edge",",","[","2",",","2","]",",","np.random.rand","(","4",")",")","for","edge","in","G.edges","(",")","]",">",">",">","G.add_factors","(","*","phi",")",">",">",">","G_chordal","=","G.triangulate","(",")"]
code: def triangulate(self, heuristic="H6", order=None, inplace=False):
      """
      Triangulate the graph.
  
      If order of deletion is given heuristic algorithm will not be used.
  
      Parameters
      ----------
      heuristic: H1 | H2 | H3 | H4 | H5 | H6
          The heuristic algorithm to use to decide the deletion order of
          the variables to compute the triangulated graph.
          Let X be the set of variables and X(i) denotes the i-th variable.
  
          * S(i) - The size of the clique created by deleting the variable.
          * E(i) - Cardinality of variable X(i).
          * M(i) - Maximum size of cliques given by X(i) and its adjacent nodes.
          * C(i) - Sum of size of cliques given by X(i) and its adjacent nodes.
  
          The heuristic algorithm decide the deletion order if this way:
  
          * H1 - Delete the variable with minimal S(i).
          * H2 - Delete the variable with minimal S(i)/E(i).
          * H3 - Delete the variable with minimal S(i) - M(i).
          * H4 - Delete the variable with minimal S(i) - C(i).
          * H5 - Delete the variable with minimal S(i)/M(i).
          * H6 - Delete the variable with minimal S(i)/C(i).
  
      order: list, tuple (array-like)
          The order of deletion of the variables to compute the triagulated
          graph. If order is given heuristic algorithm will not be used.
  
      inplace: True | False
          if inplace is true then adds the edges to the object from
          which it is called else returns a new object.
  
      References
      ----------
      http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.3607
  
      Examples
      --------
      >>> from pgmpy.models import MarkovNetwork
      >>> from pgmpy.factors.discrete import DiscreteFactor
      >>> G = MarkovNetwork()
      >>> G.add_nodes_from(['x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7'])
      >>> G.add_edges_from([('x1', 'x3'), ('x1', 'x4'), ('x2', 'x4'),
      ...                   ('x2', 'x5'), ('x3', 'x6'), ('x4', 'x6'),
      ...                   ('x4', 'x7'), ('x5', 'x7')])
      >>> phi = [DiscreteFactor(edge, [2, 2], np.random.rand(4)) for edge in G.edges()]
      >>> G.add_factors(*phi)
      >>> G_chordal = G.triangulate()
      """
      self.check_model()
  
      if self.is_triangulated():
          if inplace:
              return
          else:
              return self
  
      graph_copy = nx.Graph(self.edges())
      edge_set = set()
  
      def _find_common_cliques(cliques_list):
          """
          Finds the common cliques among the given set of cliques for
          corresponding node.
          """
          common = set([tuple(x) for x in cliques_list[0]])
          for i in range(1, len(cliques_list)):
              common = common & set([tuple(x) for x in cliques_list[i]])
          return list(common)
  
      def _find_size_of_clique(clique, cardinalities):
          """
          Computes the size of a clique.
  
          Size of a clique is defined as product of cardinalities of all the
          nodes present in the clique.
          """
          return list(
              map(
                  lambda x: np.prod(
                      [cardinalities[node] for node in x]
                  ),
                  clique,
              )
          )
  
      def _get_cliques_dict(node):
          """
          Returns a dictionary in the form of {node: cliques_formed} of the
          node along with its neighboring nodes.
  
          clique_dict_removed would be containing the cliques created
          after deletion of the node
          clique_dict_node would be containing the cliques created before
          deletion of the node
          """
          graph_working_copy = nx.Graph(graph_copy.edges())
          neighbors = list(graph_working_copy.neighbors(node))
          graph_working_copy.add_edges_from(
              itertools.combinations(neighbors, 2)
          )
  
          clique_dict = {var: [] for var in [node] + neighbors}
          max_cliques = list(nx.find_cliques(graph_working_copy))
          for var in [node] + neighbors:
              for clique in max_cliques:
                  if var in clique:
                      clique_dict[var].append(clique)
  
          graph_working_copy.remove_node(node)
  
          clique_dict_removed = {var: [] for var in neighbors}
          max_cliques = list(nx.find_cliques(graph_working_copy))
          for var in neighbors:
              for clique in max_cliques:
                  if var in clique:
                      clique_dict_removed[var].append(clique)
  
          return clique_dict, clique_dict_removed
  
      if not order:
          order = []
  
          cardinalities = self.get_cardinality()
          for index in range(self.number_of_nodes()):
              # S represents the size of clique created by deleting the
              # node from the graph
              S = {}
              # M represents the size of maximum size of cliques given by
              # the node and its adjacent node
              M = {}
              # C represents the sum of size of the cliques created by the
              # node and its adjacent node
              C = {}
              for node in set(graph_copy.nodes()) - set(order):
                  clique_dict, clique_dict_removed = _get_cliques_dict(
                      node
                  )
                  S[node] = _find_size_of_clique(
                      _find_common_cliques(
                          list(clique_dict_removed.values())
                      ),
                      cardinalities,
                  )[0]
                  common_clique_size = _find_size_of_clique(
                      _find_common_cliques(list(clique_dict.values())),
                      cardinalities,
                  )
                  M[node] = np.max(common_clique_size)
                  C[node] = np.sum(common_clique_size)
  
              if heuristic == "H1":
                  node_to_delete = min(S, key=S.get)
  
              elif heuristic == "H2":
                  S_by_E = {
                      key: S[key] / cardinalities[key] for key in S
                  }
                  node_to_delete = min(S_by_E, key=S_by_E.get)
  
              elif heuristic == "H3":
                  S_minus_M = {key: S[key] - M[key] for key in S}
                  node_to_delete = min(S_minus_M, key=S_minus_M.get)
  
              elif heuristic == "H4":
                  S_minus_C = {key: S[key] - C[key] for key in S}
                  node_to_delete = min(S_minus_C, key=S_minus_C.get)
  
              elif heuristic == "H5":
                  S_by_M = {key: S[key] / M[key] for key in S}
                  node_to_delete = min(S_by_M, key=S_by_M.get)
  
              else:
                  S_by_C = {key: S[key] / C[key] for key in S}
                  node_to_delete = min(S_by_C, key=S_by_C.get)
  
              order.append(node_to_delete)
  
      graph_copy = nx.Graph(self.edges())
      for node in order:
          for edge in itertools.combinations(
              graph_copy.neighbors(node), 2
          ):
              graph_copy.add_edge(edge[0], edge[1])
              edge_set.add(edge)
          graph_copy.remove_node(node)
  
      if inplace:
          for edge in edge_set:
              self.add_edge(edge[0], edge[1])
          return self
  
      else:
          graph_copy = MarkovNetwork(self.edges())
          for edge in edge_set:
              graph_copy.add_edge(edge[0], edge[1])
          return graph_copy
  
imports: import itertools
  from collections import defaultdict
  import networkx
  import numpy
  from networkx.algorithms.components import connected_components
  from pgmpy.base import UndirectedGraph
  from pgmpy.factors import factor_product
  from pgmpy.factors.discrete import DiscreteFactor
  from pgmpy.independencies import Independencies
label_desc: Use image node_id 10 for calling the MarkovNetwork obj's underlying member method code with example usage: obj.triangulate(heuristic, order, inplace) and returns: list, list, clique_dict,  clique_dict_removed, self, graph_copy, self