util.graph

Class Graphs

java.lang.Object

util.graph.Graphs

public final class Graphs
extends java.lang.Object

Provides a lot of utility methods for working with graphs

Method Summary

Modifier and Type	Method and Description
static <T,E extends DirectedEdge<T,E>> int[]	componentMapping(int vertices, java.lang.Iterable<E> edges) Returns an array representing a connected component mapping.
static int[]	componentMapping(int vertices, java.util.List<java.util.List<java.lang.Integer>> components) Creates an array representing a connected component mapping.
static <T,E extends DirectedEdge<T,E>> java.util.List<java.util.List<java.lang.Integer>>	components(int vertices, java.lang.Iterable<E> edges) Takes a graph specified by a number of vertices and an Iterable of edges and returns a List of List of Integer, where the i-th List contains the indices of all vertices that belong to the i-th connected component.
static <T,S,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>,D extends DirectedEdge<S,D>> Graph<ContractedEdge<T,E>>	contract(int vertices, java.lang.Iterable<D> span, java.lang.Iterable<E> edges) Contracts a graph specified by the number of vertices and an Iterable of edges along the edges given by the Iterable span.
static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> EdgeList<ContractedEdge<T,E>>	flatten(EdgeList<ContractedEdge<T,ContractedEdge<T,E>>> list) Takes an EdgeList of at least doubly contracted edges and removes the second-outermost layer of contracted edges
static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> Graph<ContractedEdge<T,E>>	flatten(Graph<ContractedEdge<T,ContractedEdge<T,E>>> graph) Takes a Graph of at least doubly contracted edges and removes the second-outermost layer of contracted edges
static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> java.util.Set<E>	lightestEdgePerVertex(int vertices, java.lang.Iterable<E> edges) Takes a graph specified by the number of vertices and an Iterable of edges.
static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> EdgeList<E>	removeDuplicates(int vertices, java.lang.Iterable<E> edges) Removes multiple edges between two vertices.
static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> Graph<RenamedEdge<T,E>>	renameVertices(java.lang.Iterable<E> edges) Takes an Iterable of edges and renames the vertices, so that all vertex indices are between 0 and n - 1 where n is the number of vertices
static <T,E extends DirectedEdge<T,E>> EdgeList<E>	sortEdges(int vertices, java.lang.Iterable<E> edges) Takes a graph specified by the number of vertices and an Iterable of edges and returns an EdgeList containing all edges in a sorted manner.

Methods inherited from class java.lang.Object

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

Method Detail

componentMapping

public static <T,E extends DirectedEdge<T,E>> int[] componentMapping(int vertices,
                                                                     java.lang.Iterable<E> edges)

Returns an array representing a connected component mapping. The i-th entry is the index of the connected component which the i-th vertex is part of

Type Parameters:

T - the weight type of the edges in the graph

E - the edge type of the edges in the graph

Parameters:

vertices - the number of vertices in the graph

edges - an Iterable of all edges in the graph

Returns:

an array representing a connected component mapping as described above

componentMapping

public static int[] componentMapping(int vertices,
                                     java.util.List<java.util.List<java.lang.Integer>> components)

Creates an array representing a connected component mapping. The i-th entry is the index of the connected component which the i-th vertex is part of

Parameters:

vertices - the number of vertices in the graph

components - a List of List of Integer where the i-th List contains the indices of all vertices that belong to the i-th component

Returns:

an array representing a connected component mapping as described above

components

public static <T,E extends DirectedEdge<T,E>> java.util.List<java.util.List<java.lang.Integer>> components(int vertices,
                                                                                                           java.lang.Iterable<E> edges)

Takes a graph specified by a number of vertices and an Iterable of edges and returns a List of List of Integer, where the i-th List contains the indices of all vertices that belong to the i-th connected component.

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

Parameters:

vertices - the number of vertices of the graph

edges - an Iterable of edges of the graph

Returns:

a List of List of Integer representing the connected components of the graph as described above

sortEdges

public static <T,E extends DirectedEdge<T,E>> EdgeList<E> sortEdges(int vertices,
                                                                    java.lang.Iterable<E> edges)

Takes a graph specified by the number of vertices and an Iterable of edges and returns an EdgeList containing all edges in a sorted manner.

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

Parameters:

vertices - the number of vertices in the graph

edges - an Iterable of edges in the graph

Returns:

an EdgeList containing all edges of the original graph, but sorted

removeDuplicates

public static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> EdgeList<E> removeDuplicates(int vertices,
                                                                                                             java.lang.Iterable<E> edges)

Removes multiple edges between two vertices. If there are multiple edges between two vertices, only the lightest edge is kept.

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

Parameters:

vertices - the number of vertices of the graph

edges - an Iterable of edges of the graph

Returns:

an EdgeList containing no duplicates of edges

renameVertices

public static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> Graph<RenamedEdge<T,E>> renameVertices(java.lang.Iterable<E> edges)

Takes an Iterable of edges and renames the vertices, so that all vertex indices are between 0 and n - 1 where n is the number of vertices

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

Parameters:

edges - the Iterable whose vertices shall be renamed

Returns:

a Graph representing the graph but with renamed edges

lightestEdgePerVertex

public static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> java.util.Set<E> lightestEdgePerVertex(int vertices,
                                                                                                                       java.lang.Iterable<E> edges)

Takes a graph specified by the number of vertices and an Iterable of edges. For each vertex we take the outgoing edge with smallest weight and return a Set of all of these edges

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

Parameters:

vertices - the number of vertices of the graph

edges - an Iterable of edges of the graph

Returns:

a Set containing only the lightest edge per vertex

contract

public static <T,S,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>,D extends DirectedEdge<S,D>> Graph<ContractedEdge<T,E>> contract(int vertices,
                                                                                                                                                  java.lang.Iterable<D> span,
                                                                                                                                                  java.lang.Iterable<E> edges)

Contracts a graph specified by the number of vertices and an Iterable of edges along the edges given by the Iterable span. Each group of vertices that is connected by some of the edges of span will be replaced by a single vertex in the contracted graph.

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

S - the weight type of the edges along which we contract

D - the edge type of the edges along which we contract

Parameters:

vertices - the number of vertices in the graph

span - an Iterable along which the graph shall be contracted

edges - an Iterable of edges of the graph

Returns:

the contracted graph as a Graph

flatten

public static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> EdgeList<ContractedEdge<T,E>> flatten(EdgeList<ContractedEdge<T,ContractedEdge<T,E>>> list)

Takes an EdgeList of at least doubly contracted edges and removes the second-outermost layer of contracted edges

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

Parameters:

list - the EdgeList of at least doubly contracted edges

Returns:

the flattened list of edges as an EdgeList

flatten

public static <T,E extends DirectedEdge<T,E> & java.lang.Comparable<? super E>> Graph<ContractedEdge<T,E>> flatten(Graph<ContractedEdge<T,ContractedEdge<T,E>>> graph)

Takes a Graph of at least doubly contracted edges and removes the second-outermost layer of contracted edges

Type Parameters:

T - the weight type of the edges of the graph

E - the edge type of the edges of the graph

Parameters:

graph - the Graph of at least doubly contracted edges

Returns:

the flattened Graph