帮助文档

CimNet - C++复杂网络工具包

注意！

本项目已在GitHub公开仓库，该文档不再更新，请于https://hxt-tg.github.io/cimnet-docs/查看最新的文档！（以下内容已不是最新版本，请于hxt-tg/cimnet/releases下载最新代码。）

作者：胡鑫涛

版本号：0.1.1

CimNet简介

CimNet是一个纯C++实现的复杂网络库，它基于C++11标准的语法编写。

CimNet支持以下特性：

安装CimNet

CimNet最新版发布地址：GitHub Releases

CimNet无需安装，按照下述步骤使用这个库：

  1. 在上面的发布地址下载zip文件；
  2. 解压zip文件，将其中的cimnet文件夹复制到你的工程文件夹下（或者你存放库的位置）；
  3. 将你的工程目录加入编译环境的Include查询目录中。例如，如果你使用g++作为编译器，可以用下面的命令编译一个单独的源码文件main.cc。
    g++ main.cc -o main.out -std=c++11 -O2 -I /path/to/your/project

CimNet使用说明

如果你之前编写过C语言，但是从未接触过C++语言，或者不了解C++11标准的新特性，可以跳转到章节“关于C++语言”了解快速上手CimNet的语言特性。

文件结构

CimNet工具包含于cimnet文件夹内，由以下文件组成：

文件 内容概述
cimnet/_types.h 基础数据类型
cimnet/_exception.h 网络异常类
cimnet/_base_net.h 通用无向/有向网络类
cimnet/network.h 已实现的常用网络结构
cimnet/random.h MT随机数生成

一般情况下，你只需要引用cimnet/network.h这个头文件，就可以使用默认的基础数据类型、网络异常类和有向/无向通用网络类。已实现的常用网络结构全部继承于通用无向网络，网络的节点编号类型为整型。

如果你想使用优秀的随机数生成算法，可以引用cimnet/random.h，也可以使用标准库中的随机数函数。

关于随机数

CimNet使用了Mersenne twister随机数生成算法。这个算法是由Makoto Matsumoto（松本 眞）和Takuji Nishimura（西村 拓士）于1997年提出的。这个随机数算法运行速度快，产生的随机数分布均匀，适合用于对统计信息较为敏感的场合。

cimnet/random.h中的函数如下：

函数 说明
sgenrand(unsigned long i) 将参数i设置为随机数种子
randi(unsigned long N) 返回一个0 ~ N-1的随机整数
randf() 返回一个0~1的随机小数（double型）

使用网络

1. 创建网络

你可以用下面的语句创建一个不含任何点边的空的无向网络：

Network<> net;

这个网络用Id类型作为节点编号的标识（见CimNet接口之基本数据类型）。每个节点的编号应该互不相同。创建一个空的有向网络：

DirectedNetwork<> net;

你也可以指定自己节点类型：

Network<std::string> net;

这样一来，在网络net中你可以使用标准库的字符串来唯一标识一个节点。

2. 编辑网络结构

你可以向网络中添加节点：

net.add_node(1);

网络中就增加了一个以1为编号的节点。如果你指定了节点编号类型为std::string，也可以用以下方式添加节点：

net.add_node("A");

你可以使用has_node(id)方法判断网络中是否有以id为编号的节点，以上面的网络为例，下列语句：

std::cout << net.has_node("A") << std::endl;
std::cout << net.has_node("Not existed") << std::endl;

会打印

true
false

两个节点间的连接关系称为边。向网络中添加一条边：

net.add_edge(1, 2);

如果网络net为无向网络，可以使用has_edge(id1, id2)方法判断网络中是否存在边，id1和id2的位置可以调换。你也可以使用is_neighbor(id1, id2)判断网络中id1与id2是否为邻居节点，它的作用和has_edge是一样的。

如果网络net为有向网络，可以使用has_successor(id1, id2)判断节点id1是否存在后继节点id2，使用has_predecessor(id1, id2)判断节点id1是否存在前序节点id2。有向网络也有has_edge方法，它和has_successor方法是等效的。有向网络的is_neighbor(id1, id2)方法在id1和id2之间存在连边（无论是id1指向id2或id2指向id1）时返回true。如果有向网络net中存在一条以节点1指向节点2的边，下列表达式：

net.has_successor(1, 2)
net.has_predecessor(2, 1)
net.has_edge(1, 2)
net.is_neighbor(1, 2)
net.is_neighbor(2, 1)

