Given graph/network of nodes without any loops/circuits. I'm trying to find the center: the node from which I can reach all other nodes the fastest. Imagine if I want to spread the word about something and the information traveling from one node to the next takes 1.

My solution removes nodes from the graph that have only one connection. To keep track of the amount of connections a node has I use a Counter. This process repeats till there are only nodes with one connection left. These nodes can be seen as "center" nodes of the graph.

from collections import Counter


def get_center(graph):
    c = Counter()

    for v in graph.values():
        c.update(v)

    while c.most_common(1)[0][1] > 1:
        for k, v in list(c.items()):
            if v == 1:
                tmp = graph[k][0]
                graph.pop(k)
                c.pop(k)
                c[tmp] -= 1
                graph[tmp].remove(k)

    return list(c.keys())


if __name__ == '__main__':
    graph = {'a': ['b'],
             'b': ['a', 'c'],
             'c': ['b', 'd', 'e'],
             'd': ['c'],
             'e': ['c', 'f'],
             'f': ['e']}
    print(get_center(graph))

Is there a more efficient way to tackle this problem? Either in my implementation or a completely different approach...

Update

to clarify what the above code actually tries to do:

enter image description here

In the blue example we choose node b as center of start spreading the word and need 3 steps till all nodes are aware of the message. In the yellow example we choose node c as center of start spreading the word and need only 2 steps till all nodes are informed. The algorithm should find the node that minimises the steps needed to inform the whole network. The graphs fed to the algorithm are undirected and have no disconnected parts.

  • Yes exactly: minimize the sum of distances to all other nodes. I'm missing the vocabulary - trying to learn about graphs atm – RandomDude Aug 18 at 16:45
  • 1
    @GarethRees I interpret the definition of "center" given in the question not as the node which has the smallest sum of distances to the other nodes, but as the node which has the smallest maximum distance to any other node. ("spreading the word" from this node would reach all nodes in the shortest possible time). I think the code would be correct in this interpretation, as far as §4 of your answer is concerned. (Your asking for clarification may have caused misunderstanding...) – mkrieger1 Aug 29 at 11:24
  • @mkrieger1: You might be right. I have retracted my close vote and deleted my answer. Sorry about asking for clarification. – Gareth Rees Aug 29 at 11:52

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.