2017-06-04

基于C++11/STL的邻接表图实现

我也不记得这是我第几次口口声声说着“我再也不用C++了”然后又用了C++。用了会浪费大量时间，使程序陷入无限复杂度；不用会浪费大量代码量，使程序陷入无限繁琐。一个小循环过后就会进入大循环的下一个步骤：开始转向Python等快速迭代的脚本语言，直到忍受不了其灵活而转回所谓“一步一个脚印”的主导思想当中来。唉，如果上天再给我一次机会，我坚决不学C以外的其他语言。最多加上Python。好吧还是得有Java或者C#。算了当我什么都没说。

这次实现的图是在昨天写完C版本的图之后，实在没忍住的成果。不知道为什么，在自己写的数据结构之上工作总有一种上不了台面的感觉，没有用STL来的舒坦。强烈克制住删代码的冲动以后，写了一套完全平行的图（项目代码膨胀的一个活生生的例子），并且放弃了“底层用STL上层暴露为C接口”的想法，毕竟用了C++而不用C++11，或者用了C++11而不用匿名函数，那么和咸鱼也没有什么区别了。

这回依然是一个邻接表的图，由于C++可以用模板，所以就不用再以索引的方式间接地访问顶点和边的数据了，这个图也就真的一个数据结构，而非仅仅是一堆锁链的集合了。首先定义一个辅助结构用来把边和有关信息绑定在一起：

template <typename Vertex, typename Edge> struct EdgeBox {
public:
    Vertex source, destination;
    Edge edge;
    EdgeBox(const Vertex &s, const Vertex &d, const Edge &e) {
        source = s;
        destination = d;
        edge = e;
    }
};

在边当中包含终点信息的好处自不必说，包含起点的好处是……和终点对称。对就是这样。

”所以说Edge就只是一个权重信息的过度抽象了？“确实有这种嫌疑，不过我的实际用例还真的用得到更多的信息：在一幅贝塞尔曲线作为边、曲线的交点作为顶点的图当中，一条边不但有起点终点，还有其对应的曲线的解析式。

写C版本的图时有一个夙愿，就是删除一个顶点的时候把已此顶点作为终点的边也一并删除，然而由于下层数据结构（就是那个没什么用的posarr）的限制而难以实现。这次为了达成愿望，加入一个平行的字典专为此功能：

1 2	map<Vertex, vector<EdgeType>> _graph; map<Vertex, vector<EdgeType>> _vend;

在_graph当中储存一般的邻接表结构，而_vend[vert]则储存以vert作为终点的边都有哪些。这时候边当中的起点字段就有用处了。

几个加减顶点和边的接口无需多言，遍历顶点的边的接口有了C++11的匿名函数和for (auto some : thing)语法糖以后也变得流畅很多，唯一一个瑕疵是删除边时的遍历：

void deleteEdge(const Vertex &start, const Edge &edge) {
    for (auto box = _graph[start].cbegin(); box != _graph[start].cend(); box++) {
        if (box->edge == edge) {
            _graph[start].erase(box);
            break;
        }
    }
}

这里的for循环没有办法用新语法，因为循环体内部的erase要访问迭代器本身。我想大概有更友善的方法吧。

由于深度优先搜索不需要队列的加持（虽然有了STL也不是很麻烦了），所以先实现的出来。注意：请务必读到下一条水平线再复制粘贴！

using PreviousMap = map<Vertex, const Vertex *>;
using SearchVisitor = function<int (const Vertex &v, const Edge *through,
                                    const PreviousMap prev)>;
private:
int _dfs(const Vertex &current, const SearchVisitor &visitor, const Edge *through,
         PreviousMap &prev) const {
    int status = visitor(current, through, prev);
    if (status != 0)
        return status;
    for (auto edge : _graph.at(current)) {
        if (prev[edge.destination] != nullptr) {
            prev[edge.destination] = &current;
            int s = _dfs(*prev[edge.destination], visitor, &edge.edge, prev);
            if (s != 0)
                return s;
        }
    }
    return 0;
}
public:
int dfsVisit(const Vertex &start, const SearchVisitor &&visitor) const {
    PreviousMap prev;
    for (auto pair : _graph)
        prev[pair.first] = nullptr;
    return _dfs(start, visitor, nullptr, prev);
}

这里SerachVisitor借口的设计非常反人类，需要在匿名函数声明处写一大长串的参数类型，不过除了特别简单的遍历方法应该也不会已匿名函数的方法写出，所以尚可接受。其中through为遍历中是走哪一条边到达当前顶点的，如果是对出发点调用则该参数为nullptr。正因此才把这个参数改为指针，从而破坏了全引用借口的统一性。这么说来其实指针在C++当中起到了其他语言Nullable或者? !类型的功能，这么用真的没有问题吧……

prev储存每一个顶点在遍历顺序中的前一个顶点，回调函数还可以通过返回非0值得方式提前结束遍历，这对于寻找某种最优路的场景应该是比较友善的。考虑到C++11中的匿名函数可以捕获上层作用域中的变量，所以就没有必要传一个额外的payload了。

为什么对外接口中接受的函数类型是个右值引用，而到了对内的接口就变成了左值引用呢？别问我，我只知道不这样写都会报错……

我能怎么办，我也很绝望啊