Description

5/5 - (2 votes)

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:

 

  1. 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

 

 

 

 

 

  1. 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.