Graph again (Python and Java, adjacency matrix representation)

I decided to start reviewing data structures and algorithms again, and the first thing I chose is my favorite graph.

There are quite a few ways to represent a graph, the most common two are adjacency matrix and adjacency list. In this post, I use adjacency matrix representation. 

Graph and Adjacency Matrix Representation

A graph (see here for formal definition) contains vertices and edges. Edges are used to connect vertices. Directed graphs have directions (of course!), e.g., edge(a, b) != edge (b, a). Undirected graphs, on the contrary, have no directions, e.g., edge(a, b) = edge(b, a). 

So the question is, how to represent graph in program?

Adjacency matrix representation refers to using a matrix of size (number of vertices * number of vertices) to represent the connectivity, i.e., edges. 

Consider the following graph:

The adjacency matrix representation is as follows:

Each row and column represents a vertex, the cell represents the weight of the edge between them. If there is no edge between two vertices, the weight is 0. In this example, all weights are set to 1, it is possible to personalize the weight, e.g., weight(1, 3) = 2, weight(2, 4) = 0.5. 

Since the graph is undirected, if there is an edge between v1 and  v2, then there is an edge between v2 and v1, so the matrix is symmetric. In case of a directed graph, an edge direct from 1 to 3 leads to a value in matrix[1][3], but that does not indicates there is a value in matrix[3][1], unless there is an edge that directs 3 to 1. 

Traverse the graph

There are two ways to traverse a graph, depth-first search (DFS) and breadth-first search (BFS). DFS goes as deep (yeah...) as it can until all the vertices rooted from one vertex are visited then visit a neighbor vertex. BFS goes as broad as it can until all the neighbors of a given vertex are visited then go to the next level. The following two graphs illustrate the path of DFS and BFS if we start by traversing vertex 3. 

Java code

public class Graph {
 protected int adjacencyMatrix[][];
 protected int size; //number of vertices
 
 public Graph(int size) {
  this.size = size;
  adjacencyMatrix = new int[size][size];
 }
 
 public void addEdge(int v1, int v2) {
  if (validity(v1) == false || validity(v2) == false)
   return;
  if (v1 == v2){
   System.out.printf("Same vertex %d and %d\n", v1, v2);
   return;
  }
  adjacencyMatrix[v1][v2] += 1;
  adjacencyMatrix[v2][v1] += 1;
 }
 
 public void removeEdge(int v1, int v2){
  if (validity(v1) == false || validity(v2) == false)
   return;
  if (adjacencyMatrix[v1][v2] == 0){
   System.out.printf("No edge between %d and %d\n", v1, v2);
  }
  adjacencyMatrix[v1][v2] -= 1;
  adjacencyMatrix[v2][v1] -= 1;
 }
 
 public boolean containsEdge(int v1, int v2){
  if (validity(v1) == false || validity(v2) == false)
   return false;
  return adjacencyMatrix[v1][v2] > 0 ? true : false;
 }
 
 public int getSize(){
  return size;
 }
 
 protected boolean validity(int v){
  if (v >= size || v < 0) {
   System.out.printf("Invalid vertex index %d\n", v);
   return false;
  }
  else
   return true; 
 }
 public void dfs(int startVertex){
  boolean[] visited= new boolean[this.size];
  List<integer> path = new ArrayList<integer> ();
  dfs(path, startVertex, visited);
  System.out.println(getPath(path));
 }
 private void dfs(List<integer> pathList, int v, boolean[] visited){
  if (pathList.size() == this.size)
   return;
  if (!validity(v)|| visited[v]) 
   return;
  visited[v] = true;
  pathList.add(v);
  for (int i = 0; i < this.size; i++){
   if (containsEdge(v, i)){
    dfs(pathList, i, visited);
   }
  }
 }
 public void bfs(int v){
  if (!validity(v)) 
   return;
  boolean[] visited = new boolean[this.size];
  List<integer> path = new ArrayList<integer> (this.size);
  Queue<integer> neighbors = new LinkedList<integer> ();
  neighbors.offer(v);
  while(!neighbors.isEmpty() && (path.size() < this.size)){
   int vertex = neighbors.poll();
   path.add(vertex);
   visited[vertex] = true;
   for (int i = 0; i < this.size; i++){
    if(containsEdge(vertex, i) && !visited[i]) {
     neighbors.offer(i);
    }
   }
  }
  System.out.println(getPath(path));
 }
 public String getPath(List<integer> path){
  String p = "";
  for (int v : path)
   p += String.format("%d -> ", v);
  return p.substring(0, p.length() - 3);
 }
}

