Bacon Number and Counts

Bacon number


A little history, Kevin Bacon, an American actor who played in many films, in 1994 noted that the actors with whom he starred worked with all Hollywood (and not only) actors. The public immediately reacted and created the game “to name the actor and associate him with Kevin Bacon.” The good corporation even built the game into its search engine, for example, the Bacon Number for actor John Travolta is 2 (John starred with Olivia Newton-John in the film Briolin, and she, in turn, played with Kevin Bacon in the film “She Will Have a Baby”) .

Now, let's talk about how this game can be represented, and how to calculate the Bacon number using a graph.

Graph


In this case, I will consider a directed unweighted graph, where the vertices are the actors, and the edges are the films (data can be taken from IMDb) in which they were shot, under the starting (zero) vertex will be Kevin Bacon. The number of Bacon in such a graph will be equal to the number of hops from the starting peak to the desired one or for all the others. For example, I chose such a graph:
image

An algorithm that produces search called " Search width " (Breadth-first search) and do we need calculation for O (n + m) operation, where n - the number of vertices and m - number of ribs, that is, in linear time, which is pretty good. To implement the algorithm, we need a regular queue (FIFO), where we will put all the vertices we meet.
And so the first step is to take the starting peak and place it in the queue. Next, we will have a cycle, the condition for exiting from which is to check the queue for void. In each iteration, we get a vertex from the queue, take all the descendants of this vertex, marking the edge as examined, and if the vertex is still not explored, then mark it with one and send it to the queue.

What this looks like in our example:
- mark the vertex 0 as the start one and put it in the queue.
Then the cycle until the queue is empty
- we get the zero vertex, from the edges (0,1) and (0,2) we take the descendants, because these vertices meet us for the first time, then we put them in the queue, marking them examined and setting them to HopLevel one more than the parent (in this case 1)
- the next vertex, when processing it, the vertices 3 and 4 will get into the queue, while the level for them will be set equal to 2
- then the vertex 2, in this case the descendant 4 will not get into the queue because it has already been investigated above, only 5 will be poisoned in a queue with a level equal to 2
- vertex 3, which will send a descendant of 6 with a level 3 to the queue
- the remaining vertices will simply be removed from the queue.
- on top 6, the queue is empty and the cycle ends

A little Go code:

The code
package main
import (
	"container/heap"
	"fmt"
)
type Node struct {
	HopLevel int
	Explored bool
	Edges    []int
	index    int //internal variable
}
type Graph []*Node
type Queue []*Node
func (q Queue) Len() int           { return len(q) }
func (q Queue) Less(i, j int) bool { return q[i].index < q[j].index }
func (q Queue) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }
func (q *Queue) Push(x interface{}) {
	*q = append(*q, x.(*Node))
}
func (q *Queue) Pop() interface{} {
	old := *q
	n := len(old)
	x := old[n-1]
	*q = old[0 : n-1]
	return x
}
var (
	operationsNumber int = 0
)
func main() {
	g := createGraph()
	bfs(*g, 0)
	for index, node := range *g {
		fmt.Printf(" node%d is on %d HopLevel \n", index, node.HopLevel)
	}
	fmt.Printf("Total number of operations is %d", operationsNumber)
}
func bfs(g Graph, startIndex int) {
	queue := &Queue{}
	heap.Init(queue)
	start := g[startIndex]
	start.index = 0
	start.HopLevel = 0
	start.Explored = true
	index := 1
	heap.Push(queue, start)
	for queue.Len() > 0 {
		node := heap.Pop(queue).(*Node)
		for _, childNodeIndex := range node.Edges {
			childNode := g[childNodeIndex]
			if !childNode.Explored {
				childNode.Explored = true
				childNode.HopLevel = node.HopLevel + 1
				childNode.index = index
				index++
				heap.Push(queue, childNode)
			}
			operationsNumber++
		}
		operationsNumber++
	}
}
func createGraph() *Graph {
	node0 := &Node{Edges: []int{1, 2}}
	node1 := &Node{Edges: []int{3, 4}}
	node2 := &Node{Edges: []int{1, 4, 5}}
	node3 := &Node{Edges: []int{6}}
	node4 := &Node{Edges: []int{6}}
	node5 := &Node{Edges: []int{6}}
	node6 := &Node{Edges: []int{}}
	return &Graph{node0, node1, node2, node3, node4, node5, node6}
}



In the implementation, I used the heap package, which allows us to create the queue we need by defining 5 methods. Also, the internal variable index, which we need for the queue, appeared in the Node structure.

Results:

 node0 is on 0 HopLevel 
 node1 is on 1 HopLevel 
 node2 is on 1 HopLevel 
 node3 is on 2 HopLevel 
 node4 is on 2 HopLevel 
 node5 is on 2 HopLevel 
 node6 is on 3 HopLevel 
Total number of operations is 17


The graph shown in the figure above consists of 7 vertices and 10 edges, and as we see the number of operations is 17 and each vertex is determined by the level of how far it is from the start.

Notes:

- Instead of the heap package, one could use a chanel and it would be more reasonable
- Since the graph is directed, I did not mark the edges as explored.
- The algorithm can be used for a specific vertex, then a check will also be added to the exit condition if the desired vertex is taken from the processing queue.
- Kevin Bacon is not the best actor for such a game, there are candidates much better, the maximum number of Bacon is 9.

Also popular now: