计算最长路径

作者

本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

转载自夜明的孤行灯

本文链接地址: https://www.huangyunkun.com/2024/01/31/find-longest-path-with-java/



微服务场景中很容易出现A->B->C->D->E的情况，现在想找到最长的调用链路，目前已经有从Trace中抽样的数据，遗憾的是只有直接调用关系，比如A->B、C->D、B->C、B->E 这种，所以需要自己加工一下。

由于场景边界还挺多的，而且不排除后期需要分析其他场景，比如A调用的服务数量等，所以还是考虑使用成熟的工具。

图形数据库

第一个想到的就是图形数据库，图形数据库使用图结构进行语义查询的数据库，它使用节点、边和属性来表示和存储数据。这里我们将每个调用拆分为服务作为节点，调用关系作为边来处理。

为了简单我是用的是Neo4j的嵌入模式，由于一次性需求，每次都新建数据然后查询

File dataFile = Files.createTempDirectory("neo4j").toFile();

DatabaseManagementService managementService = new DatabaseManagementServiceBuilder(dataFile.toPath()).build();
GraphDatabaseService graphDb = managementService.database(DEFAULT_DATABASE_NAME);

为了加快速度，使用ID作为索引


try (Transaction tx = graphDb.beginTx()) {
      Schema schema = tx.schema();
      schema.indexFor(label).on("id").withName("id").create();
      tx.commit();
}

然后按需解析数据，添加关联

Node main = createNode(tx, label, node);
Node children = createNode(tx, label, callingNode);
main.createRelationshipTo(children, RelTypes.CALLING);

然后查询，理论上可以使用Cypher查询语句，由于需求简单我们直接拉出所有路径取最长的

Traverser traverse = tx.traversalDescription()
                        .relationships(RelTypes.CALLING, Direction.OUTGOING)
                        .evaluator(Evaluators.all()).traverse(mainNode);

for (Path path : traverse) {
     if (longestPath == null || longestPath.length() < path.length()) {
        longestPath = path;
     }
}

JGraphT

Neo4j支持的查询比较多，但是只取最长路径有点大材小用了，而且相对来说性能比较低。JGraphT是一个免费的Java类库，提供数学图形理论对象和算法，也可以用于我们这个场景。

经过综合衡量，这里使用DirectedPseudograph

Graph<String, DefaultEdge> graph = new DirectedPseudograph<>(DefaultEdge.class);
Graphs.addEdgeWithVertices(graph, String.valueOf(node.getLong("id")), String.valueOf(callingNode.getLong("id")));

JGraphT提供的算法工具大部分是最短路径的，比如AStarShortestPath、BFSShortestPath等，而我们需要最长路径，考虑到图整体不大，我们这里直接用Dijkstra穷举。

List<List<String>> result = Lists.newArrayList();
Set<String> allVertices = new HashSet<>(graph.vertexSet());
allVertices.remove(id);

GraphPath<String, DefaultEdge> longestPath = null;
double longestPathLength = Double.NEGATIVE_INFINITY;

for (String targetVertex : allVertices) {
     if (targetVertex != null) {
       AllDirectedPaths<String, DefaultEdge> allPaths = new AllDirectedPaths<>(graph);
       List<GraphPath<String, DefaultEdge>> pathsFromNodeA = allPaths.getAllPaths(id, targetVertex, true, null);

      for (GraphPath<String, DefaultEdge> path : pathsFromNodeA) {
         if (path.getLength() > longestPathLength) {
             longestPath = path;
             longestPathLength = path.getLength();
         }
     }
  }
}

当然这个使用实际上有一些限制，比如不能有loop等。



本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

转载自夜明的孤行灯

本文链接地址: https://www.huangyunkun.com/2024/01/31/find-longest-path-with-java/

发表评论