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

Java example source code file (Network.java)

This example Java source code file (Network.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, endpoints, graph, network, object, override, set, util

The Network.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 network consisting of a set of nodes of type N and a set of edges of type E.
 * That is, a subtype of {@link Graph} that represents edges as explicit first-class objects.
 * Users that are not interested in edges as first-class objects should use a {@link Graph}
 * instead.
 *
 * <p>Users that wish to modify a {@code Network} must work with its subinterface,
 * {@code 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>parallel edges (multiple edges which connect a single set of nodes)
 * </ul>
 *
 * <p>Extensions or implementations of this interface may enforce or disallow any or all
 * of these variations.
 *
 * <p>Definitions:
 * <ul>
 * <li>{@code edge} and {@code node} are incident to each other if the set of
 *     {@code edge}'s endpoints includes {@code node}.
 * <li>{@code nodeA} and {@code nodeB} are mutually adjacent if both are incident
 *     to a common {@code edge}.
 *     <br>Similarly, {@code edge1} and {@code edge2} are mutually adjacent if both are
 *     incident to a common {@code node}.
 * <li>Elements are connected if they are either incident or adjacent.
 * <li>{@code edge} is an incoming edge of a {@code node} if it can be traversed (in
 *     the direction, if any, of {@code edge}) from a node adjacent to {@code node}.
 * <li>{@code edge} is an outgoing edge of {@code node} if it can be traversed (in
 *     the direction, if any, of {@code edge}) from {@code node} to reach a node adjacent to
 *     {@code node}.
 *   <ul>
 *   <li>Note: undirected edges are both incoming and outgoing edges of a {@code node},
 *       while <b>directed edges are either incoming or outgoing edges of {@code node}
 *       (and not both, unless the edge is a self-loop).
 *       <br>Thus, in the following example {@code edge1} is an incoming edge of {@code nodeB} and
 *       an outgoing edge of {@code nodeA}, while {@code edge2} is both an incoming and an outgoing
 *       edge of both {@code node3} and {@code node4}:
 *       <br>

 *         directedGraph.addEdge(edge1, nodeA, nodeB);
 *         undirectedGraph.addEdge(edge2, node3, node4);
 *       </pre>
 *   </ul>
 * <li>A node {@code pred} is a predecessor of {@code node} if it is incident to an incoming
 *     {@code edge} of {@code node} (and is not itself {@code node} unless {@code edge} is
 *     a self-loop).
 * <li>A node {@code succ} is a successor of {@code node} if it is incident to an outgoing
 *     {@code edge} of {@code node} (and is not itself {@code node} unless {@code edge} is
 *     a self-loop).
 * <li>Directed edges only:
 *   <ul>
 *   <li>{@code node} is a source of {@code edge} if {@code edge} is an outgoing edge
 *       of {@code node}.
 *   <li>{@code node} is a target of {@code edge} if {@code edge} is an incoming edge
 *       of {@code node}.
 *   </ul>
 * </ul>
 *
 * <p>General notes:
 * <ul>
 * <li>Nodes/edges 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}, and the same for edges.
 *   <li>If you would otherwise have duplicate edges (e.g. weighted edges represented by a Double),
 *       you can instead wrap the edges in a custom class that defers to {@link Object} for its
 *       {@code equals()} and {@code hashCode()} implementations.
 *   <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/edges and
 * store mutable per-element state in a separate data structure (e.g. an element-to-state map).
 * <li>There are no Node or Edge classes built in.  So you can have a {@code Graph}
 *     or a {@code Graph<Author,Publication>} 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}
 *       that maps nodes onto their incident edges); this implies that the nodes and edges
 *       are just keys, and can be shared among graphs
 *   <li>the nodes store the topology (for example, by storing a {@code List} of incident edges);
 *       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 a node/edge
 *     that is not in the graph.
 * <li>Accessors take Object parameters rather than N/E generic type specifiers to match the pattern
 *     set by the Java Collections Framework.
 * </ul>
 *
 * <p>Notes for implementors:
 * <ul>
 * <li>Implementations have numerous options for internal representations: matrices, adjacency
 *     lists, adjacency maps, etc.
 * <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 that the implementations of {@link #equals(Object)} and
 *     {@link #hashCode()} are mutually consistent, and consistent 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>
* <li>Traversing a directed graph edge-wise: * <pre> * // Update the shortest-path distances of the successors to {@code node} * // in a directed graph (inner loop of Dijkstra's algorithm): * void updateDistances(N node) { * nodeDistance = distances.get(node); * for (E outEdge : graph.outEdges(node)) { * N target = graph.target(outEdge); * double targetDistance = nodeDistance + outEdge.getWeight(); * if (targetDistance < distances.get(target)) { * distances.put(target, targetDistance); * } * } * } * </code> * </ul> * * @author Joshua O'Madadhain * @param <N> Node parameter type * @param <E> Edge parameter type * @since 20.0 */ @Beta public interface Network<N, E> extends Graph { /** * Returns all edges in this network, in the order specified by {@link #edgeOrder()}. */ Set<E> edges(); // // Graph properties // /** * {@inheritDoc} * * <p>A directed edge is an {@linkplain #outEdges(Object) outgoing edge} of its * {@linkplain Endpoints#source() source}, and an {@linkplain #inEdges(Object) incoming edge} * of its {@linkplain Endpoints#target() target}. An undirected edge connects its * {@linkplain #incidentNodes(Object) incident nodes} to each other, and is both an * {@linkplain #outEdges(Object) outgoing edge} and {@linkplain #inEdges(Object) incoming edge} * of each incident node. */ @Override boolean isDirected(); /** * Returns true if this graph allows parallel edges. Attempting to add a parallel edge to a graph * that does not allow them will throw an {@link UnsupportedOperationException}. */ boolean allowsParallelEdges(); /** * Returns the order of iteration for the elements of {@link #edges()}. */ ElementOrder<? super E> edgeOrder(); // // Element-level accessors // /** * Returns the edges whose endpoints in this graph include {@code node}. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ Set<E> incidentEdges(Object node); /** * Returns the nodes which are the endpoints of {@code edge} in this graph as {@link Endpoints}. * * @throws IllegalArgumentException if {@code edge} is not an element of this graph */ Endpoints<N> incidentNodes(Object edge); /** * Returns the edges which have an {@linkplain #incidentNodes(Object) incident node} * in common with {@code edge} in this graph. * * <p>Whether an edge is considered adjacent to itself is not defined by this interface, but * generally edges are not considered to be self-adjacent. * * @throws IllegalArgumentException if {@code edge} is not an element of this graph */ Set<E> adjacentEdges(Object edge); /** * Returns the set of edges that connect {@code nodeA} to {@code nodeB}. * * <p>This set is the intersection of {@code outEdges(nodeA)} and {@code inEdges(nodeB)}. If * {@code nodeA} is equal to {@code nodeB}, then it is the set of self-loop edges for that node. * * @throws IllegalArgumentException if {@code nodeA} or {@code nodeB} is not an element * of this graph */ Set<E> edgesConnecting(Object nodeA, Object nodeB); /** * Returns all edges in this graph which can be traversed in the direction (if any) of the edge * to end at {@code node}. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ Set<E> inEdges(Object node); /** * Returns all edges in this graph which can be traversed in the direction (if any) of the edge * starting from {@code node}. * * @throws IllegalArgumentException if {@code node} is not an element of this graph */ Set<E> outEdges(Object node); // // Element-level queries // /** * {@inheritDoc} * * <p>Equivalent to {@code incidentEdges(node).size()}. */ @Override int degree(Object node); /** * {@inheritDoc} * * <p>Equivalent to {@code inEdges(node).size()}. */ @Override int inDegree(Object node); /** * {@inheritDoc} * * <p>Equivalent to {@code outEdges(node).size()}. */ @Override int outDegree(Object node); /** * Returns {@code true} iff {@code object} is a graph that has the same node/edge 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 edge set * <li>A and B have the same incidence relationships, e.g., for each node/edge in A and in B * its incident edge/node set in A is the same as its incident edge/node set in B. * <br>Thus, every edge in A and B connect the same nodes in the same direction (if any). * </ul> * * <p>Graph properties are not respected by this method. For example, two graphs may be * considered equal even if one allows parallel edges 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(Network, Network)}. */ @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 incident edges. * * <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 Network.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.