com.facebook.buck.core.util.graph

Class MutableDirectedGraph<T>

java.lang.Object

com.facebook.buck.core.util.graph.MutableDirectedGraph<T>

Type Parameters:

T - the type of object stored as nodes in this graph

All Implemented Interfaces:

TraversableGraph<T>

public final class MutableDirectedGraph<T>
extends Object
implements TraversableGraph<T>

Represents a directed graph with unweighted edges. For a given source and sink node pair, there is at most one directed edge connecting them in the graph. The graph is not required to be connected or acyclic.

Constructor Summary

Constructors

Constructor and Description
MutableDirectedGraph() Creates a new graph with no nodes or edges.

Method Summary

Modifier and Type	Method and Description
void	addEdge(T source, T sink) Adds an edge between source and sink.
boolean	addNode(T node) Adds the specified node to the graph.
boolean	containsEdge(T source, T sink)
boolean	containsNode(T node)
static <T> MutableDirectedGraph<T>	createConcurrent()
com.google.common.collect.ImmutableSet<com.google.common.collect.ImmutableSet<T>>	findCycles()
Set<Set<T>>	findStronglyConnectedComponents() For this graph, returns the set of strongly connected components using Tarjan's algorithm.
int	getEdgeCount()
Iterable<T>	getIncomingNodesFor(T sink)
int	getNodeCount()
Set<T>	getNodes()
Iterable<T>	getNodesWithNoIncomingEdges()
Iterable<T>	getNodesWithNoOutgoingEdges()
Iterable<T>	getOutgoingNodesFor(T source)
boolean	hasIncomingEdges(T node)
boolean	isAcyclic()
void	removeEdge(T source, T sink) Removes the edge between source and sink.
boolean	removeNode(T node) Removes the specified node from the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

MutableDirectedGraph

public MutableDirectedGraph()

Creates a new graph with no nodes or edges.

Method Detail

createConcurrent

public static <T> MutableDirectedGraph<T> createConcurrent()

getNodeCount

public int getNodeCount()

Returns:

the number of nodes in the graph

getEdgeCount

public int getEdgeCount()

Returns:

the number of edges in the graph

containsNode

public boolean containsNode(T node)

Returns:

whether the specified node is present in the graph

containsEdge

public boolean containsEdge(T source,
                            T sink)

Returns:

whether an edge from the source to the sink is present in the graph

addNode

public boolean addNode(T node)

Adds the specified node to the graph.

removeNode

public boolean removeNode(T node)

Removes the specified node from the graph.

addEdge

public void addEdge(T source,
                    T sink)

Adds an edge between source and sink. Adds the nodes to the graph if they are not already present.

removeEdge

public void removeEdge(T source,
                       T sink)

Removes the edge between source and sink. This does not remove source or sink from the graph. Note that this may leave either source or sink as unconnected nodes in the graph.

getOutgoingNodesFor

public Iterable<T> getOutgoingNodesFor(T source)

Specified by:

getOutgoingNodesFor in interface TraversableGraph<T>

Returns:

Iterable that the caller is not allowed to mutate.

getIncomingNodesFor

public Iterable<T> getIncomingNodesFor(T sink)

Specified by:

getIncomingNodesFor in interface TraversableGraph<T>

Returns:

Iterable that the caller is not allowed to mutate.

hasIncomingEdges

public boolean hasIncomingEdges(T node)

getNodes

public Set<T> getNodes()

Specified by:

getNodes in interface TraversableGraph<T>

Returns:

an unmodifiable view of the nodes in this graph

isAcyclic

public boolean isAcyclic()

findCycles

public com.google.common.collect.ImmutableSet<com.google.common.collect.ImmutableSet<T>> findCycles()

findStronglyConnectedComponents

public Set<Set<T>> findStronglyConnectedComponents()

For this graph, returns the set of strongly connected components using Tarjan's algorithm. Note this is O(|V| + |E|).

Returns:

an unmodifiable Set of sets, each of which is also an unmodifiable Set and represents a strongly connected component.

getNodesWithNoIncomingEdges

public Iterable<T> getNodesWithNoIncomingEdges()

Specified by:

getNodesWithNoIncomingEdges in interface TraversableGraph<T>

Returns:

Iterable that the caller is not allowed to mutate.

getNodesWithNoOutgoingEdges

public Iterable<T> getNodesWithNoOutgoingEdges()

Specified by:

getNodesWithNoOutgoingEdges in interface TraversableGraph<T>

Returns:

Iterable that the caller is not allowed to mutate.