從紙本作者列表中計算鄂爾多斯數

Question

Erdős數字描述了一個人和數學家PaulErdős之間的「協作距離」，用數學論文的作者衡量。要分配一個Erdős號碼，某人必須是另一個Erdős號碼有限的人的研究論文的合着者。保羅·埃爾多斯的埃爾多斯數爲零。任何其他人的Erdős數是k + 1，其中k是任何合作者的最低Erdős數。 Wikipedia。

鑑於作者（和論文）的列表，我想爲每組作者編制一個Erdős數。源數據如下（從.txt文件的輸入）：

1(means only one scenario from this input, could have more than one from other entries) 

4 3 
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors 
Erdos, P., Reisig, W.: Stuttering in petri nets 
Smith, M.N., Chen, X.: First order derivates in structured programming 
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures 
Smith, M.N. 
Hsueh, Z. 
Chen, X. 

計算鄂爾多斯號碼的作者是：

Smith, M.N. 
Hsueh, Z. 
Chen, X. 

我目前的計劃是採取了名的每個條目的並形成名稱的列表（或列表）。但我不確定這樣做的最佳方式。我應該使用什麼？ numpy的？的ReadLine？

更新： 輸出應該是這樣的：

Scenario 1 
Smith, M.N. 1 
Hsueh, Z. infinity 
Chen, X. 2 

Answer 1

我已經提交一個編輯您的問題，試圖澄清你希望達到的目標。在此基礎上，我寫了下面的代碼來解答一下我以爲你試圖問：

f = ['Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors', 
'Erdos, P., Reisig, W.: Stuttering in petri nets', 
'Smith, M.N., Chen, X.: First order derivates in structured programming', 
'Jablonski, T., Hsueh, Z.: Selfstabilizing data structures'] 

author_en = {} # Dict to hold scores/author 
coauthors = [] 
targets = ['Smith, M.N.','Hsueh, Z.','Chen, X.'] 

for line in f: 
    # Split the line on the : 
    authortext,papers = line.split(':') 

    # Split on comma, then rejoin author (every 2) 
    # See: http://stackoverflow.com/questions/9366650/string-splitting-after-every-other-comma-in-string-in-python 
    authors = authortext.split(', ') 
    authors = map(', '.join, zip(authors[::2], authors[1::2])) 

    # Authors now contains a list of authors names  
    coauthors.append(authors) 

    for author in authors: 
     author_en[ author ] = None 

author_en['Erdos, P.'] = 0 # Special case 

在這一點上，我們現在我們有一個列表的列表：包含來自合着者每個列表給予出版物和字典來保持分數。我們需要遍歷每篇論文併爲作者分配一個分數。我對鄂爾多斯分數的計算並不完全清楚，但您可能想循環分數分配，直到沒有變化 - 以考慮影響早期分數的後續論文。

for ca in coauthors: 
    minima = None 
    for a in ca: 
     if author_en[a] != None and (author_en[a]<minima or minima is None): # We have a score 
      minima = author_en[a] 

    if minima != None: 
     for a in ca: 
      if author_en[a] == None: 
       author_en[a] = minima+1 # Lowest score of co-authors + 1 

for author in targets: 
    print "%s: %s" % (author, author_en[author])    

Answer 2

爲了更好地理解這個問題，注意，基本上這只是unweighted single-source shortest path problem，可使用Breadth-first Search解決。 問題中的圖形定義如下：

1. 每個節點代表作者。
2. 如果有兩篇節點代表的兩位作者共同創作的論文，則兩節點之間存在邊緣。

爲了您的例子，該圖如下：

 
Reisig 
    | 
    | 
Erdos -- Martin 
    | /
    | /
    | /
    | /
    |/
Smith -- Chen 


Jablonski -- Hsueh 

所以算法最初將分配給其他人的距離0至鄂爾多斯和無窮大。然後，當它迭代訪問鄰居時，它指定增加的距離。所以下一次迭代將給Reisig，Martin和Smith分配1的距離（或者在這種情況下Erdos數）爲1。下一次和最後一次迭代將給陳的距離爲2。 Jablonski和Hsueh的距離將保持爲無窮大。

該圖表示使用Adjacency List：

 
e = Erdos 
r = Reisig 
m = Martin 
s = Smith 
c = Chen 
j = Jablonski 
h = Hsueh 

e: r m s 
r: e 
m: e s 
s: e c 
c: s 
j: h 
h: j 

與代碼來解決它在Python：

import Queue 

def calc_erdos(adj_lst): 
    erdos_numbers = {} 
    queue = Queue.Queue() 
    queue.put(('Erdos, P.', 0)) 
    while not queue.empty(): 
     (cur_author, dist) = queue.get() 
     if cur_author not in erdos_numbers: 
      erdos_numbers[cur_author] = dist 
     for author in adj_lst[cur_author]: 
      if author not in erdos_numbers: 
       queue.put((author, dist+1)) 
    return erdos_numbers 

def main(): 
    num_scenario = int(raw_input()) 
    raw_input() # Read blank line 
    for idx_scenario in range(1, num_scenario+1): 
     [num_papers, num_queries] = [int(num) for num in raw_input().split()] 
     adj_lst = {} 
     for _ in range(num_papers): 
      paper = raw_input() 
      [authors, title] = paper.split(':') 
      authors = [author.strip() for author in authors.split(',')] 
      authors = [', '.join(first_last) for first_last in zip(authors[::2], authors[1::2])] 
      # Build the adjacency list 
      for author in authors: 
       author_neighbors = adj_lst.get(author,set()) 
       for coauthor in authors: 
        if coauthor == author: 
         continue 
        author_neighbors.add(coauthor) 
       adj_lst[author] = author_neighbors 

     erdos_numbers = calc_erdos(adj_lst) 

     print 'Scenario %d' % idx_scenario 
     for _ in range(num_queries): 
      author = raw_input() 
      print '%s %s' % (author, erdos_numbers.get(author,'infinity')) 

if __name__=='__main__': 
    main() 

，其與輸入：

 
1 

4 3 
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors 
Erdos, P., Reisig, W.: Stuttering in petri nets 
Smith, M.N., Chen, X.: First order derivates in structured programming 
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures 
Smith, M.N. 
Hsueh, Z. 
Chen, X. 

將輸出：

 
Scenario 1 
Smith, M.N. 1 
Hsueh, Z. infinity 
Chen, X. 2 

注：

的更一般的問題可以描述爲single-source shortest path problem，爲此，最簡單的解決方案是使用Djikstra's Algorithm。