通用图搜索工具

这是一个图搜索工具，支持广度优先和深度优先搜索策略，支持并行搜索，关心路径
权重不支持小数，如果有小数，请自行放大适当倍数来转换成整数
要求jdk1.8

编写背景：

为了解决一些图搜索问题，如：求两点最短距离及路线、求两点不重复（节点）的路线、求两点间不超过指定长度的所有路线等等

分析：

上述几个问题具有一定的共性，可以提取出通用需求，以达到复用的目的，用来解决这一类问题

通用需求提取：

实现图搜索，关心路径而不仅是路线条数或最短距离
为了应对不同场景，允许指定采用广度优先还是深度优先搜索策略
为了提升性能，利用多核资源，允许使用分治，并行搜索

约束：

为了简化问题，限定权重不能为小数，如果不满足，可以整体放大多少倍来适配

实现思路：

1、任务抽象

将具体任务抽象成一个Task类，其中有一个最关键的抽象方法check：

protected abstract ReturnState check(List<N> steps, int depth, int weight, R resultHolder, Boolean isRepeated);

工具在每一步搜索时都会调用此方法，它将传入当前路径、总权重、搜索深度等，在具体的任务中，可根据这些信息来完成具体的求解逻辑

通过返回不同的ReturnState，来指明是否结束当前路径的后续搜索，或者是结束整个任务，或者继续往下搜索，或者是指示将后续搜索转成一个并行任务

如果开启了并行搜索，则需要实现getForkResultHandler方法来定义一个ForkResultHandler，它指明了如何从当前结果收集器创建新的收集器（例如求最短路径的任务就需要用到当前结果，即已找到的最短路径），以及如何合并等

2、图数据整理（初始化）

在工具使用时，首先将图中的节点（比如节点为String类型，或是其它自定义对象）转换成索引，用索引值来表示图中的节点，以便于使用，提高效率对应于GraphSearcher类中的mapper、unmapper 然后将图中的路径、权重信息重新构建成一个二维数组data[][]，data[m][n]表示从第m个节点到第n个节点的权重是多少，如果不可达，则用特定值标识，如-1

在搜索时，会遍历data[m]这个数组来寻找m节点可以到达哪些节点，为了提高 在m能到达的节点非常少的情况下 的遍历效率，构建的时候，例如data[m]为如下数组时 -1，-1，-1，-1，6，9，11，-1，-1，-1，4，8 会将data[m][0]修改为某个标记值，如-10004，用来表示下一个可到达的节点为data[m][4]，同理，会将data[m][7]修改为-10010，修改后的数组为 -10004，-1，-1，-1，6，9，11，-10010，-1，-1，4，8 这样，便可以跳过中间连续的不可达节点，以达到快速遍历的目的

同时，为了节约内存，会尝试对data[m]进行前后截取，当data[m]的前后为连续的不可达节点，并超过一定长度时，会进行截取以减少内存占用，data[m]的最后一个元素一律用来记录头部截取了多少个元素，通过简单的加减运算，便可从截取后的数组中找到原来的第n个节点

3、搜索算法

a)深度优先

这个比较简单，使用递归就可以了，实现类GraphSearcher.DepthFirstSearcher<N>

b)宽度优先

算法比较复杂（实现类GraphSearcher.BreadthFirstSearcher<N>），因为要保留路径信息，仅仅将下一批可到达节点插到队列中的做法便不能达到此目的，于是我将路径信息也放入到队列中，但为减少内存占用，我采取了很多措施来优化。

例如：下面是队列中的两段数据 10003，2，3，1，4，5，3，1，10002，5，2，8，6，7 10003为控制信息，大于10000（代码中实际取的值为node个数+1），10003-10000得到的3表示，接下来的3个元素（2，3，1）表示，当前路径的最后3个节点切换成这3个节点，便可将当前路径切换到这段控制信息中记录的路径（因为在图搜索时，首先调整的是尾部的节点，所以这种记录方式是有效的），再接下来的4，5，3，1（直到遇到下一个控制元素为止）为这条路径接下需要搜索的节点。同理10002表明了接下来切换路径时，只需将当前路径中的最后两个节点切换成5和2，接下来的8，6，7为此路径的下一次搜索节点。

如果在搜索10003，2，3，1，4，5，3，1时，都被舍弃了，不需要进一步搜索时，此条控制信息便无意义了，此时，这条路径的控制部分（10003，2，3，1）会与后面的控制部分（10002，5，2）合并，变成10003，2，5，2。 上面说的是尾部合并，还有头部合并机制，队列最开始会插入一个周期标记，用来感知何时完成了一轮遍历，如果一个周期结束，路径的头部没发生过切换，那么没发生切换的这一段头部便可以移除掉，以此来节约空间，当搜索深度非常深且存活的路径只有尾部不一样时，便可省下大量控制元素。

为了减少内存占用，列队我没有使用自带的ArrayDeque，而是参照它自己实现了一个双向队列。

因为ArrayDeque内部使用的是一个对象数组，对象引用占用4个字节（64位可以指针压缩），而我往队列中插入的主要是节点的索引以及一些控制信息，都是非常小的整数，可能一个byte便够用了，这样便能成倍地减少内存占用，所以我编写了一个MagicArrayQueue，它有3种实现，区别在于内部使用的数组是byte[]、short[]还是int[]，创建时参考传入的可能的最大元素值，来选择合适的实现，它们可以向上兼容，比如byte[]的实现，即ByteImpl也可以插入一个int，比如0x1FFFFFFF，此时便会使用4个byte来表示这个元素，第一个byte会包含一个控制信息，表明这个元素由4个byte构成。同时，还添加了针对这个搜索工具的修改方法，例如moveTail，在搜索时，可以在某个时候记录当前队列尾指针，接下来发现新插入的元素其实不需要，便不需要一个一个再移除元素，直接用moveTail来退回到原来位置即可，更高效。

4、其它

工具中还加入了节点重复检测，如果启用，则搜索出现重复节点时，结束该路径的后续搜索。