javautils.graph
Class Graphs

java.lang.Object
  |
  +--javautils.collections.Algs
        |
        +--javautils.graph.Graphs

public class Graphs

extends Algs

Static utility methods for dealing with graphs.

Field Summary

Fields inherited from class javautils.collections.Algs

EMPTY_ARRAY, EMPTY_LIST, EMPTY_MAP, EMPTY_SEQUENCE, EMPTY_SET

Constructor Summary

Graphs()

Method Summary

static ImmutablePair	asSourceTargetPair(Graph graph, java.lang.Object edge)
static java.lang.String	asString(Graph graph) A string representation of the graph, where node ids are the nodes themselves and edge ids are assigned using a counter.
static java.lang.String	asString(Graph graph, Function nodeToIdFun, Function edgeToIdFun) A string representation of the graph.
static AugmentedGraph	augmented(Graph graph) Augmented view of the given graph.
static java.util.Collection	connectedComponents(Graph directedGraph) The connected components of the given graph.
static java.util.Iterator	edges(Graph graph) A sequence of all edges of the graph.
static java.util.Set	edgeSet(Graph graph) A set of all edges of the graph.
static void	forEachEdge(Graph graph, Function proc) Calls the given procedure for each edge of the given graph.
static void	forEachNode(Graph graph, Function proc) Calls the given procedure for each node of the given graph.
static Graph	inducedByEdgesAndContainingNodes(Graph graph, java.util.Iterator edges, java.util.Iterator includedNodes) A graph induced by the specified edges and additionally containing the specified nodes.
static boolean	invariant(Graph graph) True if and only if the invariant of the graph holds.
static boolean	isAcyclic(Graph graph) True iff the given graph is acyclic.
static boolean	isIncoming(Graph graph, java.lang.Object edge, java.lang.Object node) True iff the given node is the target of the given edge.
static boolean	isSelf(Graph graph, java.lang.Object edge) True iff the given edge is a self edge.
static java.util.List	nodesByDecreasingDfsFinishingTime(Graph graph) A list of all nodes of the given graph in order of decreasing DFS-finishing time.
static java.util.List	nodesByIncreasingIndegree(Graph graph) A list of all nodes of the given graph in increasing order of indegree.
static java.util.List	nodesByIncreasingOutdegree(Graph graph) A list of all nodes of the given graph in increasing order of outdegree.
static java.util.Set	nodeSet(Graph graph) A set of all nodes of the graph.
static java.util.Set	nodesReachableFrom(Graph graph, java.util.Collection roots)
static java.util.Set	nodesReachableFrom(Graph graph, java.util.Iterator roots) Set of nodes reachable from the specified roots.
static java.util.Set	nodesReachableFrom(Graph graph, java.lang.Object root)
static java.lang.Object	otherNode(Graph graph, java.lang.Object edge, java.lang.Object node) The other node of the edge.
static Graph	randomGraph(int numNodes, int numEdges) A new random graph with the specified number of nodes and edges.
static Graph	restrictedToNodes(Graph graph, java.util.Collection nodes)
static Graph	restrictedToNodes(Graph graph, java.util.Iterator nodes) A graph restricted to the specified nodes and edges between the specified nodes.
static Graph	restrictedToNodes(Graph graph, java.lang.Object[] nodes)
static boolean	sameNodesAndEdges(Graph lhs, Graph rhs) True if and only if the given graphs have the same nodes and edges.
static java.util.Collection	stronglyConnectedComponents(Graph graph) The strongly connected components of the given directed graph.
static Graph	transitiveIrreflexiveClosure(Graph graph) Transitive, irreflexive closure of the given graph.
static AugmentedGraph	transposed(AugmentedGraph graph) Transpose view of the given finite graph.
static Graph	transposed(Graph graph) Transpose view of the given finite graph.
static UndirectedGraph	undirected(Graph graph) Undirected view of the given finite graph.

Methods inherited from class javautils.collections.Algs

addAll, allSuperInterfaces, asArray, asArray, asComparator, asUnmodifiableList, collect, collectMap, collectSet, collectUnmodifiable, concat, concat, concat, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOf, copyOfArray, drop, ensureLength, exists, exists, exists, filter, filter, filter, find, find, find, flatten, flatten, flatten, fold, fold, fold, foldRight, foldRight, foldRight, forAll, forAll, forAll, forEach, forEach, forEach, forEach, forEach, forEach, forEachInProduct, forEachInProduct, forEachInProduct, forEachInProduct, genAddAll, genConcat, genConcat, genForEach, genForEach, getOrIfNull, integersInRange, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iterator, iteratorOverArray, map, map, map, map, map, map, mapMorphism, mapMorphismTo, mapTransform, max, max, max, max, max, max, max, min, min, min, min, min, min, min, newMap, newShapedArray, newUnmodifiableList, putAll, putAll, reverseIterator, reverseIterator, select, select, select, sign, singletonIterator, sort, sort, sorted, sorted, take, transform, transform, transform

Methods inherited from class java.lang.Object

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

Constructor Detail

Graphs

public Graphs()

Method Detail

