毕设简单地说就是基于大量已经正确的代码，对提交的错误代码进行大概的错误位置提示。
最早是期望着基于诸如SIM的程序试求两个程序的diff，然而这一类程序仅基于文法，并不可行。
如果基于AST，而整个树的形态受代码的书写风格也会出现很大的变化，讨论下来并不可行。
讨论后决定从程序的CFG出发，进行后续的处理。
当能够获得一个程序的CFG之后，首先很容易就会得出一个非常朴素的想法，只要知道如何在CFG层面上从左边图变到右边的图，那么很显然我们就能知道两个程序之间的对应关系，那么，两者之间的区别想必也能够拿到了。
但是很尴尬的一点，从一个图变到另一个图，其间的操作为图编辑距离（GED），最优解的算法复杂度是指数级的，这就很让人黯然心伤了。对于任意一个稍微大一点点的图，其求解时间就是不可接受的。
而在代码查重层面上并不需要两个图之间的对应情况，以这篇文章为例，他将程序CFG每个点的内容都舍弃掉，将两个邻接矩阵填充到一样的大小，一维化后再进行传统的编辑距离的计算，称能比较两个程序CFG形态上的相似程度（which我尚未理解其得出距离后如何定义其程度），并将其作为整个程序的相似性。但是无论如何，这样处理出来的数据，也没法做进一步的处理了。
可能会想，那么不需要最优解呢，差不多用用就成了。说是这么说，哪来的不是最优的GED的实现来给你用呢，毕竟直接称GED的话，只是一个定义而已。另外，本来这个图上的编辑距离的应用和研究少，相关的内容也比较难以找到。
从老师给了这个题目开始，一直是想东想西，毫无进展，我认为可能一个很根本的原因就是，现在一切都是在理论上想象的，这样使得实现的方向上只有一个非常宽松的限制，任意一个方向，都不能说它不行，也没法确信它是能够行的通的，也使得了我写了好多代码却都只能删除了事。
ぐるぐる回して，又打算准备着眼于基于图的同构的思路。考虑这样一个情况，当两个人思路相近的时候，那么其程序的整个流程总应是一样的，应该放弃什么某人多写了一堆导致两个图之间需要一定的插入删除才能对应上的高难度放卫星的思想。那么两个CFG的结构应该是相同的，仅会在序号的标号上存在出入。
以这个前提为基础，那么整个流程就变成了这样：
- 获取程序的
CFG。 - 建立对应的图。
- 在两个程序的
CFG上进行同构的匹配，获得两者之间的对应关系。 - 对于所有分支节点，再进行一个相互比较，从而修正分支的对应关系。
- 再对于所有的对应节点，进行类似
SIM的词法上的分析，进行求diff的操作。 - 设计一个评级，将差异较大的节点位置输出。
而图的同构这一问题，虽然依旧是NP问题，研究的人就多了些了，也有了更多的一点底气。稍作搜索，可以找到一个称为VF2的图的同构的算法，似乎挺符合的。先找了一个基于原论文的java实现进行简单研读并上手试了一下。又是令人绝望的一天，其运行结果甚至传入两个相同的图都给我返回了false，不知是哪里出现了偏差。此时，又突然发现boost里竟然有实现这个算法，令人惊奇，应选黄道吉日阅读文档进行测试。
因为，我的程序，已经从C#->Python->C#->java走了三个语言了，很快就要写不动了。
Windows下使用C++的库的体验总是如此糟糕，先按下不表。
俗话说得好，不出活，写再多也没用，于是准备先在现成的东西上试一下，最初用python就是要用这个networkx的库，但是因为最初的想法是图编辑距离，which它并没有，就作罢了，可是，图同构有啊。
然后试着写了几个样例，发现自己还是naïve了，想象以下这个场景，某一正确的代码在代码中间某一部位进行了几步无用的操作，但是相较于待对比的代码而言，正确的代码的CFG就会中间多出一个节点，which使得图之间的匹配必然走向fail。一定程度上，或许图同构也靠不上了？哪有只在图外周插边插点的，只有一模一样的才能匹配上，这与一定程度上抗插入无用代码的初衷完全背离了。
int main() { //1|1
int T;
scanf("%d", &T); //2|2
while(T--) { //6|7
if (T % 2 == 0) //3|3
printf("0"); //4|4
} else {
printf("1"); //5|5
}
/*
//插入的即这一段
int a = 0;
int b;
b = a; // |6
*/
}
return 0; //7|8
}
| file1.c | file2.c |
|---|---|
| ;; 2 succs { 6 } | ;; 2 succs { 7 } |
| ;; 3 succs { 4 5 } | ;; 3 succs { 4 5 } |
| ;; 4 succs { 6 } | ;; 4 succs { 6 } |
| ;; 5 succs { 6 } | ;; 5 succs { 6 } |
| ;; 6 succs { 3 7 } | ;; 6 succs { 7 } |
| ;; 7 succs { 1 } | ;; 7 succs { 3 8 } |
| ;; 8 succs { 1 } |
或许就是要用理论上的图编辑距离which我完全看不懂也不会写的东西，或者某些我尚未想到的方法。这就非常让人头疼了。
经过蛋老师一番指点，一举扭转了我妄想着用什么高端算法一举解决的念头，开始使用最为’优秀’的BF算法来搞这个东西。
不就是多了几个点嘛，我加上不就能匹配上了。差几个点就上几个for套一套，有闲心的话再把所有修改方法都列出来，要是真的像，肯定得能匹配上。
根据git的提交记录，以6天摸鱼2天的总时长将第一个在受控样例下对微小节点差异具有鲁棒性的，加点加边方法没有排列组合完的，存在一定程度上的面向样例编程的版本完成。
明天从OJ上翻点代码当样例再继续改进吧。
说到底，就算是面向样例编程，只要样例够多，在一定范围内，终究是能够得到足够理想的结果的。从来也没有什么智能的错误提示，优秀如clang，也是靠人力堆出精准的错误提示的。
于是稍作操作，这个可运行版本就于2月完工了，再经过痛苦的测试环节，也得出了还算不错的结果，匹配率挺高的，后续待大体完成后继续更新。
