Package org.onlab.graph

Class TarjanGraphSearch<V extends Vertex,E extends Edge<V>>

java.lang.Object

org.onlab.graph.TarjanGraphSearch<V,E>

All Implemented Interfaces:

GraphSearch<V,E>

public class TarjanGraphSearch<V extends Vertex,E extends Edge<V>>
extends java.lang.Object
implements GraphSearch<V,E>

Tarjan algorithm for searching a graph and producing results describing the graph SCC (strongly-connected components).

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	TarjanGraphSearch.SccResult<V extends Vertex,E extends Edge<V>>	Graph search result augmented with SCC vertexData.

Nested classes/interfaces inherited from interface org.onlab.graph.GraphSearch

GraphSearch.Result<V extends Vertex,E extends Edge<V>>

Constructor Summary

Constructors

Constructor	Description
TarjanGraphSearch()

Method Summary

Modifier and Type	Method	Description
TarjanGraphSearch.SccResult<V,E>	search(Graph<V,E> graph, EdgeWeigher<V,E> weigher)	Searches the specified graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

TarjanGraphSearch

public TarjanGraphSearch()

Method Detail

search

public TarjanGraphSearch.SccResult<V,E> search(Graph<V,E> graph,
                                                     EdgeWeigher<V,E> weigher)

Searches the specified graph.

This implementation produces results augmented with information on SCCs within the graph.

To prevent traversal of an edge, the EdgeWeigher.weight(E) should return a negative value as an edge weigher.

Specified by:

search in interface GraphSearch<V extends Vertex,E extends Edge<V>>

Parameters:

graph - graph to be searched

weigher - optional edge-weigher; if null, DefaultEdgeWeigher will be used (assigns equal weights to all links)

Returns:

search results