generic_graph

一个Rust库，提供实现图的特质的接口。

所有特质都是使用泛型定义的，给程序员在实现上提供了更多的自由。

提供的默认实现考虑了标准用例，应该适用于大多数情况。

特质描述

DirectedGraph

pub trait DirectedGraph<T, E, K, V, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Add + Sub + Eq + Ord + Copy,
          T: Vertex<K, V>,
          E: Edge<K, W, C>
{
    fn adjacent(&self, from: &K, to: &K) -> bool;

    fn neighbors(&self, from: &K) -> Vec<&K>;

    fn leading_to(&self, to: &K) -> Vec<&K>;

    fn get_all_keys(&self) -> Vec<&K>;

    fn get_all_pairs(&self) -> Vec<(&K, &K)>;

    fn get_vertex(&self, key: &K) -> Option<&T>;

    fn get_mut_vertex(&mut self, key: &K) -> Option<&mut T>;

    fn get_edge(&self, pair: (&K, &K)) -> Option<&E>;

    fn get_mut_edge(&mut self, pair: (&K, &K)) -> Option<&mut E>;
}

这是在这个库中定义的主要特质。它旨在实现具有有向边的图。

• adjacent 接收两个顶点的键，返回一个布尔值，表示是否存在从第一个到第二个的弧。
• neighbors 接收一个顶点的键，返回一个包含所有相邻顶点键（从传递的顶点可达）的向量。
• leading_to 接收一个顶点的键，返回一个包含作为邻居的顶点的向量。
• 其余的是简单的获取器。

Graph

pub trait Graph<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Add + Sub + Eq + Ord + Copy,
          T: Vertex<K, V>,
          E: Edge<K, W, C>
{}

这个特质不定义方法。它仅指定图不是有向的。

以下属性必须成立

• graph.neighbors().sort() ==graph.leading_to().sort()
• graph.get_edge((a, b)) == graph.get_edge((b, a)) (同样适用于 get_mutable_edge())
• graph.adjacent(a,b) ==graph.adjacent(b,a)

VariableVertexes

pub trait VariableVertexes<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Add + Sub + Eq + Ord + Copy,
          T: Vertex<K, V>,
          E: Edge<K, W, C>
{
    fn add_vertex(&mut self, vertex: T)  -> Option<T>;

    fn remove_vertex(&mut self, key: K) -> Option<T>;
}

这个特质增加了对顶点的添加和删除方法。必须在具有可变数量顶点的图中实现。

add_vertex() 方法如果在之前未设置元素，则应返回 None。否则，元素将被更新（但不是键），并返回旧元素作为 Some(old_element)。

remove_vertex() 方法如果在未找到元素，则返回 None；如果找到，则返回 Some(element)。

VariableEdges

pub trait VariableEdges<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Add + Sub + Eq + Ord + Copy,
          T: Vertex<K, V>,
          E: Edge<K, W, C>
{
    fn add_edge(&mut self, edge: E) -> Result<Option<E>, EdgeSide>;

    fn remove_edge(&mut self, pair: (&K, &K)) -> Option<E>;
}

此特性添加了边的添加和删除方法。必须在具有可变边数的图中实现。

add_edge() 方法如果在之前未设置元素，则返回 Ok(None)。否则，元素将被更新（但不是键），并返回旧元素作为 Ok(Some(old_element))。如果涉及的顶点之一或两个都缺少，则返回包含枚举指定缺少哪一方的错误（Err(EdgeSide)）。

remove_edge() 方法如果在未找到元素，则返回 None；如果找到并删除，则返回 Some(element)。

Vertex

pub trait Vertex<K, V>
    where K: Hash + Eq + Clone
{
    fn get_value(&self) -> &V;

    fn get_mut_value(&mut self) -> &mut V;

    fn key(&self) -> K;
}

这是定义顶点行为的特性。键类型（K）必须是可哈希的、可比较的（非部分）且可复制的。不需要实现复制，但建议这样做。

Edge

pub trait Edge<K, W, C>
    where K: Hash + Eq + Clone,
          C: Hash + Eq + Clone,
          W: Add + Sub + Eq + Ord + Copy
{
    fn get_weight(&self) -> W;

    fn set_weight(&mut self, weight: W);

    fn left(&self) -> &K;

    fn right(&self) -> &K;

    fn get_pair(&self) -> (&K, &K);

    fn generate_key(pair: (&K, &K)) -> C;

    fn key(&self) -> C;
}

此特性定义了边的行性行为。它需要两种键类型，一种用于顶点（K）和一种用于边（C）。它还要求有一个可求和的、可减去的、可比较的、有序且可复制的权重类型。

边必须实现一个关联函数，从一对顶点键生成键。边的键必须由一对顶点键生成，不能再由其他东西生成。

默认实现

库提供了具有一些默认实现的模块，针对标准用例进行了优化。在选择要使用哪个模块之前或是否应该实现自己的模块之前，请检查实现的目标。

AdjacencyList

具有可变数量顶点和边的有向图，适用于处理大型增长图。

顶点的键和值类型以及边的权重类型是泛型。

它使用 HashMap 实现，以保持结构快速，同时允许其按大小增长。

AdjacencyMatrix（未来实现）

适用于处理小型快速图的有向图。顶点数是固定的，但可以添加或删除边。

顶点的键类型是 usize，顶点的值类型和边的权重类型仍然是泛型。

它使用一个二维矩阵存储权重，允许直接访问边，但以防止顶点数量的可变性为代价。

（尚未定义的无向图）

未来将添加无向图的实现。

附加类型

SimpleVertex

pub struct SimpleVertex<K: Hash + Eq + Clone, V> {
    key: K,
    value: V,
}

impl<K: Hash + Eq + Clone, V> SimpleVertex<K, V> {
    pub fn new(key: K, value: V) -> SimpleVertex<K, V> {}
}

impl<K: Hash + Eq + Clone, V> Vertex<K, V> for SimpleVertex<K, V> {}

此类型为Vertex提供了一种简单的默认实现，对于大多数使用场景来说是足够的。

它附带了一个关联函数new()，该函数不是由trait定义的。

EdgeSide

pub enum EdgeSide {
    Left,
    Right,
    Both
}

EdgeSide类型是一个枚举，用于指定哪条边的哪一侧导致了特定情况。当程序试图向图中添加边，但涉及的顶点之一或两个缺失时，由add_edge()方法中的Result::Err()返回时，会返回此枚举。这表明在尝试添加边时缺失了一个或两个顶点。

它旨在由用户实现的功能用于处理此类情况。