edu.princeton.cs.algorithms

Class DegreesOfSeparation

java.lang.Object

edu.princeton.cs.algorithms.DegreesOfSeparation

public class DegreesOfSeparation
extends Object

The DegreesOfSeparation class provides a client for finding the degree of separation between one distinguished individual and every other individual in a social network. As an example, if the social network consists of actors in which two actors are connected by a link if they appeared in the same movie, and Kevin Bacon is the distinguished individual, then the client computes the Kevin Bacon number of every actor in the network.

The running time is proportional to the number of individuals and connections in the network. If the connections are given implicitly, as in the movie network example (where every two actors are connected if they appear in the same movie), the efficiency of the algorithm is improved by allowing both movie and actor vertices and connecting each movie to all of the actors that appear in that movie.

For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Method Summary

Modifier and Type	Method and Description
static void	main(String[] args) Reads in a social network from a file, and then repeatedly reads in individuals from standard input and prints out their degrees of separation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

main

public static void main(String[] args)

Reads in a social network from a file, and then repeatedly reads in individuals from standard input and prints out their degrees of separation. Takes three command-line arguments: the name of a file, a delimiter, and the name of the distinguished individual. Each line in the file contains the name of a vertex, followed by a list of the names of the vertices adjacent to that vertex, separated by the delimiter.