// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/Node.java
// public class Node extends Variable {
// 
//   private final List<Double> probs;
//   private List<String> valueList;
//   private Potential potential;
//   private Map<String, Object> metadata;
// 
//   public Node() {
//     probs = new ArrayList<>();
//   }
// 
//   public Node(Variable v) {
//     probs = new ArrayList<>();
//     metadata = new HashMap<>();
//     this.id = v.id;
//     this.name = v.name;
//     this.values = v.values;
//     this.valueList = this.values.stream()
//         .collect(Collectors.toList());
//   }
// 
//   private Node(NodeBuilder builder) {
//     id = builder.id;
//     metadata = new HashMap<>();
//     name = builder.name;
//     values = builder.values;
//     probs = builder.probs;
//     this.valueList = this.values.stream()
//         .collect(Collectors.toList());
//   }
// 
//   public static NodeBuilder builder() {
//     return new NodeBuilder();
//   }
// 
//   /**
//    * Adds any metadata.
//    *
//    * @param k Key.
//    * @param v Value.
//    */
//   public void addMetadata(String k, Object v) {
//     metadata.put(k, v);
//   }
// 
//   /**
//    * Gets the metadata associated with the specified key.
//    *
//    * @param k Key.
//    * @return Value.
//    */
//   public Object getMetadata(String k) {
//     return metadata.get(k);
//   }
// 
//   public Potential getPotential() {
//     return potential;
//   }
// 
//   public void setPotential(Potential potential) {
//     this.potential = potential;
//   }
// 
//   public Node addProb(Double prob) {
//     probs.add(prob);
//     return this;
//   }
// 
//   public int weight() {
//     return values.size();
//   }
// 
//   public List<Double> probs() {
//     return probs;
//   }
// 
//   public List<String> getValueList() {
//     return valueList;
//   }
// 
//   public static final class NodeBuilder {
// 
//     private String id;
//     private String name;
//     private Set<String> values;
//     private List<Double> probs;
// 
//     private NodeBuilder() {
//       values = new LinkedHashSet<>();
//       probs = new ArrayList<>();
//     }
// 
//     public NodeBuilder from(Variable v) {
//       this.id = v.id;
//       this.name = v.name;
//       this.values = v.values;
//       return this;
//     }
// 
//     public NodeBuilder id(String val) {
//       id = val;
//       return this;
//     }
// 
//     public NodeBuilder name(String val) {
//       name = val;
//       return this;
//     }
// 
//     public NodeBuilder value(String val) {
//       values.add(val);
//       return this;
//     }
// 
//     public NodeBuilder values(Set<String> val) {
//       values = val;
//       return this;
//     }
// 
//     public NodeBuilder probs(List<Double> probs) {
//       this.probs = probs;
//       return this;
//     }
// 
//     public NodeBuilder prob(Double prob) {
//       this.probs.add(prob);
//       return this;
//     }
// 
//     public Node build() {
//       return new Node(this);
//     }
//   }
// }
// 
// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/Pdag.java
// 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)) {
//         //if right -> -- -> -- left path exists
//         //then adding left -> right will form cycle
//         //do not add it!
//         return this;
//       }
// 
//       super.addEdge(edge);
// 
//       Node n1 = edge.left;
//       Node n2 = edge.right;
// 
//       List<Node> parents = parents(n2);
//       if (!parents.contains(n1)) {
//         parents.add(n1);
//       }
// 
//       List<Node> children = children(n1);
//       if (!children.contains(n2)) {
//         children.add(n2);
//       }
//     }
// 
//     return this;
//   }
// 
//   public List<Node> parents(Node node) {
//     List<Node> parents = this.parents.get(node.id);
//     if (null == parents) {
//       parents = new ArrayList<>();
//       this.parents.put(node.id, parents);
//     }
//     return parents;
//   }
// 
//   public List<Node> children(Node node) {
//     List<Node> children = this.children.get(node.id);
//     if (null == children) {
//       children = new ArrayList<>();
//       this.children.put(node.id, children);
//     }
//     return children;
//   }
// }


import com.github.vangj.jbayes.inf.exact.graph.Node;
import com.github.vangj.jbayes.inf.exact.graph.Pdag;
import java.util.HashSet;
import java.util.Set;
package com.github.vangj.jbayes.inf.exact.graph.traversal;


public class PdagShortestPath extends GraphShortestPath {