Python code:
The easiest way to write a graph using Python is:
To use the SparseGraph class provided by APGL library.

from apgl.graph import SparseGraph
import time
def main():
    graph = SparseGraph(5)
    graph.addEdge(0, 3)
    graph.addEdge(1, 4)
    graph.addEdge(2, 3)
    graph.addEdge(2, 4)
    graph.addEdge(1, 3)

    print(graph.depthFirstSearch(3))
    print(graph.breadthFirstSearch(3))

if __name__ == '__main__':
    start_time = time.time()
    main()
    print("Running time: %f microseconds" % ((time.time() - start_time)*1000))

Where is the fun of writing code?!

Using the same structure as I do in Java:

from collections import deque

class Graph(object):
    def __init__(self, size):
        self.adjacencyMatrix = []
        for i in range(size):
            self.adjacencyMatrix.append([0 for i in range(size)])
        self.size = size

    def addEdge(self, v1, v2):
        if not self.validity(v1) and not self.validity(v2):
            return
        if v1 == v2:
            print("Same vertex %d and %d" % (v1, v2))
        self.adjacencyMatrix[v1][v2] += 1
        self.adjacencyMatrix[v2][v1] += 1

    def removeEdge(self, v1, v2):
        if not self.validity(v1) and not self.validity(v2):
            return
        if self.adjacencyMatrix[v1][v2] == 0:
            print("No edge between %d and %d" % (v1, v2))
            return
        self.adjacencyMatrix[v1][v2] -= 1
        self.adjacencyMatrix[v2][v1] -= 1

    def containsEdge(self, v1, v2):
        if not self.validity(v1) and not self.validity(v2):
            return False
        return True if self.adjacencyMatrix[v1][v2] > 0 else False

    def __len__(self):
        return self.size

    def validity(self, v):
        if v >= self.size or v < 0:
            print("Invalid vertex index %d" % v)
            return False
        else:
            return True

    def dfs(self, startVertex):
        if not self.validity(startVertex):
            return;
        visited = []
        for i in range(self.size):
            visited.append(False)
        path = []
        self._dfsR(path, startVertex, visited)
        print(self.getPath(path))

    def _dfsR(self, path, v, visited):
        if(len(path) == self.size):
            return;
        if visited[v]:
            return;
        visited[v] = True;
        path.append(v);
        for i in range(self.size):
            if self.containsEdge(v, i):
                self._dfsR(path, i, visited)

    def bfs(self, v):
        if v >= self.size or v < 0:
            return
        visited = []
        for i in range(self.size):
            visited.append(False)
        path = []
        neighbors = deque()
        neighbors.append(v)
        while neighbors and len(path) < self.size:
            vertex = neighbors.popleft()
            path.append(vertex)
            visited[vertex] = True
            for i in range(self.size):
                if self.containsEdge(vertex, i) and not visited[i]:
                    neighbors.append(i)
        print(self.getPath(path))

    def getPath(self, path):
        p = ""
        for v in path:
            p += "%d -> " % v
        return p[:len(p) - 3]

Performance
This is always my favorite part. Using the following pieces of test code for Java and Python:

public class GraphTester {
 public static void main(String[] args) {
  final long startTime = System.nanoTime();
  Graph g = new Graph(5);
  g.addEdge(0, 3);
  g.addEdge(1, 4);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(1, 3);
  //g.addEdge(1, 5);
  
  g.dfs(3);
  g.bfs(3);
  System.out.println("Running time: " + ((System.nanoTime() - startTime)/1000) + "ms");
 }
}

from graph.Graph import Graph
import time
def main():
    g = Graph(5)
    g.addEdge(0, 3)
    g.addEdge(1, 4)
    g.addEdge(2, 3)
    g.addEdge(2, 4)
    g.addEdge(1, 3)

    g.dfs(3)
    g.bfs(3)

if __name__ == '__main__':
    start_time = time.time()
    main()
    print("Running time: %f microseconds" % ((time.time() - start_time)*1000))

And the result:
Python 0.157 ms vs. Java 4495 ms.
And guess what, using SparseGraph class takes 0.118 ms (feeling good ).

Check if a graph contains a cycle

