5
\$\begingroup\$

Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am not sure if there are better ways to implement in terms of performance. If you also find any other code issues or bugs, please point them out as well.

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.

My code ,

# below two connectMatrix are just two test cases, you can use either one for the testing, or use new ones
connectMatrix=[
    [1,1,0,0],
    [1,1,1,0],
    [0,0,1,1],
    [1,0,0,1]
]

connectMatrix=[
    [1,1,0],
    [0,1,1],
    [1,0,1]
]
inDegree = [0] * len(connectMatrix)
visited = [0] * len(connectMatrix)
allVisited = 0

# if (x,y) == 1, it means x follows y
# if (x,y) == 1, it means y can send message to x

def BFS(connectMatrix, visitedPersons, personID):
    global allVisited
    visitQueue = []
    result = []
    visitQueue.append(personID)
    result.append(personID)
    visitedPersons[personID]=1
    allVisited += 1
    while len(visitQueue) > 0:
        personID = visitQueue.pop(0)
        # downstream: check what other person this person can reach to
        for i in range(len(connectMatrix)):
            if connectMatrix[i][personID] == 1 and visitedPersons[i] == 0:
                visitedPersons[i] = 1
                visitQueue.append(i)
                allVisited += 1
                result.append(i)

    return result

if __name__ == "__main__":

    for j in range (len(connectMatrix)):
        degree = 0
        for i in range(len(connectMatrix)):
            if connectMatrix[i][j] == 1:
                degree += 1
        inDegree[j] = degree

    results = []

    # find non-visited person with minimal in-degree
    while allVisited < len(connectMatrix):
        minDegree = max(inDegree) + 1
        nextIndex = -1
        # find next person to iterate
        for i in range(len(connectMatrix)):
            if (visited[i] == 0) and inDegree[i] < minDegree:
                nextIndex = i
                minDegree = inDegree[i]
        results.append(nextIndex)
        print BFS(connectMatrix, visited, nextIndex)

    print 'persons to send message, ', results
\$\endgroup\$
  • 1
    \$\begingroup\$ Why do you have two matrixes with the same name ? As it is, the first declaration of connectMatrix will be neglected. \$\endgroup\$ – Grajdeanu Alex. Oct 3 '16 at 4:45
  • \$\begingroup\$ @Dex'ter, it is just my two test cases, you can test with either one. Thanks for asking, if you have any thoughts on my original question, it will be great. \$\endgroup\$ – Lin Ma Oct 3 '16 at 5:23
  • \$\begingroup\$ @Dex'ter, updated post as well to address your comments. Thanks. \$\endgroup\$ – Lin Ma Oct 3 '16 at 5:25
  • 1
    \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Phrancis Oct 4 '16 at 7:56
  • \$\begingroup\$ @Phrancis, thanks for clarification for the rules. I will obey in the future. \$\endgroup\$ – Lin Ma Oct 4 '16 at 22:44
11
+50
\$\begingroup\$

1. Bug

The algorithm does not always find the minimum number of messages! Suppose that we have the following follower graph (an arrow from A to B means that A follows B).

To reach everyone, only one message is needed (to C or D; either will do). But when I represent this graph as an adjacency matrix:

connectMatrix = [
    [1, 1, 1, 0],
    [1, 1, 0, 0],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
]

and run the code from the post, I get the following output:

[0, 1]
[3, 2]
persons to send message,  [0, 3]

