class_docstr: Class for constraint-based estimation of DAGs using the PC algorithm
  from a given data set.  Identifies (conditional) dependencies in data
  set using statistical independence tests and estimates a DAG pattern
  that satisfies the identified dependencies. The DAG pattern can then be
  completed to a faithful DAG, if possible.
  
  Parameters
  ----------
  data: pandas DataFrame object
      dataframe object where each column represents one variable.  (If some
      values in the data are missing the data cells should be set to
      `numpy.NaN`.  Note that pandas converts each column containing
      `numpy.NaN`s to dtype `float`.)
  
  References
  ----------
  [1] Koller & Friedman, Probabilistic Graphical Models - Principles and Techniques,
      2009, Section 18.2
  [2] Neapolitan, Learning Bayesian Networks, Section 10.1.2 for the PC algorithm (page 550), http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf
docstr: Orients the edges of a graph skeleton based on information from
  `separating_sets` to form a DAG pattern (DAG).
  
  Parameters
  ----------
  skeleton: UndirectedGraph
      An undirected graph skeleton as e.g. produced by the
      estimate_skeleton method.
  
  separating_sets: dict
      A dict containing for each pair of not directly connected nodes a
      separating set ("witnessing set") of variables that makes then
      conditionally independent. (needed for edge orientation)
  
  Returns
  -------
  Model after edge orientation: pgmpy.base.DAG
      An estimate for the DAG pattern of the BN underlying the data. The
      graph might contain some nodes with both-way edges (X->Y and Y->X).
      Any completion by (removing one of the both-way edges for each such
      pair) results in a I-equivalent Bayesian network DAG.
  
  References
  ----------
  Neapolitan, Learning Bayesian Networks, Section 10.1.2, Algorithm 10.2 (page 550)
  http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf
  
  
  Examples
  --------
  >>> import pandas as pd
  >>> import numpy as np
  >>> from pgmpy.estimators import PC
  >>> data = pd.DataFrame(np.random.randint(0, 4, size=(5000, 3)), columns=list('ABD'))
  >>> data['C'] = data['A'] - data['B']
  >>> data['D'] += data['A']
  >>> c = PC(data)
  >>> pdag = c.skeleton_to_pdag(*c.build_skeleton())
  >>> pdag.edges() # edges: A->C, B->C, A--D (not directed)
  [('B', 'C'), ('A', 'C'), ('A', 'D'), ('D', 'A')]