This post is also derived from my last night's post "Construct tree with minimum weight from an acyclic undirected unweighted graph", because in order for that algorithm to work, the assumption is that the graph must be a tree or forest. So I write a simple method to check the assumption.

The algorithm is based on the Union/Find AST. This is my third version of it, since I want to create a generic class.

The UnionFind class:

import java.util.*;
public class UnionFind {
 Map elements;
 int count;
 public UnionFind(){
  elements = new HashMap ();
 }
 public UnionFind(int size){
  elements = new HashMap (size);
 }
 public void add(T e){
  elements.put(e, new Element(e, e, 1));
  count++;
 }
 public void add(Collection collection){
  for(T e : collection)
   add(e);
 }
 public T find(T e){
  Element curr = elements.get(e);
  Element root = elements.get(curr.root);
  if(curr.root != root.root){
   curr.root = find(root.root);
  }
  return curr.root;
 }
 public boolean union(T e1, T e2){
  if(count <= 1)
   return false;
  Element c1 = elements.get(e1);
  Element c2 = elements.get(e2);
  c1.root = find(e1);
  c2.root = find(e2);
  if(c1.root == c2.root)
   return false;
  if(c1.rank < c2.rank)
   c1.root = c2.element;
  else if(c1.rank > c2.rank)
   c2.root = c1.element;
  else{
   c2.root = c1.element;
   c1.rank++;
  }
  count--;
  return true;
 }
 private class Element{
  T element;
  T root;
  int rank;
  public Element(T element, T root, int rank){
   this.element = element;
   this.root = root;
   this.rank = rank;
  }
 }
}

The actual method to check if a cycle exists is quite straightforward: union all connecting vertices, if they have already been in one union, then there is a cycle.

private boolean isForest(){
  UnionFind uf = new UnionFind ();
  uf.add(forest.vertices.values());
  for(UndirectedGraphNode n : forest.vertices.values()){
   for(UndirectedGraphNode nei : n.neighbors){
    if(!uf.union(nei, n))
     return false;
   }
  }
  return true;
 }

Diameter of a graph

So after last night's two posts, I decide to practice and write a code to calculate the diameter of a graph.

The graph is an undirected weighted graph (my same old Graph class), so the way I do it is use Dijkstra to calculate and get the maximum shortest distance from one node to all other nodes, and update the max shortest distance each time. The maximum shortest distance among all is the diameter.

public class Diameter {
 private Graph g;
 public Diameter(Graph g){
  this.g = g;
 }
 public double maxShortestDistance(Node n){
  g.chooseSource(n);
  PriorityQueue pq = new PriorityQueue(new NodeComparator());
  //Set visited = new HashSet ();
  pq.offer(n);
  double maxDist = 0.0;
  while(!pq.isEmpty()){
   Node curr = pq.poll();
   for(Node nei : g.neighbors.get(curr)){
    double distance = g.getEdge(curr.label, nei.label).weight + curr.dist;
    if(distance < nei.dist){
     pq.remove(nei);
     nei.dist = distance;
     pq.offer(nei);
     maxDist = Math.max(maxDist, distance);
    }
   }
  }
  return maxDist;
 }
 public double diameter(){
  double diameter = 0.0;
  for(Node v : g.vertices.values()){
   diameter = Math.max(diameter, maxShortestDistance(v));
  }
  return diameter;
 }
 private class NodeComparator implements Comparator{
  
  public int compare(Node a, Node b){
   if(a.dist - b.dist > 0)
    return 1;
   else if (a.dist - b.dist < 0)
    return -1;
   return 0;
  }
 }
}

Construct tree with minimum weight from an acyclic undirected unweighted graph

Given an acyclic undirected unweighted connected graph, find its representation as a tree with the least height. Brute force is O(n^2). Come up with an O(n) solution

Well, the problem is the same as saying given a tree, find it's root. An acyclic graph, unfortunately, is a tree. The problem is, we don't know where is the root. So the way we do it is to find the diameter of the graph. The diameter of the graph is defined as:

The diameter  of a graph is the maximum eccentricity of any vertex in the graph. That is,  it is the greatest distance between any pair of vertices or, alternatively, . To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

To do it in O(n), we first randomly select a node from the graph. find the farthest node it can reach, call it farthest1. Then find the farthest node farthest1 can reach, call it farthest2. The diameter of the graph is the distance between farthest1 and farthest2. The reason it works is that the given graph is a tree, so the two farthest nodes will only have one neighbor. If not, the we can go farther down find the next farthest node.

