JunctionTreeBuilder { public JunctionTree junctionTree(List<OpenBitSet> cliques, boolean init) { return junctionTree(null, null, null, cliques, init); } JunctionTreeBuilder(Graph<BayesVariable> graph); Graph<BayesVariable> getGraph(); JunctionTree build(); JunctionTree build(boolean init); JunctionTree build(Resource resource, String namespace, String name); JunctionTree build(Resource resource, String namespace, String name, boolean init); void moralize(); void moralize(GraphNode<BayesVariable> v, GraphNode v1); static void connect(boolean[][] adjMatrix, int v1, int v2); static void disconnect(boolean[][] adjMatrix, int v1, int v2); List<OpenBitSet> triangulate(); void eliminateVertex(PriorityQueue<EliminationCandidate> p, Map<Integer, EliminationCandidate> elmVertMap, boolean[][] clonedAdjMatrix, boolean[] adjList, Set<Integer> verticesToUpdate, EliminationCandidate v); void createClique(int v, boolean[][] clonedAdjMatrix, Set<Integer> verticesToUpdate, boolean[] adjList); static void updateCliques(List<OpenBitSet> cliques, OpenBitSet newClique); boolean[][] getAdjacencyMatrix(); static boolean[][] cloneAdjacencyMarix(boolean[][] src); JunctionTree junctionTree(List<OpenBitSet> cliques, boolean init); JunctionTree junctionTree(Resource resource, String namespace, String name, List<OpenBitSet> cliques, boolean init); void mergeGraphs(SeparatorSet[][][] graphs, SeparatorSet separatorSet); int createJunctionTreeGraph(SeparatorSet[][] sepGraph, JunctionTreeClique parent, JunctionTreeClique[] jtNodes, JunctionTreeSeparator[] jtSeps, int i); void mapNodeToCliqueFamily(OpenBitSet[] varNodeToCliques, JunctionTreeClique[] jtNodes); void mapVarNodeToCliques(OpenBitSet[] nodeToCliques, int id, OpenBitSet clique); static List<Integer> getAdjacentVertices(boolean[][] adjacencyMatrix, int i);  }
@Test public void testJunctionTree() { Graph<BayesVariable> graph = new BayesNetwork(); GraphNode x0 = addNode(graph); GraphNode x1 = addNode(graph); GraphNode x2 = addNode(graph); GraphNode x3 = addNode(graph); GraphNode x4 = addNode(graph); GraphNode x5 = addNode(graph); GraphNode x6 = addNode(graph); OpenBitSet OpenBitSet1 = bitSet("00001110"); OpenBitSet OpenBitSet2 = bitSet("00011100"); OpenBitSet OpenBitSet3 = bitSet("00110000"); OpenBitSet OpenBitSet4 = bitSet("01110000"); List<OpenBitSet> cliques = new ArrayList<OpenBitSet>(); cliques.add ( OpenBitSet1 ); cliques.add ( OpenBitSet2 ); cliques.add ( OpenBitSet3 ); cliques.add ( OpenBitSet4 ); List<SeparatorSet> separatorSets = new ArrayList<SeparatorSet>(); for ( int i = 0; i < cliques.size(); i++ ) { OpenBitSet ci = cliques.get(i); for ( int j = i+1; j < cliques.size(); j++ ) { OpenBitSet cj = cliques.get(j); if ( ci.intersects( cj ) ) { SeparatorSet separatorSet = new SeparatorSet( ci, 0, cj, 0, graph ); } } } Collections.sort(separatorSets); }
@Test public void testJunctionTreeNoPruning() { Graph<BayesVariable> graph = new BayesNetwork(); GraphNode x0 = addNode(graph); GraphNode x1 = addNode(graph); GraphNode x2 = addNode(graph); GraphNode x3 = addNode(graph); GraphNode x4 = addNode(graph); GraphNode x5 = addNode(graph); GraphNode x6 = addNode(graph); GraphNode x7 = addNode(graph); List<OpenBitSet> list = new ArrayList<OpenBitSet>(); OpenBitSet OpenBitSet1 = bitSet("00001111"); OpenBitSet OpenBitSet2 = bitSet("00111100"); OpenBitSet OpenBitSet3 = bitSet("11100000"); OpenBitSet intersect1And2 = ((OpenBitSet)OpenBitSet2.clone()); intersect1And2.and(OpenBitSet1); OpenBitSet intersect2And3 = ((OpenBitSet)OpenBitSet2.clone()); intersect2And3.and(OpenBitSet3); list.add(OpenBitSet1); list.add(OpenBitSet2); list.add(OpenBitSet3); JunctionTreeBuilder jtBuilder = new JunctionTreeBuilder( graph ); JunctionTreeClique jtNode = jtBuilder.junctionTree(list, false).getRoot(); assertEquals( OpenBitSet1, jtNode.getBitSet() ); assertEquals( 1, jtNode.getChildren().size() ); JunctionTreeSeparator sep = jtNode.getChildren().get(0); assertEquals( OpenBitSet1, sep.getParent().getBitSet() ); assertEquals( OpenBitSet2, sep.getChild().getBitSet() ); assertEquals( intersect1And2, sep.getBitSet() ); jtNode = sep.getChild(); assertEquals( OpenBitSet2, jtNode.getBitSet() ); assertEquals( 1, jtNode.getChildren().size() ); sep = jtNode.getChildren().get(0); assertEquals( OpenBitSet2, sep.getParent().getBitSet() ); assertEquals( OpenBitSet3, sep.getChild().getBitSet() ); assertEquals( intersect2And3, sep.getBitSet() ); }
@Test public void testJunctionWithPruning1() { Graph<BayesVariable> graph = new BayesNetwork(); GraphNode x0 = addNode(graph); GraphNode x1 = addNode(graph); GraphNode x2 = addNode(graph); GraphNode x3 = addNode(graph); GraphNode x4 = addNode(graph); GraphNode x5 = addNode(graph); GraphNode x6 = addNode(graph); GraphNode x7 = addNode(graph); List<OpenBitSet> list = new ArrayList<OpenBitSet>(); OpenBitSet OpenBitSet1 = bitSet("00001111"); OpenBitSet OpenBitSet2 = bitSet("00111100"); OpenBitSet OpenBitSet3 = bitSet("11100001"); OpenBitSet intersect1And2 = ((OpenBitSet)OpenBitSet2.clone()); intersect1And2.and(OpenBitSet1); OpenBitSet intersect2And3 = ((OpenBitSet)OpenBitSet2.clone()); intersect2And3.and(OpenBitSet3); list.add(OpenBitSet1); list.add(OpenBitSet2); list.add(OpenBitSet3); JunctionTreeBuilder jtBuilder = new JunctionTreeBuilder( graph ); JunctionTreeClique jtNode = jtBuilder.junctionTree(list, false).getRoot(); assertEquals( OpenBitSet1, jtNode.getBitSet() ); assertEquals( 2, jtNode.getChildren().size() ); JunctionTreeSeparator sep = jtNode.getChildren().get(0); assertEquals( OpenBitSet1, sep.getParent().getBitSet() ); assertEquals( OpenBitSet2, sep.getChild().getBitSet() ); assertEquals(0, sep.getChild().getChildren().size()); sep = jtNode.getChildren().get(1); assertEquals( OpenBitSet1, sep.getParent().getBitSet() ); assertEquals( OpenBitSet3, sep.getChild().getBitSet() ); assertEquals( 0, sep.getChild().getChildren().size() ); }
@Test public void testJunctionWithPruning2() { Graph<BayesVariable> graph = new BayesNetwork(); GraphNode x0 = addNode(graph); GraphNode x1 = addNode(graph); GraphNode x2 = addNode(graph); GraphNode x3 = addNode(graph); GraphNode x4 = addNode(graph); GraphNode x5 = addNode(graph); GraphNode x6 = addNode(graph); GraphNode x7 = addNode(graph); List<OpenBitSet> list = new ArrayList<OpenBitSet>(); OpenBitSet OpenBitSet1 = bitSet("00001111"); OpenBitSet OpenBitSet2 = bitSet("00111100"); OpenBitSet OpenBitSet3 = bitSet("11100000"); OpenBitSet OpenBitSet4 = bitSet("00100001"); OpenBitSet intersect1And2 = ((OpenBitSet)OpenBitSet2.clone()); intersect1And2.and(OpenBitSet1); OpenBitSet intersect2And3 = ((OpenBitSet)OpenBitSet2.clone()); intersect2And3.and(OpenBitSet3); OpenBitSet intersect1And4 = ((OpenBitSet)OpenBitSet1.clone()); intersect1And4.and(OpenBitSet4); list.add(OpenBitSet1); list.add(OpenBitSet2); list.add(OpenBitSet3); list.add(OpenBitSet4); JunctionTreeBuilder jtBuilder = new JunctionTreeBuilder( graph ); JunctionTreeClique jtNode = jtBuilder.junctionTree(list, false).getRoot(); JunctionTreeClique root = jtNode; assertEquals( OpenBitSet1, root.getBitSet() ); assertEquals( 2, root.getChildren().size() ); JunctionTreeSeparator sep = root.getChildren().get(0); assertEquals( OpenBitSet1, sep.getParent().getBitSet() ); assertEquals( OpenBitSet2, sep.getChild().getBitSet() ); assertEquals(1, sep.getChild().getChildren().size()); jtNode = sep.getChild(); assertEquals( OpenBitSet2, jtNode.getBitSet() ); assertEquals( 1, jtNode.getChildren().size() ); sep = jtNode.getChildren().get(0); assertEquals( OpenBitSet2, sep.getParent().getBitSet() ); assertEquals( OpenBitSet3, sep.getChild().getBitSet() ); assertEquals( intersect2And3, sep.getBitSet() ); assertEquals( 0, sep.getChild().getChildren().size()); sep = root.getChildren().get(1); assertEquals( OpenBitSet1, sep.getParent().getBitSet() ); assertEquals( OpenBitSet4, sep.getChild().getBitSet() ); assertEquals( intersect1And4, sep.getBitSet() ); assertEquals( 0, sep.getChild().getChildren().size() ); }
@Test public void testJunctionWithPruning3() { Graph<BayesVariable> graph = new BayesNetwork(); GraphNode x0 = addNode(graph); GraphNode x1 = addNode(graph); GraphNode x2 = addNode(graph); GraphNode x3 = addNode(graph); GraphNode x4 = addNode(graph); GraphNode x5 = addNode(graph); GraphNode x6 = addNode(graph); GraphNode x7 = addNode(graph); List<OpenBitSet> list = new ArrayList<OpenBitSet>(); OpenBitSet OpenBitSet1 = bitSet("00001111"); OpenBitSet OpenBitSet2 = bitSet("00011110"); OpenBitSet OpenBitSet3 = bitSet("11100000"); OpenBitSet OpenBitSet4 = bitSet("01100001"); OpenBitSet intersect1And2 = ((OpenBitSet)OpenBitSet2.clone()); intersect1And2.and(OpenBitSet1); OpenBitSet intersect2And3 = ((OpenBitSet)OpenBitSet2.clone()); intersect2And3.and(OpenBitSet3); OpenBitSet intersect1And4 = ((OpenBitSet)OpenBitSet1.clone()); intersect1And4.and(OpenBitSet4); OpenBitSet intersect3And4 = ((OpenBitSet)OpenBitSet3.clone()); intersect3And4.and(OpenBitSet4); list.add(OpenBitSet1); list.add(OpenBitSet2); list.add(OpenBitSet3); list.add(OpenBitSet4); JunctionTreeBuilder jtBuilder = new JunctionTreeBuilder( graph ); JunctionTreeClique jtNode = jtBuilder.junctionTree(list, false).getRoot();; JunctionTreeClique root = jtNode; assertEquals( OpenBitSet1, root.getBitSet() ); assertEquals( 2, root.getChildren().size() ); JunctionTreeSeparator sep = root.getChildren().get(0); assertEquals( OpenBitSet1, sep.getParent().getBitSet() ); assertEquals( OpenBitSet2, sep.getChild().getBitSet() ); assertEquals(0, sep.getChild().getChildren().size()); sep = root.getChildren().get(1); assertEquals( OpenBitSet1, sep.getParent().getBitSet() ); assertEquals( OpenBitSet4, sep.getChild().getBitSet() ); assertEquals( intersect1And4, sep.getBitSet() ); assertEquals( 1, sep.getChild().getChildren().size() ); jtNode = sep.getChild(); assertEquals( OpenBitSet4, jtNode.getBitSet() ); assertEquals( 1, jtNode.getChildren().size() ); sep = jtNode.getChildren().get(0); assertEquals( OpenBitSet4, sep.getParent().getBitSet() ); assertEquals( OpenBitSet3, sep.getChild().getBitSet() ); assertEquals( intersect3And4, sep.getBitSet() ); assertEquals( 0, sep.getChild().getChildren().size() ); }