廣度優先搜索 - 標準Python庫

Question

我遇到了一個問題，需要解決涉及控制對方利益的公司。如果A擁有超過50％的B，或者如果A擁有一系列其他公司擁有超過50％的B，則公司控制另一個公司。如果A擁有一系列其他公司，並且擁有B的50％以上。

我正在用頂點圖代表與所有公司的所有關係的邊緣。

我想我需要實現一個廣度優先搜索（或者Dijkstra算法齒輪的最長的路徑，而不是最短）沿着企業間的路徑後面，只要路徑從A總和到B的權重大於50％。我不知道如何實現這一點，因爲我只能使用標準Python 3.x庫作爲問題。任何幫助將不勝感激！

採樣輸入

CompanyA CompanyB 30 
CompanyB CompanyC 52 
CompanyC CompanyD 51 
CompanyD CompanyE 70 
CompanyE CompanyD 20 
CompanyD CompanyC 20 

樣本輸出

CompanyA has a controlling interest in no other companies. 
CompanyB has a controlling interest in CompanyC, CompanyD, and CompanyE. 
CompanyC has a controlling interest in CompanyD, and CompanyE. 
CompanyD has a controlling interest in CompanyE. 
CompanyE has a controlling interest in no other companies. 

我的代碼迄今：

import sys 

class Vertex: 
    def __init__(self, key): 
     self.id = key 
     self.connectedTo = {} 

    def addNeighbour(self, nbr, weight = 0): 
     self.connectedTo[nbr] = weight 

    def __str__(self): 
     return str(self.id) + 'connectedTo: ' + str([x.id for x in self.connectedTo]) 

    def getConnections(self): 
     return self.connectedTo.keys() 

    def getId(self): 
     return self.id 

    def getWeight(self, nbr): 
     return self.connectedTo[nbr] 

class Graph: 
    def __init__(self): 
     self.vertList = {} 
     self.numVerticies = 0 

    def addVertex(self, key): 
     self.numVerticies = self.numVerticies + 1 
     newVertex = Vertex(key) 
     self.vertList[key] = newVertex 
     return newVertex 

    def getVertex(self,n): 
     if n in self.vertList: 
      return self.vertList[n] 
     else: 
      return None 

    def __contains__(self, n): 
     return n in self.vertList 

    def addEdge(self, f, t, cost = 0): 
     if f not in self.vertList: 
      nv = self.addVertex(f) 
     if t not in self.vertList: 
      nv = self.addVertex(t) 
     self.vertList[f].addNeighbour(self.vertList[t], cost) 

    def getVertices(self): 
     return self.vertList.keys() 

    def __iter__(self): 
     return iter(self.vertList.values()) 

#all code above this line deals with the ADTs for Vertex and Graph objects 
#all code below this line deals with taking input, parsing and output 

def main(): 
    f = sys.argv[1] #TODO deal with standard input later 
    temp = graphFunction(f) 

def graphFunction(filename): 
    openFile = open(filename, 'r') 
    coList = [] 
    g = Graph() 

    for line in openFile: 
     lineSplit = line.split() 
     g.addEdge(lineSplit[0], lineSplit[1], lineSplit[2]) 
     coList.append(lineSplit[0]) 
     coList.append(lineSplit[1]) 
    coSet = set(coList) 
    coList = list(coSet) #converting this from a list to a set to a list removes all duplicate values within the original list 
    openFile.close() 

    #this is where there should be a Breadth First Search. Notthing yet, code below is an earlier attempt that kinda sorta works. 

    newConnList = [] #this is a list of all the new connections we're going to have to make later 
    for v in g: #for all verticies in the graph 
     for w in v.getConnections(): #for all connections for each vertex 
      #print("%s, %s, with weight %s" % (v.getId(), w.getId(), v.getWeight(w))) 
      #print(v.getId(), w.getId(), v.getWeight(w)) 
      firstCo = v.getId() 
      secondCo = w.getId() 
      edgeWeight = v.getWeight(w) 
      if int(edgeWeight) > 50: #then we have a controlling interest situation 
       for x in w.getConnections(): 
        firstCo2 = w.getId() 
        secondCo2 = x.getId() 
        edgeWeight2 = w.getWeight(x) 
        #is the secondCo2 already in a relationship with firstCo? 
        if x.getId() in v.getConnections(): 
         #add the interest to the original interest 
         tempWeight = int(v.getWeight(x)) 
         print(tempWeight) 
         tempWeight = tempWeight + int(w.getWeight(x)) 
         newConnList.append((firstCo, secondCo2, tempWeight)) #and create a new edge 
         print('loop pt 1') 
        else: 
         newConnList.append((firstCo, secondCo2, edgeWeight2)) 
    for item in newConnList: 
     firstCo = item[0] 
     secondCo = item[1] 
     edgeWeight = item[2] 
     g.addEdge(firstCo, secondCo, edgeWeight) 
     #print(item) 
    for v in g: 
     for w in v.getConnections(): 
      print(v.getId(), w.getId(), v.getWeight(w)) 

main() 

Answer 1

我相信一個深度優先搜索將是一個更好的辦法，因爲你需要誰擁有誰。

所以，我做什麼，是創建一個名爲，com.txt一個文本文件，裏面：

A B 30 
B C 52 
C D 51 
D E 70 
E D 20 
D C 20 

這是腳本：

從收藏導入defaultdict，雙端隊列

with open('com.txt', 'r') as companies: 

    # Making a graph using defaultdict 
    connections = defaultdict(list) 
    for line in companies: 
     c1, c2, p = line.split() 
     connections[c1].append((c2, int(p))) 

    for item in connections: 
     q = deque([item]) 
     used = set() 
     memory = [] 
     while q: 
      c = q.pop() 
      if c in connections and c not in used: 
       memory.append(c) 
       to_add = [key for key, cost in connections[c] if cost > 50] 
       if to_add: 
        q.extend(to_add) 
        used.add(c) 
       else: 
        break 
     if len(memory) < 2: 
      print(memory[0], "does not own any other company") 
     else: 
      owner = memory[0] 
      comps = memory[1:] 
      print(owner, "owns", end=' ') 
      print(" and ".join(comps)) 
     del used 

我過濾了變量沒有當我第一次建立連接時，公司的50％所有權IST。並且此腳本產生：

{'A': [('B', 30)], 'C': [('D', 51)], 'B': [('C', 52)], 'E': [('D', 20)], 'D': [('E', 70), ('C', 20)]} 
A does not own any other company 
C owns D and E 
B owns C and D and E 
E does not own any other company 
D owns E 

正如所料。