I was practicing graph traversal when I found a
video about FB's recommender system, so I thought, hey, why not try implementing one.
Apparently, I am not capable of implementing a real recommender system, but based on some concepts in the video, I did this small project.
There are three main parts in this project:
1. The network, which is implemented by a graph.(Graph, Node, Edge)
2. Find recommendations for a user(node) in the graph. (FindFriend)
3. Find connections from a node to another node.(FindFriend)
The Graph
Update: 2015 - 03 - 12
My first version of the graph looks, well, memory expensive, I optimized a little bit. Here is the new version.
/**
* undirected graph
* user can only retrieve the node by its label
* all labels are unique
* @author shirleyyoung
*
*/
public class Graph {
Map vertices;
Set edges;
Map> neighbors;
public Graph (){
vertices = new HashMap();
edges = new HashSet();
neighbors = new HashMap>();
}
/**
* construct a graph from another graph
* @param G
*/
public Graph (Graph G) {
this.vertices = new HashMap();
this.edges = new HashSet();
copyGraph(G);
}
/**
* clone a graph from another one
* ConcurrentModificationException:
* For example, it is not generally permissible
* for one thread to modify a Collection
* while another thread is iterating over it.
*/
private void copyGraph(Graph G) {
//clone nodes
for (Node n : G.vertices.values()) {
this.vertices.put(n.label, new Node(n));
}
//clone edges
for(Edge e : G.edges){
List nodes = (List) e.getNodes();
Node n1 = nodes.get(0);
Node n2 = nodes.get(1);
this.edges.add(new Edge(vertices.get(n1.label), vertices.get(n2.label)));
if(!neighbors.containsKey(n1))
neighbors.put(n1, new ArrayList());
if(!neighbors.containsKey(n2))
neighbors.put(n2, new ArrayList());
neighbors.get(n1).add(n2);
neighbors.get(n2).add(n1);
}
}
/**
* Add vertex
* @param label
*/
public boolean addVertex(int label) {
if(containsVertex(label))
return false;
vertices.put(label, new Node(label));
return true;
}
/**
* connect two nodes
* @param l1
* @param l2
* @param distance
* @return
*/
public double addEdge(int l1, int l2, double distance) {
if(!containsVertex(l1) || !containsVertex(l2))
throw new NullPointerException("Graph doesn't contain such nodes");
Edge e = getEdge(l1, l2);
if(e != null)
e.modifyWeight(distance);
else{
Node n1 = getNode(l1);
Node n2 = getNode(l2);
e = new Edge(n1, n2, distance);
edges.add(e);
if(!neighbors.containsKey(n1))
neighbors.put(n1, new ArrayList());
if(!neighbors.containsKey(n2))
neighbors.put(n2, new ArrayList());
neighbors.get(n1).add(n2);
neighbors.get(n2).add(n1);
}
return e.weight;
}
public void chooseSource(int label) {
Node source = getNode(label);
source.dist = 0;
}
/**
* if a node exists
* @param label
* @return
*/
public boolean containsVertex(int label) {
return vertices.containsKey(label);
}
/**
* get the node
* @param label
* @return
*/
Node getNode(int label) {
if (containsVertex(label))
return vertices.get(label);
return null;
}
/**
* if there exists an edge between two node
* @param l1
* @param l2
* @return
*/
public boolean isConnected(int l1, int l2) {
if(!containsVertex(l1) || !containsVertex(l2))
throw new NullPointerException("Graph doesn't contain such node!");
Edge tmp = new Edge(getNode(l1), getNode(l2));
for(Edge e : edges){
if(e.equals(tmp))
return true;
}
return false;
}
/**
* get an existing edge from the graph
* @param l1
* @param l2
* @return
*/
Edge getEdge(int l1, int l2){
if(!containsVertex(l1) || !containsVertex(l2))
throw new NullPointerException("Graph doesn't contain such node!");
Edge tmp = new Edge(getNode(l1), getNode(l2));
for(Edge e : edges){
if(e.equals(tmp))
return e;
}
return null;
}
/**
* @return number of vertices in the graph
*/
public int getSize() {
return vertices.size();
}
/**
* @return number of edges in the graph
*/
public int numEdges(){
return edges.size();
}
public String toString() {
StringBuilder s = new StringBuilder();
String NEWLINE = System.getProperty("line.separator");
s.append(getSize() + " vertices, " + numEdges() + " edges " + NEWLINE);
for (Node v : vertices.values()) {
s.append("Node: " + v.label + "\n");
s.append("neighbors: \n");
for (Node nb: neighbors.get(v)){
s.append(nb.label + " ");
}
s.append(NEWLINE);
}
s.append(NEWLINE);
for(Edge e : edges){
List nodes = (List) e.getNodes();
s.append(nodes.get(0).label).append(" - ").append(nodes.get(1).label + "\n");
}
s.append(NEWLINE);
return s.toString();
}
}
public class Node {
int label;
double dist;
Node(int x) {
label = x;
dist = Integer.MAX_VALUE;
}
Node(Node n) {
//only copy the label from another node,
//neighbors and edges need
//to be redefined
this.label = n.label;
dist = Integer.MAX_VALUE;
}
public boolean equals(Node n) {
return label == n.label;
}
}
public class Edge implements Comparator {
double weight;
Node n1;
Node n2;
/**
* default weight = 1.0
* @param n1
* @param n2
*/
public Edge(Node n1, Node n2) {
if (n1.equals (n2))
throw new IllegalArgumentException("Cannot form an edge with itself!");
this.n1 = n1;
this.n2 = n2;
weight = 1.0;
}
/**
* constructor that allows user defined weight
* @param n1
* @param n2
* @param weight
*/
public Edge(Node n1, Node n2, double weight) {
if (n1.equals (n2))
throw new IllegalArgumentException("Dont't cheat, connecting with yourself doens't mean you have one more fan!");
this.n1 = n1;
this.n2 = n2;
this.weight = weight;
}
/**
* to modify the weight
* @param w
*/
public void modifyWeight(double w) {
if (w <= 0.0)
throw new IllegalArgumentException("Weight must be positive!");
weight = w;
}
/**
* get the nodes that are connected by this edge
* @return
*/
public Collection getNodes() {
List nodes = new ArrayList ();
nodes.add(n1);
nodes.add(n2);
return nodes;
}
/**
* get the weight
* @return
*/
public double getWeight() {
return weight;
}
public int compare(Edge e1, Edge e2){
if(e1.weight > e2.weight)
return 1;
else if(e1.weight < e2.weight)
return -1;
return 0;
}
public boolean equals(Edge e){
for(Node n : e.getNodes()){
if(!this.getNodes().contains(n))
return false;
}
return true;
}
}
The graph is implemented by three classes: Node, Edge and Graph.
Node
Node class has three objects: a unique label, a list of neighbors and a map that stores edge and the neighbor node it connects. My initial idea is to include duplicate label conditions, because in reality it is possible that two people have the same name, sex, age, etc. Then I realize no matter how similar two nodes are, there must be something to distinguish them, so I finalized with unique label. If in future other data needs to be included in the calculation of distance between two nodes, a map<label, data> can be used to store extra data.
There are two methods in the Node class, getHash() and equals(), they have the same purpose: two check the equality of two nodes. I wrote the getHash() because initially I was thinking about duplicate labels, so I need to include neighbors to check the equality. However, if unique labels are used, this method is unnecessary.
import java.util.*;
public class Node {
int label;
List neighbors;
//
Map edges;
Node(int x) {
label = x;
neighbors = new ArrayList ();
edges = new HashMap ();
}
Node(Node n) {
//only copy the label from another node,
//neighbors and edges need
//to be redefined
this.label = n.label;
neighbors = new ArrayList();
edges = new HashMap ();
}
//the hash function to determine the equality of two nodes
//for graphs with unique nodes, this is not required
private int getHash() {
int hash_a = 378551;
int hash_b = 63689;
int hash = 0;
for (Node neighbor : neighbors) {
hash += hash * hash_a + neighbor.label;
hash_a = hash_a * hash_b;
}
//hash += label;
return hash;
}
public boolean equals(Node n) {
return label == n.label && (getHash() == n.getHash());
}
}
Edge
Initially I used a map in the node class to store the distance and connecting nodes, but I want the graph to look concrete, so I separated it and wrote this class. There are three objects in this class, two connecting nodes, and the weight. The weights are used to calculate the distance among nodes. There are two constructors, the first one set default weight to 1 and only require two nodes as inputs. The second one allows user to define weights. When Edge is initialized, both nodes will be added to the neighbor list of the other.
getNodes() method is used to get the two nodes that are connected by the edge and getWeight(), obviously, is used to get the weight.
import java.util.*;
public class Edge {
int weight;
Node n1;
Node n2;
//default weight = 1
public Edge(Node n1, Node n2) {
if (n1.equals (n2))
throw new IllegalArgumentException("Cannot form an edge with itself!");
if (n1.neighbors.contains(n2))
throw new IllegalArgumentException("Edege exists!");
this.n1 = n1;
this.n2 = n2;
n1.neighbors.add(n2);
n2.neighbors.add(n1);
weight = 1;
}
//constructor that allows user defined weight
public Edge(Node n1, Node n2, int weight) {
if (n1.equals (n2))
throw new IllegalArgumentException("Dont't cheat, connecting with yourself doens't mean you have one more fan!");
if (n1.edges.containsKey(n2) && n2.edges.containsKey(n1))
throw new IllegalArgumentException("Edege exists!");
this.n1 = n1;
this.n2 = n2;
n1.neighbors.add(n2);
n2.neighbors.add(n1);
this.weight = weight;
}
//to modify the weight
public void modifyWeight(int w) {
if (w <= 0)
throw new IllegalArgumentException("Weight must be positive!");
weight = w;
}
//get the nodes that are connected by this edge
public List getNodes() {
List nodes = new ArrayList ();
nodes.add(n1);
nodes.add(n2);
return nodes;
}
//get the weight
public int getWeight(Node n1, Node n2) {
if (!(n1.equals(this.n1) && n2.equals(this.n2)) && !(n1.equals(this.n2) && n2.equals(this.n1)))
throw new IllegalArgumentException("Wrong input node!");
return weight;
}
}
Graph
The Graph class is used to construct the "social network". It is an undirected graph (I don't see the reason if I connect with you but you cannot connect with me). I used a map to store <label, node> assuming users can only access the node by its label. A graph can be initialized as an empty graph or by clone another graph.
Some necessary methods include addVertex(), addEdge(), containsVertex(), isConnected() and toString(). Initially I mad getNode() method private, because I want the node can only be accessed within the class (accessed by label outside the class). Then my FindFriends class need to access the node, so I made it public.
I am making a note here to make the modifications later. I commented out the Iterable version of getNeighbors() method because the user outside the class may only want to "see" the neighbors.
import java.util.*;
//undirected graph
//user can only retrieve the node by its label
//all labels are unique
//if other data needs to be stored in the node, a map can be used
public class Graph {
private Map vertices;
//# of vertices
private int size;
//# of edges
private int edges;
public Graph (){
size = 0;
vertices = new HashMap();
edges = 0;
}
//construct a graph from another graph
public Graph (Graph G) {
this.size = G.size;
this.vertices = new HashMap();
this.edges = G.edges;
copyGraph(G);
}
//clone a graph from another one
/*
* ConcurrentModificationException:
* For example, it is not generally permissible
* for one thread to modify a Collection
* while another thread is iterating over it.
*/
private void copyGraph(Graph G) {
//clone nodes
for (Node n : G.vertices.values()) {
this.vertices.put(n.label, new Node(n));
}
//clone edges
for (Node n : G.vertices.values()) {
Node curr = getNode(n.label);
for (Node w : n.neighbors) {
Node neighbor = getNode(w.label);
if (!isConnected(curr, neighbor)) {
int weight = n.edges.get(w).getWeight(n, w);
Edge e = new Edge(curr, neighbor, weight);
curr.edges.put(neighbor, e);
neighbor.edges.put(curr, e);
}
}
}
}
//Add vertex
public void addVertex(int label) {
Node n = new Node(label);
vertices.put(label, n);
size++;
}
//Add edge
//The edge class will take care of adding neighbors to the neighbor list of the node
public void addEdge(int l1, int l2, int distance) {
Node v = getNode(l1);
Node w = getNode(l2);
if (v.neighbors.contains(w) && w.neighbors.contains(v)) {
System.out.println("Edge exists!");
return;
}
Edge e = new Edge(v, w, distance);
v.edges.put(w, e);
w.edges.put(v, e);
edges++;
}
//if a node exists
public boolean containsVertex(int label) {
return vertices.containsKey(label);
}
//if there exists an edge between two node
public boolean isConnected(int l1, int l2) {
return getNode(l1).edges.containsKey(getNode(l2))
&& getNode(l2).edges.containsKey(getNode(l1));
}
private boolean isConnected(Node n1, Node n2) {
return n1.edges.containsKey(n2) && n2.edges.containsKey(n1);
}
public Node getNode(int label) {
if (containsVertex(label))
return vertices.get(label);
return null;
}
/*public Iterable getNeighbors(int label) {
if(!containsVertex(label))
throw new IllegalArgumentException("Graph doesn't contain such node!");
return getNode(label).neighbors;
}*/
//get neighbors of a node
public String getNeighbors(int label) {
String neighbor = "";
for (Node n : getNode(label).neighbors) {
neighbor += n.label + ", ";
}
return neighbor.substring(0, neighbor.length() - 2);
}
public int neighborSize(int label) {
if (!containsVertex(label))
throw new IllegalArgumentException("Graph doesn't contain such node!");
return getNode(label).neighbors.size();
}
public String toString() {
StringBuilder s = new StringBuilder();
String NEWLINE = System.getProperty("line.separator");
s.append(size + " vertices, " + edges + " edges " + NEWLINE);
for (Node v : vertices.values()) {
s.append("Node: " + v.label + "\n");
for (Node w : v.neighbors) {
s.append(w.label + "; edge: " + v.edges.get(w).getWeight(v, w) + NEWLINE);
}
s.append(NEWLINE);
}
return s.toString();
}
}
FindFriends
The purpose of this class is to, first, find desired number of recommendations for the user and, second, find connections between the user and a target.
This class is aimed to one user, so the constructor will require user to input a "user", kidding, a node. A list of potential friends will be generated upon initialization.
The potential friends list is generated from FOF, i.e., friends of friends. According to the FB video, a FB user on average has 100 friends, so FOF will be in the order of 10^4, if we consider third degree connection, it will be 10^6, so don't worry, you don't want to know that many people in your life.
Another map, distanceFOF is used to store the distance of FOF from the user. getDistance() is calculated by the following equation:
Of course it is from that interesting FB video. Make it simple, this equation calculate the priority of an FOF to the friend, to smaller the value, the high priority the FOF is, i.e., he or she will be highly recommended. Delta is the number of days that a person is connected with the other (user, friend i; friend i, FOF). I used the weight of the edge to represent delta. I didn't fully understand what "friends" in the divisor means, I guess it means the friends size(neighbor list) of the friend i. The equation then adds up all friends of the user that are friends with the FOF.
In fact, I don't have to make things that complicated, I am not going to need this equation anyway, but , just for fun. :)
Update: 2015 - 03 - 30
So this class is finally updated too. :)
import java.util.*;
/**
* This class is used for
* 1. find recommendations from friends of friends of the user
* 2. find the closest connections between the user and a person
* @author shirleyyoung
*
*/
public class FindFriends {
Node user;
Graph g;
Set potentialFriends;
Map scoreFOF;
int numRecommendations;
/**
* this constructor will find the potential friends list for the user
* and generate the distance between the user and a potential friend (fof)
*/
public FindFriends(int label, int numRecommendations, Graph g){
if (numRecommendations <= 0)
throw new IllegalArgumentException("At least one recommendation, please...");
this.g = g;
if(!g.containsVertex(label))
throw new IllegalArgumentException("No such user!");
user = g.getNode(label);
potentialFriends = new HashSet ();
scoreFOF = new HashMap ();
this.numRecommendations = numRecommendations;
getPotentialFriends();
}
//find all fof from user's friends
private void getPotentialFriends() {
List neighbors = g.neighbors.get(user);
for (Node w : neighbors) {
for (Node fof : g.neighbors.get(w)) {
if (!neighbors.contains(fof) && !fof.equals(user)
&& potentialFriends.add(fof))
getDistance(fof);
}
}
}
/**
* distance is calculated by a formula from FB
* the weight of the edge is actually the number of days
* that two people are connected
* @param fof
*/
private void getDistance(Node fof) {
if(scoreFOF.containsKey(fof))
return;
double v = 0;
for (Node ffof : g.neighbors.get(fof)) {
if(g.isConnected(ffof.label, user.label)){
//distance between user and friend
double u_f = g.getEdge(user.label, ffof.label).weight;
//distance between friend and fof
double f_fof = g.getEdge(fof.label, ffof.label).weight;
v += Math.pow(u_f * f_fof, -0.3) / Math.sqrt(g.neighbors.get(ffof).size());
}
}
scoreFOF.put(fof, v);
}
/**
* find recommendations
* fofs with shortest distance will be recommended
* Greedy approach
* @return
*/
private Collection getRecommendations() {
NodeComparator nc = new NodeComparator() ;
PriorityQueue recommendedFriend = new PriorityQueue(numRecommendations, nc);
for (Node fof : potentialFriends) {
//System.out.println(fof.label);
if (recommendedFriend.size() < numRecommendations) {
recommendedFriend.add(fof);
} else {
if(nc.compare(fof, recommendedFriend.peek()) < 0) {
recommendedFriend.poll();
recommendedFriend.offer(fof);
}
}
}
return recommendedFriend;
}
public String recommendedFriend() {
Collection pq = getRecommendations();
StringBuilder sb = new StringBuilder();
sb.append("People you may know: \n");
for (Node n : pq) {
sb.append(n.label).append(", ");
}
return sb.delete(sb.length() - 2, sb.length() - 1).append("\n*****").toString();
}
private class NodeComparator implements Comparator {
public int compare(Node a, Node b) {
double da = scoreFOF.get(a);
double db = scoreFOF.get(b);
if (da - db < 0)
return 1;
else if (da - db > 0)
return -1;
return 0;
}
}
/**
* find the shortest path from the user to a random (-.-)person
* BFS is used
* @param target
* @param termination
* @return
*/
private List> findConnections(Node target, int termination) {
if(termination < 3){
termination = 3;
}
//
Map> predecessor = new HashMap>();
//
Map distance = new HashMap();
List> connections = new ArrayList> ();
getConnections(target, predecessor, distance, termination);
if (distance.size() == 1)
return connections;
getList(target, predecessor, distance, connections, new ArrayList());
return connections;
}
private void getConnections(Node target, Map> predecessor,
Map distance, int termination) {
Queue q = new LinkedList ();
predecessor.put(user, new ArrayList());
distance.put(user, 0);
q.offer(user);
boolean found = false;
//terminate the search after certain degree or if the whole graph has been searched
int degree = 0;
while (distance.size() < g.getSize() && degree < termination && !found) {
Node curr = q.poll();
if (curr.equals(target)) {
found = true;
break;
}
for (Node neighbor : g.neighbors.get(curr)) {
if (neighbor.equals(user))
continue;
if (!predecessor.containsKey(neighbor)) {
predecessor.put(neighbor, new ArrayList());
predecessor.get(neighbor).add(curr);
}
else {
if (!predecessor.get(neighbor).contains(curr))
predecessor.get(neighbor).add(curr);
}
if (!distance.containsKey(neighbor)) {
distance.put(neighbor, distance.get(curr) + 1);
}
q.add(neighbor);
}
}
}
private void getList(Node curr, Map> predecessor, Map distance,
List> connections, List path) {
path.add(curr);
if (curr.equals(user)) {
Collections.reverse(path);
connections.add(new ArrayList (path));
//Never ever forget this!
Collections.reverse(path);
}
else {
for (Node n : predecessor.get(curr)) {
if (distance.containsKey(n) && distance.get(curr) == distance.get(n) + 1) {
getList(n, predecessor, distance, connections, path);
}
}
}
path.remove(path.size() - 1);
}
public String connection(int label, int termination) {
if(!g.containsVertex(label))
throw new IllegalArgumentException("No such user!");
Node target = g.getNode(label);
List> connections = findConnections(target, termination);
String NEWLINE = System.getProperty("line.separator");
StringBuilder sb = new StringBuilder();
sb.append("You can be connected with " + target.label + " through: " + NEWLINE);
for (List path : connections) {
for (Node n : path) {
sb.append(n.label + " -> ");
}
sb.delete(sb.length() - 4, sb.length() - 1);
sb.append(NEWLINE);
}
return sb.toString();
}
}
After initialization, all the FOFs and distances will be generated.
public class FindFriends {
Node user;
List potentialFriends;
//all friends of the user that connect with fof
Map> connectingFriends;
Map distanceFOF;
int numRecommendations;
int GraphSize;
/*
* this constructor will find the potential friends list for the user
* and generate the distance between the user and a potential friend (fof)
*/
public FindFriends(Node n, int numRecommendations, int GraphSize){
if (numRecommendations <= 0)
throw new IllegalArgumentException("At least one recommendation, please...");
user = n;
potentialFriends = new ArrayList ();
connectingFriends = new HashMap>();
distanceFOF = new HashMap ();
this.numRecommendations = numRecommendations;
this.GraphSize = GraphSize;
getPotentialFriends(n);
getDistance();
}
//find all fof from user's friends
private void getPotentialFriends(Node n) {
for (Node w : n.neighbors) {
for (Node fof : w.neighbors) {
if (!n.neighbors.contains(fof) && !fof.equals(user)) {
if (!potentialFriends.contains(fof))
potentialFriends.add(fof);
if (!connectingFriends.containsKey(fof)) {
connectingFriends.put(fof, new ArrayList());
connectingFriends.get(fof).add(w);
}
else
connectingFriends.get(fof).add(w);
}
}
}
}
/*
* distance is calculated by a formula from FB
* the weight of the edge is actually the number of days
* that two people are connected
*/
private void getDistance() {
for (Node fof : potentialFriends) {
double v = 0;
for (Node friend : connectingFriends.get(fof)) {
//distance between user and friend
double u_f = user.edges.get(friend).getWeight(user, friend);
//distance between friend and fof
double f_fof = friend.edges.get(fof).getWeight(friend, fof);
v += Math.pow(u_f * f_fof, -0.3) / Math.sqrt(friend.neighbors.size());
}
distanceFOF.put(fof, v);
}
}
Find recommendations
Now all we need to do is to return the number of recommendations required. I used a priority queue with a fixed size, the number of recommendations. The queue will be sorted by the distance of the FOF with the user. If the queue reaches its initialized size, the queue will remove the last element, if it is larger than the current FOF.
/*
* find recommendations
* fofs with shortest distance will be recommended
*/
private PriorityQueue getRecommendations() {
NodeComparator nc = new NodeComparator() ;
PriorityQueue recommendedFriend = new PriorityQueue(numRecommendations, nc);
Collections.sort(potentialFriends, nc);
Node last = null;
for (Node fof : potentialFriends) {
//System.out.println(fof.label);
if (recommendedFriend.size() < numRecommendations) {
recommendedFriend.add(fof);
last = fof;
}
else {
if(nc.compare(fof, last) < 0) {
System.out.println(last.label);
recommendedFriend.remove(last);
recommendedFriend.add(fof);
last = fof;
}
}
}
return recommendedFriend;
}
public String recommendedFriend() {
PriorityQueue pq = getRecommendations();
StringBuilder sb = new StringBuilder();
sb.append("People you may know: \n");
for (Node n : pq) {
sb.append(n.label).append(", ");
}
return sb.delete(sb.length() - 2, sb.length() - 1).append("\n*****").toString();
}
private class NodeComparator implements Comparator {
public int compare(Node a, Node b) {
double da = distanceFOF.get(a);
double db = distanceFOF.get(b);
if (da - db < 0)
return -1;
else if (da - db > 0)
return 1;
return 0;
}
}
Find connections
This is not my initial plan. After I finished recommendation part, I thought, eh, my purpose is to learn BFS and DFS, but there is no BFS and DFS in this project. I know there is this find connections product on Linkedin, so I decided to try it myself. When I googled "the shortest path" yesterday, all it showed were some advanced algorithms like A*. I was ready to take the pain and try one, but my friend reminded me that BFS actually works. And indeed, it worked. These three methods combine BFS and DFS, it will return all the shortest path from the user to the target, i.e., you can ask anyone you are more familiar with to introduce you. :)
The idea came from a LeetCode problem Word Ladder, take a look at my
blog if you are interested. Probably that problem is the origin of all of these: I wasn't familiar with BFS and DFS.
/*
* find the shortest path from the user to a random (-.-)person
* BFS is used
*/
private List> findConnections(Node target) {
//
Map> predecessor = new HashMap>();
//
Map distance = new HashMap();
List> connections = new ArrayList> ();
getConnections(target, predecessor, distance);
if (distance.size() == 1)
return connections;
getList(target, predecessor, distance, connections, new ArrayList());
return connections;
}
private void getConnections(Node target, Map> predecessor,
Map distance) {
Queue q = new LinkedList ();
predecessor.put(user, new ArrayList());
distance.put(user, 0);
q.offer(user);
boolean found = false;
//is it possible to terminate the recursion without knowing the graph size
//if no path is found?
while (distance.size() < GraphSize && predecessor.size() < GraphSize && !found) {
Node curr = q.poll();
if (curr.equals(target)) {
found = true;
continue;
}
for (Node neighbor : curr.neighbors) {
if (neighbor.equals(user))
continue;
if (!predecessor.containsKey(neighbor)) {
predecessor.put(neighbor, new ArrayList());
predecessor.get(neighbor).add(curr);
}
else {
if (!predecessor.get(neighbor).contains(curr))
predecessor.get(neighbor).add(curr);
}
if (!distance.containsKey(neighbor)) {
distance.put(neighbor, distance.get(curr) + 1);
}
q.add(neighbor);
}
}
}
private void getList(Node curr, Map> predecessor, Map distance,
List> connections, List path) {
path.add(curr);
if (curr.equals(user)) {
Collections.reverse(path);
connections.add(new ArrayList (path));
//Never ever forget this!
Collections.reverse(path);
}
else {
for (Node n : predecessor.get(curr)) {
if (distance.containsKey(n) && distance.get(curr) == distance.get(n) + 1) {
getList(n, predecessor, distance, connections, path);
}
}
}
path.remove(path.size() - 1);
}
public String connection(Node target) {
List> connections = findConnections(target);
String NEWLINE = System.getProperty("line.separator");
StringBuilder sb = new StringBuilder();
sb.append("You can be connected with " + target.label + " through: " + NEWLINE);
for (List path : connections) {
for (Node n : path) {
sb.append(n.label + " -> ");
}
sb.delete(sb.length() - 4, sb.length() - 1);
sb.append(NEWLINE);
}
return sb.toString();
}
Test
I drew this graph randomly for tests. Honestly, it took me a while to figure out what I was drawing.
Graph
Well, at least my code gives me the correct answer, worth the pain.
FindFriends
It took me a while to figure out that I forgot to reverse the reversed path list. -_-||| Eh, otherwise I should be sleeping right now.
Source code
All source code can be found on GitHub: https://github.com/shirleyyoung0812/Graph.git
import java.util.*;
//undirected graph
//user can only retrieve the node by its label
//all labels are unique
//if other data needs to be stored in the node, a map can be used
public class Graph {
private Map vertices;
//# of vertices
private int size;
//# of edges
private int edges;
public Graph (){
size = 0;
vertices = new HashMap();
edges = 0;
}
//construct a graph from another graph
public Graph (Graph G) {
this.size = G.size;
this.vertices = new HashMap();
this.edges = G.edges;
copyGraph(G);
}
//clone a graph from another one
/*
* ConcurrentModificationException:
* For example, it is not generally permissible
* for one thread to modify a Collection
* while another thread is iterating over it.
*/
private void copyGraph(Graph G) {
//clone nodes
for (Node n : G.vertices.values()) {
this.vertices.put(n.label, new Node(n));
}
//clone edges
for (Node n : G.vertices.values()) {
Node curr = getNode(n.label);
for (Node w : n.neighbors) {
Node neighbor = getNode(w.label);
if (!isConnected(curr, neighbor)) {
int weight = n.edges.get(w).getWeight(n, w);
Edge e = new Edge(curr, neighbor, weight);
curr.edges.put(neighbor, e);
neighbor.edges.put(curr, e);
}
}
}
}
//Add vertex
public void addVertex(int label) {
Node n = new Node(label);
vertices.put(label, n);
size++;
}
//Add edge
//The edge class will take care of adding neighbors to the neighbor list of the node
public void addEdge(int l1, int l2, int distance) {
Node v = getNode(l1);
Node w = getNode(l2);
if (v.neighbors.contains(w) && w.neighbors.contains(v)) {
System.out.println("Edge exists!");
return;
}
Edge e = new Edge(v, w, distance);
v.edges.put(w, e);
w.edges.put(v, e);
edges++;
}
//if a node exists
public boolean containsVertex(int label) {
return vertices.containsKey(label);
}
//if there exists an edge between two node
public boolean isConnected(int l1, int l2) {
return getNode(l1).edges.containsKey(getNode(l2))
&& getNode(l2).edges.containsKey(getNode(l1));
}
private boolean isConnected(Node n1, Node n2) {
return n1.edges.containsKey(n2) && n2.edges.containsKey(n1);
}
public Node getNode(int label) {
if (containsVertex(label))
return vertices.get(label);
return null;
}
/*public Iterable getNeighbors(int label) {
if(!containsVertex(label))
throw new IllegalArgumentException("Graph doesn't contain such node!");
return getNode(label).neighbors;
}*/
//get neighbors of a node
public String getNeighbors(int label) {
String neighbor = "";
for (Node n : getNode(label).neighbors) {
neighbor += n.label + ", ";
}
return neighbor.substring(0, neighbor.length() - 2);
}
public int neighborSize(int label) {
if (!containsVertex(label))
throw new IllegalArgumentException("Graph doesn't contain such node!");
return getNode(label).neighbors.size();
}
public String toString() {
StringBuilder s = new StringBuilder();
String NEWLINE = System.getProperty("line.separator");
s.append(size + " vertices, " + edges + " edges " + NEWLINE);
for (Node v : vertices.values()) {
s.append("Node: " + v.label + "\n");
for (Node w : v.neighbors) {
s.append(w.label + "; edge: " + v.edges.get(w).getWeight(v, w) + NEWLINE);
}
s.append(NEWLINE);
}
return s.toString();
}
}
import java.util.*;
public class Node {
int label;
List neighbors;
//
Map edges;
Node(int x) {
label = x;
neighbors = new ArrayList ();
edges = new HashMap ();
}
Node(Node n) {
//only copy the label from another node,
//neighbors and edges need
//to be redefined
this.label = n.label;
neighbors = new ArrayList();
edges = new HashMap ();
}
//the hash function to determine the equality of two nodes
//for graphs with unique nodes, this is not required
private int getHash() {
int hash_a = 378551;
int hash_b = 63689;
int hash = 0;
for (Node neighbor : neighbors) {
hash += hash * hash_a + neighbor.label;
hash_a = hash_a * hash_b;
}
//hash += label;
return hash;
}
public boolean equals(Node n) {
return label == n.label && (getHash() == n.getHash());
}
}
import java.util.*;
public class Edge {
int weight;
Node n1;
Node n2;
//default weight = 1
public Edge(Node n1, Node n2) {
if (n1.equals (n2))
throw new IllegalArgumentException("Cannot form an edge with itself!");
if (n1.neighbors.contains(n2))
throw new IllegalArgumentException("Edege exists!");
this.n1 = n1;
this.n2 = n2;
n1.neighbors.add(n2);
n2.neighbors.add(n1);
weight = 1;
}
//constructor that allows user defined weight
public Edge(Node n1, Node n2, int weight) {
if (n1.equals (n2))
throw new IllegalArgumentException("Dont't cheat, connecting with yourself doens't mean you have one more fan!");
if (n1.edges.containsKey(n2) && n2.edges.containsKey(n1))
throw new IllegalArgumentException("Edege exists!");
this.n1 = n1;
this.n2 = n2;
n1.neighbors.add(n2);
n2.neighbors.add(n1);
this.weight = weight;
}
//to modify the weight
public void modifyWeight(int w) {
if (w <= 0)
throw new IllegalArgumentException("Weight must be positive!");
weight = w;
}
//get the nodes that are connected by this edge
public List getNodes() {
List nodes = new ArrayList ();
nodes.add(n1);
nodes.add(n2);
return nodes;
}
//get the weight
public int getWeight(Node n1, Node n2) {
if (!(n1.equals(this.n1) && n2.equals(this.n2)) && !(n1.equals(this.n2) && n2.equals(this.n1)))
throw new IllegalArgumentException("Wrong input node!");
return weight;
}
}
import java.util.*;
/*
* This class is used for
* 1. find recommendations from friends of friends of the user
* 2. find the closest connections between the user and a person
*/
public class FindFriends {
Node user;
List potentialFriends;
//all friends of the user that connect with fof
Map> connectingFriends;
Map distanceFOF;
int numRecommendations;
int GraphSize;
/*
* this constructor will find the potential friends list for the user
* and generate the distance between the user and a potential friend (fof)
*/
public FindFriends(Node n, int numRecommendations, int GraphSize){
if (numRecommendations <= 0)
throw new IllegalArgumentException("At least one recommendation, please...");
user = n;
potentialFriends = new ArrayList ();
connectingFriends = new HashMap>();
distanceFOF = new HashMap ();
this.numRecommendations = numRecommendations;
this.GraphSize = GraphSize;
getPotentialFriends(n);
getDistance();
}
//find all fof from user's friends
private void getPotentialFriends(Node n) {
for (Node w : n.neighbors) {
for (Node fof : w.neighbors) {
if (!n.neighbors.contains(fof) && !fof.equals(user)) {
if (!potentialFriends.contains(fof))
potentialFriends.add(fof);
if (!connectingFriends.containsKey(fof)) {
connectingFriends.put(fof, new ArrayList());
connectingFriends.get(fof).add(w);
}
else
connectingFriends.get(fof).add(w);
}
}
}
}
/*
* distance is calculated by a formula from FB
* the weight of the edge is actually the number of days
* that two people are connected
*/
private void getDistance() {
for (Node fof : potentialFriends) {
double v = 0;
for (Node friend : connectingFriends.get(fof)) {
//distance between user and friend
double u_f = user.edges.get(friend).getWeight(user, friend);
//distance between friend and fof
double f_fof = friend.edges.get(fof).getWeight(friend, fof);
v += Math.pow(u_f * f_fof, -0.3) / Math.sqrt(friend.neighbors.size());
}
distanceFOF.put(fof, v);
}
}
/*
* find recommendations
* fofs with shortest distance will be recommended
*/
private PriorityQueue getRecommendations() {
NodeComparator nc = new NodeComparator() ;
PriorityQueue recommendedFriend = new PriorityQueue(numRecommendations, nc);
Collections.sort(potentialFriends, nc);
Node last = null;
for (Node fof : potentialFriends) {
//System.out.println(fof.label);
if (recommendedFriend.size() < numRecommendations) {
recommendedFriend.add(fof);
last = fof;
}
else {
if(nc.compare(fof, last) < 0) {
System.out.println(last.label);
recommendedFriend.remove(last);
recommendedFriend.add(fof);
last = fof;
}
}
}
return recommendedFriend;
}
public String recommendedFriend() {
PriorityQueue pq = getRecommendations();
StringBuilder sb = new StringBuilder();
sb.append("People you may know: \n");
for (Node n : pq) {
sb.append(n.label).append(", ");
}
return sb.delete(sb.length() - 2, sb.length() - 1).append("\n*****").toString();
}
private class NodeComparator implements Comparator {
public int compare(Node a, Node b) {
double da = distanceFOF.get(a);
double db = distanceFOF.get(b);
if (da - db < 0)
return -1;
else if (da - db > 0)
return 1;
return 0;
}
}
/*
* find the shortest path from the user to a random (-.-)person
* BFS is used
*/
private List> findConnections(Node target) {
//
Map> predecessor = new HashMap>();
//
Map distance = new HashMap();
List> connections = new ArrayList> ();
getConnections(target, predecessor, distance);
if (distance.size() == 1)
return connections;
getList(target, predecessor, distance, connections, new ArrayList());
return connections;
}
private void getConnections(Node target, Map> predecessor,
Map distance) {
Queue q = new LinkedList ();
predecessor.put(user, new ArrayList());
distance.put(user, 0);
q.offer(user);
boolean found = false;
//is it possible to terminate the recursion without knowing the graph size
//if no path is found?
while (distance.size() < GraphSize && predecessor.size() < GraphSize && !found) {
Node curr = q.poll();
if (curr.equals(target)) {
found = true;
continue;
}
for (Node neighbor : curr.neighbors) {
if (neighbor.equals(user))
continue;
if (!predecessor.containsKey(neighbor)) {
predecessor.put(neighbor, new ArrayList());
predecessor.get(neighbor).add(curr);
}
else {
if (!predecessor.get(neighbor).contains(curr))
predecessor.get(neighbor).add(curr);
}
if (!distance.containsKey(neighbor)) {
distance.put(neighbor, distance.get(curr) + 1);
}
q.add(neighbor);
}
}
}
private void getList(Node curr, Map> predecessor, Map distance,
List> connections, List path) {
path.add(curr);
if (curr.equals(user)) {
Collections.reverse(path);
connections.add(new ArrayList (path));
//Never ever forget this!
Collections.reverse(path);
}
else {
for (Node n : predecessor.get(curr)) {
if (distance.containsKey(n) && distance.get(curr) == distance.get(n) + 1) {
getList(n, predecessor, distance, connections, path);
}
}
}
path.remove(path.size() - 1);
}
public String connection(Node target) {
List> connections = findConnections(target);
String NEWLINE = System.getProperty("line.separator");
StringBuilder sb = new StringBuilder();
sb.append("You can be connected with " + target.label + " through: " + NEWLINE);
for (List path : connections) {
for (Node n : path) {
sb.append(n.label + " -> ");
}
sb.delete(sb.length() - 4, sb.length() - 1);
sb.append(NEWLINE);
}
return sb.toString();
}
}
