Six degrees of Kevin Bacon featuring Quickgraph

If you don't know what a Bacon Number is you can look it up here.

The basic idea is to calculate between how many movies there are between Kevin Bacon and another actor, the higher the number the further away. It is a very geeky calculation, in fact it so geeky that it is a part of google. Just google [actor name] bacon number and...

So how would you do this yourself?

First off we will need some data.

I used this to create a movie database. Basically you get an Actor table, a Dvd table and a Dvd_Actor table to link them.

Next we will just have to loop through all the records and create nodes(vertices) for each actor and movie in the database.

I used quickgraph and a sinple class to keep the nodes:

    public class MovieInformationNode
    {
        public int Id { get; set; }
        public NodeTypes NodeType { get; set; }
        public string Name { get; set; }
        public string PresentationName
        {
            get
            {

                if (NodeType == NodeTypes.Actor)
                    return "Actor: " + Name;
                else
                    return "Movie: " + Name;
            }
        }
    }

I declared the graph as:

private UndirectedGraph<MovieInformationNode, Edge<MovieInformationNode>> movieGraph                   = new UndirectedGraph<MovieInformationNode, Edge<MovieInformationNode>>();

For each Actor and Dvd I created a node and inserted it into the graph:

                MovieInformationNode node = new MovieInformationNode();
                node.NodeType = NodeTypes.Movie; //or actor if it is an actor, enum to keep track of type
                node.Id = dvd.Id;
                node.Name = dvd.DVD_Title.Trim();
                movieGraph.AddVertex(node);

For each link in Dvd_Actor I found the nodes in the graph and added an edge between them:

                //find actor

                MovieInformationNode actorNode = movieGraph.Vertices.Where(s => s.Id ==                                                               performance.Id && s.NodeType == NodeTypes.Actor).First();

                //find movie

                MovieInformationNode movieNode = movieGraph.Vertices.Where(s => s.Id ==                                                         performance.dvdid && s.NodeType == NodeTypes.Movie).First();

                Edge<MovieInformationNode> edge = new Edge<MovieInformationNode>(actorNode,                                                                               movieNode);

                movieGraph.AddEdge(edge);

Then you just need to get the shortest path:

            Func<Edge<MovieInformationNode>, double> edgeCost = (edge => 1.0D); //no weights

            var tryPath = movieGraph.ShortestPathsDijkstra(edgeCost, sourceNode);

            IEnumerable<Edge<MovieInformationNode>> path;

            if (tryPath(destinationNode, out path))

            {

                foreach (var item in path)

           {

                    listFrom.Items.Add(item.Source);

                    listFrom.Items.Add(item.Target);

           }

            }

To get this working you will need to get quickgraph here.