Package com.google.common.graph

Class ConfigurableValueGraph<N,V>

java.lang.Object

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

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

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

Type Parameters:

N - Node parameter type

V - Value parameter type

All Implemented Interfaces:

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

Direct Known Subclasses:

ConfigurableMutableValueGraph, ImmutableValueGraph

class ConfigurableValueGraph<N,V>
extends AbstractValueGraph<N,V>

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

Field Summary

Fields

Modifier and Type	Field	Description
private boolean	allowsSelfLoops
protected long	edgeCount
private boolean	isDirected
protected MapIteratorCache<N,GraphConnections<N,V>>	nodeConnections
private ElementOrder<N>	nodeOrder

Constructor Summary

Constructors

Constructor	Description
ConfigurableValueGraph(AbstractGraphBuilder<? super N> builder)	Constructs a graph with the properties specified in builder.
ConfigurableValueGraph(AbstractGraphBuilder<? super N> builder, java.util.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 Type	Method	Description
java.util.Set<N>	adjacentNodes(N 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).
protected GraphConnections<N,V>	checkedConnections(N node)
protected boolean	containsNode(N node)
protected long	edgeCount()	Returns the number of edges in this graph; used to calculate the size of AbstractBaseGraph.edges().
V	edgeValueOrDefault(EndpointPair<N> endpoints, V defaultValue)	Returns the value of the edge that connects endpoints (in the order, if any, specified by endpoints), if one is present; otherwise, returns defaultValue.
V	edgeValueOrDefault(N nodeU, N nodeV, V defaultValue)	Returns the value of the edge that connects nodeU to nodeV, if one is present; otherwise, returns defaultValue.
protected V	edgeValueOrDefault_internal(N nodeU, N nodeV, V defaultValue)
boolean	hasEdgeConnecting(EndpointPair<N> endpoints)	Returns true if there is an edge that directly connects endpoints (in the order, if any, specified by endpoints).
boolean	hasEdgeConnecting(N nodeU, N nodeV)	Returns true if there is an edge that directly connects nodeU to nodeV.
protected boolean	hasEdgeConnecting_internal(N nodeU, N nodeV)
boolean	isDirected()	Returns true if the edges in this graph are directed.
ElementOrder<N>	nodeOrder()	Returns the order of iteration for the elements of ValueGraph.nodes().
java.util.Set<N>	nodes()	Returns all nodes in this graph, in the order specified by ValueGraph.nodeOrder().
java.util.Set<N>	predecessors(N 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.
java.util.Set<N>	successors(N 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.

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, incidentEdges, 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

degree, edges, incidentEdges, inDegree, outDegree

Field Detail

isDirected

private final boolean isDirected

allowsSelfLoops

private final boolean allowsSelfLoops

nodeOrder

private final ElementOrder<N> nodeOrder

nodeConnections

protected final MapIteratorCache<N,GraphConnections<N,V>> nodeConnections

edgeCount

protected long edgeCount

Constructor Detail

ConfigurableValueGraph

ConfigurableValueGraph(AbstractGraphBuilder<? super N> builder)

Constructs a graph with the properties specified in builder.

ConfigurableValueGraph

ConfigurableValueGraph(AbstractGraphBuilder<? super N> builder,
                       java.util.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

nodes

public java.util.Set<N> nodes()

Description copied from interface: ValueGraph

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

isDirected

public boolean isDirected()

Description copied from interface: ValueGraph

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.

allowsSelfLoops

public boolean allowsSelfLoops()

Description copied from interface: ValueGraph

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.

nodeOrder

public ElementOrder<N> nodeOrder()

Description copied from interface: ValueGraph

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

adjacentNodes

public java.util.Set<N> adjacentNodes(N node)

Description copied from interface: ValueGraph

Returns the nodes which have an incident edge in common with node in this graph.

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

predecessors

public java.util.Set<N> predecessors(N node)

Description copied from interface: ValueGraph

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.

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

successors

public java.util.Set<N> successors(N node)

Description copied from interface: ValueGraph

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.

In an undirected graph, this is equivalent to ValueGraph.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).

hasEdgeConnecting

public boolean hasEdgeConnecting(N nodeU,
                                 N nodeV)

Description copied from interface: BaseGraph

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

Specified by:

hasEdgeConnecting in interface BaseGraph<N>

Specified by:

hasEdgeConnecting in interface ValueGraph<N,V>

Overrides:

hasEdgeConnecting in class AbstractBaseGraph<N>

hasEdgeConnecting

public boolean hasEdgeConnecting(EndpointPair<N> endpoints)

Description copied from interface: BaseGraph

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

Specified by:

hasEdgeConnecting in interface BaseGraph<N>

Specified by:

hasEdgeConnecting in interface ValueGraph<N,V>

Overrides:

hasEdgeConnecting in class AbstractBaseGraph<N>

edgeValueOrDefault

public V edgeValueOrDefault(N nodeU,
                            N nodeV,
                            V defaultValue)

Description copied from interface: ValueGraph

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

edgeValueOrDefault

public V edgeValueOrDefault(EndpointPair<N> endpoints,
                            V defaultValue)

Description copied from interface: ValueGraph

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.

edgeCount

protected long edgeCount()

Description copied from class: AbstractBaseGraph

Returns the number of edges in this graph; used to calculate the size of AbstractBaseGraph.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.

Overrides:

edgeCount in class AbstractBaseGraph<N>

checkedConnections

protected final GraphConnections<N,V> checkedConnections(N node)

containsNode

protected final boolean containsNode(N node)

hasEdgeConnecting_internal

protected final boolean hasEdgeConnecting_internal(N nodeU,
                                                   N nodeV)

edgeValueOrDefault_internal

protected final V edgeValueOrDefault_internal(N nodeU,
                                              N nodeV,
                                              V defaultValue)