的值均为true。

3. 存储节点/边数据

在存储数据前需要在模板类处指定存储的数据类型。我们定义如下两种类型：

typedef std::string NodeDescribe;
typedef struct {
    int amount;
    double weight;
} EdgeDetail;

并且以这种方式声明网络，并添加一条边：

Network<Id, NodeDescribe, EdgeDetail> net;
net.add_edge(1, 2);

网络中便有了两个点和一条边。接下来你可以这样在网络的节点中添加数据：

net.node(1) = "First node";
net[2] = "Second node;

上面两个语句都能用来添加数据。第一条语句使用node(id)方法返回了节点id存储的引用，这使得你可以通过引用修改内部存储。网络类也提供了下标的方式返回节点引用（即第二条语句所示），这使得你可以更方便地存取网络节点的数据。在网络的边上添加数据也可以通过类似的方式：

net.edge(1, 2) = {3, 3.14};
net(1, 2) = {3, 3.14};

同理，第一条语句使用调用函数的形式访问边数据的引用，第二条语句是一种更简便的方式——它重载了这个类的括号操作符。当然，由于edge(id1, id2)方法返回的是EdgeDetail结构体的引用，你可以使用.直接修改内部成员：

net.edge(1, 2).amount = 4;
net(1, 2).amount = 4;

点数据和边数据都能存储其它任意的你定义过的类的对象，但是每个点之间或每条边之间存储的类型要一致。

在添加节点和边的方法里也可以直接添加数据：

net.add_node(1, "First node");
net.add_node(2, "Second node");
net.add_edge(1, 2, {3, 3.14});

4. 网络拷贝和转换

CimNet提供拷贝构造器完成网络的拷贝操作。你可以将一个网络及其内部数据完全复制给另一个网络，此后前一个网络的修改不影响拷贝后的网络数据。只需要将原始网络作为参数传入新网络的初始化参数列表中即可。

Network<Id, NodeDescribe, EdgeDetail> net;
// Add nodes and edges to net
Network<Id, NodeDescribe, EdgeDetail> net_copy(net);
DirectedNetwork<Id, NodeDescribe, EdgeDetail> di_net_copy(net);

需要注意拷贝网络的模板参数需要保持一致，它的类既可以是Network也可以是DirectedNetwork。如果原网络是无向网络且新网络是有向网络，所有无向的连边会转化成两条有向且指向相反的连边。如果将有向网络拷贝为无向网络，所有的有向连边失去方向，变为无向连边。

5. 网络数据和遍历

在无向网络中使用degree(id)方法可以获知节点id的度。

在有向网络中，in_degree(id)返回节点id的入度，out_degree(id)返回节点id的出度，degree(id)返回了入度和出度的和。

number_of_nodes()方法会返回网络的节点数量，number_of_edges()方法会返回网络边的数量。total_degree()方法会返回网络的总度数，它从数值上等于网络总边数的两倍。

你也可以直接使用std::cout输出流打印网络信息：

std::cout << net << std::endl;

它会简要打印网络的节点数、边数和总度数信息。

调用nodes()方法可以获取网络中所有的节点编号（std::vector<NodeId>），edges()方法可以获取网络中所有的边，它是一个点对的集合容器（std::unordered_set<std::pair<NodeId, NodeId>>）。neighbors(id)返回节点id的所有邻居（std::vector<NodeId>）。可以参考下面的方式遍历网络和邻居的节点编号：

for (auto &node : net.nodes())
    // Visit node
for (auto &edge : net.edges())
    // Visit edge.first and edge.second
for (auto &neighbor : net.neighbors())
    // Visit neighbor

其中由于边edge是std::pair<NodeId, NodeId>类型，C++11中需要用first和second访问一条边中的两个节点编号。对于无向网络而言，edge.first是一条边中较小的一个节点编号（数值较小或字符串字母序靠前的）；有向网络中edge.first是前序节点，edge.second是后继节点。

（如果你支持C++17以上的编译，可以尝试将循环替换为for (auto &[i, j] : net.edges())，其中i和j等效于edge.first和edge.second。）

另外，对于无向网络而言，neighbors(id)返回了节点id所有相邻节点编号；对于有向网络而言，neighbors(id)返回了所有与节点id有关联（无论方向）的节点编号。有向网络还提供了predecessors(id)方法用来返回节点id的所有前序节点编号，successors()方法用来返回节点id的所有后继节点编号，它们的遍历方式与neighbors(id)类似。

