<jupyter_start><jupyter_text>Group 06 Contributors : <NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME>Special packages to download : future and networkxconda install networkx, future<jupyter_code>import networkx as nx
import numpy as np
import itertools
from past.builtins import xrange
from itertools import chain
import copy
class Node(object):
    """
    Node in a directed graph
    """
    def __init__(self, name=""):
        """
        Construct a new node, and initialize the list of parents and children.
        Each parent/child is represented by a (key, value) pair in dictionary, 
        where key is the parent/child's name, and value is an Node object.
        Args:
            name: a unique string identifier.
        """
        self.name = name
        self.parents = dict()
        self.children = dict()

    def add_parent(self, parent):
        """
        Args:
            parent: an Node object.
        """
        if not isinstance(parent, Node):
            raise ValueError("Parent must be an instance of Node class.")
        pname = parent.name
        self.parents[pname] = parent

    def add_child(self, child):
        """
        Args:
            child: an Node object.
        """
        if not isinstance(child, Node):
            raise ValueError("Parent must be an instance of Node class.")
        cname = child.name
        self.children[cname] = child


class BN(object):
    """
    Bayesian Network
    """
    def __init__(self):
        """
        Initialize the list of nodes in the graph.
        Each node is represented by a (key, value) pair in dictionary, 
        where key is the node's name, and value is an Node object
        """
        self.nodes = dict()

    def add_edge(self, edge):
        """
        Add a directed edge to the graph.
        
        Args:
            edge: a tuple (A, B) representing a directed edge A-->B,
                where A, B are two strings representing the nodes' names
        """
        (pname, cname) = edge

        ## construct a new node if it doesn't exist
        if pname not in self.nodes:
            self.nodes[pname] = Node(name=pname)
        if cname not in self.nodes:
            self.nodes[cname] = Node(name=cname)

        ## add edge
        parent = self.nodes.get(pname)
        child = self.nodes.get(cname) 
        parent.add_child(child)
        child.add_parent(parent)

    def print_graph(self):
        """
        Visualize the current graph.
        """
        print("Bayes Network:")
        for nname, node in self.nodes.iteritems():
            print("\tNode " + nname)
            print("\t\tParents: " + str(node.parents.keys()))
            print("\t\tChildren: " + str(node.children.keys()))

    def find_obs_anc(self, observed):
        """
        Traverse the graph, find all nodes that have observed descendants.
        Args:
            observed: a list of strings, names of the observed nodes. 
        Returns:
            a list of strings for the nodes' names for all nodes 
            with observed descendants.
        """
        visit_nodes = copy.copy(observed) ## nodes to visit
        obs_anc = set() ## observed nodes and their ancestors

        ## repeatedly visit the nodes' parents
        while len(visit_nodes) > 0:
            next_node = self.nodes[visit_nodes.pop()]
            ## add its' parents
            for parent in next_node.parents:
                obs_anc.add(parent)

        return obs_anc

    def is_dsep(self, start, end, observed):
        """
        Check whether start and end are d-separated given observed.
        This algorithm mainly follows the "Reachable" procedure in 
        Koller and Friedman (2009), 
        "Probabilistic Graphical Models: Principles and Techniques", page 75.
        Args:
            start: a string, name of the first query node
            end: a string, name of the second query node
            observed: a list of strings, names of the observed nodes. 
        """

        ## all nodes having observed descendants.
        obs_anc = self.find_obs_anc(observed)

        ## Try all active paths starting from the node "start".
        ## If any of the paths reaches the node "end", 
        ## then "start" and "end" are *not* d-separated.
        ## In order to deal with v-structures, 
        ## we need to keep track of the direction of traversal:
        ## "up" if traveled from child to parent, and "down" otherwise.
        via_nodes = [(start, "up")]
        visited = set() ## keep track of visited nodes to avoid cyclic paths

        while len(via_nodes) > 0: 
            (nname, direction) = via_nodes.pop()
            node = self.nodes[nname]

            ## skip visited nodes
            if (nname, direction) not in visited:
                visited.add((nname, direction)) 

                ## if reaches the node "end", then it is not d-separated
                if nname not in observed and nname == end:
                    return False

                ## if traversing from children, then it won't be a v-structure
                ## the path is active as long as the current node is unobserved
                if direction == "up" and nname not in observed:
                    for parent in node.parents:
                        via_nodes.append((parent, "up"))
                    for child in node.children:
                        via_nodes.append((child, "down"))
                ## if traversing from parents, then need to check v-structure
                elif direction == "down":
                    ## path to children is always active
                    if nname not in observed: 
                        for child in node.children:
                            via_nodes.append((child, "down"))
                    ## path to parent forms a v-structure
                    if nname in observed or nname in obs_anc: 
                        for parent in node.parents:
                            via_nodes.append((parent, "up"))
        return True