asString

public static java.lang.String asString(Graph graph)

A string representation of the graph, where node ids are the nodes themselves and edge ids are assigned using a counter.

asString

public static java.lang.String asString(Graph graph,
                                        Function nodeToIdFun,
                                        Function edgeToIdFun)

A string representation of the graph.

augmented

public static AugmentedGraph augmented(Graph graph)

Augmented view of the given graph. If the given graph is already augmented, the same graph will simply be returned.

connectedComponents

public static java.util.Collection connectedComponents(Graph directedGraph)

The connected components of the given graph. The graph is interpreted as undirected. Two nodes a and b are in the same component if there exists a path, {{a,c0}, {c0,c1}, ..., {cn,b}}, between them. The result is a collection of component graphs.

edges

public static java.util.Iterator edges(Graph graph)

A sequence of all edges of the graph.

edgeSet

public static java.util.Set edgeSet(Graph graph)

A set of all edges of the graph.

forEachEdge

public static void forEachEdge(Graph graph,
                               Function proc)

Calls the given procedure for each edge of the given graph.

forEachNode

public static void forEachNode(Graph graph,
                               Function proc)

Calls the given procedure for each node of the given graph.

inducedByEdgesAndContainingNodes

public static Graph inducedByEdgesAndContainingNodes(Graph graph,
                                                     java.util.Iterator edges,
                                                     java.util.Iterator includedNodes)

A graph induced by the specified edges and additionally containing the specified nodes.

invariant

public static boolean invariant(Graph graph)

True if and only if the invariant of the graph holds. This method handles both graphs and augmented graphs.

isAcyclic

public static boolean isAcyclic(Graph graph)

True iff the given graph is acyclic. This method is not meaningful on undirected graphs.

isIncoming

public static boolean isIncoming(Graph graph,
                                 java.lang.Object edge,
                                 java.lang.Object node)

True iff the given node is the target of the given edge.

isSelf

public static boolean isSelf(Graph graph,
                             java.lang.Object edge)

True iff the given edge is a self edge.

nodesByIncreasingIndegree

public static java.util.List nodesByIncreasingIndegree(Graph graph)

A list of all nodes of the given graph in increasing order of indegree.

nodesByIncreasingOutdegree

public static java.util.List nodesByIncreasingOutdegree(Graph graph)

A list of all nodes of the given graph in increasing order of outdegree.

nodesByDecreasingDfsFinishingTime

public static java.util.List nodesByDecreasingDfsFinishingTime(Graph graph)

A list of all nodes of the given graph in order of decreasing DFS-finishing time.

nodesReachableFrom

public static java.util.Set nodesReachableFrom(Graph graph,
                                               java.util.Iterator roots)

Set of nodes reachable from the specified roots.

nodesReachableFrom

public static java.util.Set nodesReachableFrom(Graph graph,
                                               java.util.Collection roots)

nodesReachableFrom

public static java.util.Set nodesReachableFrom(Graph graph,
                                               java.lang.Object root)

nodeSet

public static java.util.Set nodeSet(Graph graph)

A set of all nodes of the graph.

otherNode

public static java.lang.Object otherNode(Graph graph,
                                         java.lang.Object edge,
                                         java.lang.Object node)

The other node of the edge.

randomGraph

public static Graph randomGraph(int numNodes,
                                int numEdges)

A new random graph with the specified number of nodes and edges.

restrictedToNodes

public static Graph restrictedToNodes(Graph graph,
                                      java.util.Iterator nodes)

A graph restricted to the specified nodes and edges between the specified nodes.

restrictedToNodes

public static Graph restrictedToNodes(Graph graph,
                                      java.util.Collection nodes)

restrictedToNodes

public static Graph restrictedToNodes(Graph graph,
                                      java.lang.Object[] nodes)

sameNodesAndEdges

public static boolean sameNodesAndEdges(Graph lhs,
                                        Graph rhs)

True if and only if the given graphs have the same nodes and edges.

asSourceTargetPair

public static ImmutablePair asSourceTargetPair(Graph graph,
                                               java.lang.Object edge)

stronglyConnectedComponents

public static java.util.Collection stronglyConnectedComponents(Graph graph)

The strongly connected components of the given directed graph. The result is a collection of collections of nodes of each component.

transitiveIrreflexiveClosure

public static Graph transitiveIrreflexiveClosure(Graph graph)

Transitive, irreflexive closure of the given graph.

transposed

public static AugmentedGraph transposed(AugmentedGraph graph)

Transpose view of the given finite graph. The transpose view shares the same node and edge objects with the original graph.

Note: Neither the original graph nor the transpose view should ever be modified.

transposed

public static Graph transposed(Graph graph)

Transpose view of the given finite graph. The transpose view shares the same node and edge objects with the original graph.

Note: Neither the original graph nor the transpose view should ever be modified.

undirected

public static UndirectedGraph undirected(Graph graph)

Undirected view of the given finite graph. The undirected view shares the same node objects with the original graph.

Note:

• The undirected view does not share the same edge objects with the original graph.
• Neither the original graph nor the undirected view should ever be modified.