注意昨天有遗留任务：检索来的四篇论文检查是否是做Batch disjoint path的
今日目标：选定论文并看完（明天准备ppt）；baseline和Msbfs优化完成，做出效果；（有时间：思考统一p2搜索）
上午
- 1，2
- 读论文选论文
- 3
- hw meeting
下午
- 1
- 就不按常规来思考呢？
- 2
- 决定论文就讲suurrble了
- 继续思考，有进展！
- 3
- read surrble impl
- 继续思考！
- 4
- 继续思考！
- 5
- 继续思考！
晚上
- 1
- 继续思考
- 2
- 继续思考
idea
surrble中很重要的一点为啥处理subtree之间的non-tree-edge不会增加复杂度是因为，subtree只会划分得越来越小，划分是在上一轮划分的结果下继续划分下去，且一条non-tree-edge只会最多被处理一次，
这两点都是基于T上每个顶点最多被扩展一次
输入：点对集合，每个点对一条p1，图H
输出：每对点对一条p2
原始方法：每对点对都反向p1，把这个更新增量标记，从s和t双向bfs找p2
所有点对p1的并集图p1g，有几个弱连通分量(通过依次从所有s出发在p1g上按无向图搜索)，每个分量p1g_comp中的点对分成一组，这个组中的点对只需要考虑p1g_comp(其他的p1都不是这个组中点对的，这个组中的点对搜p2时，都不需要反向其他p1)
直接的实现：
p1g_comp记录：每条边u->v都记录了两条(除非()bitset==0)：u->v(bitset), v->u(bitset)，这两条边都称作p1-edge
msbfs扩展当前点：v,iset：
考虑&seen[nbr]之前的，需要考虑哪些nbr：
v出发的不在p1g_comp中的边(non-p1-edge)
v出发的在p1g_comp中的边(p1-edge)，&iset
希望：不区分点对，面向统一的图H’，搜索模式修改
msbfs扩展当前点：v,iset：考虑&seen[nbr]之前的，需要考虑哪些nbr：
直接的实现：
v出发的non-p1-edge
v出发的p1-edge，&iset不为0
idea的核心：走p1-edge的时候一下沿p1-edge走很远：只要进入p1g_comp就直接传送出去
suurble中是通过subtree之间的跨边直接得到的这个，而没有显式地进行搜索看能被传送到哪里
idea的好处（为什么这么做）：
- 增大搜p2时的共享程度：搜p2的共享程度没搜p1时大，一个原因是反向p1导致某个instance从iset中拆出来单独走自己的
- 复用p1，直接完成抵消
- 直接实现中，每次batch到p1g_comp上的顶点时，都要沿着其中部分做”nbr-msk”的访问，这些是不是可以一起先处理了弄成一个索引
- 可以不用split vertex了！split vertex本来就只是用来确保vertex disjoint的，这样单独处理了p1p2交叠部分的话，搜p2时也不需要split vertex了
- 只需要对p1g做split vertex来得到索引，其他地方都不需要split vertex了
一个索引start_reach_index: 很直观的
内容：
输入和输出都是：没有split vertex的顶点
闭包允许搜p2在非p1部分不用split vertex
- 一个CSR：从p1g_comp上每个顶点u，以全batch(这个p1g_comp中所有p1对应的点对)出发，在p1g_comp上可以到达哪些{v,iset}
注意，这个信息，在在p1g_comp中某些顶点被visited之后会发生变化，对于某instance从某顶点出发，现在可能有些原先可以到达的顶点现在到达不了，但是移除掉某些顶点（某些顶点被visited之后），从某顶点u出发可以到达的{v,iset}是没移除前的子集，且不能到达的那些{v,iset}是被移除掉的顶点可以到达的那些，因此之前在visit那些顶点时就会把这些顶点的seen设置，从而此时从u出发用原始信息+msk seen的话是正确的
- 空间：|p1g_comp所有顶点|^2*batchset
- |p1g_comp所有顶点|在实验中大概是64对点对*路径长度10=640
- 上述中，u到{v,iset}的前驱
- 空间：p1g_comp的拓扑CSR*batchset
使用：
搜索：扩展{u,iset}，若u在p1g_comp中则根据索引传送，为传送到达的nbr不仅记录prec，还记录u
构造路径：p1p2抵消的地方只可能发生在传送段
构造方法：p1g_comp上全顶点all batch的msbfs，注意all batch就变成了计算的数据，而遍历过程用msbfs也有其一套bitset(每个bit表示一个出发点)
- 空间：p1g_comp的拓扑CSR*batchset
从p1g_comp上出发？
是否有树的祖先关系可以用于加速之类的？
存档
msbfs扩展当前点：v,iset：考虑&seen[nbr]之前的，需要考虑哪些nbr：
idea：
v出发的non-p1-edge(对于iset中任意instance都有这部分需要扩展)
移除v之后把p1g_comp分成的多个弱连通分量之间的non-p1-edge
要求non-p1-edge的起点：iset沿p1g_comp可以走到
不是跨边、只有一个端点在p1g_comp上的non-p1-edge是否要考虑呢？所有两端点不在同一个弱连通分量中的non-p1-edge(包括两个端点都在p1g_comp上的跨边，和只有一个端点在p1g_comp上的)
一个索引p1g_comp_terminal_index(一个p1g_comp对应一个)：对于每个有non-p1-edge的顶点，如果batch到达这个顶点，batch会被传送到哪些(顶点,iset)
- suurble中是通过subtree之间的跨边直接得到的这个，而没有显式地进行搜索看能被传送到哪里
如何构造p1g_comp_terminal_index：从p1g_comp中每个顶点以全1bitset出发在p1g_comp上做bfs，得到从其中每个顶点出发，可以到达的所有首个不在p1g_comp中的(顶点terminal,iset)
iset表示只有这些iset可以到达terminal
这样的索引还是要用batch和所有entry做&操作耶
一个索引p1_nbrs_index：每条p1存一个CSR：此CSR可以得到从p1上某一点v开始直到s的其上游所有顶点有哪些不属于p1的邻居
在重构路径的时候，如果走到这个CSR中的点，则v会被用到用来重构路径，且重构路径时就完成抵消
p1: s->v0->v1->v2->t
msbfs扩展当前点：v,iset：
- 若v在p1g_comp上，且(设v在p1_has_v_iset这些instance的p1上)若p1_has_v_iset&iset不为空，则p1_has_v_iset&iset中的每个instance都根据索引p1_nbrs_index进行传送(instance传送到v的所有p1上游，~instance传送给v的在p1上的下游邻居)，iset的其他部分正常扩展non-p1-edge
- 否则正常扩展
limit: 这个索引可能效果十分有限，因为这个只是压缩了沿反向p1的边进行的搜索，但是在实际数据集上可以观察到，p1反向边被用上的数目很少，几百的数量级，所以这个效果很有限
