View Javadoc
1   /*
2    * Copyright (C) 2017 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 java.util.Set;
20  
21  /**
22   * A non-public interface for the methods shared between {@link Graph} and {@link ValueGraph}.
23   *
24   * @author James Sexton
25   * @param <N> Node parameter type
26   */
27  interface BaseGraph<N> extends SuccessorsFunction<N>, PredecessorsFunction<N> {
28    //
29    // Graph-level accessors
30    //
31  
32    /** Returns all nodes in this graph, in the order specified by {@link #nodeOrder()}. */
33    Set<N> nodes();
34  
35    /** Returns all edges in this graph. */
36    Set<EndpointPair<N>> edges();
37  
38    //
39    // Graph properties
40    //
41  
42    /**
43     * Returns true if the edges in this graph are directed. Directed edges connect a {@link
44     * EndpointPair#source() source node} to a {@link EndpointPair#target() target node}, while
45     * undirected edges connect a pair of nodes to each other.
46     */
47    boolean isDirected();
48  
49    /**
50     * Returns true if this graph allows self-loops (edges that connect a node to itself). Attempting
51     * to add a self-loop to a graph that does not allow them will throw an {@link
52     * IllegalArgumentException}.
53     */
54    boolean allowsSelfLoops();
55  
56    /** Returns the order of iteration for the elements of {@link #nodes()}. */
57    ElementOrder<N> nodeOrder();
58  
59    //
60    // Element-level accessors
61    //
62  
63    /**
64     * Returns the nodes which have an incident edge in common with {@code node} in this graph.
65     *
66     * @throws IllegalArgumentException if {@code node} is not an element of this graph
67     */
68    Set<N> adjacentNodes(N node);
69  
70    /**
71     * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
72     * {@code node}'s incoming edges <i>against</i> the direction (if any) of the edge.
73     *
74     * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
75     *
76     * @throws IllegalArgumentException if {@code node} is not an element of this graph
77     */
78    @Override
79    Set<N> predecessors(N node);
80  
81    /**
82     * Returns all nodes in this graph adjacent to {@code node} which can be reached by traversing
83     * {@code node}'s outgoing edges in the direction (if any) of the edge.
84     *
85     * <p>In an undirected graph, this is equivalent to {@link #adjacentNodes(Object)}.
86     *
87     * <p>This is <i>not</i> the same as "all nodes reachable from {@code node} by following outgoing
88     * edges". For that functionality, see {@link Graphs#reachableNodes(Graph, Object)}.
89     *
90     * @throws IllegalArgumentException if {@code node} is not an element of this graph
91     */
92    @Override
93    Set<N> successors(N node);
94  
95    /**
96     * Returns the count of {@code node}'s incident edges, counting self-loops twice (equivalently,
97     * the number of times an edge touches {@code node}).
98     *
99     * <p>For directed graphs, this is equal to {@code inDegree(node) + outDegree(node)}.
100    *
101    * <p>For undirected graphs, this is equal to {@code adjacentNodes(node).size()} + (1 if {@code
102    * node} has an incident self-loop, 0 otherwise).
103    *
104    * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
105    *
106    * @throws IllegalArgumentException if {@code node} is not an element of this graph
107    */
108   int degree(N node);
109 
110   /**
111    * Returns the count of {@code node}'s incoming edges (equal to {@code predecessors(node).size()})
112    * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
113    *
114    * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
115    *
116    * @throws IllegalArgumentException if {@code node} is not an element of this graph
117    */
118   int inDegree(N node);
119 
120   /**
121    * Returns the count of {@code node}'s outgoing edges (equal to {@code successors(node).size()})
122    * in a directed graph. In an undirected graph, returns the {@link #degree(Object)}.
123    *
124    * <p>If the count is greater than {@code Integer.MAX_VALUE}, returns {@code Integer.MAX_VALUE}.
125    *
126    * @throws IllegalArgumentException if {@code node} is not an element of this graph
127    */
128   int outDegree(N node);
129 
130   /**
131    * Returns true if there is an edge directly connecting {@code nodeU} to {@code nodeV}. This is
132    * equivalent to {@code nodes().contains(nodeU) && successors(nodeU).contains(nodeV)}.
133    *
134    * <p>In an undirected graph, this is equal to {@code hasEdgeConnecting(nodeV, nodeU)}.
135    *
136    * @since 23.0
137    */
138   boolean hasEdgeConnecting(N nodeU, N nodeV);
139 }