CODEWITHSUNDEEP
pythonclassdictionarygraphgraph-theory
Daniel Porteous
Daniel Porteous

Reputation: 6343

Python: Accessing a specific object efficiently as if it were a dict

Currently I'm coding up some graph theory stuff in Python, at this point DFS. I've made a Node class which holds the name of the Node (vertex if you like) and a list of strings with the names of all the other nodes with which it is connected. 

# Simplified for the sake of the question.
class Node:
    """ Node using an adjacency list to know which other
        nodes it's connected to. """
    def __init__(self, name, edges):
        self.name = name # Letter normally, like C.
        self.edges = sorted(edges) # List of letters for Nodes.
        self.visited = False

I found it unrealistic to try and include a list of Node objects instead of a string for the name of each node because that would involve making sure all the Nodes exist before creating the list of connected nodes.

This means that when I want to lookup a node for doing something like DFS, I need a function like this:

def getNode(nodeLetter, nodes):
    for node in nodes:
        if node.name == nodeLetter:
            return node
    return None

This function can take O(|V|) time, proportional to the number of vertices. This will build up over time because throughout an explore I will need to access every vertex, making a total complexity of O(|V|^2). If I had used a dictionary instead, for example like this:

{"A": ["C", "E"], "E", ["A"]}

I could have constant time lookup. This does of course however introduce problems such as where I store the extra attributes like visited, as well as pre and post numbers, and anything else I might need.

How can I get the best of both worlds here, with the neatness of a class and the efficiency of a dict. Is there such a thing as an efficient dict of classes with a given key? Keen to learn how best to go about this.

Upvotes: 0

Views: 105

Answers (2)

Hani
Hani

Reputation: 1424

Why you don't create a dict that link letters to nodes instead of traversing all nodes whenever you want to know which node has the letter.

So the idea is simple

  • create dic with letters as keys and nodes as values
  • and whenever you create a node add it to the dict
  • and when ever you want to know which node has the letter just query the dict which is O(1)

by that way you can eliminate this loop

def getNode(nodeLetter, nodes):
    for node in nodes:
        if node.name == nodeLetter:
            return node
    return None

to this

def getNode(nodeLetter, nodesandlettersdict):
    return nodesandlettersdict(nodeLetter)

Upvotes: 0

Alex Huszagh
Alex Huszagh

Reputation: 14614

You can subclass most Python types (besides the NoneType, to my knowledge, and the GeneratorType).

Just do something like this:

class MyDict(dict):
    '''This walks and talks like a dict'''

    def do_something(self):
        print(repr(self))

You can extend it however you like, you can even override the __getitem__ and __setitem__ magic methods to control how data is accessed and stored in the dict.

In this case, we can then instantiate the dict, and get the best of both worlds:

>>> mydict = MyDict([('a', 3)])
>>> kwd_init = MyDict(a=3)
>>> dict_init = MyDict({'a': 3})
>>> mydict.do_something()
{'a': 3}

In your specific case, just apply it to the node architecture.

class Node(dict):
    '''Defines a node object'''

    get_node = dict.__getitem__
    set_node = dict.__setitem__

Now we can extend this to store previously visited nodes, most likely by using a list.

class Node(dict):
    '''Defines a node object'''

    def __init__(self, *args, **kwds):
        super(Node, self).__init__(*args, **kwds)

        self.visited = []

    def __getitem__(self, name):
        '''Get the node but also store it as the last visited item'''

        value = dict.__getitem__(self, name)
        self.visited.append(name)
        return value

    get_node = __getitem__
    set_node = dict.__setitem__

If you want to have constant lookup time for the visited nodes, use a set. If you want both, try a custom OrderedSet.

Not too hard, was that?

Upvotes: 1

Related Questions