软件构造实验2相关思路

软件构造实验2相关思路

1 实验目标概述
针对给定的应用问题，从问题描述中识别所需的 ADT；
设计 ADT 规约并评估规约的质量；
根据 ADT 的规约设计测试用例；
ADT 的泛型化；
根据规约设计 ADT 的多种不同的实现；针对每种实现，设计其表示
（representation）、表示不变性（rep invariant）、抽象过程（abstraction
function）
使用 OOP 实现 ADT，并判定表示不变性是否违反、各实现是否存在表
示泄露；
测试 ADT 的实现并评估测试的覆盖度；
使用 ADT 及其实现，为应用问题开发程序；
在测试代码中，能够写出 testing strategy 并据此设计测试用例。

2 实验环境配置
本次实验需要安装EclEmma，在安装eclipse的过程中已经安装，因此没有遇到什么困难。

3 实验过程
3.1 Poetic Walks
本任务需要我使用边以及点分别实现一个有向图，再利用该有向图完成句子填空。
(1)完善Graph接口类，并运用泛型的思想，将String拓展为泛型L类；
(2)实现Graph类的方法：add、set、remove、vertices、sources、targets；
(3)利用实现的Graph类，应用图的思想，实现GraphPoet类，如果输入的文本的两个单词之间存在桥接词，则插入该桥接词；若存在多个单一桥接词，则选取边权重较大者。
3.1.1 Get the code and prepare Git repository
从https://github.com/rainywang/Spring2021_HITCS_SC_Lab2/tree/master/P1获取实验代码，git clone 到本地，然后github建立本次实验的仓库，用git命令将远程仓库克隆到本地，然后将远程仓库与本地仓库关联。
3.1.2 Problem 1: Test Graph
为Graph写测试代码
测试策略：
（1）Graph.add:加入一个图中没有的点，返回true,加入图中存在的点返回false.
（2）Graph.set:对于图中已经存在的两个顶点，但顶点间没有边，加入边（边的权值非零），测试返回值是否正确；
对于图中已经存在的边，修改权值，测试返回值是否正确；
对于图加入一个含有原图不存在的顶点的边，测试再次加入该点返回值是否为false（即测试刚刚加边是否成功）；
对于已存在的边，将其删除，将其权值改为0，测试返回值是否正确（返回0）。
（3）Graph.remove:删除图中存在的点，看返回值是否正确,然后再测试被删除的点所在的边是否存在。
（4） Graph.vertices:在图中加入几个点，判断点的个数是否与加入的点相同
（5） Graph.sources:测试图中存在的边的终点，看返回集合是否包含起点，测试返回的起点集合中元素个数；测试图中的非终点，观测返回值。
（6） Graph.targets:测试图中存在的边的起点，看返回集合是否包含终点，测试返回的终点集合中元素个数；测试图中的非起点，观测返回值。
其中，在Graph.sources和Graph.targets用到如下所示的图：

3.1.3 Problem 2: Implement Graph
3.1.3.1 Implement ConcreteEdgesGraph
（1）Edge类（immutable）
三个属性:

表示泄露的检测：检测source target不能为空，weight大于等于0.
五个方法：getWeight(), getSource(), getTarget(), toString(), 还有一个判断是否为相同边的sameEdge().
其中，前三个易实现，toString()通过”Edge:source->target:weight”的模式将抽象的图转化为具象。

sameEdge()函数通过判断起点终点是否对应相同来判断是否为同一条边。

（2）ConcreteEdgesGraph类
a.检测表示泄露
两点之间只能有一条边，因此不能有重复的边

b.AF RI

c.方法
一共有七个方法，如图所示：

其中前六个方法都是重写实现。
add() vertices集合中不包含欲加入的点，则加入；若包含，则不加入。
Set() 先检测图是否包含欲加入边的顶点，如果不包含，则用add()加入；然后判断权值，如果权值为0，即两点间不存在边；只有当权值大于0时，才会进行加边或对于边权值的修改。其中修改部分我利用先删除原来边，再整体加入新边来实现。部分代码如图：

remove() 利用迭代器，如果边的起点或终点是想要删除的点，那么再edges中删除该边。

vertices() 直接利用Collections.unmodifiableSet(vertices)
sources() 利用迭代器遍历，如果终点是输入参数，就将它加入返回的HashMap.

targets() 类似source（）
toString() 直接返回ConcreteEdgesGraph的两个属性