docstr_tok: ["Orients","the","edges","of","a","graph","skeleton","based","on","information","from","`","separating_sets","`","to","form","a","DAG","pattern","(","DAG",")",".","Parameters","--","--","--","--","--","skeleton",":","UndirectedGraph","An","undirected","graph","skeleton","as","e.g",".","produced","by","the","estimate_skeleton","method",".","separating_sets",":","dict","A","dict","containing","for","each","pair","of","not","directly","connected","nodes","a","separating","set","(","``","witnessing","set","''",")","of","variables","that","makes","then","conditionally","independent",".","(","needed","for","edge","orientation",")","Returns","--","--","--","-","Model","after","edge","orientation",":","pgmpy.base.DAG","An","estimate","for","the","DAG","pattern","of","the","BN","underlying","the","data",".","The","graph","might","contain","some","nodes","with","both-way","edges","(","X-",">","Y","and","Y-",">","X",")",".","Any","completion","by","(","removing","one","of","the","both-way","edges","for","each","such","pair",")","results","in","a","I-equivalent","Bayesian","network","DAG",".","References","--","--","--","--","--","Neapolitan",",","Learning","Bayesian","Networks",",","Section","10.1.2",",","Algorithm","10.2","(","page","550",")","http",":","\/\/www.cs.technion.ac.il\/~dang\/books\/Learning","%","20Bayesian","%","20Networks","(","Neapolitan",",","%","20Richard",")",".pdf","Examples","--","--","--","--",">",">",">","import","pandas","as","pd",">",">",">","import","numpy","as","np",">",">",">","from","pgmpy.estimators","import","PC",">",">",">","data","=","pd.DataFrame","(","np.random.randint","(","0",",","4",",","size=","(","5000",",","3",")",")",",","columns=list","(","'ABD","'",")",")",">",">",">","data","[","'","C","'","]","=","data","[","'","A","'","]","-","data","[","'","B","'","]",">",">",">","data","[","'D","'","]","+=","data","[","'","A","'","]",">",">",">","c","=","PC","(","data",")",">",">",">","pdag","=","c.skeleton_to_pdag","(","*","c.build_skeleton","(",")",")",">",">",">","pdag.edges","(",")","#","edges",":","A-",">","C",",","B-",">","C",",","A","--","D","(","not","directed",")","[","(","'","B","'",",","'","C","'",")",",","(","'","A","'",",","'","C","'",")",",","(","'","A","'",",","'D","'",")",",","(","'D","'",",","'","A","'",")","]"]
code: def skeleton_to_pdag(skeleton, separating_sets):
      """Orients the edges of a graph skeleton based on information from
      `separating_sets` to form a DAG pattern (DAG).
  
      Parameters
      ----------
      skeleton: UndirectedGraph
          An undirected graph skeleton as e.g. produced by the
          estimate_skeleton method.
  
      separating_sets: dict
          A dict containing for each pair of not directly connected nodes a
          separating set ("witnessing set") of variables that makes then
          conditionally independent. (needed for edge orientation)
  
      Returns
      -------
      Model after edge orientation: pgmpy.base.DAG
          An estimate for the DAG pattern of the BN underlying the data. The
          graph might contain some nodes with both-way edges (X->Y and Y->X).
          Any completion by (removing one of the both-way edges for each such
          pair) results in a I-equivalent Bayesian network DAG.
  
      References
      ----------
      Neapolitan, Learning Bayesian Networks, Section 10.1.2, Algorithm 10.2 (page 550)
      http://www.cs.technion.ac.il/~dang/books/Learning%20Bayesian%20Networks(Neapolitan,%20Richard).pdf
  
  
      Examples
      --------
      >>> import pandas as pd
      >>> import numpy as np
      >>> from pgmpy.estimators import PC
      >>> data = pd.DataFrame(np.random.randint(0, 4, size=(5000, 3)), columns=list('ABD'))
      >>> data['C'] = data['A'] - data['B']
      >>> data['D'] += data['A']
      >>> c = PC(data)
      >>> pdag = c.skeleton_to_pdag(*c.build_skeleton())
      >>> pdag.edges() # edges: A->C, B->C, A--D (not directed)
      [('B', 'C'), ('A', 'C'), ('A', 'D'), ('D', 'A')]
      """
  
      pdag = skeleton.to_directed()
      node_pairs = list(permutations(pdag.nodes(), 2))
  
      # 1) for each X-Z-Y, if Z not in the separating set of X,Y, then orient edges as X->Z<-Y
      # (Algorithm 3.4 in Koller & Friedman PGM, page 86)
      for pair in node_pairs:
          X, Y = pair
          if not skeleton.has_edge(X, Y):
              for Z in set(skeleton.neighbors(X)) & set(
                  skeleton.neighbors(Y)
              ):
                  if Z not in separating_sets[frozenset((X, Y))]:
                      pdag.remove_edges_from([(Z, X), (Z, Y)])
  
      progress = True
      while progress:  # as long as edges can be oriented (removed)
          num_edges = pdag.number_of_edges()
  
          # 2) for each X->Z-Y, orient edges to Z->Y
          # (Explanation in Koller & Friedman PGM, page 88)
          for pair in node_pairs:
              X, Y = pair
              if not pdag.has_edge(X, Y):
                  for Z in (
                      set(pdag.successors(X))
                      - set(pdag.predecessors(X))
                  ) & (
                      set(pdag.successors(Y))
                      & set(pdag.predecessors(Y))
                  ):
                      pdag.remove_edge(Y, Z)
  
          # 3) for each X-Y with a directed path from X to Y, orient edges to X->Y
          for pair in node_pairs:
              X, Y = pair
              if pdag.has_edge(Y, X) and pdag.has_edge(X, Y):
                  for path in nx.all_simple_paths(pdag, X, Y):
                      is_directed = True
                      for src, dst in list(zip(path, path[1:])):
                          if pdag.has_edge(dst, src):
                              is_directed = False
                      if is_directed:
                          pdag.remove_edge(Y, X)
                          break
  
          # 4) for each X-Z-Y with X->W, Y->W, and Z-W, orient edges to Z->W
          for pair in node_pairs:
              X, Y = pair
              for Z in (
                  set(pdag.successors(X))
                  & set(pdag.predecessors(X))
                  & set(pdag.successors(Y))
                  & set(pdag.predecessors(Y))
              ):
                  for W in (
                      (
                          set(pdag.successors(X))
                          - set(pdag.predecessors(X))
                      )
                      & (
                          set(pdag.successors(Y))
                          - set(pdag.predecessors(Y))
                      )
                      & (
                          set(pdag.successors(Z))
                          & set(pdag.predecessors(Z))
                      )
                  ):
                      pdag.remove_edge(W, Z)
  
          progress = num_edges > pdag.number_of_edges()
  
      # TODO: This is temp fix to get a PDAG object.
      edges = set(pdag.edges())
      undirected_edges = []
      directed_edges = []
      for u, v in edges:
          if (v, u) in edges:
              undirected_edges.append((u, v))
          else:
              directed_edges.append((u, v))
      return PDAG(
          directed_ebunch=directed_edges,
          undirected_ebunch=undirected_edges,
      )
  
file_path: pgmpy/pgmpy/estimators/PC.py
imports: from itertools import chain, combinations, permutations
  import networkx
  from joblib import Parallel, delayed
  from tqdm.auto import tqdm
  from pgmpy import config
  from pgmpy.base import PDAG
  from pgmpy.estimators import StructureEstimator
  from pgmpy.estimators.CITests import *
  from pgmpy.global_vars import logger
label_desc: Use image node_id 4 for calling the PC obj's underlying member method code with example usage: obj.skeleton_to_pdag(skeleton, separating_sets) and returns: PDAG