Top Description Fields Constructors Methods
com.google.common.graph

pack-priv Class StandardValueGraph<N, V>

extends AbstractValueGraph<N, V>
Class Inheritance
Known Direct Subclasses
com.google.common.graph.ImmutableValueGraph, com.google.common.graph.StandardMutableValueGraph
Annotations
@ElementTypesAreNonnullByDefault
Type Parameters
<N>
Node parameter type
<V>
Value parameter type
Static Imports
com.google.common.base.Preconditions.checkNotNull, com.google.common.graph.GraphConstants.DEFAULT_NODE_COUNT, .Graphs.checkNonNegative
Standard implementation of ValueGraph that supports the options supplied by AbstractGraphBuilder.

This class maintains a map of nodes to GraphConnections.

Collection-returning accessors return unmodifiable views: the view returned will reflect changes to the graph (if the graph is mutable) but may not be modified by the user.

The time complexity of all collection-returning accessors is O(1), since views are returned.

Authors
James Sexton, Joshua O'Madadhain, Omar Darwish

Field Summary

Modifier and TypeField and Description
private final boolean
allowsSelfLoops

pack-priv long
edgeCount

private final boolean
isDirected

pack-priv final MapIteratorCache<N, GraphConnections<N, V>>
nodeConnections

private final ElementOrder<N>
nodeOrder

Constructor Summary

AccessConstructor and Description
pack-priv
StandardValueGraph(AbstractGraphBuilder<? super N> builder)

Constructs a graph with the properties specified in builder.

pack-priv
StandardValueGraph(AbstractGraphBuilder<? super N> builder, Map<N, GraphConnections<N, V>> nodeConnections, long edgeCount)

Constructs a graph with the properties specified in builder, initialized with the given node map.

Method Summary

Modifier and TypeMethod and Description
public Set<N>
adjacentNodes(N node)

Implements com.google.common.graph.ValueGraph.adjacentNodes, com.google.common.graph.BaseGraph.adjacentNodes.

Returns a live view of the nodes which have an incident edge in common with node in this graph.
public boolean
allowsSelfLoops()

Implements com.google.common.graph.ValueGraph.allowsSelfLoops, com.google.common.graph.BaseGraph.allowsSelfLoops.

Returns true if this graph allows self-loops (edges that connect a node to itself).
private final GraphConnections<N, V>
checkedConnections(N node)

pack-priv final boolean
containsNode(N node)

protected long
edgeCount()

Overrides com.google.common.graph.AbstractBaseGraph.edgeCount.

Returns the number of edges in this graph; used to calculate the size of Graph#edges().
public V
edgeValueOrDefault(N nodeU, N nodeV, V defaultValue)

Implements com.google.common.graph.ValueGraph.edgeValueOrDefault.

Returns the value of the edge that connects nodeU to nodeV, if one is present; otherwise, returns defaultValue.
public V
edgeValueOrDefault(EndpointPair<N> endpoints, V defaultValue)

Implements com.google.common.graph.ValueGraph.edgeValueOrDefault.

Returns the value of the edge that connects endpoints (in the order, if any, specified by endpoints), if one is present; otherwise, returns defaultValue.
private final V
edgeValueOrDefaultInternal(N nodeU, N nodeV, V defaultValue)

public boolean
hasEdgeConnecting(N nodeU, N nodeV)

Overrides com.google.common.graph.AbstractBaseGraph.hasEdgeConnecting.

Implements com.google.common.graph.ValueGraph.hasEdgeConnecting, com.google.common.graph.BaseGraph.hasEdgeConnecting.

Returns true if there is an edge that directly connects nodeU to nodeV.
public boolean
hasEdgeConnecting(EndpointPair<N> endpoints)

Overrides com.google.common.graph.AbstractBaseGraph.hasEdgeConnecting.

Implements com.google.common.graph.ValueGraph.hasEdgeConnecting, com.google.common.graph.BaseGraph.hasEdgeConnecting.

Returns true if there is an edge that directly connects endpoints (in the order, if any, specified by endpoints).
private final boolean
hasEdgeConnectingInternal(N nodeU, N nodeV)

public Set<EndpointPair<N>>
incidentEdges(N node)

Overrides com.google.common.graph.AbstractBaseGraph.incidentEdges.

Implements com.google.common.graph.ValueGraph.incidentEdges, com.google.common.graph.BaseGraph.incidentEdges.

Returns a live view of the edges in this graph whose endpoints include node.
public boolean
isDirected()

Implements com.google.common.graph.ValueGraph.isDirected, com.google.common.graph.BaseGraph.isDirected.

Returns true if the edges in this graph are directed.
public ElementOrder<N>
nodeOrder()