（3）ConcreteEdgesGraph类的测试
该类的测试继承了Graph类，因此只需要再添加对于Edge类的测试，以及对toString方法的测试。
其中，测试toString方法采用将设计好的特定的字符串与toStrin*生的字符串相比较，观察返回值。

最终测试结果如图所示：

3.1.3.2 Implement ConcreteVerticesGraph
(1)Vertex类（mutable）
a.属性：顶点名；Map存储可达顶点的边的起点以及权值；Map存储可产生的顶点的终点以及权值。

b.AF RI :

c.检查表示独立性：checkRep 所有边的权值大于0，且起点终点不能相同。在这里利用乘法判断所有的边权值是否都大于0。利用this判断是否起点终点相同。

d.构造器：

e.方法
我一共定义了8个方法，分别为：
getverName()：返回点名
getverSource()：返回可达该点的边的起点以及边的权值，类型为Map。
getverTarget()：返回该点可产生的边的终点以及边的权值，类型为Map。
addverSource(L source, Integer value)：添加可达该点的边的起点以及边的权值，返回类型为Map。
addverTarget(L target, Integer value)：添加该点可产生的边的终点以及边的权值，返回类型为Map。
del_verTarget(L target, Integer value)：删除可达该点的边的起点以及边的权值，返回类型为Map。
del_verSource(L source, Integer value)：删除该点可产生的边的终点以及边的权值，返回类型为Map。
toString()：返回人能读懂的字符串。格式为：Vertex[该点]：As source{->target:value,} As target{<-source:value,}

（2）ConcreteVerticesGraph类
a.属性：

b.AF RI：

c.检查表示独立性：类似于ConcreteEdgesGraph。图中的边不应重复。

d.方法：
@Override add() 如果图中不存在该点，加入；若已经存在，返回false.
@Override set() 添加边。先检测原图是否存在顶点，若不存在，添加顶点。然后检测边的权值，如果边权值等于0，直接返回0；当边的权值大于0时，我分了四种情况遍历所有的点。大体看该边是否原来有权值，如果有权值，先删除原边，重新添加；若原来该边没有权值，即不存在，可直接添加。然后检测表示独立。部分实现如下：

@Override remove() 其中删除其他点与该点关系的时候，参考set()，在删除该点本身时，利用了迭代器加it的模式，成功删除。

@Override vertices() 遍历所有点，将图中存在的点的名字加入一个集合中，最后返回该集合。
@Override
Sources() 遍历所有的点，将该点所在边的起点以及对应的权值存入一个HashMap中，返回Map.

@Override targets() 遍历所有的点，将该点所在边的终点以及对应的权值存入一个HashMap中，返回Map.
toString()
以上重写的方法最后都检查了表示独立。

（3）ConcreteVerticesGraph类的测试
该类的测试继承了Graph的测试，因此添加对于Vertex类以及toString()方法的测试。
Vertex类测试：
策略：用一个测试测试是否能正确返回Vertex的三个属性,能否正确删减verSource,verTarget；再用一个测试测试vertex_toString()。对vertex_toString()的测试如下：

toString()方法的测试：
将设计好的特定的字符串与toStrin*生的字符串相比较，观察返回值。

3.1.4 Problem 3: Implement generic Graph
3.1.4.1 Make the implementations generic
将两个实现中可以修改为泛型的String全部替换为L占位符，而在test中将constuctors中将泛型具体化为String。
如图，修改后的一个test方法：

修改的ConcreteEdgesGraph类：

修改后进行Junit test结果如图：

3.1.4.2 Implement Graph.empty()
修改Graph.empty为：

修改后，所有测试仍能通过。

3.1.5 Problem 4: Poetic walks
3.1.5.1 Test GraphPoet
分别对空文件，文件中有一行或多行进行检测。具体测试函数如下模式：

3.1.5.2 Implement GraphPoet
a.属性：graph存储整个语法图，而words则存储分割好的词汇。

b.AF RI：

c.表示独立性的检测查

d.
public GraphPoet(File corpus) 首先，利用Scanner BufferedReader FileReader 将文件中的内容读出并将其按空格划分成单个词汇。

然后利用graph.add添加点，利用graph.set添加边。在添加边的过程中，需要判断该边之前是否存在，若存在，在其旧权值基础上加1；若不存在，添加该边，权值为1.

