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,
- Build a totally new graph (after finding strongly connected components), and build mapping between new old and old node
- For a node in a strongly connected component, build out connection only between this node and nodes not in this strongly connected component;
- For a node in a strongly connected component, build in connection only between this node and node not in this strongly connected components;
- 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:
- 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.)
- 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).
- If the graph has no nodes, stop.
- 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.)
- Remove the sink from the graph, along with every node that has a path to the sink.
- 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()