CODEWITHSUNDEEP
pythongraphdepth-first-search
sujaypatil
sujaypatil

Reputation: 58

DFS on a graph specified with edges as list of tuples

I have a graph with its edges specified as a list of tuples. Say, for example, we have:

edges = [('human', 'mammal'), ('mammal', 'vertebrate'), ('mouse', 'mammal'), ('vertebrate', 'animal')]

How would we write a method that recursively iterates over all the nodes that can be constructed from the above graph to perform a depth first search traversal in Python?

Any help is appreciated, thank you!

Upvotes: 0

Views: 490

Answers (1)

Grismar
Grismar

Reputation: 31354

This is a rather fun problem, which you should probably still try to solve yourself, but here's an example of an implementation:

from typing import Generator, Union


def construct(edges: list[tuple[str, str]]) -> dict:
    root = {}
    index = {}
    for x, isa in edges:
        if x in root:
            root[isa] = {x: root[x]}
            del root[x]
            index[isa] = root[isa]
        else:
            if x in index:
                raise SyntaxError(f'Invalid tree structure')
            if isa in index:
                index[isa][x] = (d := {})
            else:
                root[isa] = {x: (d := {})}
                index[isa] = root[isa]
            index[x] = d

    return root


def traverse(tree: Union[list[tuple[str, str]], dict]) -> Generator[str, None, None]:
    # this assumes that, if tree is a dict, it is a well-constructed tree, as construct() would return it
    if not isinstance(tree, dict):
        tree = construct(tree)

    for node in tree:
        yield node
        yield from traverse(tree[node])


def main():
    edges = [('human', 'mammal'), ('mammal', 'vertebrate'), ('mouse', 'mammal'), ('vertebrate', 'animal')]
    
    for node in traverse(edges):
        print(node)


if __name__  == '__main__':
    main()

This constructs a tree in linear time and then traverses it depth-first, yielding the visited nodes. It rejects trees that have duplicate leaf or node values, or cycles.

Output:

animal
vertebrate
mammal
human
mouse

My recommendation would be you give this example a try, try to understand it, and then write your own from scratch with whatever you learned.

Upvotes: 2

Related Questions