Efficient both ways mapping in Python with flag values

Question

What is the best data structure to have a both-ways mapping of object, with flag values for each couple, in Python ? For instance, let's imagine I have two pools of men and women I want to match together. I want a datastructure to store de matches so I can access the corresponding man of each woman, the corresponding woman of each man and, let's say, a number representing the value of this couple.

The key feature is that I want to access all of these data with a constant time (about the time of a key-access in a dictionary) without wasting resources for the construction.

If there wasn't for the particularity of the "flag value", a bidict from the library suggested in this post would be absolutely perfect. Indeed, every time I add a couple in my all-stars-couples datastructure, it automatically updates to avoid polygamy :

couples = bidict({ 
    'leonard' : 'penny',
    'howard'  : 'bernadette',
    'sheldon' : 'amy'
})
couples.forceput('stephen', 'amy')
print couples

>> bidict({'stephen': 'amy', 'leonard': 'penny', 'howard': 'bernadette'})

I am now asking for advice on the most efficient and pythonic way to implement a quality feature such that, for instance :

quality('stephen', 'amy')

>> 0.4

couples.forceput('sheldon', 'amy', quality = 1.0)
quality('sheldon', 'amy')

>> 1.0

quality('stephen', 'amy')

>> Raise KeyError

Answer 1

Consider that tuples are hashable. You can create a dict that maps from a couple to whatever data you want, including quality:

quality = dict()
quality[ ('stephen', 'amy') ] = 0.4

Answer 2

Solution 1 : Quick and dirty

Here is a trivial implementation built on top of bidict, done on the suggestions made by adrin and Austin :

class couple ( bidict ) :

    self._flags = {}

    def add ( self, key, val, flag ) :
        try :
            del self._flags[ self._inv[ val ] ]
        except KeyError :
            pass
        self._put(key, val, overwrite_key=True, overwrite_val=True)
        self._flags[ key ] = flag

    def flag ( self, key, val ) :
        if ( self._fwd.get( key ) == val ) :
            return self._flags[ key ]
        else :
            raise KeyError( key, val )

This way, one can obtain the following behaviour :

bbt = couple()
bbt.add( 'stephen', 'amy', 0.4 )
bbt.flag( 'stephen', 'amy' )

>> 0.4

bbt.add( 'sheldon', 'amy', 1.0 )
bbt.flag( 'sheldon', 'amy' )

>> 1.0

bbt.flag( 'stephen', 'amy' )

>> KeyError: ('stephen', 'amy')

Solution 2 : Specific and standalone

Since I finally ended up coding my own structure. It is standalone and can be c/c if needed by anyone passing here :

class FlaggedDoubleMapper :
    """Flagged Double Mapper"""

    def __init__ ( self, keys = [], vals = [], flags = [] ) :
        """Initializes a flagged double mapper with lists of keys, values and
        flags.
        """

        self._flg = {}     # Flags dictionary
        self._fwd = {}     # Forward dictionary
        self._bwd = {}     # Backward dictionary

        for key, val, flag in zip( keys, vals, flags ) :
            self.add( key, val, flag )

    def __repr__ ( self ) :
        """Representation bidict-style."""

        return 'fdm({})'.format( self._fwd )

    def contains ( self, key, val ) :
        """Returns True if and only if self contains the key-val binding."""

        try :
            return ( self._fwd[ key ] == val )
        except KeyError :
            return False

    def add ( self, key, val, flag ) :
        """Adds a flagged binding, overwriting all corresponding bindings."""

        try :
            _val = self._fwd[ key ]
            del self._bwd[ _val ]
        except KeyError :
            pass

        try :
            _key = self._bwd[ val ]
            del self._flg[ _key ]
            del self._fwd[ _key ]
        except KeyError :
            pass

        self._flg[ key ] = flag
        self._fwd[ key ] = val
        self._bwd[ val ] = key

    def remove ( self, key, *args ) :
        """Removes a binding.
         - remove( key ) will send a KeyError( key ) if no binding with key as a
         forward key is found.
         - remove( key, val ) will send a KeyError( key, val ) if no forward
         key-val binding is found.
        """

        try :
            _val = args[0]
            if ( _val != self._fwd[ key ] ) :   # Can raise a KeyError( key )
                raise KeyError( key, _val )
        except IndexError :
            _val = self._fwd[ key ]             # Can raise a KeyError( key )

        del self._flg[ key ]
        del self._fwd[ key ]
        del self._bwd[ _val ]

    def flag ( self, key, *args ) :
        """Returns the flag of a binding.
         - flag( key ) will send a KeyError( key ) if no binding with key as a
         forward key is found.
         - flag( key, val ) will send a KeyError( key, val ) if no forward
         key-val binding is found.
        """

        try :
            _val = args[0]
            if ( _val != self._fwd[ key ] ) :   # Can raise a KeyError( key )
                raise KeyError( key, _val )
        except IndexError :
            pass

        return self._flg[ key ]

Answer 3

Since you use keys that are hashable the immediate solution would be to add a dictionnary that uses a frozenset of {man, woman} as a key and has quality as value.

However, you reach a point where specifying all of your needs and fitting it in a proper object architecture begins to matter. You have here a graph architecture, in the sense that you data is tied to nodes (people name and sex) and links (relations and quality). I would probably borrow or implement a graph structure to represent this, choose the best one depending of speed/memory considerations, and the structure would make future extension an easy task.

Considering you only have one link per node at maximum, and you want an O(1) access to people and their partners, here you would optimize by implementing your graph in this fashion:

class People ():
    def __init__(self, name, sex):
        self.name = name
        self.sex = sex
        self.relationship = None

    def force_link(self, partner, quality = None):
        #You can implement a sex check here for example
        self.relationship = Relationship (quality)
        partner.relationship = self.relationship

class Relationship ():
    def __init__(self, quality):
        #May grow over time
        self.quality = quality

class Graph ():
    def __init__(self):
        # Indexing by name
        self.nodes = { name : People(name, sex) for name, sex in zip(namelist,sexlist) }
        # Linking example
        self.nodes['brandon'].force_link(self.nodes['amy'],0.2)
        # Get quality example
        print (self.nodes['amy'].relationship.quality)