  private final Pdag pdag;

// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/Node.java
// public class Node extends Variable {
// 
//   private final List<Double> probs;
//   private List<String> valueList;
//   private Potential potential;
//   private Map<String, Object> metadata;
// 
//   public Node() {
//     probs = new ArrayList<>();
//   }
// 
//   public Node(Variable v) {
//     probs = new ArrayList<>();
//     metadata = new HashMap<>();
//     this.id = v.id;
//     this.name = v.name;
//     this.values = v.values;
//     this.valueList = this.values.stream()
//         .collect(Collectors.toList());
//   }
// 
//   private Node(NodeBuilder builder) {
//     id = builder.id;
//     metadata = new HashMap<>();
//     name = builder.name;
//     values = builder.values;
//     probs = builder.probs;
//     this.valueList = this.values.stream()
//         .collect(Collectors.toList());
//   }
// 
//   public static NodeBuilder builder() {
//     return new NodeBuilder();
//   }
// 
//   /**
//    * Adds any metadata.
//    *
//    * @param k Key.
//    * @param v Value.
//    */
//   public void addMetadata(String k, Object v) {
//     metadata.put(k, v);
//   }
// 
//   /**
//    * Gets the metadata associated with the specified key.
//    *
//    * @param k Key.
//    * @return Value.
//    */
//   public Object getMetadata(String k) {
//     return metadata.get(k);
//   }
// 
//   public Potential getPotential() {
//     return potential;
//   }
// 
//   public void setPotential(Potential potential) {
//     this.potential = potential;
//   }
// 
//   public Node addProb(Double prob) {
//     probs.add(prob);
//     return this;
//   }
// 
//   public int weight() {
//     return values.size();
//   }
// 
//   public List<Double> probs() {
//     return probs;
//   }
// 
//   public List<String> getValueList() {
//     return valueList;
//   }
// 
//   public static final class NodeBuilder {
// 
//     private String id;
//     private String name;
//     private Set<String> values;
//     private List<Double> probs;
// 
//     private NodeBuilder() {
//       values = new LinkedHashSet<>();
//       probs = new ArrayList<>();
//     }
// 
//     public NodeBuilder from(Variable v) {
//       this.id = v.id;
//       this.name = v.name;
//       this.values = v.values;
//       return this;
//     }
// 
//     public NodeBuilder id(String val) {
//       id = val;
//       return this;
//     }
// 
//     public NodeBuilder name(String val) {
//       name = val;
//       return this;
//     }
// 
//     public NodeBuilder value(String val) {
//       values.add(val);
//       return this;
//     }
// 
//     public NodeBuilder values(Set<String> val) {
//       values = val;
//       return this;
//     }
// 
//     public NodeBuilder probs(List<Double> probs) {
//       this.probs = probs;
//       return this;
//     }
// 
//     public NodeBuilder prob(Double prob) {
//       this.probs.add(prob);
//       return this;
//     }
// 
//     public Node build() {
//       return new Node(this);
//     }
//   }
// }
// 
// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/Pdag.java
// 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)) {
//         //if right -> -- -> -- left path exists
//         //then adding left -> right will form cycle
//         //do not add it!
//         return this;
//       }
// 
//       super.addEdge(edge);
// 
//       Node n1 = edge.left;
//       Node n2 = edge.right;
// 
//       List<Node> parents = parents(n2);
//       if (!parents.contains(n1)) {
//         parents.add(n1);
//       }
// 
//       List<Node> children = children(n1);
//       if (!children.contains(n2)) {
//         children.add(n2);
//       }
//     }
// 
//     return this;
//   }
// 
//   public List<Node> parents(Node node) {
//     List<Node> parents = this.parents.get(node.id);
//     if (null == parents) {
//       parents = new ArrayList<>();
//       this.parents.put(node.id, parents);
//     }
//     return parents;
//   }
// 
//   public List<Node> children(Node node) {
//     List<Node> children = this.children.get(node.id);
//     if (null == children) {
//       children = new ArrayList<>();
//       this.children.put(node.id, children);
//     }
//     return children;
//   }
// }


// Path: src/main/java/com/github/vangj/jbayes/inf/exact/graph/traversal/PdagShortestPath.java
import com.github.vangj.jbayes.inf.exact.graph.Node;
import com.github.vangj.jbayes.inf.exact.graph.Pdag;
import java.util.HashSet;
import java.util.Set;

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


public class PdagShortestPath extends GraphShortestPath {

  private final Pdag pdag;

  protected PdagShortestPath(Pdag pdag, Node start, Node stop, ShortestPathListener listener) {