Search code examples
pythonpython-3.xalgorithmgraphadjacency-list

Get all leafs in an adjacency list

Given a structure like the following:

graph = {

    # c1 is root node, graph is directed, c1 is source/root node
    'c1': ['c2', 'c3'],
    'c2': ['c4']

}

      c1
      /\
     /  \ 
    c2   c3
   /
  /
c4

What would be a general-purpose algorithm to find all the leafs on the graph? My first thought was:

# values in the 'from' section, that don't have a 'to' entry
set(itertools.chain(*graph.values())) - set(graph.keys())
# {'c3', 'c4'}

Is this the proper way to do it? What would be some other approaches to determine if something is a leaf or not?

Solution

  • You might simplify your piece to make it more efficient:

    leaves = set()
leaves.update(*graph.values())
leaves -= graph.keys()