图数据结构库

您可以在这里找到 API 文档

GDSL 是一个图数据结构库，提供高效且易于使用的抽象，用于处理连接节点和图。与许多其他图实现不同，在 GDSL 中，图主要只是一个容器，功能在 Node<K, N, E> 结构中，该结构可以用来创建不同的图表示，或者更自由地用作其他数据结构的一部分。

• 有向和无向图以及节点类型。

• 节点和图类型的正常和同步版本。通常，节点被包装在 Rc 指针中，相邻边在 RefCell 中。在同步版本中，这些是 Arc 和 RwLock。

• 节点实现算法的构建块，包括广度优先、深度优先和优先级优先遍历以及后序和前序。

• 用于创建易于阅读的行内图的宏。

• 删除或插入连接或以其他方式操作图或其任何节点是稳定的。对节点或边的任何引用都保持一致。这是由于不依赖于底层容器，在底层容器中，节点和边会被表示为单独的列表并按索引访问，在 GDSL 中，一个节点“拥有”其所有传入和传出连接。另一方面，每个节点代表一个堆分配，并将其相邻边存储在 RefCell 或 RwLock 中。

• 图实现了 Serde 的序列化和反序列化。

创建此库的动机在于探索将图和连接节点作为更通用的数据结构的概念，这些结构存储数据而不依赖于中央图容器，而中央图容器反过来又实现图逻辑。

有关 GDSL 实现的算法的注释示例可以在 examples 文件夹中找到。

概述

节点类型不需要是图容器的组成部分。它们是自包含的“连接智能指针”，可以通过指针语法连接到其他节点并解引用。节点的唯一性由类型为 K 的泛型键确定。

let n1 = Node::<char, i32, f64>::new('A', 42);
let n2 = Node::<char, i32, f64>::new('B', 6);

n1.connect(&n2, 0.5);

assert!(*n1 == 42);
assert!(n2.key() == &'B');

// Get the next edge from the outbound iterator.
let Edge(u, v, e) = n1.iter_out().next().unwrap();

assert!(u.key() == &'A');
assert!(v == n2);
assert!(e == 0.5);

节点包含它们的入边和出边，即使在有向图中也是如此。这样做是为了使图成为“动态”的，即易于在运行时修改。如果我们想有效地从一个图中删除节点，例如，如果我们知道节点的入边连接，那么我们可以轻松地断开节点与另一个节点的连接。在定向图中，迭代器用于迭代出边或入边，在无向图中，迭代器用于迭代相邻边。

// Edge is a tuple struct so can be decomposed using tuple syntax..
for Edge(u, v, e) in &node {
    println!("{} -> {} : {}", u.key(), v.key(), e);
}

// ..or used more conventionally as one type.
for edge in &node {
    println!("{} -> {} : {}", edge.source().key(), edge.target().key(), edge.value());
}

// Transposed iteration i.e. iterating the inbound edges of a node in digrap.
for Edge(v, u, e) in node.iter_in() {
    println!("{} <- {} : {}", u.key(), v.key(), e);
}

如上例所示，边在迭代器和其他结构中表示为元组 (u, v, e)，在闭包中作为参数表示为 |u, v, e|。边的内部表示不会暴露给用户。

节点包含用于搜索和排序节点的接口。这些接口作为 search objects 实现，它们的工作方式类似于迭代器。

let path = node.dfs()
    .target(&'A')
    .search_path();

let ordering = node.order()
    .post()
    .filter(&|u, v, v| /* filter search */)
    .search_nodes();

该库提供用于创建图（如 digraph![] 和 ungraph![]）的宏，具有特殊的语法和不同的类型签名。

let g = digraph![
    (usize)
    (0) => [1, 2]
    (1) => [1]
    (2) => [0]
];

示例：简单图

以下是如何创建没有容器或使用任何宏以方便方式创建图的简单示例。实际上，大部分功能都位于 Node 中。节点包含连接（添加边）、断开连接、搜索等方法。它们还作为“智能指针”使用，并实现了 Deref，以便可以将它们解引用到其内部值。

use gdsl::digraph::node::Node;
use gdsl::*;

fn main() {

    // We create directed nodes with characters as keys and integers as values.
    // The turbofish type-signature is included in the first line for clarity,
    // but the types could be completely inferred. Note that in order to infer
    // the type for the edge, `connect()` or `connect!()` must be used.
    let node_a = Node::<char, i32, ()>::new('A', 1);
    let node_b = Node::new('B', 2);
    let node_c = Node::new('C', 3);

    // We connect nodes a -> b and b -> c. The () empty tuple is used to denote
    // that the edge has no value associated with it.
    node_a.connect(&node_b, ());
    node_b.connect(&node_c, ());

    // Check that a -> b && b -> c && !(a -> c)
    assert!(node_a.is_connected(&node_b));
    assert!(node_b.is_connected(&node_c));
    assert!(!node_a.is_connected(&node_c));
}

