graph.traversal

Class TraversalUtil

java.lang.Object

graph.traversal.TraversalUtil

public class TraversalUtil
extends java.lang.Object

Contains methods for finding path between vertices which meet certain special conditions. Used as part of more complex algorithms.

Constructor Summary

Constructors

Constructor and Description
TraversalUtil()

Method Summary

Modifier and Type	Method and Description
static <V extends Vertex,E extends Edge<V>> java.util.List<E>	circularNoCrossingsPath(V v1, V v2, java.util.Map<V,java.util.List<E>> adj, boolean debug, java.util.List<V> excluding, java.util.List<E> excludingEdges) Finds a path from one vertex to another such that the there are no back edges and no edge crossings.

Methods inherited from class java.lang.Object

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

Constructor Detail

TraversalUtil

public TraversalUtil()

Method Detail

circularNoCrossingsPath

public static <V extends Vertex,E extends Edge<V>> java.util.List<E> circularNoCrossingsPath(V v1,
                                                                                             V v2,
                                                                                             java.util.Map<V,java.util.List<E>> adj,
                                                                                             boolean debug,
                                                                                             java.util.List<V> excluding,
                                                                                             java.util.List<E> excludingEdges)

Finds a path from one vertex to another such that the there are no back edges and no edge crossings. In other words, the path can be a part of the outer facial cycle of a planar embedding of a graph.

Type Parameters:

V - The vertex type

E - The edge type

Parameters:

v1 - Start vertex

v2 - Destination vertex

adj - Adjacency map

debug - Indicator if debug information should be shown

excluding - Vertices that cannot be of the path

excludingEdges - Edges that cannot be of the path

Returns:

Path from v1 to v2 with such that it is a part of the outer facial cycle of a planar embedding of a graph.