CODEWITHSUNDEEP
python
Some Guy
Some Guy

Reputation: 721

Recursive method for a multilinked structure

I have this class in python which accepts two hash and links them together. What I want is to be able to recursively fetch all linked hashes, however I'm struggling to write a correct recursive function. What I have so far:

class MultiLink:
    def __init__(self):
        self.map = {}

    def get(self, md5: str, scanned: list = None) -> list:
        matches = []
        scanned = scanned or []
        for match in self.map[md5]:
            matches.append(match)

            if match in scanned:
                continue

            scanned.append(match)
            for mmatch in self.map[match]:
                if mmatch not in scanned:
                    matches += self.get(mmatch, scanned=scanned)

        return list(set(matches))

    def link(self, first: str, second: str) -> None:
        try:
            self.map[first].append(second)
        except KeyError:
            self.map[first] = [second]

        try:
            self.map[second].append(first)
        except KeyError:
            self.map[second] = [first]

As you can see the output does not perform as I expect it to:

l = MultiLink()
l.link("a", "b")
l.link("b", "c")
l.link("c", "a")
l.get("c")

This outputs ['c', 'b', 'a'], but l.get("a") outputs ['c', 'b'].

If I then do l.link("d", "a"), it returns ['c', 'a'] instead of the whole set of results.

What I want instead, is for the get function to start at a given node and recursively follow all other nodes until it fetches all directly or indirectly linked nodes. So l.get("b") would return ["a", "c", "d"], "d" included because it's linked through "a". Likewise l.get("d") would get all the other letters because they are linked through "a".

This is my first attempt at writing something like this, so I'm sure I'm making a very stupid error somewhere, but I cannot find it by myself. Does anyone know how to make this work? Or if there's already an implementation of this somewhere? I checked the collections module but I found nothing of interest there.

Upvotes: 1

Views: 49

Answers (1)

lnogueir
lnogueir

Reputation: 2085

A simple graph traversal will do it:

Changed your code a bit to use a set and apply a DFS:

class MultiLink:
    def __init__(self):
        self.map = {}

    def get(self, md5: str) -> set:
        result = set([])
        def DFS(key: str) -> None:
            for match in self.map[key]:
                if match not in result and match != md5:
                    result.add(match)
                    DFS(match)
        DFS(md5)
        return result

    def link(self, first: str, second: str) -> None:
        if first in self.map:
            self.map[first].add(second)
        else:
            self.map[first] = set([second])

        if second in self.map:
            self.map[second].add(first)
        else:
            self.map[second] = set([first])

Upvotes: 1

Related Questions