写点什么

GitHub 上有哪些好项目?GeaFlow 图计算快速上手之 SSSP 算法

作者:GeaFlow
  • 2023-07-25
    浙江
  • 本文字数:2246 字

    阅读完需:约 7 分钟

GitHub上有哪些好项目?GeaFlow图计算快速上手之SSSP算法

GeaFlow(品牌名 TuGraph-Analytics) 已正式开源,欢迎大家关注!!! 欢迎给我们 Star 哦! GitHub👉https://github.com/TuGraph-family/tugraph-analytics更多精彩内容,关注我们的博客 https://geaflow.github.io/



引言

下面这张图是 GitHub 中约 500 个开源项目仓库与话题组成的关系网络,密布的连线恐怕没有人能从中找到任何有用的信息。然而 GitHub 目前总共有 3000000+的仓库!



如何在 5 分钟内发现有哪些我们感兴趣好项目?


今天我们使用 GeaFlow 帮助我们实现 SSSP(单源最短路径算法),来试一试盲人摸象!


GeaFlow(品牌名 TuGraph-Analytics)是蚂蚁集团开源的分布式实时图计算引擎,目前广泛应用于金融风控、社交网络、知识图谱以及数据应用等场景。

SSSP(单源最短路径算法)算法介绍

SSSP 单源最短路径算法(Single Source Shortest Path)是一种基于图论的算法,用于寻找一个起点到其他所有节点的最短路径。该算法可以应用于多种实际问题,如地图导航、网络拓扑等。


在 GitHub 开源项目仓库与话题组成的关系网络中,从仓库到话题再到仓库的关系边可以支持 SSSP 算法的运行。



如图,在关系网络局部,从起点出发,通过箭头的个数可以标记话题/仓库到源点的距离。例如仓库 FiraCode 与仓库 Font-Awesome 的距离为 2,通过 2 个箭头可到达,它们也是互相距离最近的关联仓库。


简单来说,标记出我们感兴趣的仓库,那些与我们感兴趣仓库距离最近的仓库就是推荐的好仓库。或者更进一步,STAR 数更多的近距离仓库更值得推荐。

GeaFlow 实现 SSSP

要运行 SSSP 算法,我们可以指定使用的图,直接在图查询里调用图算法,语法形式如下:


USE GRAPH github_repo_topicINSERT INTO tbl_resultCALL sssp('source_vertex') YIELD (repoName, distance)RETURN repoName, distance;
复制代码


这段代码在图 github_repo_topic 上运行,将 source_vertex 作为算法起点,输出所有其他点的距离。如果无需这么多结果,可以在 RETURN 中加上 WHERE 条件过滤,一切和 SQL 语句一样!


如果需要定制一个图算法,我们可以实现 AlgorithmUserFunction 接口。GeaFlow 内置了多种图算法的通用实现,这些算法无需单独定制,例如 SSSP 算法的参考实现如下:


@Description(name = "sssp", description = "built-in udga Single Source Shortest Path")public class SSSP implements AlgorithmUserFunction<Object, Long> {
private AlgorithmRuntimeContext<Object, Long> context; @Override public void init(AlgorithmRuntimeContext<Object, Long> context, Object[] parameters) { //初始化算法上下文 this.context = context; }
@Override public void process(RowVertex vertex, Iterator<Long> messages) { long currentDistance; //初始化所有点距离初始值 if (context.getCurrentIterationId() == 1L) { //初始化所有点距离初始值 } else if (context.getCurrentIterationId() <= $maxIteration) { //计算最短距离 } else { //返回结果 } //更新距离值 context.updateVertexValue(ObjectRow.create($currentDistance)); //向邻居发送消息 context.sendMessage(vertex.getId(), $currentDistance); long scatterDistance = $currentDistance == Long.MAX_VALUE ? Long.MAX_VALUE : currentDistance + 1; for (RowEdge edge : context.loadEdges(EdgeDirection.OUT)) { context.sendMessage(edge.getTargetId(), scatterDistance); } }
@Override public StructType getOutputType() { //算法返回值数据类型 return new StructType( new TableField("id", StringType.INSTANCE, false), new TableField("distance", LongType.INSTANCE, false) ); }}
复制代码


图查询以提交作业的形式完成,作业可以运行在本地或 K8S 集群中,GeaFlow 提供控制台管理和回溯这些图研发作业。


在 GitHub 关系图上盲人摸象

话不多说,我们找到 GitHub 上目前星星数最多的项目,计算与它距离为 2(即具有共同话题)的项目都有哪些?


目前星星最多的项目是 freeCodeCamp,这里数据GitHub Public Repository Metadata截止 2023 年 5 月。


USE GRAPH github_repo_topicINSERT INTO tbl_resultSELECT repoName, distance FROM (    CALL sssp('freeCodeCamp') YIELD (repoName, distance)    RETURN repoName, distance) WHERE distance = 2 LIMIT 10;
复制代码


短短时间我们就拿到了计算结果,来看看 GeaFlow 都给我淘到了哪些好项目吧。这里不按星星数排序,随机呈现 10 条记录。


id,stars,forkspapers-we-love,72164,5162system-design-primer,220197,39109free-programming-books-zh_CN,102417,2751633-js-concepts,56077,7850build-your-own-x,201052,1962930-seconds-of-code,111510,11483carbon,32588,1854freecodecamp.cn,36459,1369Web-Dev-For-Beginners,69680,10904free-programming-books,279431,55158
复制代码

总结

本文介绍了实时图计算引擎 GeaFlow 支持图算法 SSSP 的基本原理以及在 GeaFlow 中的实现细节,并展示其在 GitHub 数据集上的一个应用。



GeaFlow(品牌名 TuGraph-Analytics) 已正式开源,欢迎大家关注!!!

欢迎给我们 Star 哦!

Welcome to give us a Star!

GitHub👉https://github.com/TuGraph-family/tugraph-analytics

更多精彩内容,关注我们的博客 https://geaflow.github.io/

用户头像

GeaFlow

关注

欢迎访问:geaflow.github.io 2023-07-05 加入

GeaFlow(品牌名TuGraph-Analytics) 是一个分布式流图计算引擎 欢迎给我们 Star 哦! GitHub👉github.com/TuGraph-family/tugraph-analytics 更多精彩内容,关注我们的博客geaflow.github.io

评论

发布
暂无评论
GitHub上有哪些好项目?GeaFlow图计算快速上手之SSSP算法_图算法_GeaFlow_InfoQ写作社区