6. 已实现的网络结构

目前所有已实现的网络结构都是模板类，且节点编号都是Id类型的——所以模板只接受两个模板参数，NodeData和EdgeData，它们默认都是None。这些网络的用法和通用网络类型基本一致，只是初始化时需要传入指定的参数。这里给出一个较为完整的程序实例：构建一个包含10个节点的规则网络，这个网络的每个节点都和周围6个邻居连边（即，每个节点向顺时针方向的3个邻居添加连边）。最后我们打印网络信息和一号节点的邻居节点编号。

#include "cimnet/network.h"

int main(void) {
    RegularNetwork<> net(10, 3);
    std::cout << net << std::endl;
    std::cout << "Neighbors of node 1: ";
    for (auto &n : net.neighbors(1))
        std::cout << n << " ";
    std::cout << std::endl;
    return 0;
}

这段代码的第1行引用了网络结构的头文件。主函数的第1行用模板类定义了规则网络net，主函数的第4行遍历了网络中1号节点的邻居，变量n的值为每次遍历到的一个邻居节点的编号。

CimNet接口说明

基本数据类型

基本数据类型在cimnet/_types.h内定义，在引用cimnet/network.h后可以直接使用。建议使用以下更加表意的类型对你的变量定义。基本数据类型包含以下三种类型：

类型名 原始类型 说明
Id unsigned int 默认的节点编号类型
Weight double 建议作为网络权重数据的类型
None class _NoneType {} 不存储任何数据的空类，标识”空”的概念

网络异常类

网络异常类在cimnet/_exception.h内定义，用于库中的异常抛出。

通用网络异常

继承关系：class NetworkException : public std::exception

NetworkException::NetworkException(const std::string &info);

构造网络异常的基类，将info作为网络异常的报错信息。支持的方法：

缺失节点异常

继承关系：class NoNodeException : public NetworkException

NoNodeException<NodeId>::
    NoNodeException(const NodeId &id);

模板参数默认为Id。构造缺失节点异常类时需要传入：

参数 说明
id 缺失节点的编号

缺失边异常

继承关系：class NoEdgeException : public NetworkException

NoEdgeException<NodeId>::
    NoEdgeException(const NodeId &id1, const NodeId &id2, bool is_directed);

模板参数默认为Id。构造缺失边异常类时需要传入：

参数 说明
id1 缺失边的第一个节点编号
id2 缺失边的第二个节点编号
is_directed 是否为有向边（默认为false）

通用无向网络类Network

通用无向网络类在cimnet/_base_net.h内定义，类的声明如下：

template <class NodeId, class NodeData, class EdgeData> class Network;

其中模板参数默认分别为Id、None和None。Network包含以下三个构造器：

通用无向网络类中定义的方法如下：

通用有向网络类DirectedNetwork

通用有向网络类在cimnet/_base_net.h内定义，类的声明如下：

template <class NodeId, class NodeData, class EdgeData> class DirectedNetwork;

其中模板参数默认分别为Id、None和None。DirectedNetwork包含以下三个构造器：

通用有向网络类中定义的方法如下：

已实现的常用网络

已实现的常用网络在cimnet/network.h内定义，它们均继承于通用无向网络类。

这些常用网络均以Id作为节点编号，且均为模板类，支持传入两个模板参数，依次为节点数据和边数据，默认均为None.

FullConnectedNetwork - 全连接网络

FullConnectedNetwork<NodeData, EdgeData>::
    FullConnectedNetwork(int n_nodes);

构造网络时需要传入：

参数 说明
n_nodes 网络的总节点数

RegularNetwork - 规则网络

RegularNetwork<NodeData, EdgeData>::
    RegularNetwork(int n_nodes, int n_links);

构造网络时需要传入：

参数 说明
n_nodes 网络的总节点数
n_links 每个节点顺时针方向新增的边数

n_links不能大于n_nodes-1。该网络创建后，每个点的度均为2*n_links。

ERNetwork - ER随机图

ERNetwork<NodeData, EdgeData>::
    ERNetwork(int n_nodes, double prob_link);

构造网络时需要传入：

参数 说明
n_nodes 网络的总节点数
prob_link 每两对节点间的连边概率

GridNetwork - 格子网络

GridNetwork<NodeData, EdgeData>::
    GridNetwork(int width, int height, int n_neighbors);

构造网络时需要传入：

