图形表示

此库提供了不同图形的表示，其中一些使用效率高，而另一些构建效率高。

该库支持在不同表示之间进行转换，同时保留节点ID。

快速入门示例

创建一个邻接数组。

use graphrepresentations::simplegraph::SimpleGraph;
use graphrepresentations::graph::{MutableGraph, Node, Edge, Graph};
use graphrepresentations::adjacencyarray::AdjacencyArray;

let mut simple_graph = SimpleGraph::new();
let n1 = simple_graph.add_node(Node::new(5));
let n2 = simple_graph.add_node(Node::new(7));
let e1 = simple_graph.add_edge(Edge::new(n1, n2, 'c')).unwrap_or_else(|error| panic!("The edge refers nonexistent nodes: {:?}", error));
let adjacency_array = AdjacencyArray::from(&simple_graph);

let mut node_iter = adjacency_array.node_id_iter();
let mut edge_iter = adjacency_array.edge_id_iter();
assert_eq!(simple_graph.node_data(node_iter.next().expect("Node got lost")), adjacency_array.node_data(n1)); // The order of the nodes is guaranteed to stay the same
assert_eq!(simple_graph.node_data(node_iter.next().expect("Node got lost")), adjacency_array.node_data(n2));
assert_eq!(node_iter.next(), None);
assert_eq!(adjacency_array.edge(edge_iter.next().expect("Edge was not converted correctly")), simple_graph.edge(e1));
assert_eq!(edge_iter.next(), None);

遍历相同的邻接数组。

// The same adjacency array as above
let mut neighbors = adjacency_array.out_edges(n1);
assert_eq!(adjacency_array.edge(neighbors.next().expect("Edge was not converted correctly")), simple_graph.edge(e1));
assert_eq!(neighbors.next(), None);

图形特性

• Graph 图的基本特性。它不能做很多，只能作为不可修改的容器。支持遍历节点和边ID，以及通过ID查找节点和边数据。
• MutableGraph 可变图的特性。实现此特性的图应允许高效的变异。目前，此特性仅要求 add 方法。
• ForwardNavigableGraph 可向前导航的图。它需要返回节点所有出边迭代器的 out_edges 方法。
• IterableGraph 支持高效遍历完整节点和边数据的图。这尚未实现，并受阻于 #29661。

图形表示

目前，此库支持两种图形表示。一种动态的，一种静态的。

• SimpleGraph: Graph + MutableGraph 一个动态图形表示，允许高效修改，但不太适合实现任何算法。
• AdjacencyArray: Graph + ForwardNavigableGraph 一个静态图形表示，在图形算法中使用效率高，但修改效率低。目前，修改需要通过从 SimpleGraph 重建它来完成。

ID解释

这个包使用ID来引用节点和边。在实现邻接数组或边列表时，这是很自然的。它是一种快速且简单的方法，可以在客户端代码中传递节点和边数据，而无需担心借用。ID是32位（未来可能也是64位），因此传递它们基本上是无成本的。

请注意，ID与创建它们的图实例没有任何绑定。没有保护措施可以防止在一个图实例中使用ID去引用另一个图，这可能导致不可预测的行为。但是，使用一个图实例的节点ID与该图转换后的版本一起使用，如果转换后没有任何图被修改，则可以保证一致地工作。

如果您缺少某个功能或发现了错误，请在github上提交问题。