2. Review

  1. The code is not portable to Python 3 because it uses the print statement. It would be easy to make it portable by using from __future__ import print_function.

  2. The code is awkward to test because it only runs as a script and so it can't be run from the interactive interpreter, or from a unit test case. It would be better to organize the code into functions. For example, I would write:

    def min_sinks(connectMatrix):
        """Return the smallest list of sinks such that each node in the graph
        has a path to at least one of the sinks.
    
        """
        inDegree = [0] * len(connectMatrix)
        visited = [0] * len(connectMatrix)
        allVisited = 0
        # ... etc ...
    

    But this doesn't quite work because BFS uses the global variable allVisited. The way to fix that is to observe that BFS adds one to allVisited for each node it adds to result, and so in min_sinks we can update allVisited as follows:

    visited_nodes = BFS(connectMatrix, visited, nextIndex)
    allVisited += len(visited_nodes)
    
  3. The name allVisited doesn't describe the variable very well: better would be something like visited_count.

  4. The code in BFS uses the name persons for the nodes in the graph. But nothing in this code depends on the fact that the nodes represent persons. So it would be better to use a neutral name like nodes.

  5. Popping the leftmost item of a list takes time proportional to the length of the list (see the time complexity page on the Python wiki). It's necessary to use a collections.deque to ensure that popping is efficient.

  6. The data structure visitedNodes is a list whose value at index i is 1 if the node i has been visited, and 0 if it has not. It would be clearer to use True and False instead of 1 and 0.

  7. The code in the post uses an adjacency matrix to represent the graph. But this is a poor representation for this algorithm, for two reasons. First, an adjacency matrix takes \$Θ(n^2)\$ space to store a graph on \$n\$ nodes, and this is only efficient if the graph is dense, whereas a graph of Twitter followers is (most likely) sparse. Second, at each iteration of the breadth-first search, the code needs to iterate over the followers of a node, and that takes \$Θ(n)\$ in the adjacency matrix represention, which is inefficient if the graph is spare.

    It would be better to use a different representation, for example adjacency list.

3. 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.

For example, suppose that we start with this graph:

At step 1 we find the strongly connected components:

At step 2 we replace each component with a new single node:

At step 4 we find that there is one node of out-degree zero (the node CD) so we add either C or D to the set of sinks (it doesn't matter which). At step 5 we remove CD from the graph together with every node that has a path to CD. This leaves the graph empty, so we are done.

4. Answers to questions

  1. You asked in comments whether "out-degree zero" in step 4 of the algorithm is a mistake for "in-degree zero".

    The answer is no: "out-degree" is correct. Remember that the graph is a follower graph. So a node with out-degree zero represents someone who doesn't follow anyone (or a strongly connected component nones of whose members follows anyone outside of the component). The only way that someone who doesn't follow anyone can receive the message is if they receive it directly. So that person needs to be added to the set of sinks.

  2. You asked for clarification about the direction of edges in the graph. I took this directly from the problem statement:

    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.

    This says that "A follows B" implies "A → B" which implies that there is an edge from A to B. I stated this explicitly in §1 above, where I wrote:

    (an arrow from A to B means that A follows B)

    Of course you are free to represent the graph the other way round, so that if A follows B then B → A. If you do this then this doesn't affect the strongly connected component part of the algorithm (since a component remains strongly connected if you reverse all the edges), but you will need to swap "out-neighbour" and "in-neighbour" in the remainder of the algorithm.

\$\endgroup\$
  • \$\begingroup\$ Thanks Garesh, vote up for your reply. I want to further improve code by import print_function from future module, but I am not sure how it impacts to my existing Python 2.7 code and how it facilitate migration (if I migrate to Python 3.0 in the future), I read here but feel lost (python.org/dev/peps/pep-3105), it does not mention how future module works. If you could shed some lights, it will be great. :)) \$\endgroup\$ – Lin Ma Oct 4 '16 at 5:36
  • \$\begingroup\$ (cont'd) I ask future module print function since I tested for code in Python 2.7 print 'hello', 'world' it does not work (in Python 2.7) if I import print function from future module, so confused how much benefit I can get to use from future import print function? Thanks. \$\endgroup\$ – Lin Ma Oct 4 '16 at 5:37
  • 1
    \$\begingroup\$ @LinMa: Here on Code Review we'd prefer that you post a new question if you would like a review of your new code. \$\endgroup\$ – Gareth Rees Oct 4 '16 at 9:14
  • 1
    \$\begingroup\$ @LinMa: see updated answer. \$\endgroup\$ – Gareth Rees Oct 9 '16 at 20:15
  • 1
    \$\begingroup\$ @LinMa: see updated answer. \$\endgroup\$ – Gareth Rees Oct 10 '16 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.