Implements com.google.common.graph.ValueGraph.nodeOrder, com.google.common.graph.BaseGraph.nodeOrder.

Returns the order of iteration for the elements of nodes().
public Set<N>
nodes()

Implements com.google.common.graph.ValueGraph.nodes, com.google.common.graph.BaseGraph.nodes.

Returns all nodes in this graph, in the order specified by nodeOrder().
public Set<N>
predecessors(N node)

Implements com.google.common.graph.ValueGraph.predecessors, com.google.common.graph.BaseGraph.predecessors.

Returns a live view of 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.
public Set<N>
successors(N node)

Implements com.google.common.graph.ValueGraph.successors, com.google.common.graph.BaseGraph.successors.

Returns a live view of 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.
Inherited from com.google.common.graph.AbstractValueGraph:
asGraphedgeValueedgeValueequalshashCodetoString

Field Detail

allowsSelfLoopsback to summary
private final boolean allowsSelfLoops
edgeCountback to summary
pack-priv long edgeCount
isDirectedback to summary
private final boolean isDirected
nodeConnectionsback to summary
pack-priv final MapIteratorCache<N, GraphConnections<N, V>> nodeConnections
nodeOrderback to summary
private final ElementOrder<N> nodeOrder

Constructor Detail

StandardValueGraphback to summary
pack-priv StandardValueGraph(AbstractGraphBuilder<? super N> builder)

Constructs a graph with the properties specified in builder.

StandardValueGraphback to summary
pack-priv StandardValueGraph(AbstractGraphBuilder<? super N> builder, Map<N, GraphConnections<N, V>> nodeConnections, long edgeCount)

Constructs a graph with the properties specified in builder, initialized with the given node map.

Method Detail

adjacentNodesback to summary
public Set<N> adjacentNodes(N node)

Implements com.google.common.graph.ValueGraph.adjacentNodes, com.google.common.graph.BaseGraph.adjacentNodes.

Doc from com.google.common.graph.ValueGraph.adjacentNodes.

Returns a live view of the nodes which have an incident edge in common with node in this graph.

This is equal to the union of predecessors(Object) and successors(Object).

If node is removed from the graph after this method is called, the Set view returned by this method will be invalidated, and will throw IllegalStateException if it is accessed in any way, with the following exceptions:

  • view.equals(view) evaluates to true (but any other `equals()` expression involving view will throw)
  • hashCode() does not throw
  • if node is re-added to the graph after having been removed, view's behavior is undefined
Annotations
@Override
allowsSelfLoopsback to summary
public boolean allowsSelfLoops()

Implements com.google.common.graph.ValueGraph.allowsSelfLoops, com.google.common.graph.BaseGraph.allowsSelfLoops.

Doc from com.google.common.graph.ValueGraph.allowsSelfLoops.

Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting to add a self-loop to a graph that does not allow them will throw an IllegalArgumentException.

Annotations
@Override
checkedConnectionsback to summary
private final GraphConnections<N, V> checkedConnections(N node)
containsNodeback to summary
pack-priv final boolean containsNode(N node)
edgeCountback to summary
protected long edgeCount()

Overrides com.google.common.graph.AbstractBaseGraph.edgeCount.

Doc from com.google.common.graph.AbstractBaseGraph.edgeCount.

Returns the number of edges in this graph; used to calculate the size of Graph#edges(). This implementation requires O(|N|) time. Classes extending this one may manually keep track of the number of edges as the graph is updated, and override this method for better performance.

Annotations
@Override
edgeValueOrDefaultback to summary
public V edgeValueOrDefault(N nodeU, N nodeV, V defaultValue)

Implements com.google.common.graph.ValueGraph.edgeValueOrDefault.

Doc from com.google.common.graph.ValueGraph.edgeValueOrDefault.

Returns the value of the edge that connects nodeU to nodeV, if one is present; otherwise, returns defaultValue.

In an undirected graph, this is equal to edgeValueOrDefault(nodeV, nodeU, defaultValue).

Annotations
@Override
@CheckForNull
edgeValueOrDefaultback to summary
public V edgeValueOrDefault(EndpointPair<N> endpoints, V defaultValue)

Implements com.google.common.graph.ValueGraph.edgeValueOrDefault.

Doc from com.google.common.graph.ValueGraph.edgeValueOrDefault.

Returns the value of the edge that connects endpoints (in the order, if any, specified by endpoints), if one is present; otherwise, returns defaultValue.

If this graph is directed, the endpoints must be ordered.

Annotations
@Override
@CheckForNull
edgeValueOrDefaultInternalback to summary
private final V edgeValueOrDefaultInternal(N nodeU, N nodeV, V defaultValue)
Annotations
@CheckForNull
hasEdgeConnectingback to summary
public boolean hasEdgeConnecting(N nodeU, N nodeV)

