Class SubgraphUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.SubgraphUtil
public final class SubgraphUtil extends Object
Subgraph Util - Subgraph Extraction and Operations 子图工具类 - 子图提取和操作

Utility class for creating subgraphs from existing graphs through various selection criteria.

通过各种选择条件从现有图创建子图的工具类。

Features | 主要功能:

  • Vertex-induced subgraph - 顶点诱导子图
  • Edge-induced subgraph - 边诱导子图
  • Filter by vertex/edge predicates - 按顶点/边谓词过滤
  • K-hop neighborhood extraction - K跳邻域提取
  • Graph union/intersection/difference - 图的并集/交集/差集
  • Reverse graph - 反转图
  • Ego network extraction - 自我网络提取

Usage Examples | 使用示例:

// Vertex-induced subgraph
Graph<String> sub = SubgraphUtil.induced(graph, Set.of("A", "B", "C"));

// Filter vertices by predicate
Graph<String> filtered = SubgraphUtil.filterVertices(graph, v -> v.startsWith("node"));

// K-hop neighborhood
Graph<String> neighborhood = SubgraphUtil.neighborhood(graph, "A", 2);

// Graph union
Graph<String> union = SubgraphUtil.union(graph1, graph2);

// Ego network (1-hop neighborhood)
Graph<String> ego = SubgraphUtil.egoNetwork(graph, "A");

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns empty graphs for null inputs) - 空值安全: 是（null输入返回空图）

Performance | 性能特性:

  • Time complexity: O(V + E) - 时间复杂度: O(V + E)
  • Space complexity: O(V + E) - 空间复杂度: O(V + E)
