Package com.google.common.graph

Class StandardMutableValueGraph<N,V>

java.lang.Object

com.google.common.graph.AbstractBaseGraph<N>

com.google.common.graph.AbstractValueGraph<N,V>

com.google.common.graph.StandardValueGraph<N,V>

com.google.common.graph.StandardMutableValueGraph<N,V>

Type Parameters:

N - Node parameter type

V - Value parameter type

All Implemented Interfaces:

BaseGraph<N>, MutableValueGraph<N,V>, PredecessorsFunction<N>, SuccessorsFunction<N>, ValueGraph<N,V>

final class StandardMutableValueGraph<N,V>
extends StandardValueGraph<N,V>
implements MutableValueGraph<N,V>

Standard implementation of MutableValueGraph that supports both directed and undirected graphs. Instances of this class should be constructed with ValueGraphBuilder.

Time complexities for mutation methods are all O(1) except for removeNode(N node), which is in O(d_node) where d_node is the degree of node.

Field Summary

Fields

Modifier and Type	Field	Description
private ElementOrder<N>	incidentEdgeOrder

Fields inherited from class com.google.common.graph.StandardValueGraph

edgeCount, nodeConnections

Constructor Summary

Constructors

Constructor	Description
StandardMutableValueGraph(AbstractGraphBuilder<? super N> builder)	Constructs a mutable graph with the properties specified in builder.

Method Summary

Modifier and Type	Method	Description
boolean	addNode(N node)	Adds node if it is not already present.
private GraphConnections<N,V>	addNodeInternal(N node)	Adds node to the graph and returns the associated GraphConnections.
ElementOrder<N>	incidentEdgeOrder()	Returns an ElementOrder that specifies the order of iteration for the elements of BaseGraph.edges(), BaseGraph.adjacentNodes(Object), BaseGraph.predecessors(Object), BaseGraph.successors(Object) and BaseGraph.incidentEdges(Object).
private GraphConnections<N,V>	newConnections()
V	putEdgeValue(EndpointPair<N> endpoints, V value)	Adds an edge connecting endpoints if one is not already present, and sets a value for that edge to value (overwriting the existing value, if any).
V	putEdgeValue(N nodeU, N nodeV, V value)	Adds an edge connecting nodeU to nodeV if one is not already present, and sets a value for that edge to value (overwriting the existing value, if any).
V	removeEdge(EndpointPair<N> endpoints)	Removes the edge connecting endpoints, if it is present.
V	removeEdge(N nodeU, N nodeV)	Removes the edge connecting nodeU to nodeV, if it is present.
boolean	removeNode(N node)	Removes node if it is present; all edges incident to node will also be removed.

Methods inherited from class com.google.common.graph.StandardValueGraph

adjacentNodes, allowsSelfLoops, checkedConnections, containsNode, edgeCount, edgeValueOrDefault, edgeValueOrDefault, edgeValueOrDefault_internal, hasEdgeConnecting, hasEdgeConnecting, hasEdgeConnecting_internal, incidentEdges, isDirected, nodeOrder, nodes, predecessors, successors

Methods inherited from class com.google.common.graph.AbstractValueGraph

asGraph, edgeValue, edgeValue, equals, hashCode, toString

Methods inherited from class com.google.common.graph.AbstractBaseGraph

degree, edges, inDegree, isOrderingCompatible, outDegree, validateEndpoints

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface com.google.common.graph.ValueGraph

adjacentNodes, allowsSelfLoops, asGraph, degree, edges, edgeValue, edgeValue, edgeValueOrDefault, edgeValueOrDefault, equals, hasEdgeConnecting, hasEdgeConnecting, hashCode, incidentEdges, inDegree, isDirected, nodeOrder, nodes, outDegree, predecessors, successors

Field Detail

incidentEdgeOrder

private final ElementOrder<N> incidentEdgeOrder

Constructor Detail

StandardMutableValueGraph

StandardMutableValueGraph(AbstractGraphBuilder<? super N> builder)

Constructs a mutable graph with the properties specified in builder.

Method Detail

incidentEdgeOrder

public ElementOrder<N> incidentEdgeOrder()

Description copied from interface: BaseGraph

Returns an ElementOrder that specifies the order of iteration for the elements of BaseGraph.edges(), BaseGraph.adjacentNodes(Object), BaseGraph.predecessors(Object), BaseGraph.successors(Object) and BaseGraph.incidentEdges(Object).

Specified by:

incidentEdgeOrder in interface BaseGraph<N>

Specified by:

incidentEdgeOrder in interface ValueGraph<N,V>

Overrides:

incidentEdgeOrder in class AbstractBaseGraph<N>

addNode

public boolean addNode(N node)

Description copied from interface: MutableValueGraph

Adds node if it is not already present.

Nodes must be unique, just as Map keys must be. They must also be non-null.

Specified by:

addNode in interface MutableValueGraph<N,V>

Returns:

true if the graph was modified as a result of this call

addNodeInternal

private GraphConnections<N,V> addNodeInternal(N node)

Adds node to the graph and returns the associated GraphConnections.

Throws:

java.lang.IllegalStateException - if node is already present

putEdgeValue

public V putEdgeValue(N nodeU,
                      N nodeV,
                      V value)

Description copied from interface: MutableValueGraph

Adds an edge connecting nodeU to nodeV if one is not already present, and sets a value for that edge to value (overwriting the existing value, if any).

If the graph is directed, the resultant edge will be directed; otherwise, it will be undirected.

Values do not have to be unique. However, values must be non-null.

If nodeU and nodeV are not already present in this graph, this method will silently add nodeU and nodeV to the graph.

Specified by:

putEdgeValue in interface MutableValueGraph<N,V>

Returns:

the value previously associated with the edge connecting nodeU to nodeV, or null if there was no such edge.

putEdgeValue

public V putEdgeValue(EndpointPair<N> endpoints,
                      V value)

Description copied from interface: MutableValueGraph

Adds an edge connecting endpoints if one is not already present, and sets a value for that edge to value (overwriting the existing value, if any).

If the graph is directed, the resultant edge will be directed; otherwise, it will be undirected.

If this graph is directed, endpoints must be ordered.

Values do not have to be unique. However, values must be non-null.

If either or both endpoints are not already present in this graph, this method will silently add each missing endpoint to the graph.

Specified by:

putEdgeValue in interface MutableValueGraph<N,V>

Returns:

the value previously associated with the edge connecting nodeU to nodeV, or null if there was no such edge.

removeNode

public boolean removeNode(N node)

Description copied from interface: MutableValueGraph

Removes node if it is present; all edges incident to node will also be removed.

Specified by:

removeNode in interface MutableValueGraph<N,V>

Returns:

true if the graph was modified as a result of this call

removeEdge

public V removeEdge(N nodeU,
                    N nodeV)

Description copied from interface: MutableValueGraph

Removes the edge connecting nodeU to nodeV, if it is present.

Specified by:

removeEdge in interface MutableValueGraph<N,V>

Returns:

the value previously associated with the edge connecting nodeU to nodeV, or null if there was no such edge.

removeEdge

public V removeEdge(EndpointPair<N> endpoints)

Description copied from interface: MutableValueGraph

Removes the edge connecting endpoints, if it is present.

If this graph is directed, endpoints must be ordered.

Specified by:

removeEdge in interface MutableValueGraph<N,V>

Returns:

the value previously associated with the edge connecting endpoints, or null if there was no such edge.

newConnections

private GraphConnections<N,V> newConnections()