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

Java example source code file (Graph.java)

This example Java source code file (Graph.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

annotation, beta, elementorder, graph, object, override, set, util

The Graph.java Java example source code

/*
 * Copyright (C) 2014 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 com.google.common.annotations.Beta;

import java.util.Set;

import javax.annotation.Nullable;

/**
 * A graph consisting of a set of nodes of type N and a set of (implicit) edges.
 * Users that want edges to be first-class objects should use the subtype {@link Network} instead.
 *
 * <p>For convenience, we may use the term 'graph' to refer to any subtype of {@link Graph},
 * including {@link Network}.
 *
 * <p>Users that wish to modify a {@code Graph} must work with its subinterface,
 * {@link MutableNetwork}.
 *
 * <p>This interface permits, but does not enforce, any of the following variations of graphs:
 * <ul>
 * <li>directed and undirected edges
 * <li>nodes and edges with attributes (for example, weighted edges)
 * <li>nodes and edges of different types (for example, bipartite or multimodal graphs)
 * <li>internal representations as matrices, adjacency lists, adjacency maps, etc.
 * </ul>
 *
 * <p>Extensions or implementations of this interface may enforce or disallow any or all
 * of these variations.
 *
 * <p>Definitions:
 * <ul>
 * <li>{@code nodeA} and {@code nodeB} are mutually adjacent (or connected) in
 *     {@code graph} if an edge has been added between them:
 *     <br>

 *       graph.addEdge(nodeA, nodeB);  // after this returns, nodeA and nodeB are adjacent
 *     </pre>
 *   In this example, if {@code graph} is <b>directed, then:
 *   <ul>
 *   <li>{@code nodeA} is a predecessor of {code nodeB} in {@code graph}
 *   <li>{@code nodeB} is a successor of {@code nodeA} in {@code graph}
 *   <li>{@code nodeA} has an (implicit) outgoing edge to {@code nodeB} in {@code graph}
 *   <li>{@code nodeB} has an (implicit) incoming edge from {@code nodeA} in {@code graph}
 *   </ul>
 *   If {@code graph} is <b>undirected, then:
 *   <ul>
 *   <li>{@code nodeA} and {@code nodeB} are mutually predecessors and successors
 *       in {@code graph}
 *   <li>{@code nodeA} has an (implicit) edge in {@code graph} that is both outgoing to
 *       to {@code nodeB} and incoming from {@code nodeB}, and vice versa.
 *   </ul>
 * <li>A self-loop is an edge that connects a node to itself.
 * </ul>
 *
 * <p>General notes:
 * <ul>
 * <li>Nodes must be useable as {@code Map} keys:
 *   <ul>
 *   <li>They must be unique in a graph: nodes {@code nodeA} and {@code nodeB} are considered
 *       different if and only if {@code nodeA.equals(nodeB) == false}.
 *   <li>If graph elements have mutable state:
 *     <ul>
 *     <li>the mutable state must not be reflected in the {@code equals/hashCode} methods
 *         (this is discussed in the {@code Map} documentation in detail)
 *     <li>don't construct multiple elements that are equal to each other and expect them to be
 *         interchangeable.  In particular, when adding such elements to a graph, you should
 *         create them once and store the reference if you will need to refer to those elements
 *         more than once during creation (rather than passing {@code new MyMutableNode(id)}
 *         to each {@code add*()} call).
 *     </ul>
 *   </ul>
 *   <br>Generally speaking, your design may be more robust if you use immutable nodes and
 * store mutable per-element state in a separate data structure (e.g. an element-to-state map).
 * <li>There are no Node classes built in.  So you can have a {@code Graph}
 *     or a {@code Graph<Author>} or a {@code Graph}.
 * <li>This framework supports multiple mechanisms for storing the topology of a graph,
 *      including:
 *   <ul>
 *   <li>the Graph implementation stores the topology (for example, by storing a
 *       {@code Map<N, N>} that maps nodes onto their adjacent nodes); this implies that the nodes
 *       are just keys, and can be shared among graphs
 *   <li>the nodes store the topology (for example, by storing a {@code List} of adjacent nodes);
 *       this (usually) implies that nodes are graph-specific
 *   <li>a separate data repository (for example, a database) stores the topology
 *   </ul>
 * </ul>
 *
 * <p>Notes on accessors:
 * <ul>
 * <li>Accessors which return collections may return views of the Graph. Modifications to the graph
 *     which affect a view (e.g. calling {@code addNode(n)} or {@code removeNode(n)} while iterating
 *     through {@code nodes()}) are not supported and may result in ConcurrentModificationException.
 * <li>Accessors which return collections will return empty collections if their inputs are valid
 *     but no elements satisfy the request (for example: {@code adjacentNodes(node)} will return an
 *     empty collection if {@code node} has no adjacent nodes).
 * <li>Accessors will throw {@code IllegalArgumentException} if passed an element
 *     that is not in the graph.
 * <li>Accessors take Object parameters rather than generic type specifiers to match the pattern
 *     set by the Java Collections Framework.
 * </ul>
 *
 * <p>Notes for implementors:
 * <ul>
 * <li>For accessors that return a {@code Set}, there are several options for the set behavior,
 *     including:
 *     <ol>
 *     <li>Set is an immutable copy (e.g. {@code ImmutableSet}): attempts to modify the set in any
 *         way will throw an exception, and modifications to the graph will <b>not be reflected
 *         in the set.
 *     <li>Set is an unmodifiable view (e.g. {@code Collections.unmodifiableSet()}): attempts to
 *         modify the set in any way will throw an exception, and modifications to the graph will be
 *         reflected in the set.
 *     <li>Set is a mutable copy: it may be modified, but modifications to the graph will not
 *         be reflected in the set, and vice versa.
 *     <li>Set is a modifiable view: it may be modified, and modifications to the graph will be
 *         reflected in the set (but modifications to the set will <b>not be reflected in the
 *         graph).
 *     <li>Set exposes the internal data directly: it may be modified, and modifications to the
 *         graph will be reflected in the set, and vice versa.
 *     </ol>
 *     Note that (1) and (2) are generally preferred. (5) is generally a hazardous design choice
 *     and should be avoided, because keeping the internal data structures consistent can be tricky.
 * <li>Prefer extending {@link AbstractGraph} over implementing {@link Graph} directly. This will
 *     ensure consistent {@link #equals(Object)} and {@link #hashCode()} across implementations.
 * <li>{@code Multimap}s are not sufficient internal data structures for Graph implementations
 *     that support isolated nodes (nodes that have no incident edges), due to their restriction
 *     that a key either maps to at least one value, or is not present in the {@code Multimap}.
 * </ul>
 *
 * <p>Examples of use:
 * <ul>
 * <li>Is {@code node} in the graph?
 * <pre>
 *   graph.nodes().contains(node)
 * </code>
* <li>Traversing an undirected graph node-wise: * <pre> * // Visit nodes reachable from {@code node}. * void depthFirstTraverse(N node) { * if (!isVisited(node)) { * visit(node); * for (N successor : graph.successors(node)) { * depthFirstTraverse(successor); * } * } * } * </code>
* </ul> * * @author Joshua O'Madadhain * @param <N> Node parameter type * @since 20.0 */ @Beta public interface Graph<N> { /** * Returns all nodes in this graph, in the order specified by {@link #nodeOrder()}. */ Set<N> nodes(); // // Graph properties // /** * Returns true if the edges in this graph have a direction associated with them. */ boolean isDirected(); /** * 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 * {@link UnsupportedOperationException}. */ boolean allowsSelfLoops(); /** * Returns the order of iteration for the elements of {@link #nodes()}. */ ElementOrder<? super N> nodeOrder(); // // Element-level accessors // /** * Returns the nodes which have an incident edge in common with {@code node} in this graph. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ Set<N> adjacentNodes(Object node); /** * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing * {@code node}'s incoming edges <i>against the direction (if any) of the edge. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ Set<N> predecessors(Object node); /** * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing * {@code node}'s outgoing edges in the direction (if any) of the edge. * * <p>This is not the same as "all nodes reachable from {@code node} by following outgoing * edges" (also known as {@code node}'s transitive closure). * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ Set<N> successors(Object node); // // Element-level queries // /** * Returns the number of edges incident in this graph to {@code node}. If this node has more than * {@code Integer.MAX_VALUE} incident edges in this graph, returns {@code Integer.MAX_VALUE}. * * <p>Note that self-loops only count once towards a node's degree. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ int degree(Object node); /** * Returns the number of incoming edges in this graph of {@code node}. If this node has more than * {@code Integer.MAX_VALUE} incoming edges in this graph, returns {@code Integer.MAX_VALUE}. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ int inDegree(Object node); /** * Returns the number of outgoing edges in this graph of {@code node}. If this node has more than * {@code Integer.MAX_VALUE} outgoing edges in this graph, returns {@code Integer.MAX_VALUE}. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ int outDegree(Object node); /** * Returns {@code true} iff {@code object} is a graph that has the same node relationships * as those in this graph. * * <p>Thus, two graphs A and B are equal if all of the following are true: * <ul> * <li>A and B have the same node set * <li>A and B have the same adjacency relationships, e.g., for each {@code node} the sets of * successor and predecessor nodes are the same in both graphs. * <br>This implies that every edge in A and B connects the same nodes in the same * direction (if any). * </ul> * * <p>Graph properties are not respected by this method. For example, two relations may * be considered equal even if one allows self-loops and the other doesn't. Additionally, the * order in which edges or nodes are added to the graph, and the order in which they are * iterated over, are irrelevant. * * <p>A reference implementation of this is provided by {@link Graphs#equal(Graph, Graph)}. */ @Override boolean equals(@Nullable Object object); /** * Returns the hash code for this graph. The hash code of a graph is defined as the hash code * of a map from each of the graph's nodes to their adjacent nodes. * * <p>A reference implementation of this is provided by {@link Graphs#hashCode(Graph)}. * * <p>Note that by this definition, two graphs that are equal in every aspect except edge * direction will have the same hash code (but can still be differentiated by * {@link #equals(Object)}. */ @Override int hashCode(); }

Other Java examples (source code examples)

Here is a short list of links related to this Java Graph.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.