Since:
JDK 25, opencode-base-graph V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • induced

      public static <V> Graph<V> induced(Graph<V> graph, Set<V> vertices)
      Create vertex-induced subgraph. 创建顶点诱导子图。

      The induced subgraph contains all specified vertices and all edges between those vertices that exist in the original graph.

      诱导子图包含所有指定的顶点以及原图中这些顶点之间存在的所有边。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      vertices - the vertices to include | 要包含的顶点
      Returns:
      the induced subgraph | 诱导子图

    • edgeInduced

      public static <V> Graph<V> edgeInduced(Graph<V> graph, Set<Edge<V>> edges)
      Create edge-induced subgraph. 创建边诱导子图。

      The induced subgraph contains all specified edges and their endpoint vertices.

      诱导子图包含所有指定的边及其端点顶点。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      edges - the edges to include | 要包含的边
      Returns:
      the induced subgraph | 诱导子图

    • filterVertices

      public static <V> Graph<V> filterVertices(Graph<V> graph, Predicate<V> predicate)
      Filter graph by vertex predicate. 按顶点谓词过滤图。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      predicate - the vertex filter predicate | 顶点过滤谓词
      Returns:
      filtered subgraph | 过滤后的子图

    • filterEdges

      public static <V> Graph<V> filterEdges(Graph<V> graph, Predicate<Edge<V>> predicate)
      Filter graph by edge predicate. 按边谓词过滤图。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      predicate - the edge filter predicate | 边过滤谓词
      Returns:
      filtered subgraph | 过滤后的子图

    • filterByWeight

      public static <V> Graph<V> filterByWeight(Graph<V> graph, double minWeight, double maxWeight)
      Filter edges by weight range. 按权重范围过滤边。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      minWeight - minimum weight (inclusive) | 最小权重（含）
      maxWeight - maximum weight (inclusive) | 最大权重（含）
      Returns:
      filtered subgraph | 过滤后的子图

    • neighborhood

      public static <V> Graph<V> neighborhood(Graph<V> graph, V center, int k)
      Extract k-hop neighborhood of a vertex. 提取顶点的k跳邻域。

      Returns the subgraph containing all vertices within k hops of the center vertex and all edges between them.

      返回包含中心顶点k跳范围内所有顶点及其之间所有边的子图。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      center - the center vertex | 中心顶点
      k - maximum distance (hops) | 最大距离（跳数）
      Returns:
      neighborhood subgraph | 邻域子图

    • egoNetwork

      public static <V> Graph<V> egoNetwork(Graph<V> graph, V ego)
      Extract ego network (1-hop neighborhood). 提取自我网络（1跳邻域）。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      ego - the ego vertex | 自我顶点
      Returns:
      ego network subgraph | 自我网络子图

    • egoNetwork

      public static <V> Graph<V> egoNetwork(Graph<V> graph, V ego, int radius)
      Extract ego network with specified radius. 提取指定半径的自我网络。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      ego - the ego vertex | 自我顶点
      radius - the radius (hops) | 半径（跳数）
      Returns:
      ego network subgraph | 自我网络子图

    • union

      public static <V> Graph<V> union(Graph<V> g1, Graph<V> g2)
      Compute union of two graphs. 计算两个图的并集。

      The union contains all vertices and edges from both graphs.

      并集包含两个图的所有顶点和边。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      g1 - the first graph | 第一个图
      g2 - the second graph | 第二个图
      Returns:
      union graph | 并集图

    • intersection

      public static <V> Graph<V> intersection(Graph<V> g1, Graph<V> g2)
      Compute intersection of two graphs. 计算两个图的交集。

      The intersection contains vertices and edges present in both graphs.

      交集包含两个图中都存在的顶点和边。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      g1 - the first graph | 第一个图
      g2 - the second graph | 第二个图
      Returns:
      intersection graph | 交集图

    • difference

      public static <V> Graph<V> difference(Graph<V> g1, Graph<V> g2)
      Compute difference of two graphs (g1 - g2). 计算两个图的差集（g1 - g2）。

      The difference contains vertices and edges from g1 that are not in g2.

      差集包含g1中但不在g2中的顶点和边。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      g1 - the first graph | 第一个图
      g2 - the second graph | 第二个图
      Returns:
      difference graph | 差集图

    • symmetricDifference

      public static <V> Graph<V> symmetricDifference(Graph<V> g1, Graph<V> g2)
      Compute symmetric difference of two graphs. 计算两个图的对称差集。

      The symmetric difference contains elements in either graph but not in both.

      对称差集包含在任一图中但不同时在两个图中的元素。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      g1 - the first graph | 第一个图
      g2 - the second graph | 第二个图
      Returns:
      symmetric difference graph | 对称差集图

    • reverse

      public static <V> Graph<V> reverse(Graph<V> graph)
      Create a reversed (transposed) graph. 创建反转（转置）图。

      For directed graphs, all edge directions are reversed. For undirected graphs, returns a copy.

      对于有向图，所有边方向反转。对于无向图，返回副本。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      Returns:
      reversed graph | 反转图

    • copy

      public static <V> Graph<V> copy(Graph<V> graph)
      Create a copy of the graph. 创建图的副本。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      Returns:
      graph copy | 图副本

    • complement

      public static <V> Graph<V> complement(Graph<V> graph)
      Create the complement of a graph. 创建图的补图。

      The complement contains all edges not in the original graph.

      补图包含原图中不存在的所有边。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      Returns:
      complement graph | 补图

    • removeIsolated

      public static <V> Graph<V> removeIsolated(Graph<V> graph)
      Remove isolated vertices (vertices with no edges). 移除孤立顶点（没有边的顶点）。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      Returns:
      graph without isolated vertices | 无孤立顶点的图

    • sampleVertices

      public static <V> Graph<V> sampleVertices(Graph<V> graph, int numVertices, Random random)
      Sample a random subgraph with specified number of vertices. 采样具有指定顶点数的随机子图。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      numVertices - number of vertices to sample | 要采样的顶点数
      random - random number generator | 随机数生成器
      Returns:
      sampled subgraph | 采样子图

    • sampleEdges

      public static <V> Graph<V> sampleEdges(Graph<V> graph, int numEdges, Random random)
      Sample a random subgraph with specified number of edges. 采样具有指定边数的随机子图。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the source graph | 源图
      numEdges - number of edges to sample | 要采样的边数
      random - random number generator | 随机数生成器
      Returns:
      sampled subgraph | 采样子图