Social network broadcast message algorithm (part 2)

Question

This is new code and continue discussion from thread (Social network broadcast message algorithm), and this thread focus on build new graph from strong connected graph part. Let me post the problem again, this time I want to focus more on the 2nd step of the algorithm (i.e. code after replace nodes in a strongly connected component with a new node part). Appreciate for any comments in advance.

Major ideas of implementation,

1. Build a totally new graph (after finding strongly connected components), and build mapping between new old and old node
2. For a node in a strongly connected component, build out connection only between this node and nodes not in this strongly connected component;
3. For a node in a strongly connected component, build in connection only between this node and node not in this strongly connected components;
4. Deal with in/out connections for nodes not in any strongly connected components.

Wondering if more elegant ways to implement, my overhead of implementation is (1) a old/new node mapping and (2) a complete new graph

Problem,

Let's suppose that I'd like to spread a promotion message across all people in Twitter. Assuming the ideal case, if a person tweets a message, then every follower will re-tweet the message.

You need to find the minimum number of people to reach out (for example, who doesn't follow anyone etc) so that your promotion message is spread out across entire network in Twitter.

Also, we need to consider loops like, if A follows B, B follows C, C follows D, D follows A (A -> B -> C -> D -> A) then reaching only one of them is sufficient to spread your message.

Input: A 2x2 matrix like below. In this case, a follows b, b follows c, c follows a.

   a b c
a  1 1 0
b  0 1 1
c  1 0 1

Output: List of people to be reached to spread out message across everyone in the network.

Let me quote the correct algorithm by Gareth.

Correct algorithm

The correct algorithm for finding the minimum number of sinks so that every node has a path to at least one sink is as follows:

1. Find the strongly connected components in the graph, for example using Tarjan's algorithm. (A strongly connected component is a group of nodes such that there is a path from every node in the component to every other node in the component. For example, a cycle.)
2. In the graph, replace each strongly connected component with a new single node (updating the edges so that if there was an edge between a node n and any node in the component, there is a corresponding edge between n and the new node).
3. If the graph has no nodes, stop.
4. Find a node of out-degree zero and add it to the set of sinks. (If the node replaced a strongly connected component in step 2, then add any node from the original component.)
5. Remove the sink from the graph, along with every node that has a path to the sink.
6. Go to step 3.

My code,

from __future__ import print_function
from collections import defaultdict

class Graph:
    def __init__(self):
        self.outConnections = defaultdict(set)
        self.inConnections = defaultdict(set)
        self.visited = set()
        self.DFSOrder = []
    def addEdge(self, fromx, toy):
        self.outConnections[fromx].add(toy)
        self.inConnections[toy].add(fromx)
    def DFS(self, root, path):
        if root in self.visited:
            return
        self.visited.add(root)
        for node in self.outConnections[root]:
            self.DFS(node, path)
        self.DFSOrder.insert(0, root)
        path.add(root)
    def getNodes(self):
        return self.outConnections.keys()
    def getConnections(self):
        for (k, v) in self.outConnections.items():
            print (k, '=>', v)
        for (k, v) in self.inConnections.items():
            print (v, '=>', k)
    def DFSReverse(self, root, path):
        if root in self.visited:
            return
        self.visited.add(root)
        for node in self.inConnections[root]:
            self.DFS(node, path)
        path.add(root)

if __name__  == "__main__":
    g = Graph()
    g.addEdge('A', 'B')
    g.addEdge('A', 'C')
    g.addEdge('B', 'A')
    g.addEdge('C', 'D')
    g.addEdge('D', 'C')

    for node in g.getNodes():
        if node not in g.visited:
            path=set()
            g.DFS(node, path)

    g.visited=set()
    SCs = []
    for node in g.DFSOrder:
        if node not in g.visited:
            path=set()
            g.DFSReverse(node, path)
            SCs.append(path)

    # replace nodes in a strongly connected component with
    # a new node
    baseName='SC-'
    i = 0
    newGraph = Graph()
    oldNewGraphMapping = defaultdict(str) # key old node, value new node
    for sc in SCs:
        for node in sc:
            oldNewGraphMapping[node]=baseName+str(i)
        newGraph.inConnections[baseName+str(i)]
        newGraph.outConnections[baseName+str(i)]
        i+=1
    # handle node not in any strongly connected graph
    nonSCNode = set()
    for node in g.inConnections.keys():
        if node not in oldNewGraphMapping:
            oldNewGraphMapping[node] = node
            newGraph.inConnections[node]
            nonSCNode.add(node)
    for node in g.outConnections.keys():
        if node not in oldNewGraphMapping:
            oldNewGraphMapping[node] = node
            newGraph.outConnections[node]
            nonSCNode.add(node)
    for sc in SCs:
        for node in sc:
            for outLink in g.outConnections[node]:
                if outLink not in sc: # point to outside
                    newGraph.addEdge(oldNewGraphMapping[node], oldNewGraphMapping[outLink])
            for inLink in g.inConnections[node]: # pointed from outside
                if inLink not in sc:
                    newGraph.addEdge(oldNewGraphMapping[inLink], oldNewGraphMapping[node])
    # deal with non-sc nodes
    for node in nonSCNode:
        for toNode in g.outConnections[node]:
            newGraph.addEdge(oldNewGraphMapping[node], oldNewGraphMapping[toNode])

        for fromNode in g.outConnections[node]:
            newGraph.addEdge(oldNewGraphMapping[fromNode], oldNewGraphMapping[toNode])

    #print (newGraph.getNodes())
    #newGraph.getConnections()

Answer 1

1. The code in my answer to your previous question had docstrings, but these have been removed in the version of the code posted here. I put the docstrings there for two reasons:

   1. Without documentation, it's very hard to use code. You have to guess what it might do from the names, or read the source code and reverse-engineer it to figure out what it does. This applies not only to second-party users, but also to yourself when you come back to use code in six months or a year and have forgotten what you were thinking when you wrote it.

   2. Without documentation, it's impossible to check that code is correct. If you spot something strange in the implementation, is it a bug, or is it a feature? You can't tell unless you know what the code is supposed to do.

2. The __init__ method lacks the convenient initialization from my answer to your previous question. I wrote there:

   The constructor makes it very easy to create example graphs:

   Graph('AB BA CD DC AC'.split())
   

   (Compare this to the ten lines of code needed to create the graph in the post.)

3. In my reviews to three of your previous questions (1, 2, 3) I made this point:

   The code is not fully organized into functions: most of it runs at the top level of the module. This makes it hard to understand and hard to test.

   This problem is still present in the code in this post.

4. There is a bug in the addEdge method: it doesn't add toy to outConnections, meaning that getNodes may return an incomplete set of nodes. Note that this bug was not present in the add_edge method in my answer to your previous question.