Geekly Articles each Day
📜 ⬆️ ⬇️

Bacon number and graphs

Bacon number


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

And now let's talk about how this game can be presented, and how you can calculate the Bacon number using the graph.

Graph


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

The algorithm that performs the search is called “ Search in width ” (Breadth-first search) and does the calculations we need for O (n + m) operations, where n is the number of vertices and m is the number of edges, that is, in linear time, which very good. To implement the algorithm, we need a regular queue (FIFO), where we will place all the vertices we meet.
And so the first step is to take the starting point and place it in the queue. Next we will have a cycle, the condition for exit from which will be a queue check for emptiness. In each iteration, we take the top from the queue, take all the descendants of this top, while marking the edge as investigated, and if the top is still not explored, then mark it as such and send it to the queue.
')
How it looks in our example:
- we mark top 0 as start and we place it in queue
Further, the loop is still not empty.
- we reach zero top, along edges (0,1) and (0,2) we take descendants, since these vertices are encountered for the first time, then we place them in the queue, noting them investigated and setting their HopLevel one more than the parent (in this case 1)
- the next vertex, when it is processed, vertices 3 and 4 will get into the queue, while the level for them will be equal to 2
- then vertex 2, in this case the descendant 4 will not be in the queue since he has already been investigated above, only 5 will be poisoned in a queue with a level equal to 2
- Vertex 3, which will send to the queue of the descendant 6 with level 3
- other peaks will be simply removed from the queue.
- on top of 6, the queue will become empty and the cycle will end

A small code on Go:

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 appeared in the Node structure, which we need for the queue.

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 can see the number of operations is 17 and each vertex is defined as far as it is from the starting one.

Notes:

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

Source: https://habr.com/ru/post/227867/

More articles:


All Articles