Flutter图形绘制插件directed_graph的使用

Directed Graph 插件介绍

directed_graph 是一个用于创建和操作有向图的数据结构的 Dart 包。它支持添加/移除顶点和边、排序顶点等功能，并提供了多种算法，如最短路径查找、权重最大/最小路径查找、所有连接两个顶点的路径查找、环检测、拓扑排序等。

术语解释

• 顶点（Vertices）：图中的元素。
• 边（Edges）：连接顶点的线段，可以是有向或无向的。
• 入度（In-degree）：指向某个顶点的边的数量。
• 出度（Out-degree）：从某个顶点出发的边的数量。
• 源节点（Source）：入度为零的顶点。
• 有向边（Directed Edge）：有序的顶点对 (v_i, v_j)。
• 路径（Path）：由至少两个相连顶点组成的有序列表，其中每个内部顶点都是唯一的。
• 环（Cycle）：首尾相同的路径。
• 遍历（Walk）：由至少两个相连顶点组成的有序列表。
• DAG（Directed Acyclic Graph）：没有环的有向图。
• 拓扑排序（Topological ordering）：图中所有顶点的一种顺序，使得如果存在一条从 v_i 到 v_j 的边，则 v_i 必须出现在 v_j 之前。

使用方法

要使用此库，请在 pubspec.yaml 文件中添加 directed_graph 作为依赖项。

示例代码

以下是一个完整的示例代码，展示了如何使用 directed_graph 库：

import 'package:directed_graph/directed_graph.dart';

void main() {
  // 自定义比较器
  int comparator(String s1, String s2) => s1.compareTo(s2);
  int inverseComparator(String s1, String s2) => -comparator(s1, s2);

  // 构建一个有向图
  final graph = DirectedGraph<String>({
    'a': {'b', 'h', 'c', 'e'},
    'b': {'h'},
    'c': {'h', 'g'},
    'd': {'e', 'f'},
    'e': {'g'},
    'f': {'i'},
    'i': {'l'},
    'k': {'g', 'f'}
  }, comparator: comparator);

  print('Example Directed Graph...');
  print('graph.toString():');
  print(graph);

  print('\nIs Acylic:');
  print(graph.isAcyclic);

  print('\nStrongly connected components:');
  print(graph.stronglyConnectedComponents);

  print('\nShortestPath(d, l):');
  print(graph.shortestPath('d', 'l'));

  print('\nInDegree(C):');
  print(graph.inDegree('c'));

  print('\nOutDegree(C)');
  print(graph.outDegree('c'));

  print('\nVertices sorted in lexicographical order:');
  print(graph.sortedVertices);

  print('\nVertices sorted in inverse lexicographical order:');
  graph.comparator = inverseComparator;
  print(graph.sortedVertices);
  graph.comparator = comparator;

  print('\nInDegreeMap:');
  print(graph.inDegreeMap);

  print('\nSorted Topological Ordering:');
  print(graph.sortedTopologicalOrdering);

  print('\nTopological Ordering:');
  print(graph.topologicalOrdering);

  print('\nLocal Sources:');
  print(graph.localSources);

  // 添加边使图变为有环图
  graph.addEdges('i', {'k'});
  graph.addEdges('l', {'l'});
  graph.addEdges('i', {'d'});

  print('\nCycle:');
  print(graph.cycle);

  print('\nShortest Paths:');
  print(graph.shortestPaths('a'));

  print('\nEdge exists: a->b');
  print(graph.edgeExists('a', 'b'));
}

加权有向图示例

以下是构建加权有向图并查找最轻路径、最重路径和最短路径的示例代码：

import 'package:directed_graph/directed_graph.dart';

void main(List<String> args) {
  int comparator(String s1, String s2) => s1.compareTo(s2);

  final a = 'a';
  final b = 'b';
  final c = 'c';
  final d = 'd';
  final e = 'e';
  final f = 'f';
  final g = 'g';
  final h = 'h';
  final i = 'i';
  final k = 'k';
  final l = 'l';

  int sum(int left, int right) => left + right;

  var graph = WeightedDirectedGraph<String, int>({
    a: {b: 1, h: 7, c: 2, e: 40, g: 7},
    b: {h: 6},
    c: {h: 5, g: 4},
    d: {e: 1, f: 2},
    e: {g: 2},
    f: {i: 3},
    i: {l: 3, k: 2},
    k: {g: 4, f: 5},
    l: {l: 0}
  }, summation: sum, zero: 0, comparator: comparator);

  print('Weighted Graph:');
  print(graph);

  print('\nNeighbouring vertices sorted by weight:');
  print(graph..sortEdgesByWeight());

  final lightestPath = graph.lightestPath(a, g);
  print('\nLightest path a -> g');
  print('$lightestPath weight: ${graph.weightAlong(lightestPath)}');

  final heaviestPath = graph.heaviestPath(a, g);
  print('\nHeaviest path a -> g');
  print('$heaviestPath weigth: ${graph.weightAlong(heaviestPath)}');

  final shortestPath = graph.shortestPath(a, g);
  print('\nShortest path a -> g');
  print('$shortestPath weight: ${graph.weightAlong(shortestPath)}');
}

更多功能

更多功能和详细信息请参考 GitHub 项目主页 和 API 文档。

如果你有任何问题或建议，请提交到 issue tracker。