我可以使用什么数据结构来建模一个节点和边缘的网络？

Question

我的应用程序需要在有40-50个节点的网络上建模和执行操作，通常每个节点的边缘小于6个。节点和边缘都是对象，每个对象都有大约1K的数据。在执行过程中，网络的映射经常会发生变化--添加和删除节点，添加和删除边缘，以及调整单个节点和边缘的属性。节点对象和边缘对象使用“new”分配，每个对象类型的结果指针存储在std::list中。

我试验了两种不同的映射方法：

1. 在每个节点中放置一个容器以保存边缘in，并在每个边缘放置2个变量来存储终端节点的in。
2. 添加一个新的顶层容器，独立于边缘容器和节点容器，以存储映射信息。

如果映射信息存储在这些类中，节点和成员类中的函数将更容易实现。如果所有映射数据都单独存储，对网络映射的更改就容易得多。但是，如果映射没有存储在节点和边缘中，那么节点和边中的成员函数就需要从父对象获取映射信息的方法。

是否有一种数据结构或概念技术能使这两种方法发挥最佳效果，而不重复数据或破坏封装？性能不是主要的问题，因为没有任何极其昂贵的计算涉及。更重要的关注是安全、可理解、可维护的代码。

Answer 1

图表可以通过多种方式实现，并且您所描述的方法肯定是正确的。

对于C++，我认为您应该对同样具有专门用于实现图的库的Boost C++库 (BGL)进行管理。如果使用该方法，还可以使用在BGL (搜索和遍历)中实现的算法，甚至可以直接使用_edge和_vertex访问者。

Answer 2

我已经用Python实现了网络操作。这是我的解决办法。

• 一个Node类，拥有一个Ports的列表
• 每个Port对象都有属性destination、proper_direction和back_port。
• Node提供链接功能，并确保对于列表中的每个Port对象都有另一个后端端口，在目标节点上创建带有负proper_direction的Port对象，并且back_port引用该后端端口。

通过这种方式，节点通过反向proper_directions在两个方向上由一对端口连接。在Python中，我们不关心指针;-)

为了在每个节点中存储数据，我派生了一个子类，它添加了一个映射。如果我也希望在每个链接中存储数据，那么我将通过Node对象来模拟链接，并且基本上通过端口来链接对象和链接(两个节点)。

这种数据结构为网络搜索和操作提供了方便。