本文整理了Java中com.google.common.graph.Graph
类的一些代码示例,展示了Graph
类的具体用法。这些代码示例主要来源于Github
/Stackoverflow
/Maven
等平台,是从一些精选项目中提取出来的代码,具有较强的参考意义,能在一定程度帮忙到你。Graph
类的具体详情如下:
包路径:com.google.common.graph.Graph
类名称:Graph
[英]An interface for graph-structured data, whose edges are anonymous entities with no identity or information of their own.
A graph is composed of a set of nodes and a set of edges connecting pairs of nodes.
There are three primary interfaces provided to represent graphs. In order of increasing complexity they are: Graph, ValueGraph, and Network. You should generally prefer the simplest interface that satisfies your use case. See the "Choosing the right graph type" section of the Guava User Guide for more details.
Graph supports the following use cases (definitions of terms):
Graph explicitly does not support parallel edges, and forbids implementations or extensions with parallel edges. If you need parallel edges, use Network.
The implementation classes that common.graph provides are not public, by design. To create an instance of one of the built-in implementations of Graph, use the GraphBuilder class:
MutableGraph graph = GraphBuilder.undirected().build();
GraphBuilder#build() returns an instance of MutableGraph, which is a subtype of Graph that provides methods for adding and removing nodes and edges. If you do not need to mutate a graph (e.g. if you write a method than runs a read-only algorithm on the graph), you should use the non-mutating Graph interface, or an ImmutableGraph.
You can create an immutable copy of an existing Graph using ImmutableGraph#copyOf(Graph):
ImmutableGraph immutableGraph = ImmutableGraph.copyOf(graph);
Instances of ImmutableGraph do not implement MutableGraph (obviously!) and are contractually guaranteed to be unmodifiable and thread-safe.
The Guava User Guide has more information on (and examples of) building graphs.
See the Guava User Guide for the common.graph package ("Graphs Explained") for additional documentation, including:
MutableGraph graph = GraphBuilder.undirected().build();
GraphBuilder#build()返回MutableGraph的一个实例,MutableGraph是Graph的一个子类型,提供了添加和删除节点和边的方法。如果您不需要对图形进行变异(例如,如果您编写的方法在图形上运行只读算法),则应使用非变异图形接口或不可变图形。
您可以使用ImmutableGraph#copyOf(Graph)创建现有图形的不可变副本:
ImmutableGraph immutableGraph = ImmutableGraph.copyOf(graph);
ImmutableGraph的实例不实现MutableGraph(显然!)并且根据合同保证不可修改且线程安全。
Guava用户指南有more information on (and examples of) building graphs。
####附加文件
请参阅《Guava用户指南》了解常见的问题。用于其他文档的图形包({$4$}),包括:
代码示例来源:origin: google/guava
/**
* Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset
* of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting
* and ending with the same node.
*
* <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
*/
public static <N> boolean hasCycle(Graph<N> graph) {
int numEdges = graph.edges().size();
if (numEdges == 0) {
return false; // An edge-free graph is acyclic by definition.
}
if (!graph.isDirected() && numEdges >= graph.nodes().size()) {
return true; // Optimization for the undirected case: at least one cycle must exist.
}
Map<Object, NodeVisitState> visitedNodes =
Maps.newHashMapWithExpectedSize(graph.nodes().size());
for (N node : graph.nodes()) {
if (subgraphHasCycle(graph, visitedNodes, node, null)) {
return true;
}
}
return false;
}
代码示例来源:origin: google/guava
private static <N> GraphConnections<N, Presence> connectionsOf(Graph<N> graph, N node) {
Function<Object, Presence> edgeValueFn = Functions.constant(Presence.EDGE_EXISTS);
return graph.isDirected()
? DirectedGraphConnections.ofImmutable(
graph.predecessors(node), Maps.asMap(graph.successors(node), edgeValueFn))
: UndirectedGraphConnections.ofImmutable(
Maps.asMap(graph.adjacentNodes(node), edgeValueFn));
}
代码示例来源:origin: google/guava
/**
* Returns a {@link GraphBuilder} initialized with all properties queryable from {@code graph}.
*
* <p>The "queryable" properties are those that are exposed through the {@link Graph} interface,
* such as {@link Graph#isDirected()}. Other properties, such as {@link #expectedNodeCount(int)},
* are not set in the new builder.
*/
public static <N> GraphBuilder<N> from(Graph<N> graph) {
return new GraphBuilder<N>(graph.isDirected())
.allowsSelfLoops(graph.allowsSelfLoops())
.nodeOrder(graph.nodeOrder());
}
代码示例来源:origin: google/guava
assertThat(graphString).contains("isDirected: " + graph.isDirected());
assertThat(graphString).contains("allowsSelfLoops: " + graph.allowsSelfLoops());
for (N node : sanityCheckSet(graph.nodes())) {
assertThat(nodeString).contains(node.toString());
if (graph.isDirected()) {
assertThat(graph.degree(node)).isEqualTo(graph.inDegree(node) + graph.outDegree(node));
assertThat(graph.predecessors(node)).hasSize(graph.inDegree(node));
assertThat(graph.successors(node)).hasSize(graph.outDegree(node));
} else {
int selfLoopCount = graph.adjacentNodes(node).contains(node) ? 1 : 0;
assertThat(graph.degree(node)).isEqualTo(graph.adjacentNodes(node).size() + selfLoopCount);
assertThat(graph.predecessors(node)).isEqualTo(graph.adjacentNodes(node));
assertThat(graph.successors(node)).isEqualTo(graph.adjacentNodes(node));
assertThat(graph.inDegree(node)).isEqualTo(graph.degree(node));
assertThat(graph.outDegree(node)).isEqualTo(graph.degree(node));
for (N adjacentNode : sanityCheckSet(graph.adjacentNodes(node))) {
if (!graph.allowsSelfLoops()) {
assertThat(node).isNotEqualTo(adjacentNode);
graph.predecessors(node).contains(adjacentNode)
|| graph.successors(node).contains(adjacentNode))
.isTrue();
for (N predecessor : sanityCheckSet(graph.predecessors(node))) {
assertThat(graph.successors(predecessor)).contains(node);
assertThat(graph.hasEdgeConnecting(predecessor, node)).isTrue();
代码示例来源:origin: google/guava
assertThat(network.nodes()).isEqualTo(asGraph.nodes());
assertThat(network.edges().size()).isAtLeast(asGraph.edges().size());
assertThat(network.nodeOrder()).isEqualTo(asGraph.nodeOrder());
assertThat(network.isDirected()).isEqualTo(asGraph.isDirected());
assertThat(network.allowsSelfLoops()).isEqualTo(asGraph.allowsSelfLoops());
N nodeU = endpointPair.nodeU();
N nodeV = endpointPair.nodeV();
assertThat(asGraph.edges()).contains(EndpointPair.of(network, nodeU, nodeV));
assertThat(network.edgesConnecting(nodeU, nodeV)).contains(edge);
assertThat(network.successors(nodeU)).contains(nodeV);
assertThat(nodeString).contains(node.toString());
assertThat(network.adjacentNodes(node)).isEqualTo(asGraph.adjacentNodes(node));
assertThat(network.predecessors(node)).isEqualTo(asGraph.predecessors(node));
assertThat(network.successors(node)).isEqualTo(asGraph.successors(node));
代码示例来源:origin: google/guava
/**
* Returns the set of nodes that are reachable from {@code node}. Node B is defined as reachable
* from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A
* and ending at node B. Note that a node is always reachable from itself via a zero-length path.
*
* <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view
* of the set of nodes reachable from {@code node}. In other words, the returned {@link Set} will
* not be updated after modifications to {@code graph}.
*
* @throws IllegalArgumentException if {@code node} is not present in {@code graph}
*/
public static <N> Set<N> reachableNodes(Graph<N> graph, N node) {
checkArgument(graph.nodes().contains(node), NODE_NOT_IN_GRAPH, node);
Set<N> visitedNodes = new LinkedHashSet<N>();
Queue<N> queuedNodes = new ArrayDeque<N>();
visitedNodes.add(node);
queuedNodes.add(node);
// Perform a breadth-first traversal rooted at the input node.
while (!queuedNodes.isEmpty()) {
N currentNode = queuedNodes.remove();
for (N successor : graph.successors(currentNode)) {
if (visitedNodes.add(successor)) {
queuedNodes.add(successor);
}
}
}
return Collections.unmodifiableSet(visitedNodes);
}
代码示例来源:origin: google/guava
/** Creates a mutable copy of {@code graph} with the same nodes and edges. */
public static <N> MutableGraph<N> copyOf(Graph<N> graph) {
MutableGraph<N> copy = GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
for (N node : graph.nodes()) {
copy.addNode(node);
}
for (EndpointPair<N> edge : graph.edges()) {
copy.putEdge(edge.nodeU(), edge.nodeV());
}
return copy;
}
代码示例来源:origin: net.kyori/lunar
checkArgument(graph.isDirected(), "the graph must be directed");
checkArgument(!graph.allowsSelfLoops(), "the graph cannot allow self loops");
for(final T node : graph.nodes()) {
for(final T successor : graph.successors(node)) {
requiredCounts.merge(successor, 1, (a, b) -> a + b);
final List<T> results = new ArrayList<>();
for(final T node : graph.nodes()) {
if(!requiredCounts.containsKey(node)) {
processing.add(node);
for(final T successor : graph.successors(now)) {
final int newCount = requiredCounts.get(successor) - 1;
if(newCount == 0) {
代码示例来源:origin: jrtom/jung
g.nodes().containsAll(nodes), "Input graph must contain all specified nodes");
ValueGraphBuilder<Object, Object> builder =
g.isDirected() ? ValueGraphBuilder.directed() : ValueGraphBuilder.undirected();
MutableValueGraph<N, Set<N>> newGraph =
builder.expectedNodeCount(nodes.size()).nodeOrder(g.nodeOrder()).build();
for (N s : g.successors(node)) {
for (N t : g.successors(s)) {
if (!nodes.contains(t) || t.equals(node)) {
continue;
代码示例来源:origin: google/guava
@Test
public void transpose_directedGraph() {
MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build();
directedGraph.putEdge(N1, N3);
directedGraph.putEdge(N3, N1);
directedGraph.putEdge(N1, N2);
directedGraph.putEdge(N1, N1);
directedGraph.putEdge(N3, N4);
MutableGraph<Integer> expectedTranspose = GraphBuilder.directed().allowsSelfLoops(true).build();
expectedTranspose.putEdge(N3, N1);
expectedTranspose.putEdge(N1, N3);
expectedTranspose.putEdge(N2, N1);
expectedTranspose.putEdge(N1, N1);
expectedTranspose.putEdge(N4, N3);
Graph<Integer> transpose = transpose(directedGraph);
assertThat(transpose).isEqualTo(expectedTranspose);
assertThat(transpose(transpose)).isSameAs(directedGraph);
AbstractGraphTest.validateGraph(transpose);
for (Integer node : directedGraph.nodes()) {
assertThat(directedGraph.inDegree(node)).isSameAs(transpose.outDegree(node));
assertThat(directedGraph.outDegree(node)).isSameAs(transpose.inDegree(node));
}
assertThat(transpose.successors(N1)).doesNotContain(N2);
directedGraph.putEdge(N2, N1);
// View should be updated.
assertThat(transpose.successors(N1)).contains(N2);
AbstractGraphTest.validateGraph(transpose);
}
代码示例来源:origin: google/guava
@Override
public Set<N> predecessors(N node) {
return delegate().successors(node); // transpose
}
代码示例来源:origin: google/guava
if (graph.isDirected()) {
for (N node : graph.nodes()) {
for (N reachableNode : reachableNodes(graph, node)) {
transitiveClosure.putEdge(node, reachableNode);
for (N node : graph.nodes()) {
if (!visitedNodes.contains(node)) {
Set<N> reachableNodes = reachableNodes(graph, node);
代码示例来源:origin: jrtom/jung
/**
* A graph is "forest-shaped" if it is directed, acyclic, and each node has at most one
* predecessor.
*/
public static <N> boolean isForestShaped(Graph<N> graph) {
checkNotNull(graph, "graph");
return graph.isDirected()
&& !Graphs.hasCycle(graph)
&& graph.nodes().stream().allMatch(node -> graph.predecessors(node).size() <= 1);
}
代码示例来源:origin: google/guava
/** Returns an immutable copy of {@code graph}. */
public static <N> ImmutableGraph<N> copyOf(Graph<N> graph) {
return (graph instanceof ImmutableGraph)
? (ImmutableGraph<N>) graph
: new ImmutableGraph<N>(
new ConfigurableValueGraph<N, Presence>(
GraphBuilder.from(graph), getNodeConnections(graph), graph.edges().size()));
}
代码示例来源:origin: google/guava
static void assertStronglyEquivalent(Graph<?> graphA, Graph<?> graphB) {
// Properties not covered by equals()
assertThat(graphA.allowsSelfLoops()).isEqualTo(graphB.allowsSelfLoops());
assertThat(graphA.nodeOrder()).isEqualTo(graphB.nodeOrder());
assertThat(graphA).isEqualTo(graphB);
}
代码示例来源:origin: jrtom/jung
/**
* Returns the weight of the edge from <code>v1</code> to <code>v2</code> plus the weight of the
* edge from <code>v2</code> to <code>v1</code>; if either edge does not exist, it is treated as
* an edge with weight 0. Undirected edges are treated as two antiparallel directed edges (that
* is, if there is one undirected edge with weight <i>w</i> connecting <code>v1</code> to <code>v2
* </code>, the value returned is 2<i>w</i>). Ignores parallel edges; if there are any such, one
* is chosen at random. Throws <code>NullPointerException</code> if either edge is present but not
* assigned a weight by the constructor-specified <code>NumberEdgeValue</code>.
*
* @param v1 the first node of the pair whose property is being measured
* @param v2 the second node of the pair whose property is being measured
* @return the weights of the edges {@code<v1, v2>} and {@code <v2, v1>}
*/
protected double mutualWeight(N v1, N v2) {
double weight = 0;
if (g.isDirected()) {
if (g.successors(v1).contains(v2)) {
weight += edge_weight.apply(v1, v2).doubleValue();
}
if (g.successors(v2).contains(v1)) {
weight += edge_weight.apply(v2, v1).doubleValue();
}
} else {
if (g.adjacentNodes(v1).contains(v2)) {
weight += edge_weight.apply(v1, v2).doubleValue();
}
}
return weight;
}
代码示例来源:origin: google/guava
private static <N> ImmutableMap<N, GraphConnections<N, Presence>> getNodeConnections(
Graph<N> graph) {
// ImmutableMap.Builder maintains the order of the elements as inserted, so the map will have
// whatever ordering the graph's nodes do, so ImmutableSortedMap is unnecessary even if the
// input nodes are sorted.
ImmutableMap.Builder<N, GraphConnections<N, Presence>> nodeConnections = ImmutableMap.builder();
for (N node : graph.nodes()) {
nodeConnections.put(node, connectionsOf(graph, node));
}
return nodeConnections.build();
}
代码示例来源:origin: google/guava
@Override
public Set<N> successors(N node) {
return delegate().predecessors(node); // transpose
}
代码示例来源:origin: google/guava
/**
* Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
* properties remain intact, and further updates to {@code graph} will be reflected in the view.
*/
public static <N> Graph<N> transpose(Graph<N> graph) {
if (!graph.isDirected()) {
return graph; // the transpose of an undirected graph is an identical graph
}
if (graph instanceof TransposedGraph) {
return ((TransposedGraph<N>) graph).graph;
}
return new TransposedGraph<N>(graph);
}
代码示例来源:origin: jrtom/jung
public static <N> ImmutableSet<N> roots(Graph<N> graph) {
checkNotNull(graph, "graph");
return graph
.nodes()
.stream()
.filter(node -> graph.predecessors(node).isEmpty())
.collect(toImmutableSet());
}
内容来源于网络,如有侵权,请联系作者删除!