参数 说明
width 格子网络的宽
height 格子网络的高
n_neighbors 每个节点邻居的数量，默认为4

格子网络是循环边界的结构，即每一行的末尾与开头相连，列向同理。

目前GridNetwork只支持n_neighbors为4和8。

CubicNetwork - 立方体网络

CubicNetwork<NodeData, EdgeData>::
    CubicNetwork(int length, int width, int height);

构造网络时需要传入：

参数 说明
length 立方体的长
width 立方体的宽
height 立方体的高

立方体网络是循环边界的结构，即每一行的末尾与开头相连，列向同理。

HoneycombNetwork - 蜂窝网络

HoneycombNetwork<NodeData, EdgeData>::
    HoneycombNetwork(int honeycomb_width, int honeycomb_height);

构造网络时需要传入：

参数 说明
honeycomb_width 蜂窝的宽
honeycomb_height 蜂窝的高

蜂窝网络是循环边界的结构，即每一行的末尾与开头相连，列向同理。

蜂窝结构与节点的关系见下图，其节点数量等于2 * honeycomb_width * honeycomb_height。

HoneycombFigure

KagomeNetwork - Kagome晶格网络

KagomeNetwork<NodeData, EdgeData>::
    KagomeNetwork(int kagome_width, int kagome_height);

构造网络时需要传入：

参数 说明
kagome_width Kagome晶格的宽
kagome_height Kagome晶格的高

Kagome晶格网络是循环边界的结构，即每一行的末尾与开头相连，列向同理。

Kagome晶格结构与节点的关系见下图，其节点数量等于3 * kagome_width * kagome_height。

KagomeFigure

ScaleFreeNetwork - 无标度网络

ScaleFreeNetwork<NodeData, EdgeData>::
    ScaleFreeNetwork(int n_nodes, int n_edges_per_node);

构造网络时需要传入：

参数 说明
n_nodes 网络总节点数
n_edges_per_node 每个节点增长的连边数

关于C++语言

这一部分的内容将帮助你在仅有C语言基础的条件下，快速学习使用CimNet所必需的C++语法。此外，阅读CimNet中提供的example也能够增加你对语言特性的理解。注意，这里只介绍一些最基本的概念，如果你希望实现一些更加高级的特性，还是需要额外学习一些专业书籍。

面向对象

大多数支持面向对象编程的语言拥有四大特性——封装，抽象，继承，多态。

封装和抽象保证了程序模块和模块之间的高度独立和易用。在你使用这个对象的时候，可以不必关心对象的实现细节，使你更加关注程序其他部分的逻辑。你可以使用更加表意的方式修改对象数据，并且保证数据修改的可靠和合理。

在CimNet中，cimnet/network.h中所有网络类都继承于Network类，这意味着你可以在例如RegularNetwork的对象中访问Network的方法。其中RegularNetwork称为子类，Network称为父类或基类。

实例化与模板类

在C++中，一个类可以实例化一个对象，每一个对象都能访问这个类中的方法，但是对象与对象之间的大部分数据并不共通。所谓方法就是函数，不过这个函数只能针对特定类实例化的对象来调用。你可以使用ClassName var;来实例化对象var，使用var.method(params, ...)来调用ClassName的方法。

C++提供了一种更加高级的方式来实现一些功能相似但数据类型不一致的类，即模板类。模板类所实现类需要指定一些模板参数，这些模板参数就是指定的数据类型。模板类里会实现针对给定模板参数的属性和方法。使用模板类的语法是在类名后加尖括号，即ClassName<ClassParams, ...>，并且用这个模板类实例化所需的对象。这里有一个语法陷阱，如果你想使用一个全部取默认的模板参数的模板类，在C++11的标准下类名后的尖括号是不能省略的，即ClassName<>。

以CimNet的Network为例：

Network<int, std::string, double> net;
net.add_edge(1, 3);

上例中第一行实例化了一个Network类的空实例n，这个模板类接受了三个模板参数。第二行调用了Network中的方法add_edge来修改网络net，你不能直接修改实现网络的数据结构，只能通过提供的接口来访问内部的数据结构，这些接口会保证进行的修改是合理有效的，一定程度上保证了网络不会出现意外的错误。

对象的指针与引用

类似C中的语法，你可以创建一个对象的指针，手动创建它的内存空间，并且在使用完毕后释放。上例也可以写成如下形式：