示例：使用宏

以不同类型签名创建图的不同方法。

use gdsl::*;

fn main() {

    // <&str, _, _>
    let g1 = digraph![
        (&str)
        ("A") => ["B", "C"]
        ("B") => ["C"]
        ("C") => ["D"]
        ("D") => []
    ];

    // <&str, i32, _>
    let g2 = digraph![
        (&str, i32)
        ("A", 42) => ["B", "C"]
        ("B", 42) => ["C"]
        ("C", 42) => ["D"]
        ("D", 42) => []
    ];

    // <&str, _, i32>
    let g3 = digraph![
        (&str) => [i32]
        ("A") => [("B", 42), ("C", 42)]
        ("B") => [("C", 42)]
        ("C") => [("D", 42)]
        ("D") => []
    ];

    // <&str, i32, f64>
    let g4 = digraph![
        (&str, i32) => [f64]
        ("A", 42) => [("B", 3.14), ("C", 3.14), ("D", 3.14)]
        ("B", 42) => [("C", 3.14), ("D", 3.14)]
        ("C", 42) => [("D", 3.14)]
        ("D", 42) => []
    ];
}

示例：Dijkstra的最短路径

以下是一个使用图库抽象实现的Dijkstra最短路径算法的注释示例。

use gdsl::*;
use std::cell::Cell;

// We create a directed graph using the `digraph![]` macro. In the macro
// invocation we specify the type of the nodes and the type of the edges
// by specifying the type-signature `(NodeKey, NodeValue) => [EdgeValue]`.
//
// The `NodeKey` type is used to identify the nodes in the graph. The
// `NodeValue` type is used to store the value of the node. The `EdgeValue`
// type is used to store the value of the edge.
//
// In this example the node stores the distance to the source node of the
// search. The edge stores the weight of the edge. The distance is wrapped
// in a `Cell` to allow for mutable access. We initialize the distance to
// `std::u64::MAX` to indicate that the node is not part of the shortest
// path.
let g = digraph![
    (char, Cell<u64>) => [u64]
    ('A', Cell::new(u64::MAX)) => [ ('B', 4), ('H', 8) ]
    ('B', Cell::new(u64::MAX)) => [ ('A', 4), ('H', 11), ('C', 8) ]
    ('C', Cell::new(u64::MAX)) => [ ('B', 8), ('C', 2), ('F', 4), ('D', 7) ]
    ('D', Cell::new(u64::MAX)) => [ ('C', 7), ('F', 14), ('E', 9) ]
    ('E', Cell::new(u64::MAX)) => [ ('D', 9), ('F', 10) ]
    ('F', Cell::new(u64::MAX)) => [ ('G', 2), ('C', 4), ('D', 14), ('E', 10) ]
    ('G', Cell::new(u64::MAX)) => [ ('H', 1), ('I', 6), ('F', 2) ]
    ('H', Cell::new(u64::MAX)) => [ ('A', 8), ('B', 11), ('I', 7), ('G', 1) ]
    ('I', Cell::new(u64::MAX)) => [ ('H', 7), ('C', 2), ('G', 6) ]
];

// In order to find the shortest path we need to specify the source node and
// set its distance to 0.
g['A'].set(0);

// In order to perform a dijkstra's we can use the priority first search or
// `pfs` for short. We determine a  source node create a `Pfs` search-object
// by calling the `pfs()` method on the node.
//
// If we find a shorter distance to a node we are traversing, we need to
// update the distance of the node. We do this by using the `for_each()` method
// on the Pfs search object. The `for_each()` method takes a closure as argument
// and calls it for each edge that is traversed. This way we can manipulate
// the distance of the node. based on the edge that is traversed.
//
// The search-object evaluates lazily. This means that the search is only
// executed when calling either `search()` or `search_path()`.
g['A'].pfs().for_each(&mut |Edge(u, v, e)| {

    // Since we are using a `Cell` to store the distance we use `get()` to
    // read the distance values.
    let (u_dist, v_dist) = (u.get(), v.get());

    // the distance stored in the node `u` + the length (weight) of the
    // Now we check if the distance stored in the node `v` is smaller than
    // edge `e`. If this is the case we update the distance stored in the
    // node `v`.
    if v_dist > u_dist + e {
        v.set(u_dist + e);
    }
}).search();

// We expect that the distance to the node `E` is 21.
assert!(g['E'].take() == 21);

类似库

• Petgraph 可能是Rust中最常用的图库。提供更多图表示，但所有这些都绑定到容器。

联系开发者

[email protected]