Package org.onlab.graph

Graph abstractions and graph path finding algorithms.

Interface Summary

Interface	Description
Edge<V extends Vertex>	Representation of a graph edge.
EdgeWeigher<V extends Vertex,E extends Edge<V>>	Abstraction of a graph edge weight function.
Graph<V extends Vertex,E extends Edge>	Abstraction of a directed graph structure.
GraphPathSearch<V extends Vertex,E extends Edge<V>>	Representation of a graph path search algorithm.
GraphPathSearch.Result<V extends Vertex,E extends Edge<V>>	Abstraction of a path search result.
GraphSearch<V extends Vertex,E extends Edge<V>>	Representation of a graph search algorithm and its outcome.
GraphSearch.Result<V extends Vertex,E extends Edge<V>>	Notion of a graph search result.
MutableGraph<V extends Vertex,E extends Edge>	Abstraction of a mutable graph that can be constructed gradually.
MutablePath<V extends Vertex,E extends Edge<V>>	Abstraction of a mutable path that allows gradual construction.
Path<V extends Vertex,E extends Edge<V>>	Representation of a path in a graph as a sequence of edges.
Vertex	Representation of a graph vertex.
Weight	Abstraction of a graph edge weight.

Class Summary

Class	Description
AbstractEdge<V extends Vertex>	Abstract graph edge implementation.
AbstractGraphPathSearch<V extends Vertex,E extends Edge<V>>	Basis for various graph path search algorithm implementations.
AdjacencyListsGraph<V extends Vertex,E extends Edge<V>>	Immutable graph implemented using adjacency lists.
BellmanFordGraphSearch<V extends Vertex,E extends Edge<V>>	Bellman-Ford graph search algorithm for locating shortest-paths in directed graphs that may contain negative cycles.
BreadthFirstSearch<V extends Vertex,E extends Edge<V>>	Implementation of the BFS algorithm.
DefaultEdgeWeigher<V extends Vertex,E extends Edge<V>>	Default weigher returns identical weight for every graph edge.
DefaultMutablePath<V extends Vertex,E extends Edge<V>>	Simple concrete implementation of a directed graph path.
DefaultPath<V extends Vertex,E extends Edge<V>>	Simple concrete implementation of a directed graph path.
DepthFirstSearch<V extends Vertex,E extends Edge<V>>	DFS graph search algorithm implemented via iteration rather than recursion.
DijkstraGraphSearch<V extends Vertex,E extends Edge<V>>	Dijkstra shortest-path graph search algorithm capable of finding not just one, but all shortest paths between the source and destinations.
DisjointPathPair<V extends Vertex,E extends Edge<V>>	Pair of disjoint paths.
Heap<T>	Implementation of an array-backed heap structure whose sense of order is imposed by the provided comparator.
KShortestPathsSearch<V extends Vertex,E extends Edge<V>>	Runs K shortest paths algorithm on a provided directed graph.
LazyKShortestPathsSearch<V extends Vertex,E extends Edge<V>>	Lazily runs K shortest paths algorithm on a provided directed graph.
MutableAdjacencyListsGraph<V extends Vertex,E extends Edge<V>>
ScalarWeight	Weight implementation based on a double value.
SrlgGraphSearch<V extends Vertex,E extends Edge<V>>	SRLG Graph Search finds a pair of paths with disjoint risk groups; i.e if one path goes through an edge in risk group 1, the other path will go through no edges in risk group 1.
SuurballeGraphSearch<V extends Vertex,E extends Edge<V>>	Suurballe shortest-path graph search algorithm capable of finding both a shortest path, as well as a backup shortest path, between a source and a destination such that the sum of the path lengths is minimized.
TarjanGraphSearch<V extends Vertex,E extends Edge<V>>	Tarjan algorithm for searching a graph and producing results describing the graph SCC (strongly-connected components).
TarjanGraphSearch.SccResult<V extends Vertex,E extends Edge<V>>	Graph search result augmented with SCC vertexData.

Enum Summary

Enum	Description
DepthFirstSearch.EdgeType	Graph edge types as classified by the DFS algorithm.