So how to find the root? Given the two farthest nodes, the root must be in between. so from one node to the other, find the middle one. The way I do it is a brutal force one, traverse both nodes to the equal distance, then find the common node. So the question is, is it possible that there exists a second common node on the path? The answer is definitely no, since the given graph is a tree.

public class ConstructTree {
 UndirectedGraph forest;
 int diameter;
 public ConstructTree(UndirectedGraph g){
  forest = g;
  //System.out.println("Tree built");
 }
 private UndirectedGraphNode getFarthest(UndirectedGraphNode n){
  Queue q = new LinkedList();
  q.add(n);
  Map distance = new HashMap ();
  distance.put(n, 0);
  //Set visited = new HashSet ();
  int maxDist = 0;
  //int currDist = 0;
  UndirectedGraphNode farthest = null;
  while(!q.isEmpty()){
   UndirectedGraphNode curr = q.poll();
   int d = distance.get(curr);
   for(UndirectedGraphNode neighbor : curr.neighbors){
    if(!distance.containsKey(neighbor)){
     distance.put(neighbor, d + 1);
     q.offer(neighbor);
    }
   }
  }
  for(Entry e : distance.entrySet()){
   if(e.getValue() > maxDist){
    maxDist = e.getValue();
    farthest = e.getKey();
   }
  }
  diameter = maxDist;
  return farthest;
 }
 private UndirectedGraphNode getRoot(UndirectedGraphNode n1, UndirectedGraphNode n2){
  int d1, d2;
  if(diameter % 2 == 0)
   d1 = d2 = diameter / 2;
  else{
   d1 = diameter / 2;
   d2 = diameter - d1;
  }
  Queue q1 = new LinkedList();
  q1.add(n1);
  Queue q2 = new LinkedList();
  q2.add(n2);
  UndirectedGraphNode toReturn = null;
  while(!q1.isEmpty() && d1 > 0){
   UndirectedGraphNode curr = q1.poll();
   for(UndirectedGraphNode nei : curr.neighbors)
    q1.offer(nei);
   d1--;
  }
  while(!q2.isEmpty() && d2 > 0){
   UndirectedGraphNode  curr = q2.poll();
   for(UndirectedGraphNode nei : curr.neighbors)
    q2.offer(nei);
   d2--;
  }
  for(UndirectedGraphNode node1 : q1){
   for(UndirectedGraphNode node2 : q2){
    if (node1 == node2){
     toReturn = node1;
     break;
    }
   }
  }
  return toReturn;
 }
 
 public UndirectedGraphNode construct(){
  UndirectedGraphNode random = forest.vertices.entrySet().iterator().next().getValue();
  UndirectedGraphNode farthest = getFarthest(random);
  UndirectedGraphNode farthest2 = getFarthest(farthest);
  return getRoot(farthest, farthest2);
 }
}

Dijkstra Algorithm

The Dijkstra Algorithm finds the shortest path from a source to all destination in a directed graph, i.e., single source shortest path problem. During the process, it will also determine a spanning tree for the graph.

Dijkstra partitions all nodes into two distinct sets. Unsettled and settled. Initially all nodes are in the unsettled sets, e.g., they must be still evaluated. A node is move to the settled set if a shortest path from the source to this node has been found.
Initially the distance of each node to the source is set to a very high value, e.g., Integer.MAX_VALUE.

The algorithms runs until the unsettledNodes are empty. In each iteration it selects the node with the lowest distance from the source out the unsettled nodes.

I used my previous Graph class. However, I added a new method chooseSource(int label) to select a node in the graph as the source node. In the node class, I added one more variable, initially assigned to Integer.MAX_VALUE, if a source node is chosen, the distance of the source is set to 0. Then when we construct the Dijkstra class, all shortest paths to the source node can be acquired.

public void chooseSource(int label) {
  Node source = getNode(label);
  source.dist = 0;
  
 }

The Dijkstra class:

import java.util.*;
public class Dijkstra {
 private Graph g;
 private int[] distTo;
 Node source;
 private int[] predecessor;
 private PriorityQueue pq;
 
