TTGraph README

TTGraph是

• 许多不同数据的容器或数据库，它们相互交叉引用，形成类似图的数据结构。
• 类型化图：多个类型节点的集合。每个节点包含一些私有数据，以及指向其他节点的指针/边/引用。
• 事务性图：对图的所有操作都由事务组织，这意味着原子操作组同时应用。

TTGraph提供

• 不同类型数据的方便容器，提供一些处理类型的有用方法。
• 一个数据结构来维护节点之间的连接。TTGraph为所有类型创建一个反射来跟踪节点之间的连接，称为 link。这允许一些复杂的操作，例如重定向链接和维护双向链接。
• 一个清晰的接口，帮助消除一些讨厌的编译错误。事务的设计试图防止同一对象的不可变引用和可变引用同时存在，并试图避免陷入生命周期迷宫。
• TTGraph最初设计为编译器的中间表示系统，但其潜力不仅限于此。

TTGraph目前不提供，但可能在未来改进

• 非常高的性能。虽然TTGraph操作相对便宜（大部分是O(log(n)）），但它不是一个高性能数据库。
• 非常大的容量。所有数据都存储在内存中。

动机示例

类型节点声明

假设有几个工厂、工人和产品，以下示例使用TTGraph来维护它们的数据。

use tgraph::*;
use std::collections::HashSet;

#[derive(TypedNode)]
struct FactoryNode{
  name: String,
  workers: HashSet<NodeIndex>,
  products: HashSet<NodeIndex>,
}

#[derive(TypedNode)]
struct WorkerNode{
  name: String,
  factory: NodeIndex,
  produced: Vec<NodeIndex>,
}

#[derive(TypedNode)]
struct ProductNode{
  id: usize
}

在这里，一个工厂有一个名称、多个工人和产品。 name 是一个 数据字段，TTGraph不关心它。它可以是在Rust中的任何类型。

workers 和 products 是 链接。链接是与另一个节点的连接。TTGraph 使用 NodeIndex 来索引节点，它实现了 Copy。如果字段是以下类型之一，则被视为链接。（注意：在宏中，类型是通过名称匹配的，tgraph::NodeIndex/NodeIndex/std::collections::Vec::<NodeIndex>/Vec::<tgraph::NodeIndex> 都是可接受的。）

• 直接链接：NodeIndex
• 向量链接：Vec<NodeIndex>
• 无序集链接：HashSet<NodeIndex>
• 有序集链接：BTreeSet<NodeIndex>

图和事务

以下示例展示了如何构建一个图。

// Use an node_enum to collect all node types together
node_enum!{
  enum Node{
    Factory(FactoryNode),
    Worker(WorkerNode),
    Product(ProductNode),
  }
}

// Create the context
let ctx = Context::new();
// Create a graph of Node
let mut graph = Graph::<Node>::new(&ctx);

// Does some initial operations with a transaction
// Actual type: Transaction::<Node>, <Node> can be inferenced when commited
let mut trans = Transaction::new(&ctx);
let product1 = trans.insert(Node::Product(ProductNode{ id: 1 }));
let product2 = trans.insert(Node::Product(ProductNode{ id: 2 }));
let worker1 = trans.alloc();
let worker2 = trans.alloc();
let factory = trans.insert(Node::Factory(FactoryNode{
  name: "Factory".to_string(),
  workers: HashSet::from([worker1, worker2]),
  products: HashSet::from([product1, product2]),
}));
trans.fill_back(worker1, Node::Worker(WorkerNode{
  name: "Alice".to_string(),
  factory,
  produced: vec![product2],
}));
trans.fill_back(worker2, Node::Worker(WorkerNode{
  name: "Bob".to_string(),
  factory,
  produced: vec![product1],
}));

// Commit the transaction to the graph
graph.commit(trans);

// Get the factory node back
let factory_node = get_node!(graph, Node::Factory, factory).unwrap();
assert_eq!(factory_node.name, "Factory");
assert_eq!(factory_node.workers, HashSet::from([worker1, worker2]));
assert_eq!(factory_node.products, HashSet::from([product1, product2]));

首先，使用 node_enum! 宏创建一个枚举来收集所有类型的节点。它是一个 proc_macro，而不是 proc_macro_derive，以便在后面的示例中扩展语法。node_enum! 内部的枚举将实现 NodeEnum 特性，并可以在 Graph 中使用。

node_enum!{
  enum Node{
    Factory(FactoryNode),
    Worker(WorkerNode),
    Product(ProductNode),
  }
}

然后，使用该上下文创建一个上下文和一个图。上下文用于确保所有事务中 NodeIndexes 的一致性。图不保留对上下文的引用，因此用户有责任保留它。

let ctx = Context::new();
let mut graph = Graph::<Node>::new(&ctx);

接下来，使用与图相同的上下文创建一个事务。在事务上执行操作后，可以使用 commit 方法将其提交到图。事务不保留对图的引用，它们具有独立的生存期。（尽管，如果事务寿命超过图，则不会执行任何操作）

let mut trans = Transaction::new(&ctx);
// Do something with trans
graph.commit(trans);

现在我们更详细地看看如何构建图。Product 节点是最简单的，它只有一个 id。使用方法 insert 将节点添加到事务中。它返回一个指向新节点的 NodeIndex，这意味着我们稍后可以使用 product1 和 product2 从图中检索节点。

let product1 = trans.insert(Node::Product(ProductNode{ id: 1 }));
let product2 = trans.insert(Node::Product(ProductNode{ id: 2 }));
# graph.commit(trans);

工厂和工人之间有更复杂的关系，因为它们相互引用。这意味着我们不能单独创建 FactoryNode 或 WorkerNode。幸运的是，TTGraph 在事务中执行操作，我们可以首先使用方法 alloc 为工人分配一个 NodeIndex，然后使用方法 fill_back 填充数据。事务通过检查在提交时所有已分配的节点都已填充回来，防止悬空 NodeIndex。

let worker1 = trans.alloc();
let worker2 = trans.alloc();
let factory = trans.insert(Node::Factory(FactoryNode{
  name: "Factory".to_string(),
  workers: HashSet::from([worker1, worker2]),
  products: HashSet::from([product1, product2]),
}));
trans.fill_back(worker1, Node::Worker(WorkerNode{
  name: "Alice".to_string(),
  factory,
  produced: vec![product2],
}));
trans.fill_back(worker2, Node::Worker(WorkerNode{
  name: "Bob".to_string(),
  factory,
  produced: vec![product1],
}));

最后，在将事务提交到图之后，我们有了上述描述的节点组成的图。我们可以使用 NodeIndex 来获取节点。当节点类型已知时，使用 get_node! 宏，它返回一个 Option<&TypedNode> 来表示节点是否可用。

let factory_node = get_node!(graph, Node::Factory, factory).unwrap();
assert_eq!(factory_node.name, "Factory");
assert_eq!(factory_node.workers, HashSet::from([worker1, worker2]));
assert_eq!(factory_node.products, HashSet::from([product1, product2]));

有关更多操作，请参阅有关结构 Graph 和 Transcation 的文档。

双向链接

TTGraph 支持双向链接声明。在这个例子中，Factory 的 workers 字段和 Worker 的 factory 字段实际上是一对双向链接。我们可以修改 node_enum! 声明以获得更多支持。

node_enum!{
  enum Node{
    Factory(FactoryNode),
    Worker(WorkerNode),
    Product(ProductNode),
  }
  bidirectional!{
    Factory.workers <-> Worker.factory,
  }
}

let ctx = Context::new();
let mut graph = Graph::<Node>::new(&ctx);

let mut trans = Transaction::new(&ctx);
let product1 = trans.insert(Node::Product(ProductNode{ id: 1 }));
let product2 = trans.insert(Node::Product(ProductNode{ id: 2 }));
let factory = trans.insert(Node::Factory(FactoryNode{
  name: "Factory".to_string(),
  workers: HashSet::new(), // Here we leave this set empty to demonstrate it can be automatically filled
  products: HashSet::from([product1, product2]),
}));
let worker1 = trans.insert(Node::Worker(WorkerNode{
  name: "Alice".to_string(),
  factory,
  produced: vec![product2],
}));
let worker2 = trans.insert(Node::Worker(WorkerNode{
  name: "Bob".to_string(),
  factory,
  produced: vec![product1],
}));

graph.commit(trans);

// Get the factory node back
let factory_node = get_node!(graph, Node::Factory, factory).unwrap();
assert_eq!(factory_node.name, "Factory");
assert_eq!(factory_node.workers, HashSet::from([worker1, worker2]));
assert_eq!(factory_node.products, HashSet::from([product1, product2]));

在这里，node_enum! 宏内部使用了 bidiretional! 宏来声明双向链接。

• 使用 variant.field <-> variant.field, 来表示一对双向链接。注意：枚举的变体，而不是类型！
• bidiretional! 不是一个宏，它只能在 node_enum! 内使用

接下来，当创建工厂节点时，其工人字段简单地留空。然而，在提交到图之后，TTGraph 自动将双向链接添加到其中。

双向链接的规则是

• 以下情况可以形成双向链接：一对 NodeIndex，NodeIndex 和 Set<NodeIndex>，一对 Set<NodeIndex>。(Set 可以是 HashSet 或 BTreeSet，目前不支持 Vec)
• 当添加链接时，检查双向链接的另一侧。如果双向链接已经存在，则不发生任何操作。如果该链接有可添加的位置，则自动添加。否则，由于冲突而引发恐慌。
• 当删除链接时，检查双向链接的另一侧。如果双向链接存在，则将其删除。否则，由于 TTGraph 不知道用户是否有意删除它，因此假设不应发生任何操作。
• NodeIndex 字段：如果它是 NodeIndex::empty，则可以添加链接，否则发生冲突并引发恐慌。如果它不为空，则可以删除链接，但如果为空，则不会引发恐慌。
• Set<NodeIndex> 字段：可以始终将链接添加到或从集合中删除。
• 在修改现有的双向链接对时，请确保修改在同一个事务中发生以防止冲突。TTGraph 在维护双向链接之前执行所有其他操作。

#[derive(TypedNode)]
struct HumanWorkerNode{
  name: String,
  // ... other data
}
#[derive(TypedNode)]
struct RobotWorkerNode{
  name: String,
  // ... other data
}

node_enum!{
  enum Node{
    Human(HumanWorkerNode),
    Robot(RobotWorkerNode),
    // ... other nodes
  }
}

let ctx = Context::new();
let mut graph = Graph::<Node>::new(&ctx);
// ... building the graph

// idx: NodeIndex, node: &Node
let node = graph.get(idx).unwrap();

// Not so convinient way to get the name
let name = match node {
  Node::Human(human) => Some(&human.name),
  Node::Robot(robot) => Some(&robot.name),
  _ => None,
};

// A simplified solution
// Here, "name" is the field's name
// The "name" field is a String, so this variable is an Option<&str>
let name = node.data_ref_by_name::<String>("name");

node_enum!{
  enum Node{
    Human(HumanWorkerNode),
    Robot(RobotWorkerNode),
    // ... other nodes
  }
  group!{
    worker{Human, Robot},
  }
}

for (idx, node) in graph.iter_group("worker") {
  let name = node.data_ref_by_name::<String>("name").unwrap();
  // ...
}

#[derive(TypedNode)]
struct HumanWorkerNode{
  name: String,
  #[group(product)]
  cooked: BTreeSet<NodeIndex>,
  #[group(product)]
  maked: BTreeSet<NodeIndex>,
  // ... other data
}
#[derive(TypedNode)]
struct RobotWorkerNode{
  name: String,
  #[group(product)]
  manufactured: BTreeSet<NodeIndex>,
  // ... other data
}

let node = graph.get(idx).unwrap();
for idx in node.get_links_by_group("product") {
  // Now idx binds to all NodeIndex inside the product group
}

use ttgraph::*;
use std::collections::HashSet;
#[derive(TypedNode)]
struct FactoryNode{
 name: String,
 workers: HashSet<NodeIndex>,
}
#[derive(TypedNode)]
struct HumanWorkerNode{
  name: String,
  factory: NodeIndex,
}
#[derive(TypedNode)]
struct RobotWorkerNode{
  name: String,
  factory: NodeIndex,
}
node_enum!{
  enum Node{
    Factory(FactoryNode),
    Human(HumanWorkerNode),
    Robot(RobotWorkerNode),
  }
  link_type!{
    Factory.workers : {Human, Robot},
    Human.factory: Factory,
    Robot.factory: Factory,
  }
}