def Z_subsets_disjoint_X_Y(myBN, X, Y): 
    """
    Find all Z subsets that are disjoint with X and Y .
    Returns:
        a list of subsets
    """
    a = list(range(len(myBN.nodes)))
    Z_subsets = []
    Z_subsets.append(a)
    for i in xrange(2,len(a)+1):
        Z_subsets.append(list(itertools.combinations(a,i)))
    # flatten the list
    Z_subsets = [item for sublist in Z_subsets for item in sublist]
    # filter Z_subsets by keeping only disjoint Z subsets with X and Y
    Z_subsets_disj = [subset for subset in Z_subsets if set([X]).isdisjoint(set([subset])) and set([Y]).isdisjoint(set([subset]))]
    
    return Z_subsets_disj     

def find_backdoor_sets(adj, X, Y): 
    """
    Find backdoor sets for P(Y |do(X)), given an adjacency matrix, X and Y
    Returns:
        backdoor sets
    """
    # Create a graph given adjacency matrix
    G =nx.from_numpy_matrix(adj)
    edges = list(G.edges)
    myBN = BN()
    for edge in edges:
        myBN.add_edge(edge)

    
    # draw all possible Z subsets, such that disjoint with X and Y
    Z = Z_subsets_disjoint_X_Y(myBN, X, Y)

    # add node I parent of X
    I = len(myBN.nodes) 
    myBN.add_edge((I,X))

    # find backdoor sets
    backdoor_sets = []
    for subset in Z:

        XZ = list(chain(*(i if isinstance(i, tuple) else (i,) for i in [X,subset])))
        # Check if Y d-sep I|X,Z
        if myBN.is_dsep(Y, I, XZ): 
            # Check also if Z d-sep I
            if isinstance(subset, int):
                if myBN.is_dsep(subset, I, []):
                    backdoor_sets.append(subset)
            else :
                backdoor_bool = True
                for elem in subset:
                    if not myBN.is_dsep(elem, I, []):
                        backdoor_bool = False
                if backdoor_bool:
                    backdoor_sets.append(subset)
    return backdoor_sets<jupyter_output><empty_output><jupyter_text>Execution:<jupyter_code>adj = np.matrix([[0, 1, 0, 1, 1, 0],
       [0, 0, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0]])
X = 2
Y = 4

backdoor_sets = find_backdoor_sets(adj, X, Y)

print('The backdoor sets for P(Y |do(X)), according to the given DAG: \n\n', backdoor_sets)<jupyter_output>The backdoor sets for P(Y |do(X)), according to the given DAG: 

 [1, (0, 1)]
{'fraction_non_alphanumeric': 0.09657803743889352, 'fraction_numerical': 0.0063193036842732805, 'mean_word_length': 1.8647540983606556, 'pattern_counts': {'":': 1, '<': 14, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '286303', 'license': 'MIT', 'n_tokens_mistral': 2492, 'n_tokens_neox': 2356, 'n_words': 861, 'path': 'Assignement 2/Hw2_ex2.ipynb', 'repo_name': 'sebemery/Network-Analytics-MGT-416', 'size': '8434'}