public String poem(String input) 遍历输入的需要补全的语句中的所有词。看前一个字符串的target是否与后一个串的字符串的source有交集，若有交集，说明可以在两字符串中添加新的字符串。

然后在交集中寻找两边相加权值最大的点

最后将它们连成新的串返回。
其中需要说明的是，在切分输入的字符串时，为了让最后一个单词前面也可以有插入（可以匹配生成的图），我在切分时将最后的标点去掉了，最后在句末加上标点。也可以不去标点，但最后一个单词可能无法和图中节点匹配。

public String toString() 直接调用graph的方法。

3.1.5.3 Graph poetry slam
对样例进行测试：

Junit测试结果如下：

3.1.6 使用Eclemma检查测试的代码覆盖度

说明：FriendshipGraph.java覆盖率低是因为其中包含main函数，而覆盖率用的是Junit单元测试。Main.java也是这样。
3.1.7 Before you’re done
通过Git提交当前版本到GitHub上的Lab2仓库：
git add
git commit -m
git push

项目的目录结构树状示意图：

3.2 Re-implement the Social Network in Lab1
主要是设计一个人际关系网，可以添加新的人（即点），也可以添加新的朋友关系（即边），最后还需要计算最短路径。其中java程序，包括FriendshipGraph类，Person类，main()以及测试用例。

3.2.1 FriendshipGraph类
主要用到三个方法：addVertex, addEdge, getdistance.
addVertex主要复用ConcreteVerticesGraph里的add方法，addEdge主要复用ConcreteVerticesGraph里的set方法。getdistance用到了ConcreteVerticesGraph里的getTarget方法。前两个都是直接复用，最后一个还用到队列进行广度优先搜索，代码如下：

3.2.2 Person类
本次设计的Person类比第一次的要简明很多，第一次的add,addedge等都是通过Person类里的方法，这次直接复用ConcreteVerticesGraph方法，因此只有一个属性，private final String name。方法为getName().

3.2.3 客户端main()
main函数和第一次实现的相同。具体代码是对实验指导书的修改，不再赘述。

3.2.4 测试用例
（1）addVertexTest
加入两个person，测试图中的人的数量，看是否等于2，为方便测试，在FriendshipGraph中加入getVertices方法，复用ConcreteVerticesGraph的Vertices方法。
（2）addEdgeTest
添加人之间的朋友关系，检测其中一人的朋友数目。
（3）getdistanceTest
对gettheDistance的测试构造了一个新的图，验证计算所得是否符合预期。

4 实验进度记录
请使用表格方式记录你的进度情况，以超过半小时的连续编程时间为一行。

日期 时间段 计划任务 实际完成情况
6.9 20:00-22:00 配置相应环境，浏览任务 未完成
6.10 20:00-22:30 编写P1测试 完成
6.11 22:00-23:00 编写P1的问题2 未完成
6.12 10:00-12:00 完成ConcreteEdgesGraph 完成
6.12 13:00-17:40 完成ConcrteVerticesGraph 未完成
6.12 19:00-22:00 完善ConcrteVerticesGraph并写P2 完成
6.13 9:00-12:00 完成P1中最后一个问题 未完成
5 实验过程中遇到的困难与解决途径
遇到的难点 解决途径
写万concreteEdgeGraph后再写ConcreteVerticesGraph思路转换不过来，写的时候感觉特别绕

具体画图，通过具象的图转换为抽象表达

在写ConcreteVerticesGraph的删除一个点的方法时，删完了和其他点之间的关系，不会在整体图中删除该点本身。

利用迭代器加it实现删除

整合目录时，最初将ConcreteVerticesGraph放在src/P1/graph,而测试函数放在test/graph导致出现大量cannot be resolved to a type 错误

将文件和对应的测试放在相似的目录下。

6 实验过程中收获的经验、教训、感想
6.1 实验过程中收获的经验和教训
本次实验，我分别利用边和点的数据结构实现了一个有向图，然后用有向图产生了一个可以天填空的生成器。通过这次实验，我熟练了利用Java解决问题的流程，同时再次复习了AF RI 等，实践了对规约的书写。本次实验，我对Map，List，Set等接口的使用也更加熟练。对于泛型的使用，我也有了更加深入的了解。在FriendshipGraph中，我进一步利用Graph中的方法，使FriendshipGraph变得简单了很多。
在整合目录时，感觉后期写完项目再整合目录非常麻烦，下次实验中，我尝试在一开始导入该工程时就建立正确的目录结构。