哈工大软件构造Lab2导读 - Stanford 6.031 Problem Set 2: Poetic Walks

前言

由于实验的介绍为MIT的全英文页面，要点分散，可能造成理解上的困难。所以在这里梳理总结一下软构lab2的整个流程，可以结合MIT的问题描述来看。希望能帮到后来的学弟学妹，不要拿到程序包直接两眼一抹黑，不知从何下手。

写下这篇文章是在完成实验后进行回忆，如有疏漏请多指正。

先简单总结Lab 2完成的工作：从github将代码clone到本地，根据已有spec完成测试用例的编写（P1，Problem 1），再分别编写两个ADT： ConcreteVerticesGraph和ConcreteEdgesGraph的具体实现（P1，Problem 2 / 3）。之后，我们利用两个ADT分别实现具体的类GraphPoet，并完成一系列的工作（P1，Problem 4）。并重构我们在Lab 1中实现过的人际关系图（P2）

本实验的完成基于IDEA，可以方便地可视化代码覆盖度，所以没有涉及安装EclEmma。

一、P1-Problem 1：编写测试用例

按照TDD（Test-Driven Development，测试驱动开发）的策略，在编写具体实现之前，我们需要根据已有的spec设计出对应方法的测试。

1.GraphStaticTest

这一部分是对Graph.empty()的测试，可以先不用管，在完成 Problem 3.2 实现Graph.empty()之前，这一块的代码是跑不起来的XD

对GraphStaticTest的补充也需要在Problem 3.2中进行。

2.GraphInstanceTest

这一部分是对Graph中的具体方法进行测试，需要好好构思构思，如果刚开始草草写了/没有考虑周全，那么在后面代码覆盖度过低，会反复回头来修改这部分，耽误很多时间！

具体而言，这一部分要按等价类划分的方法，编写测试用例。严格写下来的话，代码行数不少。举个栗子：

Testing strategy
testRemove( )
测试remove( )方法，等价类划分如下：
删除点是否在图中：是，否
删除点是否有相连边：是，否

排除不可能的情况，共3个等价类，所以需要写三组测试。

另外，提醒考虑ADT对有环图的支持并测试，后续部分会用到。

二、实现两个ADT

1.AF，RI，Safety from Rep exposure .etc

具体实现两个ADT，首先要求我们撰写相信很多同学这是第一次实际写一个程序的AF、RI，这些概念的具体意义可以参见 关于AF, RI, Rep exposure
其实举个例子，照葫芦画瓢也还算容易。例如，对于ConcreteEdgesGraph，它的这些概念可以解释如下：

Abstraction function:
AF(vertices) = Graph中的点
AF(edges) = Graph中的边
　
Representation invariant:
点的名字不能重复
所有点都在vertices中
edge的权值为正
两点间的单向边最多只能有一条
　
Safety from rep exposure:
成员变量vertices与edges均用private final修饰，防止其被外部修改
在涉及返回内部变量时，采用防御性拷贝的方式，创造一份新的变量return

2.checkRep ( )

checkRep ( )部分就是针对RI设计出检查代码。比如，在RI中有一条“edge的权值为正”，则在checkRep ( )中需要用assert语句检查edge的成员是否大于0，在每次运行方法（如add，set）且修改了成员变量后，需要在return前调用checkRep ( )进行检查。

3.方法的具体实现

在实现ConcreteVerticesGraph和ConcreteEdgesGraph时，MIT的页面要求先用String型，再用泛型L，其实可以直接用泛型L来写，节省后续改的工作量。若用泛型L来写，则需要将两个ADT的部分内容修改为如下：

public class ConcreteEdgesGraph<L> implements Graph<L> { ... }class Edge<L> { ... }

和

public class ConcreteVerticesGraph<L> implements Graph<L> { ... }class Vertex<L> { ... }

相关方法的具体实现在这里暂且不表，在完成方法的实现后，可以通过前面写的测试用例来检验方法编写是否正确，并看看代码覆盖度，有哪些代码没有覆盖到。（实验要求代码覆盖度尽可能达到100%）

在这里简单讲一下IDEA的代码覆盖度测试：


