001/*
002 * Copyright (C) 2016 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.graph;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.graph.Graphs.checkNonNegative;
022
023import com.google.common.annotations.Beta;
024import com.google.common.base.Optional;
025
026/**
027 * A builder for constructing instances of {@link MutableValueGraph} or {@link ImmutableValueGraph}
028 * with user-defined properties.
029 *
030 * <p>A graph built by this class will have the following properties by default:
031 *
032 * <ul>
033 *   <li>does not allow self-loops
034 *   <li>orders {@link Graph#nodes()} in the order in which the elements were added
035 * </ul>
036 *
037 * <p>Examples of use:
038 *
039 * <pre>{@code
040 * // Building a mutable value graph
041 * MutableValueGraph<String, Double> graph =
042 *     ValueGraphBuilder.undirected().allowsSelfLoops(true).build();
043 * graph.putEdgeValue("San Francisco", "San Francisco", 0.0);
044 * graph.putEdgeValue("San Jose", "San Jose", 0.0);
045 * graph.putEdgeValue("San Francisco", "San Jose", 48.4);
046 *
047 * // Building an immutable value graph
048 * ImmutableValueGraph<String, Double> immutableGraph =
049 *     ValueGraphBuilder.undirected()
050 *         .allowsSelfLoops(true)
051 *         .<String, Double>immutable()
052 *         .putEdgeValue("San Francisco", "San Francisco", 0.0)
053 *         .putEdgeValue("San Jose", "San Jose", 0.0)
054 *         .putEdgeValue("San Francisco", "San Jose", 48.4)
055 *         .build();
056 * }</pre>
057 *
058 * @author James Sexton
059 * @author Joshua O'Madadhain
060 * @param <N> The most general node type this builder will support. This is normally {@code Object}
061 *     unless it is constrained by using a method like {@link #nodeOrder}, or the builder is
062 *     constructed based on an existing {@code ValueGraph} using {@link #from(ValueGraph)}.
063 * @param <V> The most general value type this builder will support. This is normally {@code Object}
064 *     unless the builder is constructed based on an existing {@code Graph} using {@link
065 *     #from(ValueGraph)}.
066 * @since 20.0
067 */
068@Beta
069public final class ValueGraphBuilder<N, V> extends AbstractGraphBuilder<N> {
070
071  /** Creates a new instance with the specified edge directionality. */
072  private ValueGraphBuilder(boolean directed) {
073    super(directed);
074  }
075
076  /** Returns a {@link ValueGraphBuilder} for building directed graphs. */
077  public static ValueGraphBuilder<Object, Object> directed() {
078    return new ValueGraphBuilder<>(true);
079  }
080
081  /** Returns a {@link ValueGraphBuilder} for building undirected graphs. */
082  public static ValueGraphBuilder<Object, Object> undirected() {
083    return new ValueGraphBuilder<>(false);
084  }
085
086  /**
087   * Returns a {@link ValueGraphBuilder} initialized with all properties queryable from {@code
088   * graph}.
089   *
090   * <p>The "queryable" properties are those that are exposed through the {@link ValueGraph}
091   * interface, such as {@link ValueGraph#isDirected()}. Other properties, such as {@link
092   * #expectedNodeCount(int)}, are not set in the new builder.
093   */
094  public static <N, V> ValueGraphBuilder<N, V> from(ValueGraph<N, V> graph) {
095    return new ValueGraphBuilder<N, V>(graph.isDirected())
096        .allowsSelfLoops(graph.allowsSelfLoops())
097        .nodeOrder(graph.nodeOrder())
098        .incidentEdgeOrder(graph.incidentEdgeOrder());
099  }
100
101  /**
102   * Returns an {@link ImmutableValueGraph.Builder} with the properties of this {@link
103   * ValueGraphBuilder}.
104   *
105   * <p>The returned builder can be used for populating an {@link ImmutableValueGraph}.
106   *
107   * <p>Note that the returned builder will always have {@link #incidentEdgeOrder} set to {@link
108   * ElementOrder#stable()}, regardless of the value that was set in this builder.
109   *
110   * @since 28.0
111   */
112  public <N1 extends N, V1 extends V> ImmutableValueGraph.Builder<N1, V1> immutable() {
113    ValueGraphBuilder<N1, V1> castBuilder = cast();
114    return new ImmutableValueGraph.Builder<>(castBuilder);
115  }
116
117  /**
118   * Specifies whether the graph will allow self-loops (edges that connect a node to itself).
119   * Attempting to add a self-loop to a graph that does not allow them will throw an {@link
120   * UnsupportedOperationException}.
121   *
122   * <p>The default value is {@code false}.
123   */
124  public ValueGraphBuilder<N, V> allowsSelfLoops(boolean allowsSelfLoops) {
125    this.allowsSelfLoops = allowsSelfLoops;
126    return this;
127  }
128
129  /**
130   * Specifies the expected number of nodes in the graph.
131   *
132   * @throws IllegalArgumentException if {@code expectedNodeCount} is negative
133   */
134  public ValueGraphBuilder<N, V> expectedNodeCount(int expectedNodeCount) {
135    this.expectedNodeCount = Optional.of(checkNonNegative(expectedNodeCount));
136    return this;
137  }
138
139  /**
140   * Specifies the order of iteration for the elements of {@link Graph#nodes()}.
141   *
142   * <p>The default value is {@link ElementOrder#insertion() insertion order}.
143   */
144  public <N1 extends N> ValueGraphBuilder<N1, V> nodeOrder(ElementOrder<N1> nodeOrder) {
145    ValueGraphBuilder<N1, V> newBuilder = cast();
146    newBuilder.nodeOrder = checkNotNull(nodeOrder);
147    return newBuilder;
148  }
149
150  /**
151   * Specifies the order of iteration for the elements of {@link ValueGraph#edges()}, {@link
152   * ValueGraph#adjacentNodes(Object)}, {@link ValueGraph#predecessors(Object)}, {@link
153   * ValueGraph#successors(Object)} and {@link ValueGraph#incidentEdges(Object)}.
154   *
155   * <p>The default value is {@link ElementOrder#unordered() unordered} for mutable graphs. For
156   * immutable graphs, this value is ignored; they always have a {@link ElementOrder#stable()
157   * stable} order.
158   *
159   * @throws IllegalArgumentException if {@code incidentEdgeOrder} is not either {@code
160   *     ElementOrder.unordered()} or {@code ElementOrder.stable()}.
161   * @since 29.0
162   */
163  public <N1 extends N> ValueGraphBuilder<N1, V> incidentEdgeOrder(
164      ElementOrder<N1> incidentEdgeOrder) {
165    checkArgument(
166        incidentEdgeOrder.type() == ElementOrder.Type.UNORDERED
167            || incidentEdgeOrder.type() == ElementOrder.Type.STABLE,
168        "The given elementOrder (%s) is unsupported. incidentEdgeOrder() only supports"
169            + " ElementOrder.unordered() and ElementOrder.stable().",
170        incidentEdgeOrder);
171    ValueGraphBuilder<N1, V> newBuilder = cast();
172    newBuilder.incidentEdgeOrder = checkNotNull(incidentEdgeOrder);
173    return newBuilder;
174  }
175  /**
176   * Returns an empty {@link MutableValueGraph} with the properties of this {@link
177   * ValueGraphBuilder}.
178   */
179  public <N1 extends N, V1 extends V> MutableValueGraph<N1, V1> build() {
180    return new StandardMutableValueGraph<>(this);
181  }
182
183  ValueGraphBuilder<N, V> copy() {
184    ValueGraphBuilder<N, V> newBuilder = new ValueGraphBuilder<>(directed);
185    newBuilder.allowsSelfLoops = allowsSelfLoops;
186    newBuilder.nodeOrder = nodeOrder;
187    newBuilder.expectedNodeCount = expectedNodeCount;
188    newBuilder.incidentEdgeOrder = incidentEdgeOrder;
189    return newBuilder;
190  }
191
192  @SuppressWarnings("unchecked")
193  private <N1 extends N, V1 extends V> ValueGraphBuilder<N1, V1> cast() {
194    return (ValueGraphBuilder<N1, V1>) this;
195  }
196}