Overrides com.google.common.graph.AbstractBaseGraph.hasEdgeConnecting.

Implements com.google.common.graph.ValueGraph.hasEdgeConnecting, com.google.common.graph.BaseGraph.hasEdgeConnecting.

Doc from com.google.common.graph.ValueGraph.hasEdgeConnecting.

Returns true if there is an edge that directly connects nodeU to nodeV. This is equivalent to nodes().contains(nodeU) && successors(nodeU).contains(nodeV).

In an undirected graph, this is equal to hasEdgeConnecting(nodeV, nodeU).

Annotations
@Override
hasEdgeConnectingback to summary
public boolean hasEdgeConnecting(EndpointPair<N> endpoints)

Overrides com.google.common.graph.AbstractBaseGraph.hasEdgeConnecting.

Implements com.google.common.graph.ValueGraph.hasEdgeConnecting, com.google.common.graph.BaseGraph.hasEdgeConnecting.

Doc from com.google.common.graph.ValueGraph.hasEdgeConnecting.

Returns true if there is an edge that directly connects endpoints (in the order, if any, specified by endpoints). This is equivalent to edges().contains(endpoints).

Unlike the other EndpointPair-accepting methods, this method does not throw if the endpoints are unordered and the graph is directed; it simply returns false. This is for consistency with the behavior of Collection#contains(Object) (which does not generally throw if the object cannot be present in the collection), and the desire to have this method's behavior be compatible with edges().contains(endpoints).

Annotations
@Override
hasEdgeConnectingInternalback to summary
private final boolean hasEdgeConnectingInternal(N nodeU, N nodeV)
incidentEdgesback to summary
public Set<EndpointPair<N>> incidentEdges(N node)

Overrides com.google.common.graph.AbstractBaseGraph.incidentEdges.

Implements com.google.common.graph.ValueGraph.incidentEdges, com.google.common.graph.BaseGraph.incidentEdges.

Doc from com.google.common.graph.ValueGraph.incidentEdges.

Returns a live view of the edges in this graph whose endpoints include node.

This is equal to the union of incoming and outgoing edges.

If node is removed from the graph after this method is called, the Set view returned by this method will be invalidated, and will throw IllegalStateException if it is accessed in any way, with the following exceptions:

  • view.equals(view) evaluates to true (but any other `equals()` expression involving view will throw)
  • hashCode() does not throw
  • if node is re-added to the graph after having been removed, view's behavior is undefined
Annotations
@Override
isDirectedback to summary
public boolean isDirected()

Implements com.google.common.graph.ValueGraph.isDirected, com.google.common.graph.BaseGraph.isDirected.

Doc from com.google.common.graph.ValueGraph.isDirected.

Returns true if the edges in this graph are directed. Directed edges connect a source node to a target node, while undirected edges connect a pair of nodes to each other.

Annotations
@Override
nodeOrderback to summary
public ElementOrder<N> nodeOrder()

Implements com.google.common.graph.ValueGraph.nodeOrder, com.google.common.graph.BaseGraph.nodeOrder.

Doc from com.google.common.graph.ValueGraph.nodeOrder.

Returns the order of iteration for the elements of nodes().

Annotations
@Override
nodesback to summary
public Set<N> nodes()

Implements com.google.common.graph.ValueGraph.nodes, com.google.common.graph.BaseGraph.nodes.

Doc from com.google.common.graph.ValueGraph.nodes.

Returns all nodes in this graph, in the order specified by nodeOrder().

Annotations
@Override
predecessorsback to summary
public Set<N> predecessors(N node)

Implements com.google.common.graph.ValueGraph.predecessors, com.google.common.graph.BaseGraph.predecessors.

Doc from com.google.common.graph.ValueGraph.predecessors.

Returns a live view of 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.

In an undirected graph, this is equivalent to adjacentNodes(Object).

If node is removed from the graph after this method is called, the `Set` returned by this method will be invalidated, and will throw `IllegalStateException` if it is accessed in any way.

Annotations
@Override
successorsback to summary
public Set<N> successors(N node)

Implements com.google.common.graph.ValueGraph.successors, com.google.common.graph.BaseGraph.successors.

Doc from com.google.common.graph.ValueGraph.successors.

Returns a live view of 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.

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).

If node is removed from the graph after this method is called, the Set view returned by this method will be invalidated, and will throw IllegalStateException if it is accessed in any way, with the following exceptions:

  • view.equals(view) evaluates to true (but any other `equals()` expression involving view will throw)
  • hashCode() does not throw
  • if node is re-added to the graph after having been removed, view's behavior is undefined
Annotations
@Override