Package edu.cmu.tetrad.search

Class FciOrientDijkstra

java.lang.Object
edu.cmu.tetrad.search.FciOrientDijkstra
public class FciOrientDijkstra extends Object
A simple implementation of Dijkstra's algorithm for finding the shortest path in a graph. We are modifying the algorithm to find paths for rules R5, R9, and R10 in FciOrient. We are also modifying the algorithm to stop when an end node is reached. (The end node may be left unspecified, in which case the algorithm will find the shortest path to all nodes in the graph.)

Weights should all be positive. We report distances as total weights along the shortest path from the start node to the y node. We report unreachable nodes as being a distance of Integer.MAX_VALUE. We assume the graph is undirected. An end nodes may be specified, in which case, once the end node is reached, we report all further nodes as being at a distance of Integer.MAX_VALUE.

Author:
josephramsey, chat.

  • Method Details

    • distances

      public static Map<Node,Integer> distances(FciOrientDijkstra.Graph graph, Node start, boolean uncovered, Map<Node,Node> predecessors)
      Finds shortest distances from a start node to all other nodes in a graph. Unreachable nodes are reported as being at a distance of Integer.MAX_VALUE. The graph is assumed to be undirected.
      Parameters:
      graph - The graph to search; should include only the relevant edge in the graph.
      start - The starting node.
      uncovered - Whether the path should be uncovered.
      predecessors - A map to store the predecessors of each node in the shortest path.
      Returns:
      A map of nodes to their shortest distances from the start node.

    • distances

      public static Map<Node,Integer> distances(FciOrientDijkstra.Graph graph, Node x, Node y, Map<Node,Node> predecessors, boolean uncovered)
      Finds shortest distances from a x node to all other nodes in a graph. Unreachable nodes are reported as being at a distance of Integer.MAX_VALUE. The graph is assumed to be undirected. An y node may be specified, in which case, once the y node is reached, all further nodes are reported as being at a distance of Integer.MAX_VALUE.
      Parameters:
      graph - The graph to search; should include only the relevant edge in the graph.
      x - The starting node.
      y - The ending node. Maybe be null. If not null, the algorithm will stop when this node is reached.
      predecessors - A map to store the predecessors of each node in the shortest path.
      uncovered - If true, the algorithm will not traverse edges y--z where an adjacency exists between predecessor(y) and z.
      Returns:
      A map of nodes to their shortest distances from the start node.

    • adjacent

      public static boolean adjacent(FciOrientDijkstra.Graph graph, Node currentVertex, Node predecessor)
      Checks whether a node is adjacent to another node in the graph.
      Parameters:
      graph - The graph to search.
      currentVertex - The node whose neighbors are being checked.
      predecessor - The node to check adjacency against.
      Returns:
      true if the nodes are adjacent, otherwise false.

    • getPath

      public static List<Node> getPath(Map<Node,Node> predecessors, Node start, Node end)
      Returns the shortest path from the start node to the end node. If no path is found, null is returned.
      Parameters:
      predecessors - A map of nodes to their predecessors in the shortest path.
      start - The start node.
      end - The end node.
      Returns:
      The shortest path from the start node to the end node.