View Javadoc
1   /*
2    * Copyright (C) 2016 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.graph;
18  
19  import static com.google.common.base.Preconditions.checkArgument;
20  import static com.google.common.base.Preconditions.checkNotNull;
21  import static com.google.common.graph.GraphConstants.DEFAULT_EDGE_COUNT;
22  import static com.google.common.graph.GraphConstants.DEFAULT_NODE_COUNT;
23  import static com.google.common.graph.GraphConstants.EDGE_NOT_IN_GRAPH;
24  import static com.google.common.graph.GraphConstants.NODE_NOT_IN_GRAPH;
25  
26  import com.google.common.collect.ImmutableSet;
27  import java.util.Map;
28  import java.util.Set;
29  import java.util.TreeMap;
30  import javax.annotation.Nullable;
31  
32  /**
33   * Configurable implementation of {@link Network} that supports the options supplied by {@link
34   * NetworkBuilder}.
35   *
36   * <p>This class maintains a map of nodes to {@link NetworkConnections}. This class also maintains a
37   * map of edges to reference nodes. The reference node is defined to be the edge's source node on
38   * directed graphs, and an arbitrary endpoint of the edge on undirected graphs.
39   *
40   * <p>Collection-returning accessors return unmodifiable views: the view returned will reflect
41   * changes to the graph (if the graph is mutable) but may not be modified by the user.
42   *
43   * <p>The time complexity of all collection-returning accessors is O(1), since views are returned.
44   *
45   * @author James Sexton
46   * @author Joshua O'Madadhain
47   * @author Omar Darwish
48   * @param <N> Node parameter type
49   * @param <E> Edge parameter type
50   */
51  class ConfigurableNetwork<N, E> extends AbstractNetwork<N, E> {
52    private final boolean isDirected;
53    private final boolean allowsParallelEdges;
54    private final boolean allowsSelfLoops;
55    private final ElementOrder<N> nodeOrder;
56    private final ElementOrder<E> edgeOrder;
57  
58    protected final MapIteratorCache<N, NetworkConnections<N, E>> nodeConnections;
59  
60    // We could make this a Map<E, EndpointPair<N>>. It would make incidentNodes(edge) slightly
61    // faster, but also make Networks consume 5 to 20+% (increasing with average degree) more memory.
62    protected final MapIteratorCache<E, N> edgeToReferenceNode; // referenceNode == source if directed
63  
64    /** Constructs a graph with the properties specified in {@code builder}. */
65    ConfigurableNetwork(NetworkBuilder<? super N, ? super E> builder) {
66      this(
67          builder,
68          builder.nodeOrder.<N, NetworkConnections<N, E>>createMap(
69              builder.expectedNodeCount.or(DEFAULT_NODE_COUNT)),
70          builder.edgeOrder.<E, N>createMap(builder.expectedEdgeCount.or(DEFAULT_EDGE_COUNT)));
71    }
72  
73    /**
74     * Constructs a graph with the properties specified in {@code builder}, initialized with the given
75     * node and edge maps.
76     */
77    ConfigurableNetwork(
78        NetworkBuilder<? super N, ? super E> builder,
79        Map<N, NetworkConnections<N, E>> nodeConnections,
80        Map<E, N> edgeToReferenceNode) {
81      this.isDirected = builder.directed;
82      this.allowsParallelEdges = builder.allowsParallelEdges;
83      this.allowsSelfLoops = builder.allowsSelfLoops;
84      this.nodeOrder = builder.nodeOrder.cast();
85      this.edgeOrder = builder.edgeOrder.cast();
86      // Prefer the heavier "MapRetrievalCache" for nodes if lookup is expensive. This optimizes
87      // methods that access the same node(s) repeatedly, such as Graphs.removeEdgesConnecting().
88      this.nodeConnections =
89          (nodeConnections instanceof TreeMap)
90              ? new MapRetrievalCache<N, NetworkConnections<N, E>>(nodeConnections)
91              : new MapIteratorCache<N, NetworkConnections<N, E>>(nodeConnections);
92      this.edgeToReferenceNode = new MapIteratorCache<>(edgeToReferenceNode);
93    }
94  
95    @Override
96    public Set<N> nodes() {
97      return nodeConnections.unmodifiableKeySet();
98    }
99  
100   @Override
101   public Set<E> edges() {
102     return edgeToReferenceNode.unmodifiableKeySet();
103   }
104 
105   @Override
106   public boolean isDirected() {
107     return isDirected;
108   }
109 
110   @Override
111   public boolean allowsParallelEdges() {
112     return allowsParallelEdges;
113   }
114 
115   @Override
116   public boolean allowsSelfLoops() {
117     return allowsSelfLoops;
118   }
119 
120   @Override
121   public ElementOrder<N> nodeOrder() {
122     return nodeOrder;
123   }
124 
125   @Override
126   public ElementOrder<E> edgeOrder() {
127     return edgeOrder;
128   }
129 
130   @Override
131   public Set<E> incidentEdges(N node) {
132     return checkedConnections(node).incidentEdges();
133   }
134 
135   @Override
136   public EndpointPair<N> incidentNodes(E edge) {
137     N nodeU = checkedReferenceNode(edge);
138     N nodeV = nodeConnections.get(nodeU).adjacentNode(edge);
139     return EndpointPair.of(this, nodeU, nodeV);
140   }
141 
142   @Override
143   public Set<N> adjacentNodes(N node) {
144     return checkedConnections(node).adjacentNodes();
145   }
146 
147   @Override
148   public Set<E> edgesConnecting(N nodeU, N nodeV) {
149     NetworkConnections<N, E> connectionsU = checkedConnections(nodeU);
150     if (!allowsSelfLoops && nodeU == nodeV) { // just an optimization, only check reference equality
151       return ImmutableSet.of();
152     }
153     checkArgument(containsNode(nodeV), NODE_NOT_IN_GRAPH, nodeV);
154     return connectionsU.edgesConnecting(nodeV);
155   }
156 
157   @Override
158   public Set<E> inEdges(N node) {
159     return checkedConnections(node).inEdges();
160   }
161 
162   @Override
163   public Set<E> outEdges(N node) {
164     return checkedConnections(node).outEdges();
165   }
166 
167   @Override
168   public Set<N> predecessors(N node) {
169     return checkedConnections(node).predecessors();
170   }
171 
172   @Override
173   public Set<N> successors(N node) {
174     return checkedConnections(node).successors();
175   }
176 
177   protected final NetworkConnections<N, E> checkedConnections(N node) {
178     NetworkConnections<N, E> connections = nodeConnections.get(node);
179     if (connections == null) {
180       checkNotNull(node);
181       throw new IllegalArgumentException(String.format(NODE_NOT_IN_GRAPH, node));
182     }
183     return connections;
184   }
185 
186   protected final N checkedReferenceNode(E edge) {
187     N referenceNode = edgeToReferenceNode.get(edge);
188     if (referenceNode == null) {
189       checkNotNull(edge);
190       throw new IllegalArgumentException(String.format(EDGE_NOT_IN_GRAPH, edge));
191     }
192     return referenceNode;
193   }
194 
195   protected final boolean containsNode(@Nullable N node) {
196     return nodeConnections.containsKey(node);
197   }
198 
199   protected final boolean containsEdge(@Nullable E edge) {
200     return edgeToReferenceNode.containsKey(edge);
201   }
202 }