Neo4j自定义过程开发之K最小生成树算法

Jean

上篇文章学习了有向图最小树形图朱刘算法的Python实现，但在Python客户端绕一圈毕竟还不够方便，本文先尝试改写无向图的K最小生成树算法完成Neo4j开发自定义过程的框架和流程，后面再用Java编写最小树形图及k最小树形图朱刘算法插件，以便在Cypher中可以直接调用，方便使用的同时，也降低了对使用者的要求，提高效率与集成度。

对开源软件的改造利用，个人觉得要遵守开源精神的要求与规范，尊重知识产权，尊重开源社区与贡献者，并回馈开源社区。Neo4j公司有部分代码没有开源，应予以理解与尊重，毕竟软件系统的研发需要长期的投入，公司需要商业上的回报以维持与发展，开源主要的代码已经对世界作出了很大的贡献。这样的研究性解决方案完成了，对有志于此的国内公司是一个参考和鞭策，毕竟Neo4j的先进性摆在那里，这样的解决方案就是他们对标的标准。

个人觉得，学习、应用、交流、回馈、创新，是符合双循环的精神的，国产软件可以在双循环中更快更好的实现自主与自强。科技要以需求为导向，解决实际的问题，自主自强应该有国际的视野与标准，参与者需要在市场公平竞争的历练中成长，用实力与质量赢得自己的市场份额与尊严。当然，规则共识之下任何国家对战略产业与关键核心技术的扶持都是合规合理的。

一、Noe4j GDS最小生成树及K最小生成树算法的问题。

如上图所示，GDS1.5.0的 最小生成树算法，可以计算无向图最小生成树MINST，也可以计算最大生成树MAXST，结果都是正确的，具体见 测试用例。然而它的 K最小生成树算法，并没有象最小生成树算法那样直接返回树，而是返回连接（边）数，很不直观，并且结果也有问题，具体见 测试用例及 算法文档。Neo4j GDS的最小生成树是并行的算法实现，K最小生成树算法那样写应该也是为了并行实现。我没有论证其并行实现算法是否成立的水平，但K最小生成树算法不符合自己的使用要求，所以有必要写个自己的K最小生成树实现。Neo4j的生成树算法是Prim算法，对于无向图全图的计算，最小生成树的结果证明是可以并行的，但个人认为，对于K最小生成树，按Prim算法，在求得全图的最小生成树后，只能从最小生成树的根节点出发，顺序产生K最小生成树，因为不能并行确定要剪去哪些枝叶节点，只能从根节点开始顺序遍历，这样结果一定是对的。象这样Alpha阶段的算法，有Bug或者未完全实现，也是正常的，使用时加以注意即可。

二、为开发自定义过程配置Eclipse。

编程的传统是Learn by example，先从 Neo4j的自定义过程模板开始。这是个Maven管理的Java项目，因为以前用了好久Eclipse，继续用Eclipse，首先把这个模板跑起来。

1、安装JDK11，设置JAVA_HOME及PATH指向JDK11，Neo4j 4.X在JDK11上编译。

2、修改Eclipse Maven设置，以使用国内Maven镜像下载需要的Neo4j jar包，国外的central库很慢， 参考资料。

3、 下载Neo4j procedure template 4.1（ZIP），解压后修改 pom.xml，修改dependencies中的 artifactId neo4j，neo4j-harness，neo4j-java-driver的version为4.2.1，我们将要使用Neo4j community 4.2.1来测试。

4、 选择源码解压的文件夹在Eclipse中导入Maven project，这时会产生一些Maven Dependency Problem，后面解决。

5、 更改Project Facets，指定项目编译的JDK版本为JDK11， 参考资料。

6、 下载更新Maven本地库， 参考资料。

7、 编译通过，junit单元测试通过。在项目/src/test/java下是junit测试用例，在测试用例上鼠标右键->Run As->Junit Test。

8、 Maven 打包。Project上右键->Run As->Maven Install。

9、 发布。拷贝生成的jar包procedure-template-1.0.0-SNAPSHOT.jar到D:\Neo4j\neo4j-chs-community-4.2.1-s\plugins，启动Noe4j Server。

10、 测试。在Neo4j Browser中输入语句调用测试。

三、以GDS的最小生成树及K最小生成树算法源码为模板建立新项目，用于开发测试自己的K最小生成树算法。因为不了解Neo4j及GDS的框架体系、API及数据结构等，在现有算法实现的基础上改，替换为自己的自定义过程、算法实现及测试用例是最快的途径。

1、下载 GDS最新1.5.0源码（ZIP）及运行jar包。

2、 Eclipse建立新的Maven Project，比如叫procedure-arborescence，Eclipse会建立项目的目录结构。

