1 介绍

1.1 项目特性

1. 支持多种图数据结构:通常会支持多种类型的图，如无向图、有向图、加权图、非加权图等。

2. 实现图的创建、节点和边的添加、删除等基本操作。

3. 包含一些常见的图论算法，如最短路径算法（如 Dijkstra、Bellman-Ford）、最小生成树（如 Prim、Kruskal）、拓扑排序、网络流等。

4. 本项目基于 Java 版本的 JGraphT(https://github.com/jgrapht/jgrapht)进行开发和改进，原项目是一个用于图算法和数据结构的开源库。本项目对其进行了移植，以适应仓颉环境的需求。

1.2 项目计划

1. 2024 年 9 月发布 0.1.0 版本。包含基础功能，支持无向图、有向图，带权图的创建及基本操作（添加节点、边，删除节点、边）。并发布基础文档。

2. 之后的版本中，计划完善图的基础功能，并实现图的toString方法，同时有序的引入简单的图论算法。在此基础上完善图的展示功能。

3. 在进一步完善后，引入高级图论算法，扩展可视化功能，提供更丰富的交互图形展示。

2 架构

2.1 项目结构

.
├── README.md
├── LICENSE
├── CHANGELOG
├── cjpm.toml
├── doc
|   └── readme-image
|
└── src                                               
    ├─ extension                                      
    │  └─ map.cj                                      
    ├─ graph               #核心代码                           
    │  ├─ abstract_base_graph.cj                      
    │  ├─ abstract_graph.cj                           
    │  ├─ abstract_graph_builder.cj                   
    │  ├─ as_unmodifiable_graph.cj                    
    │  ├─ as_unweighted_graph.cj                      
    │  ├─ base_intrusive_edges_specifics.cj           
    │  ├─ default_directed_graph.cj                   
    │  ├─ default_directed_weighted_graph.cj          
    │  ├─ default_edge.cj                             
    │  ├─ default_graph_iterables.cj                  
    │  ├─ default_graph_type.cj                       
    │  ├─ default_undirected_graph.cj                 
    │  ├─ default_undirected_weighted_graph.cj        
    │  ├─ default_weighted_edge.cj                    
    │  ├─ directed_edge_container.cj                  
    │  ├─ directed_multigraph.cj                      
    │  ├─ directed_specifics.cj                       
    │  ├─ edge_set_factory.cj                         
    │  ├─ fast_lookup_directed_specifics.cj           
    │  ├─ fast_lookup_graph_specifics_strategy.cj     
    │  ├─ graph.cj                                    
    │  ├─ graphs.cj                                   
    │  ├─ graph_builder.cj                            
    │  ├─ graph_delegator.cj                          
    │  ├─ graph_iterables.cj                          
    │  ├─ graph_specifics_strategy.cj                 
    │  ├─ graph_type.cj                               
    │  ├─ hash_set_edge_set_factory.cj                
    │  ├─ intrusive_edge.cj                           
    │  ├─ intrusive_edges_specifics.cj                
    │  ├─ intrusive_edge_exception.cj                 
    │  ├─ intrusive_weighted_edge.cj                  
    │  ├─ live_iterable_wrapper.cj                    
    │  ├─ pseudograph.cj                              
    │  ├─ simple_graph.cj                             
    │  ├─ specifics.cj                                
    │  ├─ uniform_intrusive_edges_specifics.cj        
    │  ├─ weighted_intrusive_edges_specifics.cj       
    │  └─ weighted_pseudograph.cj                     
    ├─ test                     #测试类                      
    │  ├─ graph                                       
    │  │  ├─ as_unmodifiable_graph_test.cj            
    │  │  ├─ as_unweighted_graph_test.cj              
    │  │  ├─ directed_graph_test.cj                       
    │  │  ├─ generic_graphs_test.cj                       
    │  │  ├─ graph_builder_test.cj                      
    │  │  ├─ weighted_graph_test.cj                             
    │  ├─ import.cj                                              
    ├─ util                                           
    │  ├─ key_map_set.cj                              
    │  ├─ pair.cj                                     
    │  └─ unmodifiable_set.cj                           
    └─ package.cj                                     

2.2 接口说明

名称	用途
public interface Graph<V, E>	这是一个图的核心接口，定义了图的基本操作，包括添加和删除节点、边，以及获取图的信息
public interface GraphType	用于表示图的类型和属性，帮助图论框架或库区分不同的图（如有向图、无向图、加权图、循环图等），并提供相关的行为约束
public interface EdgeSetFactory<V, E>	为图中的节点创建和管理边的集合，允许图的实现类根据需求灵活选择如何存储边的集合
public interface GraphIterables<V, E>	为图（Graph<V, E>）提供与图结构相关的迭代操作，以可迭代的方式访问图中的元素，而无需直接操作图的内部数据结构
public interface IntrusiveEdgesSpecifics<V, E>	为图结构提供对边（Edge）的具体管理和操作。这个接口定义了与边相关的操作，允许图结构实现类通过它来管理边的添加、移除、查询、以及边的权重设置等操作
public interface GraphSpecificsStrategy<V, E>	通过定义一系列工厂方法，为图的内部结构（特别是边和顶点）提供灵活的创建和管理方式
public interface Specifics<V, E>	定义与图结构中顶点和边相关的核心操作。它提供了对图中顶点和边的管理、查询、添加、移除等操作的具体方法

3 使用说明

3.1 编译构建（Win/Linux/Mac）

cjpm build

3.2 功能示例

3.2.1 创建一个三个点的有向简单图

    private func createMultiTriangle(): Graph<String, DefaultEdge<String>> {
        let g = DirectedMultigraph<String, DefaultEdge<String>>({=> DefaultEdge<String>()});
        initMultiTriangle(g);
        return g;
    }

    private func initMultiTriangle(g: Graph<String, DefaultEdge<String>>): Unit {
        //添加顶点v1，v2，v3
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        //添加有向边v1->v2，v2->v1，v2->v3,v3->v1
        g.addEdge(v1, v2);
        g.addEdge(v2, v1);
        g.addEdge(v2, v3);
        g.addEdge(v3, v1);
        
    }

    var g: Graph<String, DefaultEdge<String>> = createMultiTriangle();
    //v1的度为3,v2的度为3,v3的度为2
    println("${g.edgesOf(v1).size} ${g.edgesOf(v2).size} ${g.edgesOf(v3).size}")
    //v1的入度为2,v2的入度为1,v3的入度为1
    println("${g.inDegreeOf(v1)} ${g.inDegreeOf(v2)} ${g.inDegreeOf(v3)}")
    //v1的出度为1,v2的出度为2,v3的出度为1
    println("${g.outDegreeOf(v1)} ${g.outDegreeOf(v2)} ${g.outDegreeOf(v3)}")

3.2.2 创建带权图

        //创建带权伪图
        var g: WeightedPseudograph<Int64, DefaultWeightedEdge<String>> = WeightedPseudograph<Int64, DefaultWeightedEdge<String>>(
            {=> DefaultWeightedEdge<String>()})
        //添加顶点1，2
        g.addVertex(1);
        g.addVertex(2);
        //添加带权边1->2，默认边权为1
        var eOption: ?DefaultWeightedEdge<String> = g.addEdge(1, 2);
        var e = eOption.getOrThrow();
        println("${e}")
        //为边e设置权重3
        g.setEdgeWeight(e, 3.0);
        println("${g.getEdgeWeight(e)}")

3.2.3 通过图建造器对图进行简单添加操作

        var e1 = DefaultWeightedEdge<String>();
        var e2 = DefaultWeightedEdge<String>();
        //创建了一个图，共有8个点，添加了边v1->v2,边链v3->v4->v5->v6,边v7->v8，权值10,边v1->v7,边v1->v8，权值42
        var g: Graph<String, DefaultWeightedEdge<String>> = GraphBuilder<String, DefaultWeightedEdge<String>, Graph<String,
                DefaultWeightedEdge<String>>>(
            DefaultDirectedWeightedGraph<String, DefaultWeightedEdge<String>>({=> DefaultWeightedEdge<String>()})).
            addEdge(v1, v2).addEdgeChain(v3, v4, v5, v6).addEdge(v7, v8, 10.0).addEdge(v1, v7, e1).addEdge(v1, v8, e2,
            42.0).buildAsUnmodifiable();
        //共7条边，8个点
        println("${g.edgeSet().size}")
        println("${g.vertexSet().size}")
        //同理使用g.containsEdge(v7, v8)等可以检验是否加入边

3.2.4 通过图建造器将一个子图加入到新的图中

        //创建了一个图g1，共有3个点，添加了边v2->v3
        var g1: Graph<String, DefaultEdge<String>> = DefaultDirectedGraph<String, DefaultEdge<String>>.createBuilder(
            {=> DefaultEdge<String>()}).addVertex(v1).addEdge(v2, v3).buildAsUnmodifiable();
        //创建了一个图g2，加入了子图g1，加入后共有4个点，并添加了边v1->v4
        var g2: Graph<String, DefaultEdge<String>> = GraphBuilder<String, DefaultEdge<String>, Graph<String, DefaultEdge<String>>>(
            DefaultDirectedGraph<String, DefaultEdge<String>>({=> DefaultEdge<String>()})).addGraph(g1).addEdge(v1, v4).
            build();
        //g2共2条边，4个点
        println("${g2.edgeSet().size}")
        println("${g2.vertexSet().size}")
        //同理使用g2.containsEdge(v1, v4)可以检验是否加入边（包括g1中的边）

3.2.5 通过图建造器对图进行简单删除操作

        //创建了一个图g1，共有5个点，添加了边v1->v3，边链v2->v3->v4->v5
        var g1: Graph<String, DefaultEdge<String>> = GraphBuilder<String, DefaultEdge<String>, Graph<String, DefaultEdge<String>>>(
            DefaultDirectedGraph<String, DefaultEdge<String>>({=> DefaultEdge<String>()})).addEdge(v1, v3).addEdgeChain(
            v2, v3, v4, v5).buildAsUnmodifiable();
        //创建了一个图g2，加入了子图g1，加入后共有5个点，并删除了点v2，v4，v5，连带着相应边一同删除
        var g2: Graph<String, DefaultEdge<String>> = GraphBuilder<String, DefaultEdge<String>, Graph<String, DefaultEdge<String>>>(
            DefaultDirectedGraph<String, DefaultEdge<String>>({=> DefaultEdge<String>()})).addGraph(g1).removeVertex(v2).
            removeVertices(v4, v5).build();
        //g2还剩共1条边，2个点
        println("${g2.edgeSet().size}")
        println("${g2.vertexSet().size}")
        //同理使用g2.containsEdge(v1, v3)可以检验剩下的（包括g1中的边）

4 参与贡献

本项目由 SIGCANGJIE / 仓颉兴趣组 实现并维护。技术支持和意见反馈请提Issue。

本项目基于 Apache License 2.0，欢迎给我们提交PR，欢迎参与任何形式的贡献。

本项目committer：@2301_76230122

This project is supervised by @zhangyin_gitcode (HUAWEI Developer Advocate).