Package edu.cmu.tetrad.search.utils

Class R5R9Dijkstra

java.lang.Object

edu.cmu.tetrad.search.utils.R5R9Dijkstra

public class R5R9Dijkstra
extends Object

A modified implementation of Dijkstra's shortest path algorithm for the R5 and R9 rules from Zhang, J. (2008), On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias, Artificial Intelligence, 172(16-17), 1873-1896. These are rules that involve finding uncovered paths of various sorts in a graph; we use a modificiation of Dejkstra as a fast implementation of that requirement suitable for large graphs.

We report distances as total weights along the shortest path from the start node to the y node, where by default the weight of each edge is 1. We report unreachable nodes as at a distance of Integer.MAX_VALUE. Edges in the graph are dynamically calculated by the algorithm using two methods--looking for o-o edges only, suitable for the R5 rule, and looking for edges along potentially directed paths (i.e., semidirected paths), suitable for the R9 rule. The end node is used to stop the algorithm once that node has been visited, so that a shortest path has been found.

The algorithm is constrained to avoid certain paths. The start *-* end edge itself and start *-* z *-* end paths are avoided, to avoid length 1 or length 2 paths. Also, covered triples, z *-* r *-* w, z *-* w, are avoided to implement the constraint that only uncovered paths are considered. Coverings of end *-* start *-* z and start *-* end *-* w are also avoided, as specified for R5 and R9.

Author:

josephramsey 2024-8-6

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	R5R9Dijkstra.DijkstraEdge	Represents a node in Dijkstra's algorithm.
static class	R5R9Dijkstra.Graph	Represents a graph for Dijkstra's algorithm.
static enum	R5R9Dijkstra.Rule	The rule that is being implemented, R5 or R9.

Method Summary

Modifier and Type	Method	Description
static org.apache.commons.lang3.tuple.Pair<Map<Node,Integer>,Map<Node,Node>>	distances(R5R9Dijkstra.Graph graph, Node x, Node y)	Finds shortest distances from a x node to all other nodes in a graph, subject to the following constraints.
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 org.apache.commons.lang3.tuple.Pair<Map<Node,Integer>,Map<Node,Node>> distances(R5R9Dijkstra.Graph graph,
 Node x,
 Node y)

Finds shortest distances from a x node to all other nodes in a graph, subject to the following constraints. (1) Length 1 paths are not considered. (2) Length 2 paths are not considered. (3) Covered triples are not considered. (4) The y node is used to stop the algorithm once that node has been visited. (5) The graph is assumed to be undirected.

Nodes that are not reached by the algorithm 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. The algorithm will stop when this node is reached.

Returns:

A map of distances from the start node to each node in the graph, and a map of predecessors for each node.

main

public static void main(String[] args)

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

Parameters:

args - Command line arguments.