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.)
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.
If you have not already completed the last question of Practical 03, please do it now.
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.
Last modified: Wed Nov 17 17:30:13 GMT 2010