 public Dijkstra(Graph G, int s) {
  this.g = G;
  g.chooseSource(s);
  pq = new PriorityQueue (new NodeComparator());
  source = g.getNode(s);
  pq.add(source);
  distTo = new int[g.getSize()];
  distTo[s - 1] = 0; 
  predecessor = new int[g.getSize() + 1];
  predecessor[s] = -1;
 }
 public void getShortestPath() {
  while (!pq.isEmpty()) {
   Node curr = pq.poll();
   for (Node w : curr.neighbors) {
    int distanceToSource = curr.dist + curr.edges.get(w).getWeight(curr, w);
    if (distanceToSource < w.dist) {
     pq.remove(w);
     w.dist = distanceToSource;
     predecessor[w.label] = curr.label;
     pq.add(w);
    }
   }
  }
 }
 /**
  * get the shortest path from source to target node
  * @param n
  */
 public void getShortestPath(int target) {
  boolean found = false;
  while (!pq.isEmpty() && !found) {
   Node curr = pq.poll();
   for (Node w : curr.neighbors) {
    int distanceToSource = curr.dist + curr.edges.get(w).getWeight(curr, w);
    if (distanceToSource < w.dist) {
     pq.remove(w);
     w.dist = distanceToSource;
     predecessor[w.label] = curr.label;
     pq.add(w);
    }
    if (w.label == target) {
     found = true;
     break;
    }
   }
  }
  
 }
 public String shortestPath(int label) {
  Node target = g.getNode(label);
  String NEWLINE = System.getProperty("line.separator");
  StringBuilder sb = new StringBuilder();
  sb.append("The shortest distance from " + label + " to source " + source.label 
    + " is: " + target.dist);
  sb.append(NEWLINE);
  int x;
  for (x = label; g.getNode(x).dist != 0; x = predecessor[x]) {
   sb.append(x + " -> ");
  }
  sb.append(source.label);
  //sb.delete(sb.length() - 4, sb.length() - 1);
  sb.append(NEWLINE);
  return sb.toString();
 }
 private class NodeComparator implements Comparator {
  
  public int compare(Node a, Node b) {
   if (a.dist - b.dist < 0)
    return -1;
   else if (a.dist - b.dist > 0)
    return 1;
   return 0;
  }
 }
}

The amazing maze II: searching the maze

This post I will talk about how to solve a maze. If you are interested in how to build a maze. Take a look at my last post.

There are couple ways to solve a maze, the easiest ones are using DFS and BFS. Here, I implemented DFS using recursion, DFS using a stack, and BFS.

package mazeDFS;
import java.util.*;
public class SolveMaze {
 
 List path;
 private Maze m;
 
 public SolveMaze(Maze m) {
  path = new ArrayList ();
  this.m = m;
 }
 /**
  * Using DFS to solve the maze
  */
 public void solveByDFS() {
  boolean[] visited = new boolean[m.grid.length];
  //Stack stack = new Stack ();
  dfs(path, visited, 0);
 }
 //using recursion
 private void dfs(List path, boolean[] visited, int curr) {
  if (curr == m.grid.length - 1) {
   visited[curr] = true; 
   path.add(curr);
   return;
  }
  path.add(curr);
  visited[curr] = true;
  int cell = m.grid[curr];
  if ((cell & Maze.LEFT) == 0 && (curr - 1) >= 0 && !visited[curr - 1] && !visited[m.grid.length - 1] && !visited[m.grid.length - 1])
   dfs(path, visited, curr - 1);
  if ((cell & Maze.RIGHT) == 0 && (curr + 1) < m.grid.length && !visited[curr + 1] && !visited[m.grid.length - 1])
   dfs(path, visited, curr + 1);
  if ((cell & Maze.UP) == 0 && (curr - m.columns) >= 0 && !visited[curr - m.columns] && !visited[m.grid.length - 1])
   dfs(path,visited, curr - m.columns);
  if ((cell & Maze.DOWN) == 0 && (curr + m.columns) < m.grid.length && !visited[curr + m.columns] && !visited[m.grid.length - 1])
   dfs(path, visited, curr + m.columns);
  if (visited[m.grid.length - 1])
   return;
  path.remove(path.size() - 1);
 }
 //using a stack
 public void solveByDFS2() {
  Stack stack = new Stack ();
  boolean[] visited = new boolean[m.grid.length];
  int[] distTo = new int[m.grid.length];
  int[] predecessor = new int[m.grid.length];
  Arrays.fill(distTo, Integer.MAX_VALUE);
  stack.push(0);
  visited[0] = true;
  distTo[0] = 0;
  predecessor[0] = -1;
  while (!stack.isEmpty() && !visited[m.grid.length - 1]) {
   int curr = stack.pop();
   int cell = m.grid[curr];
   if (curr == m.grid.length - 1) {
    break;
   }
   if ((cell & Maze.LEFT) == 0 && (curr - 1) >= 0 && !visited[curr - 1]) {
    stack.push(curr - 1);
    visited[curr - 1] = true;
    distTo[curr - 1] = distTo[curr] + 1;
    predecessor[curr - 1] = curr;
   }
   if ((cell & Maze.RIGHT) == 0 && (curr + 1) < m.grid.length && !visited[curr + 1]) {
    stack.push(curr + 1);
    visited[curr + 1] = true;
    distTo[curr + 1] = distTo[curr] + 1;
    predecessor[curr + 1] = curr;
   }
   if ((cell & Maze.UP) == 0 && (curr - m.columns) >= 0 && !visited[curr - m.columns]) {
    stack.push(curr - m.columns);
    visited[curr - m.columns] = true;
    distTo[curr - m.columns] = distTo[curr] + 1;
    predecessor[curr - m.columns] = curr;
   }
   if ((cell & Maze.DOWN) == 0 && (curr + m.columns) < m.grid.length && !visited[curr + m.columns]) {
    stack.push(curr + m.columns);
    visited[curr + m.columns] = true;
    distTo[curr + m.columns] = distTo[curr] + 1;
    predecessor[curr + m.columns] = curr;
   }
  }
  int x;
  for (x = m.grid.length - 1; distTo[x] != 0; x = predecessor[x]) {
   path.add(x);
  }
  path.add(0);
  Collections.reverse(path);
  
 }
 