typedef Network<int, std::string, double> MyNetwork;
MyNetwork *net = new MyNetwork;
net->add_edge(1, 3);
delete n;

使用typedef语句来简化对模板类的表达。程序的第二行实例化了一个Network对象，分配了它的内存空间，初始化它为一个空的网络，并把它的地址赋值给指针变量net。new ClassName(params, ...)后的初始化参数列表可以省略，它会在初始化的时候调用默认构造器。指针变量的方法使用->而不是.访问。最后使用delete语句释放net的内存。需要注意的是，你要保证程序逻辑里的每一个被new创建的对象都被delete释放，不然会造成大量内存泄漏。

如果你需要在函数间传递对象，又要避免参数拷贝浪费的时间，建议使用引用。引用可以让你像使用原始变量一样使用引用变量，同时不会占用额外空间和拷贝时间——你修改的就是原始变量。某种意义上，引用变量是原始变量的一个别名。

typedef Network<int, std::string, double> MyNetwork;

void print_degree_ref(const MyNetwork &net) {
    std::cout << n.total_degree() << std::endl;
}

void print_degree_ptr(const MyNetwork *net) {
    std::cout << net->total_degree() << std::endl;
}

int main(void) {
    MyNetwork net;
    net.add_edge(1, 3);
    print_degree_ref(net);
    print_degree_ptr(&net);
    return 0;
}

程序用两种方式定义了打印网络总度数的函数。参数列表前的const保证变量不会在函数内部被改变。两个函数参数中的变量net都指代main函数里的网络变量net，都不会对整个变量进行拷贝，只不过一种是用指针方式，一种是用引用方式。你可以从这个例子中感受这两种方式的差异。

标准容器类的遍历

C++11提供了大量模板容器类便于你存储各种结构的数据，我们以最常用的一种容器介绍C++11的语言特性。

std::vector是标准库提供的一种动态数组容器，以下是一个使用的例子：

std::vector<std::string> array;
array.push_back("Data 1");
array.push_back("Data 2");
array.push_back("Data 3");

std::vector<std::string>表示这个容器是用来装字符串类型的。array中依次插入了三个字符串。你可以用array[2]访问字符串"Data 3"。如果你想遍历这个容器，常用的方式是这样：

for (int i = 0; i < array.size(); ++i)
    std::cout << array[i] << std::endl;

C++11提供了一种更方便的方式遍历容器：

for (auto &s : array)
    std::cout << s << std::endl;

与C语言中的auto不同，C++的auto表达的是对此处变量类型的推导。也就是此处不需要显示指明变量s的类型，编译器可以自行推导。与上文介绍的引用变量一样，这里的s也是引用，是容器内存储元素的引用，它在遍历过程中也可以不占用额外空间地快速访问array中的元素。（事实上这种遍历方式是通过访问容器迭代器std::vector<_Type>::iterator实现的，它是C++11的一个协议式语法糖，不过这里不再讨论其实现细节，只需要知道这种遍历方式十分方便即可。）Network类中的neighbors(NodeId id)方法返回的就是一个std::vector<NodeId>，你可以用一个新的std::vector接住这个返回值，也可以用它直接遍历：

for (auto &neighbor : net.neighbors(id))
    std::cout << neighbor << std::endl;

继承

谈到继承机制，就涉及到C++的高级语法部分了，在该文档内难以赘述。此处提供一个最基础的继承代码范式，你可以替换其中的部分内容完成对CimNet网络基类的继承。

class MyNetwork: public Network<NodeId, NodeData, EdgeData>{
    public:
        MyNetwork(params...) {
            // Implementation
        }
};

你可以将上面的MyNetwork替换为你的网络类名，在NodeId，NodeData和EdgeData处分别填写网络中存储的节点编号类型，节点数据和边数据。在// Implementation处编写网络的具体实现。如果你需要编写一个带模板语法的继承，或是在子类中添加独有的属性和方法，可以学习参考cimnet/network.h中的实现或联系开发者。

项目贡献者

开发者：胡鑫涛（@hxt-tg，
hxt.taoge@gmail.com）

校对和部分文档：孙嘉隆（@jl-sun，
sunjialong9@gmail.com）

漏洞报告

请使用GitHub issues报告漏洞。

开源协议

CimNet使用第三版GNU通用公共许可证（GPLv3）作为发布自由软件许可证。

权利声明：

Copyright (C) 2020 CimNet Developers
Xintao Hu <hxt.taoge@gmail.com>