Problem 1. (Independence Queries)
Your goal is to implement a variant of the Bayes-Ball algorithm for answering conditional indepen-dence queries.
Inputs
Your program needs to accept 2 input les: the graph structure (graph.txt) and the conditional
independence queries (queries.txt).
Input Format:
The graph structure (graph.txt): Given a Graph with nodes numbered 1 to K. The rst line contains the integer K, followed by a list of edges (one on each line). Each edge is denoted by a space-separated pair of integers a and b which represents an edge directed from node a to node b.
Example le for the graph shown in Fig. 1:
4
1 2
2 3
2 4
3 4
1 4
Figure 1: Example Bayesian network
The conditional independence queries (queries.txt): Each line in this le represents a query
of the from (X ? Y jZ). Each line consists of three space-separated sets for X, Y , and Z. Each set is denoted by a comma-separated list of integers inside braces, e.g., fa1; a2; : : : ; akg. An empty set is denoted by fg.
Example le:
{1} {2} {} {1} {3} {2} {1} {3} {2,4}
This le represents the following queries:
{ (f1g ? f2gj;) { (f1g ? f3gjf2g)
{ (f1g ? f3gjf2; 4g)
Output:
Your program should print out a single integer value for each query. Print out a 1 if the graph satis es the conditional independence query, 0 otherwise. Example output:
0
1
0
Code Skeleton
The skeleton code is provided below with helper functions to create the graph and read queries. The code for printing the output in the required format is also provided. You are only required to complete the is independent function which takes in the graph and sets X, Y, and Z, and returns True if X ? Y jZ and False otherwise. Please do not modify other parts of the code skeleton. Before you begin coding, do not forget to enter your names and matric numbers in the le's header.
Submission Format
Submit only the python (.py) le renamed to YourMatricNumber-PartnerMatricNumber.py on IVLE. If your matric number is A0174067B and your partner's is A0175067A, then the le should be named A0174067B-A0175067A.py. If you're doing the assignment as an individual, name it as YourMatricNumber.py. Submit only one python le per group.
45
46
47
48
49
50
51
52
53
"""Checks if X is conditionally indepedent of Y given Z.
Args:
graph (dict): the Bayesian network
X (list): list of nodes in set X
Y (list): list of nodes in set Y
Z (list): list of nodes in set Z
Returns:
bool: True if X is conditionally indepedent of Y given Z, False otherwise. """
# TODO
return True
if __name__ == __main__ :
graph = create_graph()
Qs = read_queries()
for X, Y, Z in Qs:
output = 1 if is_independent(graph, X, Y, Z) else 0
print(output)
4
