Patch for adding induced graph method

gsoc.patch

From 3be7292b35e5a7141b46b6536bd4a5bec39cf47c Mon Sep 17 00:00:00 2001
From: Pratyaksh <pratyaksh@me.com>
Date: Sun, 15 Mar 2015 00:50:12 +0530
Subject: [PATCH 1/2] Fixed typo in README

---
 README.md | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/README.md b/README.md
index 6faa61d..6a81b75 100644
--- a/README.md
+++ b/README.md
@@ -45,7 +45,7 @@ Example:
 ```python3
 from pgmpy.models import BayesianModel
 from pgmpy.factors import TabularCPD
-student = bm.BayesianModel()
+student = BayesianModel()
 # instantiates a new Bayesian Model called 'student'
 
 student.add_nodes_from(['diff', 'intel', 'grade'])
-- 
2.1.0


From d5f215171244add3af0e453942567e84a032e3db Mon Sep 17 00:00:00 2001
From: Pratyaksh <pratyaksh@me.com>
Date: Sun, 15 Mar 2015 12:46:25 +0530
Subject: [PATCH 2/2] Added method to compute induced graph

---
 README.md                         |  2 +-
 pgmpy/inference/ExactInference.py | 44 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 44 insertions(+), 2 deletions(-)

diff --git a/README.md b/README.md
index 6a81b75..94287fd 100644
--- a/README.md
+++ b/README.md
@@ -110,7 +110,7 @@ student.add_cpds(diff_cpd, intel_cpd, grade_cpd)
 student.active_trail_nodes('diff')
 
 # Finding active trail with observation
-student.active_trail_nodes('diff', observed='grades')
+student.active_trail_nodes('diff', observed='grade')
 ```
 
 
diff --git a/pgmpy/inference/ExactInference.py b/pgmpy/inference/ExactInference.py
index 130a657..1d8c1c1 100644
--- a/pgmpy/inference/ExactInference.py
+++ b/pgmpy/inference/ExactInference.py
@@ -3,7 +3,7 @@
 import numpy as np
 from pgmpy.inference import Inference
 from pgmpy.factors.Factor import factor_product
-
+import networkx as nx
 
 class VariableElimination(Inference):
     def _variable_elimination(self, variables, operation, evidence=None, elimination_order=None):
@@ -229,6 +229,48 @@ class VariableElimination(Inference):
         <networkx.classes.graph.Graph at 0x7f34ac8c5160>
         """
 
+        eliminated_variables = set()
+        working_factors = {node: {factor for factor in self.factors[node]}
+                           for node in self.factors}
+
+        # The set of cliques should be in the induced graph
+        cliques = set()
+        for factors in working_factors.values():
+            for factor in factors:
+                cliques.add(tuple(factor.scope()))
+
+        # If the elimination_order list is incomplete, raise an error
+        if len(elimination_order) < len(self.variables):
+            raise ValueError("Elimination order incomplete")
+
+
+        for var in elimination_order:
+            # Removing all the factors containing the variables which are
+            # eliminated (as all the factors should be considered only once)
+            factors = [factor for factor in working_factors[var]
+                       if not set(factor.variables).intersection(eliminated_variables)]
+            phi = factor_product(*factors)
+            phi.reduce(var+'_0')
+            cliques.add(tuple(phi.scope()))
+            del working_factors[var]
+            for variable in phi.variables:
+                working_factors[variable].add(phi)
+            eliminated_variables.add(var)
+
+        edges = []
+        # add edges corresponding to each clique
+        for clique in cliques:
+            if len(clique) > 1:
+                for i in range(len(clique)):
+                    for j in range(i+1, len(clique)):
+                        edges.append((clique[i], clique[j]))
+
+        # Final induced graph
+        graph = nx.Graph()
+        graph.add_nodes_from(elimination_order)
+        graph.add_edges_from(edges)
+        return graph
+
 class BeliefPropagation(Inference):
     """
     Class for performing inference using Belief Propagation method.
-- 
2.1.0