graph.traversal

Class GraphTraversal

java.lang.Object

graph.traversal.GraphTraversal

public class GraphTraversal
extends java.lang.Object

Contains methods which implement certain graph traversal algorithms

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
GraphTraversal()

Method Summary

Modifier and Type	Method and Description
static <V extends Vertex,E extends Edge<V>> java.util.List<Path<V,E>>	findAllPathsDFS(Graph<V,E> graph, V source, V target) Finds all paths in the given graph between two provided vertices using depth-first search
static <V extends Vertex,E extends Edge<V>> java.util.List<Path<V,E>>	findAllPathsDFS(Graph<V,E> graph, V source, V target, java.util.List<V> excluding) Finds all paths in the given graph between two provided vertices not containing any of vertices in the given list using depth-first search
static <V extends Vertex,E extends Edge<V>> java.util.List<Path<V,E>>	findAllPathsDFSContaining(Graph<V,E> graph, V source, V target, java.util.List<V> containing) Finds all paths in the given graph between two provided vertices containing a list of vertices using depth-first search
static <V extends Vertex,E extends Edge<V>> Path<V,E>	findLongestPath(Graph<V,E> graph) Finds the longest path in a graph Method should be rewritten to increase its effectiveness
static <V extends Vertex,E extends Edge<V>> Path<V,E>	nonrecursiveDFSPath(Graph<V,E> graph, V source, V target) A non-recursive implementation of the depth-first search for finding a path between two vertices More efficient than the recursive implementation

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphTraversal

public GraphTraversal()

Method Detail

findAllPathsDFS

public static <V extends Vertex,E extends Edge<V>> java.util.List<Path<V,E>> findAllPathsDFS(Graph<V,E> graph,
                                                                                             V source,
                                                                                             V target)

Finds all paths in the given graph between two provided vertices using depth-first search

Type Parameters:

V - The vertex type

E - The edge type

Parameters:

graph - Graph

source - Source vertex

target - Target (destination) vertex

Returns:

All paths in the graph between source and target vertices

findAllPathsDFSContaining

public static <V extends Vertex,E extends Edge<V>> java.util.List<Path<V,E>> findAllPathsDFSContaining(Graph<V,E> graph,
                                                                                                       V source,
                                                                                                       V target,
                                                                                                       java.util.List<V> containing)

Finds all paths in the given graph between two provided vertices containing a list of vertices using depth-first search

Type Parameters:

V - The vertex type

E - The edge type

Parameters:

graph - Graph

source - Source vertex

target - Target (destination) vertex

containing - A list of vertices the path must contain

Returns:

All paths in the graph between source and target vertices containing all of the containing vertices.

findAllPathsDFS

public static <V extends Vertex,E extends Edge<V>> java.util.List<Path<V,E>> findAllPathsDFS(Graph<V,E> graph,
                                                                                             V source,
                                                                                             V target,
                                                                                             java.util.List<V> excluding)

Finds all paths in the given graph between two provided vertices not containing any of vertices in the given list using depth-first search

Type Parameters:

V - The vertex type

E - The edge type

Parameters:

graph - Graph

source - Source vertex

target - Target (destination) vertex

excluding - A list of vertices the path shouldn't contain

Returns:

All paths in the graph between source and target vertices not containing any of the excluding vertices.

nonrecursiveDFSPath

public static <V extends Vertex,E extends Edge<V>> Path<V,E> nonrecursiveDFSPath(Graph<V,E> graph,
                                                                                 V source,
                                                                                 V target)

A non-recursive implementation of the depth-first search for finding a path between two vertices More efficient than the recursive implementation

Type Parameters:

V - The vertex type

E - The edge type

Parameters:

graph - Graph

source - Source vertex

target - Target (destination) vertex

Returns:

A path in graph between source and target vertices

findLongestPath

public static <V extends Vertex,E extends Edge<V>> Path<V,E> findLongestPath(Graph<V,E> graph)

Finds the longest path in a graph Method should be rewritten to increase its effectiveness

Type Parameters:

V - The vertex type

E - The edge type1

Parameters:

graph - The graph

Returns:

The longest path between any two vertices in a graph