 public void solveByBFS() {
  Queue q = new LinkedList ();
  boolean[] visited = new boolean[m.grid.length];
  int[] distTo = new int[m.grid.length];
  int[] predecessor = new int[m.grid.length];
  Arrays.fill(distTo, Integer.MAX_VALUE);
  q.offer(0);
  visited[0] = true;
  distTo[0] = 0;
  predecessor[0] = -1;
  while (!q.isEmpty() && !visited[m.grid.length - 1]) {
   int curr = q.poll();
   int cell = m.grid[curr];
   if (curr == m.grid.length - 1) {
    break;
   }
   if ((cell & Maze.LEFT) == 0 && (curr - 1) >= 0 && !visited[curr - 1]) {
    q.offer(curr - 1);
    visited[curr - 1] = true;
    distTo[curr - 1] = distTo[curr] + 1;
    predecessor[curr - 1] = curr;
   }
   if ((cell & Maze.RIGHT) == 0 && (curr + 1) < m.grid.length && !visited[curr + 1]) {
    q.offer(curr + 1);
    visited[curr + 1] = true;
    distTo[curr + 1] = distTo[curr] + 1;
    predecessor[curr + 1] = curr;
   }
   if ((cell & Maze.UP) == 0 && (curr - m.columns) >= 0 && !visited[curr - m.columns]) {
    q.offer(curr - m.columns);
    visited[curr - m.columns] = true;
    distTo[curr - m.columns] = distTo[curr] + 1;
    predecessor[curr - m.columns] = curr;
   }
   if ((cell & Maze.DOWN) == 0 && (curr + m.columns) < m.grid.length && !visited[curr + m.columns]) {
    q.offer(curr + m.columns);
    visited[curr + m.columns] = true;
    distTo[curr + m.columns] = distTo[curr] + 1;
    predecessor[curr + m.columns] = curr;
   }
  }
  int x;
  for (x = m.grid.length - 1; distTo[x] != 0; x = predecessor[x]) {
   path.add(x);
  }
  path.add(0);
  Collections.reverse(path); 
 }
}

Performance

Average memory usage on a 50 by 50 maze

Average running time on a 50 by 50 maze

As we can see, DFS by recursion outperforms the other two methods in both time and memory. It is understandable that BFS is slower in this circumstance. If we search layer by layer, we probably need to traverse the whole maze to find the end point. Yet if we use DFS, any path leads to the end point can terminate the searching. 

Recursive solutions often result in smaller code, which means it's more likely that the code will fit into the CPU cache. A no-recursive solution that requires an explicitly managed stack can result in larger code, more cache misses, and slower performance than recursive solution. 

Graph traversal and a simple recommender system

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();
 }
 
}