// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/traversal/PdagShortestPath.java
// public class PdagShortestPath extends GraphShortestPath {
// 
//   private final Pdag pdag;
// 
//   protected PdagShortestPath(Pdag pdag, Node start, Node stop, ShortestPathListener listener) {
//     super(pdag, start, stop, listener);
//     this.pdag = pdag;
//   }
// 
//   public static boolean exists(Pdag graph, Node start, Node stop, ShortestPathListener listener) {
//     return (new PdagShortestPath(graph, start, stop, listener)).search();
//   }
// 
//   private boolean search() {
//     if (null != listener) {
//       listener.pre(graph, start, stop);
//     }
// 
//     if (start.equals(stop)) {
//       if (null != listener) {
//         listener.post(graph, start, stop);
//       }
//       return false;
//     }
// 
//     boolean result = search(start);
// 
//     if (null != listener) {
//       listener.post(graph, start, stop);
//     }
// 
//     return result;
//   }
// 
//   private boolean search(Node node) {
//     if (null != listener) {
//       listener.visited(node);
//     }
// 
//     Set<Node> outNodes = outNodes(node);
//     if (outNodes.contains(stop)) {
//       return true;
//     } else {
//       seen.add(node);
//       for (Node outNode : outNodes) {
//         if (!seen.contains(outNode)) {
//           if (search(outNode)) {
//             return true;
//           }
//         }
//       }
//     }
// 
//     return false;
//   }
// 
//   private Set<Node> outNodes(Node node) {
//     Set<Node> outNodes = new HashSet<>();
//     outNodes.addAll(pdag.neighbors(node));
//     outNodes.removeAll(pdag.parents(node));
//     return outNodes;
//   }
// }


import com.github.vangj.jbayes.inf.exact.graph.traversal.PdagShortestPath;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
package com.github.vangj.jbayes.inf.exact.graph;


/**
 * A partially directed acyclic graph (PDAG). "A PDAG is a graph where some edges are directed and
 * some are undirected and one cannot trace a cycle by following the direction of directed edges and
 * any direction for undirected edges."
 * <ul>
 *   <li>Quote above taken directly from http://jmlr.csail.mit.edu/papers/volume8/kalisch07a/kalisch07a.pdf</li>
 * </ul>
 */
public class Pdag extends Graph {

  protected Map<String, List<Node>> parents;
  protected Map<String, List<Node>> children;

  public Pdag() {
    parents = new HashMap<>();
    children = new HashMap<>();
  }

  @Override
  protected Graph instance() {
    return new Pdag();
  }

  @Override
  public Graph addEdge(Edge edge) {
    if (Edge.Type.UNDIRECTED == edge.type) {
      super.addEdge(edge);
    } else {
// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/traversal/PdagShortestPath.java
// public class PdagShortestPath extends GraphShortestPath {
// 
//   private final Pdag pdag;
// 
//   protected PdagShortestPath(Pdag pdag, Node start, Node stop, ShortestPathListener listener) {
//     super(pdag, start, stop, listener);
//     this.pdag = pdag;
//   }
// 
//   public static boolean exists(Pdag graph, Node start, Node stop, ShortestPathListener listener) {
//     return (new PdagShortestPath(graph, start, stop, listener)).search();
//   }
// 
//   private boolean search() {
//     if (null != listener) {
//       listener.pre(graph, start, stop);
//     }
// 
//     if (start.equals(stop)) {
//       if (null != listener) {
//         listener.post(graph, start, stop);
//       }
//       return false;
//     }
// 
//     boolean result = search(start);
// 
//     if (null != listener) {
//       listener.post(graph, start, stop);
//     }
// 
//     return result;
//   }
// 
//   private boolean search(Node node) {
//     if (null != listener) {
//       listener.visited(node);
//     }
// 
//     Set<Node> outNodes = outNodes(node);
//     if (outNodes.contains(stop)) {
//       return true;
//     } else {
//       seen.add(node);
//       for (Node outNode : outNodes) {
//         if (!seen.contains(outNode)) {
//           if (search(outNode)) {
//             return true;
//           }
//         }
//       }
//     }
// 
//     return false;
//   }
// 
//   private Set<Node> outNodes(Node node) {
//     Set<Node> outNodes = new HashSet<>();
//     outNodes.addAll(pdag.neighbors(node));
//     outNodes.removeAll(pdag.parents(node));
//     return outNodes;
//   }
// }


// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/Pdag.java
import com.github.vangj.jbayes.inf.exact.graph.traversal.PdagShortestPath;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

package com.github.vangj.jbayes.inf.exact.graph;


/**
 * A partially directed acyclic graph (PDAG). "A PDAG is a graph where some edges are directed and
 * some are undirected and one cannot trace a cycle by following the direction of directed edges and
 * any direction for undirected edges."
 * <ul>
 *   <li>Quote above taken directly from http://jmlr.csail.mit.edu/papers/volume8/kalisch07a/kalisch07a.pdf</li>
 * </ul>
 */
public class Pdag extends Graph {

  protected Map<String, List<Node>> parents;
  protected Map<String, List<Node>> children;

  public Pdag() {
    parents = new HashMap<>();
    children = new HashMap<>();
  }

  @Override
  protected Graph instance() {
    return new Pdag();
  }

  @Override
  public Graph addEdge(Edge edge) {
    if (Edge.Type.UNDIRECTED == edge.type) {
      super.addEdge(edge);
    } else {
      if (PdagShortestPath.exists(this, edge.right, edge.left, null)) {