# [競程] 艾狄胥數 (Erdős Numbers)

###### tags: `競程`

* Online Judge: [10044](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=985)


**艾狄胥數**（簡稱**艾數**）（Erdős number），根據現代匈牙利數學家艾狄胥·帕爾，這個最多產的數學家命名，是描述論文中一個作者與艾狄胥的「合作距離」的一種方式。被視為數學界諾貝爾獎的菲爾茨獎，其獲得者的艾數中位數最低時為 $3$。

定義艾狄胥本人的艾數是 $0$，與其合寫過論文的人的艾數是 $1$，一個人至少要 $k$ 個中間人（合寫論文的關係）才能與艾狄胥有關聯，則他的艾數是 $k+1$。


一些著名科學家的艾數如下：
* Albert Einstein: 2
* Erwin Schrödinger: 3
* Richard Feynman: 3
* Claude Elwood Shannon: 3
* John von Neumann: 3
* Peter Shor: 2

在學術圈以外，也有其他類似的數：
* 貝肯數：以演員凱文·貝肯為中心，以是否一起演出描述與凱文·貝肯的距離，也因此產生著名的遊戲：六度空間（Six Degrees of Kevin Bacon）。
* 秀策數：圍棋中用來描述玩家和棋聖本因坊秀策之間的距離。
* Stringfield數：描述幽浮學的研究者與第一位幽浮學家Leonard H. Stringfield之間的距離。

**六度分隔理論** (Six Degrees of Separation) 認為，世界上任何互不相識的兩人，只需要很少的中間人就能夠建立起聯繫。哈佛大學心理學教授Stanley Milgram於1967年根據這個概念做過一次連鎖信實驗，嘗試證明平均只需要6步就可以聯繫任何兩個互不相識的人。也就是說，今天如果小明發明了一個「小明數」，小明的朋友都擁有「小明數 = 1」，小明朋友的朋友擁有「小明數 = 2」，以此類推，則世界上的所有人的小明數，根據六度分隔理論，最多就是6。

雖然六度分隔理論目前仍沒辦法很嚴謹的用數學證明出來，但是它在實務上運作得很好，特別是在保險及直銷等領域。甚至基於一項Facebook在2016年的研究，由於社群網路的發展，每個人與其他人間隔僅有4.57人。

## 題目
講了這麼多艾數的背景，現在我們要來實際計算這個數了。給定一系列的文章的作者名單，基於這些發表，要計算出這些名單出現的所有人（艾迪胥本人除外）的艾數。

## 範例
原始的題目的輸入資料是一個文件，裡面包含了所有文章的資料，包含作者名單與標題，需要進行一些字串處理才能計算。為了簡化題目，專注在演算法上，我們在這邊把作者名單抓出來成為一個姓名的list，一篇文章用一個作者的list代表，則全部的輸入資料就是一個list of list:

[
    ["Smith, M.N.", "Martin, G.", "Erdos, P."],
    ["Erdos, P.", "Reisig, W."],
    ["Smith, M.N.", "Chen, X".],
    ["Jablonski, T.", "Hsueh, Z."]
]

## 思路
這題直覺就是要用graph去做：把人際網路建構出來，再計算各節點對於艾狄胥本人的距離。所以整個思路可以分為兩個步驟：
1. 使用鄰接表 (adjacency list) 建構人際網路的graph
2. 透過廣度優先搜尋 (BFS) 計算各節點對於艾狄胥的距離

## 解答
### 建構人際網路
在這裡我們採取python的dictionary來建構鄰接表。這邊我們選用`collection`模組的`defaultdict`而不是普通的dictionary，這樣就不用管目前遞增的值對應的key是不是已經在dictionary裡面了。舉例來說，我們希望對於每個key，它的初始值都是一個空的list，不管我們是否已經把這個元素添加到這個dictionary裡面，我們就可以這樣做：

phone_num = defaultdict(list)

如果要為其中一個key的清單加入元素，就可以直接這樣做：

phone_num["Alice"].append("12345678")

那麼這邊我們要怎樣用`defaultdict`來建立鄰接表呢？我們可以用一個預設值是empty set（空集合）的`defaultdict`來做這件事，因為邊的清單順序並不重要所以使用`set`：

author_graph = defaultdict(set)
erdos_nums = {}
for row in authors:
    for a in row:
        erdos_nums[a] = 999999
        for b in row:
            if b != a:
                author_graph[a].add(b)
                author_graph[b].add(a)

注意這邊我們一次在`author_graph`中添加了兩個方向的邊，因為合作論文是一個雙向的關係，所以人際網路是無向的圖。這邊還初始化了一個`erdos_nums`的普通dictionary，並把所有value通通初始化為`999999`。這是什麼意思呢？事實上，這個dictionary在等等的BFS尋訪中，有兩個功能：
1. 用來標記已經尋訪過的節點
2. 用來儲存各節點的艾數

至於初始化的值我設定成`999999`，只是因為在這題目中`999999`是一個大到離譜、不可能出現的數字而已，等等就會知道為什麼要這樣設了。

### 計算艾數
接下來的步驟就是大家最喜歡的尋訪環節了。因為是BFS，所以使用queue來實作：

queue = [("Erdos, P.", 0)]

while queue:
    node, dist = queue.pop(0)
    erdos_nums[node] = min(erdos_nums[node], dist)
    if node in author_graph and author_graph[node]:
        for a in list(author_graph[node]):
            if erdos_nums[a] == 999999:
                queue.append((a, dist + 1))

很明顯可以看出，對於沒尋訪過的節點`a`，我們有`erdos_nums[a] == 999999`，所以就可以用這個條件來排除掉重複尋訪同一個節點的情形。

完整的程式碼如下：

from collections import defaultdict

authors = [\
    ["Smith, M.N.", "Martin, G.", "Erdos, P."],\
    ["Erdos, P.", "Reisig, W."],\
    ["Smith, M.N.", "Chen, X."],\
    ["Jablonski, T.", "Hsueh, Z."]\
]

def erdos_number(authors):
    author_graph = defaultdict(set)
    erdos_nums = {}
    for row in authors:
        for a in row:
            erdos_nums[a] = 999999
            for b in row:
                if b != a:
                    author_graph[a].add(b)
                    author_graph[b].add(a)

    queue = [("Erdos, P.", 0)]
    
    while queue:
        node, dist = queue.pop(0)
        erdos_nums[node] = min(erdos_nums[node], dist)
        if node in author_graph and author_graph[node]:
            for a in list(author_graph[node]):
                if erdos_nums[a] == 999999:
                    queue.append((a, dist + 1))

    del erdos_nums["Erdos, P."]
    return erdos_nums

print(erdos_number(authors))