获取代码
略
概览
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，否则不需要再写一遍。
ConcreteEdgesGraph和ConcreteVerticesGraph的完成先后由你自己决定，但相互之间不能存在依赖和共享的实现代码。
2.1 实现ConcreteEdgesGraph
为了实现ConcreteEdgesGraph，你必须使用已经提供的rep：
private final Set<String> vertices = new HashSet<>();
private final List<Edge> edges = new ArrayList<>();
你不可以增加其他字段或者不使用它们。
对于Edge类，由你自己定义spec和rep，但是Edge必须是immutable不可变的。
通常实现一个不可变的数据类型要求要同时也要实现equals和hashCode方法，本节不做此要求，但是如果不去覆盖着两个方法，意味着你不能使用equals比较两条边还想获得正确的结果。是否覆盖着两个方法取决于你。
完成spec后，先实现ConcreteEdgesGraphTest.java中对Edge的测试。然后进一步实现Edge和ConcreteEdgesGraph。
注意当你在覆盖toString时，要使用@Override注释来表明你在覆盖Object中的方法，而不是创造一个新的方法。
你需要增强ConcreteEdgesGraph.toString()的spec，然后为此在ConcreteEdgesGraphTest.java中写一个测试。注意不要写到GraphInstanceTest里。
所有Java类都继承了Object.toString()的方法和它不明确的spec，Graph没有声明更强的spec，但是两个具体的（concrete）类可以。故意不增强Graph的toString的spec是为了通用性。
写完测试后运行，commit。
2.2 实现ConcreteVerticesGraph
（这部分的任务和上面的原理是一样的，下面就概括翻译了）
首先你得用提供的rep，不能增删改。
private final List<Vertex> vertices = new ArrayList<>();
与上面的Edge类不同的是，Vertex必须是mutable可变的。
重复上面ConcreteEdgesGraph和Edge的操作：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
- 你之前声明的Edge和List<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()的实现。和ArrayList及LinkedList不同，客户端有时只是想要一个表示列表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
套路十分相似，不翻译了。
评论区