Package org.apache.calcite.util.graph

Class Graphs.FrozenGraph<V,E extends DefaultEdge>

java.lang.Object

org.apache.calcite.util.graph.Graphs.FrozenGraph<V,E>

Type Parameters:

V - Vertex type

E - Edge type

Enclosing class:

Graphs

public static class Graphs.FrozenGraph<V,E extends DefaultEdge>
extends java.lang.Object

Immutable grap.

Field Summary

Fields

Modifier and Type	Field	Description
private DefaultDirectedGraph<V,E>	graph
private java.util.Map<Pair<V,V>,java.util.List<V>>	shortestPaths

Constructor Summary

Constructors

Constructor	Description
FrozenGraph(DefaultDirectedGraph<V,E> graph, java.util.Map<Pair<V,V>,java.util.List<V>> shortestPaths)	Creates a frozen graph as a copy of another graph.

Method Summary

Modifier and Type	Method	Description
private void	findPaths(V from, V to, java.util.List<java.util.List<V>> list)
private void	findPathsExcluding(V from, V to, java.util.List<java.util.List<V>> list, java.util.Set<V> excludedNodes, java.util.List<V> prefix)	Finds all paths from "from" to "to" of length 2 or greater, such that the intermediate nodes are not contained in "excludedNodes".
java.util.List<java.util.List<V>>	getPaths(V from, V to)	Returns an iterator of all paths between two nodes, shortest first.
java.util.List<V>	getShortestPath(V from, V to)	Returns the shortest path between two points, null if there is no path.

Methods inherited from class java.lang.Object

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

Field Detail

graph

private final DefaultDirectedGraph<V,E extends DefaultEdge> graph

shortestPaths

private final java.util.Map<Pair<V,V>,java.util.List<V>> shortestPaths

Constructor Detail

FrozenGraph

FrozenGraph(DefaultDirectedGraph<V,E> graph,
            java.util.Map<Pair<V,V>,java.util.List<V>> shortestPaths)

Creates a frozen graph as a copy of another graph.

Method Detail

getPaths

public java.util.List<java.util.List<V>> getPaths(V from,
                                                  V to)

Returns an iterator of all paths between two nodes, shortest first.

The current implementation is not optimal.

getShortestPath

public java.util.List<V> getShortestPath(V from,
                                         V to)

Returns the shortest path between two points, null if there is no path.

Parameters:

from - From

to - To

Returns:

A list of arcs, null if there is no path.

findPaths

private void findPaths(V from,
                       V to,
                       java.util.List<java.util.List<V>> list)

findPathsExcluding

private void findPathsExcluding(V from,
                                V to,
                                java.util.List<java.util.List<V>> list,
                                java.util.Set<V> excludedNodes,
                                java.util.List<V> prefix)

Finds all paths from "from" to "to" of length 2 or greater, such that the intermediate nodes are not contained in "excludedNodes".