软件构造Lab1-SocialNetwork
要求
Implement and test a FriendshipGraph class that represents friendships in a social network and can compute the distance between two people in the graph. An auxiliary class Person is also required to be
implemented. You should model the social network as an undirected graph where each person is connected to zero or more people, but your underlying graph implementation should be directed. Your solution must work with the following client implementation.
- FriendshipGraph graph = new FriendshipGraph();
- Person rachel = new Person(“Rachel”);
- Person ross = new Person(“Ross”); Lab Manuals for Software Construction Lab-1 Fundamental Java Programming and Testing 6
- Person ben = new Person(“Ben”);
- Person kramer = new Person(“Kramer”);
- graph.addVertex(rachel);
- graph.addVertex(ross);
- graph.addVertex(ben);
- graph.addVertex(kramer);
- graph.addEdge(rachel, ross);
- graph.addEdge(ross, rachel);
- graph.addEdge(ross, ben);
- graph.addEdge(ben, ross);
- out.println(graph.getDistance(rachel, ross));//should print
- System.out.println(graph.getDistance(rachel, ben));//should print 2
- System.out.println(graph.getDistance(rachel, rachel));//should print 0
- System.out.println(graph.getDistance(rachel, kramer));//should print -1
Your solution should work with the client code above. The getDistance method should take two people (as Person) as arguments and return the shortest distance (an int) between the people, or -1 if the two people
are not connected (or in other words, there are no any paths that could reach the second people from the first one). Your graph implementation should be reasonably scalable. We will test your graph with several hundred or thousand vertices and edges. Use proper access modifiers (public, private, etc.) for your fields and methods. If a field/method can be private, it should be private. Do not use static fields or methods except for the main method(s) and constant Follow the Java code conventions, especially for naming and commenting. Hint: use Ctrl + Shift + F to auto-format your code! Add short descriptive
comments (/** … */) to all public methods. Additional hints/assumptions For your implementation of getDistance, you may want to review breadth-first search. You may use the standard Java libraries, including classes from java.util, but no third-party libraries. You may assume that each person has a unique name. Lab Manuals for Software Construction Lab-1 Fundamental Java Programming and Testing 7 You may handle incorrect inputs however you want (printing to standard out/error, silently failing, crashing, throwing a special exception, etc.) You should write additional samples to test your graph, similar to our main method. To print something to standard out, use System.out.println. For example: System.out.println(“DON’T PANIC”); You should also write JUnit test code to test the methods addVertex(), addEdge(), and getDistance() of the class FriendshipGraph. All the test cases should be included in FriendshipGraphTest.java in the directory \test\P3. Test cases should be sufficient enough.
设计/实现FriendshipGraph类
存储结构：
private Set<Person> persons = new HashSet<Person>();
用来存储人
private Set<String> names = new HashSet<String>();
用来存储人名，以此检查是否出现人名重复的情况
人际关系在Person类中实现（为了实现有向图）
public boolean addVertex(Person person)
将person这个节点添加到persons中，同时判断是否存在重名的问题，如果有，直接返回false，如果没有，就将其名字加入names中，返回true。
public boolean addEdge(Person per1, Person per2)
两次调用Person类中的addFriend函数即可，同时注意判断两个人是否是同一个人，并返回对应结果
getDistance(Person per1, Person per2)
使用广度优先搜索
Map<String, Boolean> visited = new HashMap<>();
Map<String, Integer> dis = new HashMap<>();
用两个图来存储一个点是否被访问和对应的距离
Queue<Person> temp
建一个队列来存储正在和将要访问的节点
流程
- 初始化visited中的每个点的vis属性为false，dis中的为0
- 将per1加入队列temp，并visited.put(src.getName(), true)
- 检查队列是否为空
若是，结束循环，返回-1
若否，取出队首节点存入vertex，重复第3、4、5步操作 - 搜索per1的friends set（在Person类中实现）中未访问过的节点
如果有子节点等于per2，即找到一条最短路，结束搜索，返回当前的路径长度
否则，将满足要求的子节点依次加入队列，将其visited对应值置为true - 所有满足条件的子节点扫描完之后，对应节点的dis ++；
设计/实现Person类
存储结构
private String name;
用来存储名字
public Queue<Person> friends = new LinkedBlockingQueue<Person>();
用来存储朋友（以此实现单边的关系）
其它函数就不再赘述，见代码
Person类
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
public class Person {
private String name;
public Queue<Person> friends = new LinkedBlockingQueue<Person>();
public Person() { System.out.println("PleaseGiveMeaName!"); }
public Person(String name) { this.name = name; }
public void setName(String name) { this.name = name; }
public String getName() { return name; }
public boolean hasFriend(Person friend) { return friends.contains(friend); }
public boolean hasFriends() { return friends.isEmpty(); }
public boolean addFriend(Person friend) {
if(friends.contains(friend)) return false;
else {
friends.add(friend);
return true;
}
}
public boolean deleteFriend(Person friend) {
if(friends.contains(friend)) {
friends.remove(friend);
return true;
} else return true;
}
}
FriendshipGraph类
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
import P3.Person;
public class FriendshipGraph {
private Set<Person> persons = new HashSet<Person>();
private Set<String> names = new HashSet<String>();
public boolean addVertex(Person person) {
if(persons.contains(person) || names.contains(person.getName()))
return false;
else {
persons.add(person);
names.add(person.getName());
return true;
}
}
public boolean addEdge(Person per1, Person per2) {
boolean flag = false;
if(per1 == per2) return false;
for(Person person : persons)
if(person.getName() == per1.getName()) {
per1 = person;
persons.remove(person);
per1.addFriend(per2);
persons.add(per1);
flag = true;
break;
}
return flag;
}
public int getDistance(Person src, Person dest){
if (src.getName().equals(dest.getName()))
return 0;
Map<String, Boolean> visited = new HashMap<>();
Map<String, Integer> dis = new HashMap<>();
for (Person person: persons) {
visited.put(person.getName(), false);
dis.put(person.getName(), 0);
}
visited.put(src.getName(), true);
Queue<Person> queue = new LinkedBlockingQueue<>();
queue.add(src);
while (!queue.isEmpty()){
Person vertex = queue.poll();
Queue<Person> temp = vertex.friends;
while (!temp.isEmpty()){
if(visited.get(temp.peek().getName())) {
temp.poll();
continue;
}
if (temp.peek().getName().equals(dest.getName()))
return dis.get(vertex.getName()) + 1;
else{
visited.put(temp.peek().getName(), true);
dis.put(temp.peek().getName(), dis.get(vertex.friends.peek().getName()) + 1);
queue.add(temp.poll());
}
}
}
return -1;
}
public static void main(String args[]) {
FriendshipGraph graph = new FriendshipGraph();
Person rachel = new Person("Rachel");
Person ross = new Person("Ross");
Person ben = new Person("Ben");
Person kramer = new Person("Kramer");
graph.addVertex(rachel);
graph.addVertex(ross);
graph.addVertex(ben);
graph.addVertex(kramer);
graph.addEdge(rachel, ross);
graph.addEdge(ross, rachel);
graph.addEdge(ross, ben);
graph.addEdge(ben, ross);
System.out.println(graph.getDistance(rachel, ross));
System.out.println(graph.getDistance(rachel, ben));
System.out.println(graph.getDistance(rachel, rachel));
System.out.println(graph.getDistance(rachel, kramer));
}
}
警告
未来的学习学妹们，这是我自己的一个记录，也是给你们的参考
请一定要自己完成，你会有很大收获的