com.google.common.graph.Graph类的使用及代码示例

x33g5p2x  于2022-01-20 转载在 其他  
字(14.7k)|赞(0)|评价(0)|浏览(566)

本文整理了Java中com.google.common.graph.Graph类的一些代码示例，展示了Graph类的具体用法。这些代码示例主要来源于Github/Stackoverflow/Maven等平台，是从一些精选项目中提取出来的代码，具有较强的参考意义，能在一定程度帮忙到你。Graph类的具体详情如下：
包路径：com.google.common.graph.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.

Capabilities

Graph supports the following use cases (definitions of terms):

  • directed graphs
  • undirected graphs
  • graphs that do/don't allow self-loops
  • graphs whose nodes/edges are insertion-ordered, sorted, or unordered

Graph explicitly does not support parallel edges, and forbids implementations or extensions with parallel edges. If you need parallel edges, use Network.

Building a Graph

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.

Additional documentation

See the Guava User Guide for the common.graph package ("Graphs Explained") for additional documentation, including:

  • equals(), hashCode(), and graph equivalence
  • Synchronization policy
  • Notes for implementors
    [中][graph](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics))结构化数据的接口，其边缘是匿名实体，没有自己的标识或信息。
    图由一组节点和一组连接成对节点的边组成。
    提供了三个主要接口来表示图形。按照复杂性的增加顺序，它们是：图、值图和网络。通常，您应该更喜欢满足您的用例的最简单接口。有关更多详细信息，请参阅Guava用户指南的"Choosing the right graph type"部分。
    ####能力
    图形支持以下用例（definitions of terms）：
    *有向图
    *无向图
    *允许/不允许自循环的图
    *节点/边按插入顺序、排序或无序排列的图
    Graph明确不支持平行边，并且禁止使用平行边的实现或扩展。如果需要平行边，请使用网络。
    ####构建图形
    实现类是通用的。根据设计，图形提供的数据不是公共的。要创建Graph的一个内置实现的实例，请使用GraphBuilder类：
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());
}

内容来源于网络，如有侵权，请联系作者删除！

Graph

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com