# Algorithms for Graphical Models (AGM)

## Practical 04: Graphs and hypergraphs

1. Checking for redundancy
2. Classifying hypergraphs
3. Conditional independence in BNs
4. Triangulation

#### Checking for redundancy

A hyperedge in a hypergraph is redundant if it is contained within another hyperedge. A hypergraph is reduced if it contains no redundant hyperedges.

In this question, your job is to complete this Python program which checks for redundancy in hypergraphs, so that it produces this output when run like this: python red_hg.py hg_exs.txt. The file hgs_exs.txt is available. Do not use gPy. You're allowed to go for something simple and sub-optimal; the solution below is like this. (It's much quicker to check for redundancy (and much else) if one maintains a dual representation of a hypergraph, but this is rather complicated for now.)

Solution

#### Classifying hypergraphs

Recall that each hypergraph H has an associated graph: its 2-section H2. Two vertices in H2 are connected if they both occur in some hyperedge of H. The cliques of H2 make a hypergraph. Sometimes this hypergraph is H and sometimes not.

For example, if H = {{A,B,C},{A,C,D}}, then H2 has the following connections: A-B,A-C,B-C,A-D,C-D. The cliques of H2 are then {A,B,C} and {A,C,D}, exactly the hyperedges of H. In contrast, consider the hypergraph H' = {{A,B},{B,C},{A,C}}. H'2 has connections A-B, B-C, A-C, so H'2 has just one clique: {A,B,C}. The hypergraph H is said to be graphical whereas H' is not. Now here's the proper definition of a graphical hypergraph.

A hypergraph H is graphical if each clique of H2 is contained within some hyperedge in H. In this case, the clique hypergraph of H2 is exactly red(H), where red(H) is the reduced version of H produced by deleting redundant hyperedges.

Use gPy to write a program which decides whether hypergraphs are graphical or not. Your program should read in hypergraphs in the format of hgs_exs.txt. Do not use gPy's `is_graphical` method (which needs improving anyway), but use anything else you find useful. You will need to look at the gPy API documentation to find useful stuff.

#### Conditional independence in BNs

If you have not already completed the last question of Practical 03, please do it now.

#### Triangulation

Look at the description of the simpler of gPy's two triangulation methods for undirected graphs. Without peeking at my source write the appropriate Python code. Give your method a different name, so that when you are testing you can be sure that it is your code that is being used. Of course, have a look once you're happy with your own solution. Feel free to use any other gPy methods.

Pages 114-117 of Algorithms for Graphical Models discuss the drawbacks of using the simple triangulation method used here and describe a superior approach.