侧边栏壁纸
  • 累计撰写 62 篇文章
  • 累计创建 35 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

软件构造Lab 2 P1-Poetic Walks 简单翻译

生榆
2019-03-27 / 0 评论 / 0 点赞 / 421 阅读 / 7360 字
温馨提示:
本文最后更新于 2022-12-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

获取代码

概览

Java集合框架(Java Collection Framework)提供了许多有用的对象集合数据结构,比如list, map, queue, set等等,但没有提供图(graph)的数据结构,所以我们来实现graph,然后创造一些神奇的东西(timeless art of unparalleled brilliance,不知道怎么翻译好)

Problem 1-3: 我们将要实现Graph<L>,这是一个抽象数据类型,用来表示一个各个顶点都有标签的可变的带权有向图。

可变(mutable)的图 顶点和边可以被加入或移除
有向图 每条边都从来源顶点(source)指向目标(target)顶点
边的权(weight) 每条边都与一个正整数关联,作为它的权
顶点拥有标签 每个顶点都依靠一个不可变的标签(label)来区分,例如他们可以用String作为名称,或者Integer作为ID

阅读 从src/graph/Graph.java中生成的 Javadoc documentation for Graph

Graph<L>是一个类似List<E>Map<K,V>的泛型……(以下略去n字的介绍文字)

(概括一下:L要求不可变)

在这次的问题中,为了练习我们设计和选择合理的AF和RI,同时避免表示暴露(rep exposure),我们要用不同的表示(Rep)来实现Graph两次

**Problem 4:**此时我们已经有了图的类型,然后我们需要实现GraphPoet,这是一个用图生成诗句的类。

Problem 1 测试Graph<String>

现在我们只需要测试用String作为顶点标签的图(然后再实现),之后再拓展到其他类型的标签。
为了使我们图的测试能够多次实现并运行,请参考下面的步骤:

  • 静态的Graph.empty()测试方法在GraphStaticTest.java中。因为这个方法(指Graph.empty()方法)是静态的,只需要有一种实现,我们只需要运行这些测试一次。这些测试已经给出了,可以自行添加或修改,也可以保留原状。
  • 在实例(instance)的测试类GraphStaticTest.java中实现你自己的测试。这些测试中你必须使用emptyInstance()来获得全新的图的对象,不是Graph.empty()!可以参考testInitialVerticesEmpty()中的例子

不像GraphStaticTest及其他已经提供的测试方法,GraphInstanceTest有些不同,因为你不能直接运行,你需要先实现emptyInstance()方法来提供一个全新的Graph对象。在下一个problem中,我们会见识到两个GraphInstanceTest的子类,分别用不同返回类型的图来填补这份空白。

你的测试必须对Graph的spec合法。然后commit吧。

Problem 2:实现Graph<String>

现在我们要用String作为顶点的标签来实现带权有向图两次

这个problem中,你写的所有类都要满足:

  • 写出AF和RI
  • 根据RI,写出你如何防止表示泄露
  • 实现checkRep来判断是否符合RI
  • 实现toString,以用人类能看懂的方式表示出你的抽象数据

未来对每个不可变的数据类型,你都需要覆盖equals方法和hashCode方法,但本problem不要求。

你写的所有类必须有清晰的spec,这意味着除了你用@Override覆盖的方法之外,每一个方法都要有Java的文档注释:

  • 当一个方法在它的类的接口中声明,在其他类中实现,例如在ConcreteEdgesGraph里的add(..)方法,在Graph中声明,如果在实现时使用@Override覆盖了,意味着这两个方法有着相同的spec,除非你要增强这个spec,否则不需要再写一遍。

ConcreteEdgesGraphConcreteVerticesGraph的完成先后由你自己决定,但相互之间不能存在依赖和共享的实现代码。

2.1 实现ConcreteEdgesGraph

为了实现ConcreteEdgesGraph,你必须使用已经提供的rep:

private final Set<String> vertices = new HashSet<>();
private final List<Edge> edges = new ArrayList<>();

你不可以增加其他字段或者不使用它们。

对于Edge类,由你自己定义spec和rep,但是Edge必须是immutable不可变的。

通常实现一个不可变的数据类型要求要同时也要实现equalshashCode方法,本节不做此要求,但是如果不去覆盖着两个方法,意味着你不能使用equals比较两条边还想获得正确的结果。是否覆盖着两个方法取决于你。

完成spec后,先实现Concrete­EdgesGraphTest.java中对Edge的测试。然后进一步实现EdgeConcreteEdgesGraph

注意当你在覆盖toString时,要使用@Override注释来表明你在覆盖Object中的方法,而不是创造一个新的方法。

你需要增强ConcreteEdgesGraph.toString()的spec,然后为此在Concrete­EdgesGraphTest.java中写一个测试。注意不要写到GraphInstanceTest里。

所有Java类都继承了Object.toString()的方法和它不明确的spec,Graph没有声明更强的spec,但是两个具体的(concrete)类可以。故意不增强GraphtoString的spec是为了通用性。

写完测试后运行,commit。

2.2 实现ConcreteVerticesGraph

(这部分的任务和上面的原理是一样的,下面就概括翻译了)

首先你得用提供的rep,不能增删改。

private final List<Vertex> vertices = new ArrayList<>();

与上面的Edge类不同的是,Vertex必须是mutable可变的。

重复上面ConcreteEdgesGraphEdge的操作:spec、测试、实现、运行测试、commit and push!

Problem 3:实现通用的Graph<L>

这部分要做的事情是将之前实现的图泛型化,你所写的两个Graph的实现都可以不依赖于把String作为顶点的标签。

3.1. 将实现通用化

a. 将声明改成如下形式:

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

class Edge<L> { ... }

和:

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

class Vertex<L> { ... }

b. 让你的实现支持L占位符,而不再是String,通俗地讲,就是要把所有String都改成L
- 你之前声明的EdgeList<Edge>需要修改成Edge<L>List<Edge<L>>
- new ConcreteEdgesGraph()new Edge()也要改成new ConcreteEdgesGraph<String>()new Edge<L>()

commit and push吧!

3.2 实现Graph.empty()

a. 选一个你的实现方法供客户端使用,然后用它完成Graph.empty()的实现。和ArrayListLinkedList不同,客户端有时只是想要一个表示列表List的东西,并不在意实现,这里也相同,客户端不需要知道你是用哪一种图来实现需求的功能的。
b. 因为Graph的实现并不关心顶点实际的标签类型,所以我们的测试使用String就足够了。

但你也可以添加额外的测试方法来测试拥有不同的类型标签的顶点(但要求是不可变的类型)。

这里要求你的实现和测试没有任何warning,而且不可使用@SuppressWarnings注释。

Problem 4:Poetic walks

(概括一下)
这里大致的任务是:给你一段语料,你需要解析内容然后生成一幅带权有向图,之后用这个图创造“诗句”。

举个例子,语料(corpus)可能长这样:

To explore strange new worlds
To seek out new life and new civilizations

然后GraphPoet将使用这些语料生成一幅图,满足:

  • 顶点忽略大小写
  • 边的权是出现次数

然后再给你一段输入,你需要用已经生成的图把一些形容词添加进去。
例如现在输入:

Seek to explore new and exciting synergies!

你得输出:

Seek to explore strange new life and exciting synergies!

(因为这段输入中有“explore new”,而上面的语料中这两个单词之间存在一个“strange”,所以你得把strange加进去)
(其他细节见GraphPoet的spec)

具体的图和分析看MIT实验手册

4.1 测试GraphPoet

套路十分相似,不翻译了。

0

评论区