Breadth First Search- Standard Python Libraries

Question

I've got a problem to solve involving companies taking controlling interests of each other. A company controls another if A owns more than 50% of B, or if A owns a series of other firms that, combined, own more than 50% of B.

I'm approaching this with a graph of vertices and edges that represent all relationships with all companies.

What I think I need to implement is a Breadth First Search (or maybe Dijkstra's algorithm gear for longest path instead of shortest) that follows along the paths between firms, as long as the sum of paths from A to B is weighted greater than 50%. I don't have a clue how to implement this, as I'm only able to use standard Python 3.x libraries for the question. Any help would be greatly appreciated!

Sample Input

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

Sample Output

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.

My code thus far:

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

I believe a depth first search would be a better approach, since you need to who owns who.

So, what I did, was create a text file called, com.txt, and inside it:

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

And this is the script:

from collections import defaultdict, deque

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

I filtered out the variables without 50% ownership of a company, when I first make the connections list. And this script produces:

{'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

As expected.