alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Java example source code file (ConfigurableMutableGraph.java)

This example Java source code file (ConfigurableMutableGraph.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

abstractconfigurablegraph, canignorereturnvalue, configurablemutablegraph, nodeadjacencies, object, override, self_loops_not_allowed

The ConfigurableMutableGraph.java Java example source code

/*
 * Copyright (C) 2016 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.graph;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.graph.GraphConstants.SELF_LOOPS_NOT_ALLOWED;

import com.google.errorprone.annotations.CanIgnoreReturnValue;

/**
 * Configurable implementation of {@link MutableGraph} that supports both directed and undirected
 * graphs. Instances of this class should be constructed with {@link GraphBuilder}.
 *
 * <p>Time complexities for mutation methods are all O(1) except for {@code removeNode(N node)},
 * which is in O(d_node) where d_node is the degree of {@code node}.
 *
 * @author James Sexton
 * @author Joshua O'Madadhain
 * @author Omar Darwish
 * @param <N> Node parameter type
 */
final class ConfigurableMutableGraph<N>
    extends AbstractConfigurableGraph<N> implements MutableGraph {

  /**
   * Constructs a mutable graph with the properties specified in {@code builder}.
   */
  ConfigurableMutableGraph(GraphBuilder<? super N> builder) {
    super(builder);
  }

  @Override
  @CanIgnoreReturnValue
  public boolean addNode(N node) {
    checkNotNull(node, "node");
    if (containsNode(node)) {
      return false;
    }
    addNodeInternal(node);
    return true;
  }

  /**
   * Adds {@code node} to the graph and returns the associated {@link NodeAdjacencies}.
   *
   * @throws IllegalStateException if {@code node} is already present
   */
  @CanIgnoreReturnValue
  private NodeAdjacencies<N> addNodeInternal(N node) {
    NodeAdjacencies<N> connections = newNodeConnections();
    checkState(nodeConnections.put(node, connections) == null);
    return connections;
  }

  /**
   * Add an edge between {@code nodeA} and {@code nodeB}; if these nodes are not already
   * present in this graph, then add them.
   * Return {@code false} if an edge already exists between {@code nodeA} and {@code nodeB},
   * and in the same direction.
   *
   * @throws IllegalArgumentException if self-loops are not allowed, and {@code nodeA} is equal to
   *     {@code nodeB}.
   */
  @Override
  @CanIgnoreReturnValue
  public boolean addEdge(N nodeA, N nodeB) {
    checkNotNull(nodeA, "nodeA");
    checkNotNull(nodeB, "nodeB");

    NodeAdjacencies<N> connectionsA = nodeConnections.get(nodeA);
    // TODO(b/28087289): does not support parallel edges
    if (connectionsA != null && connectionsA.successors().contains(nodeB)) {
      return false;
    }
    NodeAdjacencies<N> connectionsB = nodeConnections.get(nodeB);
    boolean isSelfLoop = nodeA.equals(nodeB);
    if (!allowsSelfLoops()) {
      checkArgument(!isSelfLoop, SELF_LOOPS_NOT_ALLOWED, nodeA);
    }

    if (connectionsA == null) {
      connectionsA = addNodeInternal(nodeA);
    }
    connectionsA.addSuccessor(nodeB);
    if (connectionsB == null) {
      connectionsB = isSelfLoop ? connectionsA : addNodeInternal(nodeB);
    }
    connectionsB.addPredecessor(nodeA);
    return true;
  }

  @Override
  @CanIgnoreReturnValue
  public boolean removeNode(Object node) {
    checkNotNull(node, "node");
    NodeAdjacencies<N> connections = nodeConnections.get(node);
    if (connections == null) {
      return false;
    }
    if (allowsSelfLoops()) {
      // Remove any potential self-loop first so we won't get CME while removing incident edges.
      connections.removeSuccessor(node);
      connections.removePredecessor(node);
    }
    for (N successor : connections.successors()) {
      nodeConnections.get(successor).removePredecessor(node);
    }
    for (N predecessor : connections.predecessors()) {
      nodeConnections.get(predecessor).removeSuccessor(node);
    }
    nodeConnections.remove(node);
    return true;
  }

  @Override
  @CanIgnoreReturnValue
  public boolean removeEdge(Object nodeA, Object nodeB) {
    checkNotNull(nodeA, "nodeA");
    checkNotNull(nodeB, "nodeB");
    NodeAdjacencies<N> connectionsA = nodeConnections.get(nodeA);
    if (connectionsA == null || !connectionsA.successors().contains(nodeB)) {
      return false;
    }
    NodeAdjacencies<N> connectionsB = nodeConnections.get(nodeB);
    connectionsA.removeSuccessor(nodeB);
    connectionsB.removePredecessor(nodeA);
    return true;
  }

  private NodeAdjacencies<N> newNodeConnections() {
    return isDirected()
        ? DirectedNodeAdjacencies.<N>of()
        : UndirectedNodeAdjacencies.<N>of();
  }
}

Other Java examples (source code examples)

Here is a short list of links related to this Java ConfigurableMutableGraph.java source code file:

... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.