3、 解压源码，找到这两个算法的源码，用户自定义过程在
\alpha\alpha-proc\src\main\java\org\neo4j\graphalgo\spanningtree下，算法实现在\alpha\alpha-algo\src\main\java\org\neo4j\graphalgo\impl\spanningTrees下，在\src\main\java下建立相应的package并导入源码。单元测试程序在\alpha\alpha-proc\src\test\java\org\neo4j\graphalgo 下，在\src\test\java下建立package并导入两个算法的单元测试程序。单元测试程序引用的资源文件在\alpha\alpha-proc\src\test\resources目录下，导入到项目的\src\test\resources目录下。GDS源码按模块组织，目录比较多，我用小工具Everyhting查找源码文件，很方便。

4、拷贝模板项目的pom.xml文件，根据编译的错误提示修改pom.xml加入依赖的GDS 库模块，下载更新Maven本地库。

5、 排除Maven依赖包版本的冲突。多个依赖包可能会引用更多的依赖包，Maven pom.xml中的包依赖说明可能会指向同一个包的不同版本，引起冲突，导致Maven运行失败。在Eclipse中打开项目的pom.xml，切换到Dependency Hierarchy视图，可以看到包依赖的层次视图，及有冲突的包。可以在Filter中输入包名过滤一下。比如这两个算法的单元测试代码引用了groupId org.neo4j.gds的test-utils包，它引用的包都引用了junit，但版本不同会引起冲突。一般在低版本上右键->Exclude Maven Artifact排除对低版本的引用，具体排除哪一个，要测试一下。一个项目中引用的同一个包，只能是同一个版本，排除的前提是这些版本是兼容的，没有太大的差异，否则就要改程序了。 参考资料1， 参考资料2。

7、编译通过后，如上进行单元测试，验证项目的完整性。

四、用Eclipse Java的Refactor功能更改java类的名称，生成自己的用户自定义过程框架，稍后把这个自定义过程单独打包成服务器插件部署。

1、用户自定义过程类由SpanningTreeProc.java改为MyKSpanningTreeProc.java，算法实现类由KSpanningTree.java改为PrimK.java，测试用例类由SpanningTreeProcTest.java更改为MyKSpanningTreeProcTest.java。即保留原框架体系而替换实现的逻辑，以便新的自定义过程整个嵌入GDS的框架下。Refactor更改类名时会保证同步更改源码中对该类的引用。删除多余的KSpanningTreePorc.java及KSpanningTreePorcTest.java，留着的话打包发布后，与服务器上GDS库中原有的过程重名，会引起冲突导致服务器不能启动。其它相关的源码类可以导入或保留，以便分析程序。

2、注意我要用原SpanningTreeProc与其测试用例的框架混合原KSpanningTree的算法实现，来写自己的K最小生成树算法，这样运行结果中的生成树（关系）就直接写入数据库，稍后查询即可，而不是原KSpanningTreeProc写入的节点连接数，用起来就方便多了。要更改AlgorithmFactory()中对PrimK实例化的参数，因为原来引用算法实现Prim.java，它的实例化参数与原算法实现KSpanningTree.java（现PrimK.java）是不同的。在未解决参数k由Cypher传入之前，可以先设定为常数，比如k=3，来测试PrimK算法的实现。 3、更改MyKSpanningTreeProc.java中各自定义过程的名字，有别于原名以免部署后引起冲突，比如“@Procedure(value = "gds.alpha.spanningTree.mykmin.write", mode = WRITE)”，更改测试用例中对应的自定义过程引用，比如testMinimum()中的".algo("gds.alpha.spanningTree.mykmin")"等。

4、PrimK.java是Prim.java与KSpanningTree.java合并的结果，因为要保留对原SpanningTreeProc.java，现MyKSpanningTreeProc.java的支持，要依编译的提示把Prim.java中PrimK.java缺失的部分拷过去，包括 class Result、Builder（用于返回算法运行的结果）的定义等。

5、改好编译通过，修改一下测试用例的部分assert语句，因为实现的算法变了，由Prim.compute()变成PrimK.compute()，即原KSpanningTree.compute()，结果不同了，可以把部分assert语句先注释掉，现在主要测试调用的框架流程。junit单元测试通过，新自定义过程的框架完成。

五、替换K最小生成树算法，即PrimK.compute()的实现。

1、原算法的问题。一是排序后直接删除最小（大）的k条边，剩下的节点数不对，剩下的图也不能保证是连通图。二是后面一条返回结果的语句直接放弃了前面剪枝的结果，返回最小（大）生成树的结果。应该是Alpha状态的算法未完成。