运行之后：

另外注意，两个ADT中需要分别实现成员Edge与成员Vertex，在ConcreteEdgesGraphTest与ConcreteVerticesGraphTest中，需要完成对Edge与Vertex各自成员方法的测试。

4.实现Graph.empty ( )

这一部分要求我们对Graph.java中的empty ( )方法进行实现，具体来说，就是让empty ( )方法返回两个具体ADT中的一个，如图：

完成后，在GraphStaticTest中补充测试代码，具体来说，就是模仿已有代码，验证在Interger，Double等类型下是否正确，如图：

三、Poetic Walks

到此，我们已经完成了MIT页面上的Problem 1~3，开始解决Problem 4。

1.题目意思梳理（结合MIT页面和spec看）

在这一步中，需要依据语料生成一个单词图，单词图的每个顶点是语料中的一个单词，单词图的边代表前一个单词紧接着后一个单词，边的权重为前一个单词紧接着后一个单词的次数，并且不考虑大小写与标点符号。举个例子：

hello,hello,HeLlo,world!

其中，hello→hello出现两次，hello→world出现一次，则这个语料构成的图为：

更加具体的示例可以参照MIT实验官网的页面。

在根据语料构造好图后，下面需要完成的任务是：输入一个句子，提取出句子两两相邻的单词对，在图中进行一次检索，若句子的前后两单词w1→w2在单词图中隔着一个顶点b，则将b加入句子中，得到w1→b→w2。具体的构建规则如下：

① w1与w2间只能间隔一个顶点，这也就是说，如果在图中出现了w1→a→b→w2，甚至间隔更多的情况，则不会在w1→w2间加入单词。

② 如果从w1到w2同时有两条路径w1→a→w2与w1→b→w2，则选择权重最高路径上的单词加入w1与w2之间。

③ 输出的句子中原单词的大小写保持不变，加入的单词全用小写。

④ 可以存在指向自己的边，即该图可以是带环图。

2.编写测试用例

在理清思路后，我们可以着手开始编写测试用例，具体的测试策略为编写Poem与toString方法的测试用例，对于Poem，采用不同的语料，测试能否得到正确的输出；对于toString，则用不同用例测试toString方法的正确性。

举个例子如图：
在mugar-omni-theater.txt中保存着语料

This is a test of the Mugar Omni Theater sound system.

此条测试的意义是输入句子input，经过图处理后，检验输出是否与我们的预期AccOutput相同。

3.具体实现Poet

在GraphPoet中，我们需要依次实现三个方法：

1) 构造方法GraphPoet

在GraphPoet的构造方法中，我们需要读取文本文档，并由其中语料按照前文所阐述的方法生成一个单词图。具体实现方式为：输入文件路径并按行读入，将单词进行切分，进行删除标点符号，大写转小写等预处理，每次取相邻元素在图中添加新边。

2) 生成句子方法Poem

Poem方法输入一个String参数作为原始句子，输出根据单词图匹配过的，扩充了bridge words的新句子。具体实现思路为一次读入两个单词，检索前一个单词子节点的子节点，若其中包含后一个单词，则选择途径通路权重最高的一路，将该路上途径节点表示的单词加入原来两单词之间。

3) toString方法

简单重写toString方法，将整个图中所有点的指向转化为一条字符串输出。

4.测试代码覆盖度

代码覆盖度建议尽量达到100%

四、重构Lab 1中的Social Network

这一环节要求我们基于在前面步骤中定义的Graph及其两种实现，将泛型L替换为Person，按照Lab1中Social NetWorek的要求，实现Lab1 Problem 3中FriendshipGraph的各种功能，并且尽可能复用我们在前文构造的类中已经实现的方法。最后，运行提供的main ( ) 和执行Lab1中的Junit测试用例，确保其正常运行。

有Lab 1的基础，这部分的重构算是比较快的。利用ConcreteEdgesGraphTest与ConcreteVerticesGraphTest其一便可完成。测试代码与main函数之间copy，略加修改就可。

总结

总得来说，Lab 2相较于前几届的版本，难度降低了很多，但仍有不易理解的地方，需要花一些时间才能完成。