3
\$\begingroup\$

I wanted to have a python container in which every element is a key (like in a set), but still supports mapping (like a dict) between the elements. To get a container which supports this idea the elements have to be unique like in a set and the mapping between the elements has to be bidirectional. I couldn't find such thing so I tried to implement it myself.

As this is the first data structure I implemented myself in Python I would like to ask if anybody has comments or advices for me.

EDIT: updated version following the recommendations of @Winston and added a better example

import copy

class Network(object):
    """
    A network is a container similar to a set in which
    the elements can be mapped to each other (be connected).
    The Elements in a network are called entities and are
    unique in the network.

    Single entities can be inserted into the network by
    using the method insert(entity).

    Connections between entities are made using the method
    connect(entity1, entity2), which automatically inserts
    the entity/-ies into the network if not existent beforehand.

    Calling network[entity] returns a subset of the network,
    containig all the entities connected to the given entity.

    Removing an entity from the network results in removing
    all its connections in the network aswell.
    """

    def __init__(self):
        self._db = {}

    def __delitem__(self, entity):
        self.remove(entity)

    def __getitem__(self, entity):
        """
        Returns a subset of the network, containig all the
        entities connected to the given entity
        """
        return self._db.__getitem__(entity)

    def __iter__(self):
        return self._db.__iter__()

    def __len__(self):
        """Returns the number of entities in the network"""
        return self._db.__len__()

    def __repr__(self):
        return self._db.__repr__()

    def __str__(self):
        return self._db.__str__()

    def are_connected(self, entity1, entity2):
        """Test for a connection between two entities."""
        return entity2 in self._db[entity1] #and entity1 in self._db[entity2]

    def clear(self):
        """Removes all entities from the network"""
        self._db.clear()

    def connect(self, entity1, entity2):
        """ Connects entity1 and entity2. Automatically inserts the
        entity/-ies into the network if not existent beforehand."""
        self._db.setdefault(entity1, set()).add(entity2)
        self._db.setdefault(entity2, set()).add(entity1)

    def connect_many(self, entity, seq):
        """Connects entity with all entities in seq."""
        for e in seq:
            self.connect(entity, e)

    def copy(self):
        """Returns a deep copy of the network"""
        return copy.deepcopy(self)

    def entities(self):
        """Returns a set of the entities in the network."""
        return set(self._db.keys())

    def get(self, entity, default=None):
        """Return the set of connected entities of entity if entity is in
        the network, else default. If default is not given, it defaults to
        None, so that this method never raises a KeyError."""
        return self._db.get(entity, default)

    def insert(self, entity):
        """Inserts an entity into the network."""
        self._db.setdefault(entity, set())

    def isolate(self, entity):
        """Removes all connections of an entity"""
        for e in self[entity]:
            if e != entity:
                self[e].remove(entity)
        self._db[entity].clear()

    def pop(self, entity):
        """Removes an entity from the network and returns the set of entities
        it was previously connected with."""
        temp = self[entity]
        self.remove(entity)
        return temp

    def remove(self, entity):
        """Removes an entity and all its connections from the network."""
        for e in self[entity]:
            if e != entity:
                self[e].remove(entity)
        del self.db[entity]

    def setdefault(self, entity):
        """If entity is in the network, return the set of connected entites.
        If not, insert entity and return default. default defaults to an empty set."""
        return self._db.setdefault(entity, set())

    def unique_mapping(self, entity):
        """If the given entity is mapped to a single other entity this entity is returned,
        otherwise a ValueError exception is raised."""
        entity_set = self._db[entity]
        if len(entity_set) == 1:
            return next(iter(entity_set))
        else:
            raise ValueError("The entity '%s' has no unique mapping." % entity)

    def update(self, netw):
        """Updates the network with another given network. Equal entities are merged."""
        for entity in netw:
            for e in netw[entity]:
                self.connect(entity,e)

Example usage:

>>> friends = Network()
>>> friends.connect("Peter","John")
>>> friends.connect("Peter","Paul")
>>> friends.connect("Steve","John")
>>> friends.connect("Bill","Steve")
>>> friends.connect("Mark","John")
>>> print "%s are friends of John" % ", ".join(friends["John"])
Steve, Peter, Mark are friends of John
>>> print "%s is Bills only friend" % friends.unique_mapping("Bill")
Steve is Bills only friend