2、我的算法实现， PrimK.java。把最小（大）生成树的边排序后，再次应用Prim算法，从根节点出发，按顺序每次加入一条最小（大）的边连接到已知的最小（大）生成树中，直到有k个节点。 3、同步更新测试用例中的assert语句，注意k参数现在是常数，还没有从Cypher传入。算法的junit单元测试通过。
六、从Cypher传入参数K。
1、自定义过程的类定义泛型。自定义过程的类定义泛型规定了每个GDS算法过程有三个类参数：《算法，结果，配置》，我的自定义过程使用PrimK算法，返回SpanningTree，与SpanningTreeProc.java一样使用配置SpanningTreeConfig，这个配置是没有参数K的。 2、SpanningTreeConfig是个接口类，在MyKSpanningTreeProc.newConfig()中调用SpanningTreeConfig.of()实例化。 3、真正实例化配置类的是org.neo4j.graphalgo.spanningtree.SpanningTreeConfigImpl。但这个类找不到源码，并且它是个final类，不能被继承扩展。所以要寻找编写MyKSpanningTreeConfig接口与MyKSpanningTreeConfigImpl类以外的方法来传入参数K（后面经与Noe4j公司沟通，得知该类是由接口类SpanningTreeConfig.java的@Configuretion标注在Gradle build时动态生成，据此定义了MyKSpanningTreeConfig.java接口并生成了MyKSpanningTreeConfigImpl.java，这里为说明原理仍然保留本节内容）。 4、Cypher传入的参数封装为org.neo4j.graphalgo.core.CypherMapWrapper，它是开源的。并且内部存储为Map，提供了提取增删等接口，所以我在上面的MyKSpanningTreeProc.newConfig()中，从Cypher传入的config中提取参数k，存储在类变量中，然后从config中删除k，实例化没有参数k的SpanningTreeConfig。后面MyKSpanningTreeProc.AlgorithmFactory()引用类变量中的k实例化算法PrimK，这是一个workaround。 5、修改GDS源码中的org.neo4j.graphalgo.AlgoBaseProc.newConfig()，在检查传入参数合法性前，加入参数k，这是最低限度的hack，只插入了2行代码。AlgoBaseProc是所有算法过程的abstrack父类，该方法在调用自己的abstract方法newConfig(username(), graphName, maybeImplicitCreate, config)方法时，会调用在MyKSpanningTreeProc.newConfig()中的实现，那里提取了参数k并产生了SpanningTreeConfig实例。 6、修改MyKSpanningTreeProcTest测试用例中各测试对各用户自定义过程的调用，加入参数k，同步调整各assert语句。运行单元测试，通过。 七、更新GDS源码，重新编译打包。

Noe4j为插件写了单独的ProcedureClassLoader，会检查jar包的完整性，如果直接解压替换AlgoBaseProc.class等类，会抛出Exception导致服务器启动不了，所以需要把源码中hack过的AlgoBaseProc.java替换，重新编译GDS并打包。GDS项目是用Gradle管理的，要先 下载安装Gradle。

1、安装Gradle，配置init.gradle以便Gradle使用国内镜像， 参考资料。注意要配置环境变量GRADLE_USER_HOME，与GRADLE_HOME相同，这样下载的依赖库缓存会放在该目录的caches子目录中，有近700M。

2、在命令行窗口转到GDS源码解压后的项目根目录，运行gradle命令生成项目的编译config。这个过程需要的时间比较长，要检查并下载每个子项目每个模块的依赖包，生成它们的编译配置，需要几十分钟。

3、运行gradle tasks命令，查看根项目可执行的任务。build任务是编译并运行所有测试，耗时很长。但由于一些源码处于Alpha状态，有些单元测试会失败，从而导致build失败。所以只执行gradle classes编译源码，不编译测试用例。

4、运行gradle classes编译源码。 5、运行gradle distZip打包，放在项目根目录的/build/distributions下的zip文件，解压后就是jar包。 6、在Eclipse中把自定义过程的项目也打包，项目上鼠标右键->Run As->Maven Install。

7、把两个插件都复制到D:\Neo4j\neo4j-chs-community-4.2.1-s\plugins目录下，启动Neo4j server测试。

八、测试在Cypher中调用 九、Done, to be continued...

这个实验到这里就全部完成了，后面照样拷贝Prim.java，SpanningTreeProc.java，SpanningTreeProcTest.java，并把Prim.compute()替换成朱刘算法，就可以完成有向图的最小树形图，K最小树形图照拷照改即可。

十、补充修订

经过与Neo4j公司的沟通，源码SpanningTreeConfigImpl.java是在GDS项目build的过程中动态生成的，只要定义了接口SpanningTreeConfig.java，并把该接口拷贝到GDS源码对应的目录\alpha\alpha-proc\src\main\java\org\neo4j\graphalgo\spanningtree下，转到项目根目录，在命令行下运行gradle assemble生成所有输出，会在\alpha\alpha-proc\build\generated\sources\annotationProcessor\java\main\org\neo4j\graphalgo\spanningtree目录下找到生成的Impl源码。据此定义了接口MyKSpanningTreeConfig.java，并运行gradle assemble生成了MyKSpanningTreeConfigImpl.java，在Eclipse项目中导入生成的代码后，删除拷贝到GDS源码中的MyKSpanningTreeConfig.java及生成的MyKSpanningTreeConfigImpl.java，这样就可以避免hack GDS的源码AlgoBaseProc.java，GDS恢复用发行版，版本更新就比较方便了。

然后将MyKSpanningTreeProc.java中所有对SpanningTreeConfig的引用都改为MyKSpanningTreeConfig，更新一下newConfig()方法与algorithmFactory()方法，重新单元测试、打包发布即可。