gistfile1.txt

/**
	 * checks whether two persons are connected in the social graph
	 * @param p1 person
	 * @param p2 person
	 * @return true if the two persons are connected
	 */
	public boolean areConnected(Person p1, Person p2) {
		if (p1 == null || p2 == null) {
			throw new IllegalArgumentException();
		}

		PersonProfile from = getProfile(p1);
		PersonProfile to = getProfile(p2);

		// returns false because the argument is not illegal
		// but at least one of the person is not part of
		// the kitbook
		if (from == null || to == null) {
			return false;
		}

		if (from.isBefriendedWith(to)) {
			return true;
		}
		boolean visited[] = new boolean[getSize()];
		visited[getProfileNumber(from)] = true;
		return areConnected(from, to, visited);

	}

	private boolean areConnected(PersonProfile from, PersonProfile to, boolean[] visited) {

		PersonProfile[] fromFriends = from.getFriends();

		for (int i = 0; i < fromFriends.length; i++) {
			if (visited[getProfileNumber(fromFriends[i])]) {
				continue;
			}
			if (fromFriends[i].isBefriendedWith(to)) {
				return true;
			} else {
				visited[getProfileNumber(fromFriends[i])] = true;
				return areConnected(fromFriends[i], to, visited);
			}
		}

		return false;
	}

	private int[][] calculateDistanceMatrix() {

		Person[] persons = getPersons();


		int[][] adjacentMatrix = new int[persons.length][persons.length];

		for (int i = 0; i < persons.length; i++) {
			for (int k = 0; k < persons.length; k++) {
				adjacentMatrix[i][k] = areFriends(persons[i], persons[k]) ? 1 : 0;
			}
		}

		int[][] tmpMatrix = MathUtil.copyMatrix(adjacentMatrix);
		int[][] distMatrix = MathUtil.copyMatrix(adjacentMatrix);

		for (int i = 0; i < persons.length; i++) {
			tmpMatrix = MathUtil.multiplyMatrices(tmpMatrix, adjacentMatrix);
			for (int k = 0; k < persons.length; k++) {
				for (int j = 0; j < persons.length; j++) {
					if (distMatrix[k][j] == 0 && tmpMatrix[k][j] != 0) {
						distMatrix[k][j] = i + 2;
					}
				}
			}
		}

		// add Integer.MAX_VALUE

		for (int i = 0; i < persons.length; i++) {
			for (int k = 0; k < persons.length; k++) {
				if (distMatrix[i][k] == 0) {
					distMatrix[i][k] = Integer.MAX_VALUE;
				}
			}
		}

		return distMatrix;

	}

	/**
	 * calculates the distance between two persons in the graph
	 * @param p1 person
	 * @param p2 person
	 * @return distance between the two persons in the graph
	 */
	public int calculateDistance(Person p1, Person p2) {

		if (p1 == null || p2 == null) {
			throw new IllegalArgumentException();
		}

		int index1 = getProfileNumber(getProfile(p1));
		int index2 = getProfileNumber(getProfile(p2));
		
		if(index1 == -1 || index2 == -1) {
			throw new IllegalArgumentException();
		}

		int[][] distanceMatrix = calculateDistanceMatrix();

		return distanceMatrix[index1][index2];

	}

	/**
	 * calculates the shortest path between two persons in the social graph
	 * @param p1 person
	 * @param p2 person
	 * @return shortest path between two persons
	 */
	public Person[] shortestPath(Person p1, Person p2) {

		if (p1 == null || p2 == null) {
			throw new IllegalArgumentException();
		}

		int[][] matrix = calculateDistanceMatrix();
		//System.out.println(MathUtil.matrixToString(matrix));
		Person[] persons = getPersons();
		int startIndex = getProfileNumber(getProfile(p1));
		int targetIndex = getProfileNumber(getProfile(p2));
		int length = matrix[startIndex][targetIndex];

		if (length == Integer.MAX_VALUE) {
			return null;
		}

		if (areFriends(p1, p2)) {
			Person[] path = {p1, p2};
			return path;
		}

		int currentLength = length - 1;
		Person[] path = new Person[length + 1];

		// we already know the start and end of the path
		path[0] = p1;
		path[length] = p2;

		int cur = startIndex; // current base-node: p1
		// build path
		for (int j = 1; j < path.length; j++) {
			for (int i = 0; i < matrix[cur].length; i++) {
				if (matrix[cur][i] == 1) {
					for (int k = 0; k < matrix[i].length; k++) {
						// if distance between current base-node
						// and current node equals our current path-length
						// add it to the path
						if (matrix[i][targetIndex] == currentLength) {
							path[j] = persons[i];
							currentLength--;
							// sets new base-node
							cur = i;
						}
					}
				}
			}
		}

		return path;

	}