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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	FciOrientDijkstra.DijkstraEdge	Represents a node in Dijkstra's algorithm.
static class	FciOrientDijkstra.Graph	Represents a graph for Dijkstra's algorithm.

Method Summary

Modifier and Type	Method	Description
static Map<Node,Integer>	distances(FciOrientDijkstra.Graph graph, Node x, Node y, Map<Node,Node> predecessors, boolean uncovered, boolean potentiallyDirected)	Finds shortest distances from a x node to all other nodes in a graph.
static Map<Node,Integer>	distances(FciOrientDijkstra.Graph graph, Node start, Map<Node,Node> predecessors)	Finds shortest distances from a start node to all other nodes in a graph.
static List<Node>	getPath(Map<Node,Node> predecessors, Node start, Node end)	Returns the shortest path from the start node to the end node.
static void	main(String[] args)	A simple test of the Dijkstra algorithm.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

distances

public static Map<Node,Integer> distances(FciOrientDijkstra.Graph graph,
 Node start,
 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.

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,
 boolean potentiallyDirected)

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.

potentiallyDirected - If true, the algorithm will traverse edges that are potentially directed.

Returns:

A map of nodes to their shortest distances from the start node.

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.

main

public static void main(String[] args)

A simple test of the Dijkstra algorithm. This could be moved to a unit test. TODO

Parameters:

args - Command line arguments.