Comments/advices about the general implementation of data structures in python and the style of my implementation are as welcome as suggestions regarding the performance, semantics and usage of this container. Basically feel free to critizise or give advice on anything you can come up with. Thanks alot!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The example confused me a tad, given the class name and behavior of "network" I expected to see examples more along the lines of friends.connect("James", "Joe") \$\endgroup\$ – John Gaines Jr. Oct 6 '11 at 15:59
  • \$\begingroup\$ good point. i changed that to the example you describe which suits the name of the class better. \$\endgroup\$ – tobigue Oct 6 '11 at 20:58
5
\$\begingroup\$
class network(object):

The python style guide recommends CamelCase for class names

    """
    A network is a container similar to a set in which
    the elements can be mapped to each other (be connected).
    The Elements in a network are called entities and are
    unique in the network.

    Single entities can be inserted into the network by
    using the method insert(entity).

    Connections between entities are made using the method
    connect(entity1, entity2), which automatically inserts
    the entity/-ies into the network if not existent beforehand.

    Calling network[entity] returns a subset of the network,
    containig all the entities connected to the given entity.

    Removing an entity from the network results in removing
    all its connections in the network aswell.
    """

    def __init__(self):
        self.db = dict()

I might call this _db to make it clear that it is private. Empty dictionaries are usually created with {}

    def __delitem__(self, entity):
        self.remove(entity)

    def __getitem__(self, entity):
        """
        Returns a subset of the network, containig all the
        entities connected to the given entity
        """
        return self.db.__getitem__(entity)

    def __iter__(self):
        return self.db.__iter__()

    def __len__(self):
        """Returns the number of entities in the network"""
        return self.db.__len__()

    def __repr__(self):
        return self.db.__repr__()

    def __str__(self):
        return self.db.__str__()

    def are_connected(self, entity1, entity2):
        """Test for the presence of a connection between entity1 and entity2."""
        return entity1 in self.db[entity2] and entity2 in self.db[entity1]

Do you actually need to check both?

    def clear(self):
        self.db.clear()

    def connect(self, entity1, entity2):
        """
        Connects entity1 and entity2. Automatically inserts
        the entity/-ies into the network if not existent beforehand.
        """
        self.db.setdefault(entity1, set()).add(entity2)
        self.db.setdefault(entity2, set()).add(entity1)

    def connect_many(self, entity, seq):
        """Connects entity with all entities in seq."""
        for e in seq:
            self.connect(entity, e)

    def copy(self):
        return self.db.copy()

    def entities(self):
        """Returns a set of the entities in the network."""
        return set(self.db.keys())

Why are you returning this as a set? It seems to break symmetry with everything else a dict returns which are lists or generators.

    def get(self, entity, default=None):
        return self.db.get(entity, default)

    def insert(self, entity):
        """Inserts an entity into the network."""
        self.db.setdefault(entity, set())

    def isolate(self, entity):
        """Removes all connections of an entity"""
        for e in self[entity]:
            if e != entity:
                self[e].remove(entity)
        self.db[entity].clear()

    def pop(self, entity):
        temp = self[entity]
        self.remove(entity)
        return temp

    def remove(self, entity):
        """Removes an entity and all its connections from the network."""
        for e in self[entity]:
            if e != entity:
                self[e].remove(entity)
        self.db.__delitem__(entity)

Why not del self.db[entity]?

    def setdefault(self, entity):
        return self.db.setdefault(entity, set())

You are deviating from the dict interface here. Do you have a good reason?

    def unique_mapping(self, entity):
        """If the given entity is mapped to a single entity this entity is returned"""
        if len(self.db[entity]) == 1:
            return next(iter(self.db[entity]))

You may want to avoid fetching self.db[entity] multiple times

        else:
            return False

You should throw an exception not return a sentinel value. If you insists on returning a sentinel value use None.

    def update(self, netw):
        """Updates the network with another given network. Equal entities are merged."""
        for entity in netw:
            for e in netw[entity]:
                self.connect(entity,e)

You could have this class inherit from dict, and then you'd be able to avoid all of the

def foo(self):
    return self.db.foo()

But then you might get methods you don't want as well. Thats a judgment call.

\$\endgroup\$
2
  • \$\begingroup\$ @eowl, sorry I meant iterator not generator. My point was that keys on a dictionary aren't a set even though they have the same semantics as your entities. Really, it would depend on how your class being used whether or not a set is a good idea. \$\endgroup\$ – Winston Ewert Oct 6 '11 at 13:53
  • \$\begingroup\$ @eowl, I'm torn between ValueError and a custom error class. \$\endgroup\$ – Winston Ewert Oct 6 '11 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.