N
- Node parameter type@Beta public interface Graph<N>
There are three main interfaces provided to represent graphs. In order of increasing
complexity they are: Graph
, ValueGraph
, and Network
. You should generally
prefer the simplest interface that satisfies your use case.
To choose the right interface, answer these questions:
Yes: Go to question 2. No: Use Graph
.
equal
to each other. A common example
where this would not be the case is with weighted graphs.
Yes: Go to question 3. No: Use ValueGraph
.
Yes: Use Network
. No: Go to question 4.
Yes: Use Network
. No: Use ValueGraph
.
Although MutableValueGraph
and MutableNetwork
both require users to provide
objects to associate with edges when adding them, the differentiating factor is that in ValueGraph
s, these objects can be any arbitrary data. Like the values in a Map
, they do
not have to be unique, and can be mutated while in the graph. In a Network
, these objects
serve as keys into the data structure. Like the keys in a Map
, they must be unique, and
cannot be mutated in a way that affects their equals/hashcode or the data structure will become
corrupted.
In all three interfaces, nodes have all the same requirements as keys in a Map
.
The Graph
interface does not support parallel edges()
, and forbids
implementations or extensions with parallel edges. It is possible to encode a notion of edge
multiplicity into the values of a ValueGraph
(e.g. with an integer or a list of values),
but this will not be reflected in methods such as degree(Object)
. For that
functionality, see Network
.
All mutation methods live on the subinterface MutableGraph
. If you do not need to
mutate a graph (e.g. if you write a method than runs a read-only algorithm on the graph), you
should prefer the non-mutating Graph
interface.
We provide an efficient implementation of this interface via GraphBuilder
. When using
the implementation provided, all collection-returning methods provide live, unmodifiable views of
the graph. In other words, you cannot add an element to the collection, but if an element is
added to the Graph
that would affect the collection, the collection will be updated
automatically. This also means that you cannot mutate a Graph
in a way that would affect
a collection while iterating over that collection. For example, you cannot remove either foo
or any successors of foo
from the graph while iterating over successors(foo)
(unless you first make a copy of the successors), just as you could not remove keys from a Map
while iterating over its Map.keySet()
. Behavior in such a case is undefined, and may
result in ConcurrentModificationException
.
Example of use:
MutableGraph managementGraph = GraphBuilder.directed().build();
managementGraph.putEdge("Big Boss", "Middle Manager Jack");
managementGraph.putEdge("Big Boss", "Middle Manager Jill");
managementGraph.putEdge("Middle Manager Jack", "Joe");
managementGraph.putEdge("Middle Manager Jack", "Schmoe");
managementGraph.putEdge("Middle Manager Jill", "Jane");
managementGraph.putEdge("Middle Manager Jill", "Doe");
for (String employee : managementGraph.nodes()) {
Set reports = managementGraph.successors(employee);
if (!reports.isEmpty()) {
System.out.format("%s has the following direct reports: %s%n", employee, reports);
}
}
Modifier and Type | Method and Description |
---|---|
Set<N> |
adjacentNodes(Object node)
Returns the nodes which have an incident edge in common with
node in this graph. |
boolean |
allowsSelfLoops()
Returns true if this graph allows self-loops (edges that connect a node to itself).
|
int |
degree(Object node)
Returns the count of
node 's incident edges, counting self-loops twice (equivalently,
the number of times an edge touches node ). |
Set<EndpointPair<N>> |
edges()
Returns all edges in this graph.
|
boolean |
equals(Object object)
For the default
Graph implementations, returns true iff this == object
(reference equality). |
int |
hashCode()
For the default
Graph implementations, returns System.identityHashCode(this) . |
int |
inDegree(Object node)
Returns the count of
node 's incoming edges (equal to predecessors(node).size() )
in a directed graph. |
boolean |
isDirected()
Returns true if the edges in this graph are directed.
|
ElementOrder<N> |
nodeOrder()
Returns the order of iteration for the elements of
nodes() . |
Set<N> |
nodes()
Returns all nodes in this graph, in the order specified by
nodeOrder() . |
int |
outDegree(Object node)
Returns the count of
node 's outgoing edges (equal to successors(node).size() )
in a directed graph. |
Set<N> |
predecessors(Object node)
Returns all nodes in this graph adjacent to
node which can be reached by traversing
node 's incoming edges against the direction (if any) of the edge. |
Set<N> |
successors(Object node)
Returns all nodes in this graph adjacent to
node which can be reached by traversing
node 's outgoing edges in the direction (if any) of the edge. |
Set<N> nodes()
nodeOrder()
.Set<EndpointPair<N>> edges()
boolean isDirected()
source node
to a target node
, while
undirected edges connect a pair of nodes to each other.boolean allowsSelfLoops()
UnsupportedOperationException
.ElementOrder<N> nodeOrder()
nodes()
.Set<N> adjacentNodes(Object node)
node
in this graph.IllegalArgumentException
- if node
is not an element of this graphSet<N> predecessors(Object node)
node
which can be reached by traversing
node
's incoming edges against the direction (if any) of the edge.
In an undirected graph, this is equivalent to adjacentNodes(Object)
.
IllegalArgumentException
- if node
is not an element of this graphSet<N> successors(Object node)
node
which can be reached by traversing
node
's outgoing edges in the direction (if any) of the edge.
In an undirected graph, this is equivalent to adjacentNodes(Object)
.
This is not the same as "all nodes reachable from node
by following outgoing
edges". For that functionality, see Graphs.reachableNodes(Graph, Object)
.
IllegalArgumentException
- if node
is not an element of this graphint degree(Object node)
node
's incident edges, counting self-loops twice (equivalently,
the number of times an edge touches node
).
For directed graphs, this is equal to inDegree(node) + outDegree(node)
.
For undirected graphs, this is equal to adjacentNodes(node).size()
+ (1 if node
has an incident self-loop, 0 otherwise).
If the count is greater than Integer.MAX_VALUE
, returns Integer.MAX_VALUE
.
IllegalArgumentException
- if node
is not an element of this graphint inDegree(Object node)
node
's incoming edges (equal to predecessors(node).size()
)
in a directed graph. In an undirected graph, returns the degree(Object)
.
If the count is greater than Integer.MAX_VALUE
, returns Integer.MAX_VALUE
.
IllegalArgumentException
- if node
is not an element of this graphint outDegree(Object node)
node
's outgoing edges (equal to successors(node).size()
)
in a directed graph. In an undirected graph, returns the degree(Object)
.
If the count is greater than Integer.MAX_VALUE
, returns Integer.MAX_VALUE
.
IllegalArgumentException
- if node
is not an element of this graphboolean equals(@Nullable Object object)
Graph
implementations, returns true iff this == object
(reference equality). External implementations are free to define this method as they see fit,
as long as they satisfy the Object.equals(Object)
contract.
To compare two Graph
s based on their contents rather than their references, see
Graphs.equivalent(Graph, Graph)
.
int hashCode()
Graph
implementations, returns System.identityHashCode(this)
.
External implementations are free to define this method as they see fit, as long as they
satisfy the Object.hashCode()
contract.Copyright © 2010-2016. All Rights Reserved.