"undirected" Tuple Comparison

I am currently working on an undirected graph in python, where the edges are represented by tuples (edge between A and B is represented by either (A,B) or (B,A)). I was wondering w

Solution 1:

not exactly, but in general, you can do this kind of comparison with

set (A,B) == set (B, A)

Solution 2:

Sure: undirected_comp = lambda e1,e2: e1==e2 or (e1[1],e1[0])==e2

Since edges are always exactly 2-tuples it should be robust enough, assuming the A and B objects have equality defined.

EDIT (shameless self-promotion): You probably don't want the overhead of creating two set objects for each comparator, especially if this is part of a larger algorithm. Sets are great for look up but the instantiation is much slower: https://stackoverflow.com/a/7717668/837451

Solution 3:

In addition to the solutions using sets, it is easy enough to roll your own comparison function:

In [1]: def undirected_comp(tup1, tup2):
   ...:     return tup1 == tup2 or tup1 == tup2[::-1]

In [2]: undirected_comp(('A','B'), ('B','A'))
Out[2]: TrueIn [3]: undirected_comp(('A','B'), ('A','C'))
Out[3]: FalseIn [4]: undirected_comp(('A','B'), ('A','B'))
Out[4]: True

As noted by mmdanziger, this is faster than the solution with the sets, since you do not have to pay the cost of the set creation.

But if you care about speed and you spend more time on comparing various edges than on creating them, it is probably best not to store the edges as a tuple with arbitrary order, but to pre-process them and store them in a different format. The two best options would probably be a frozenset or a sorted tuple (i.e. by convention, you always store the smallest node first). Some quick timing:

# edge creation, this time is spent only once, so presumably we don't care:
In [1]: tup1 = (1, 2); tup2 = (2, 1)
In [2]: fs1 = frozenset(tup1); fs2 = frozenset(tup2)
In [3]: sorted_tup1 = tuple(sorted(tup1)); sorted_tup2 = tuple(sorted(tup2))

# now time the comparison operations
In [4]: timeit set(tup1) == set(tup2) # Corley's solution1000000 loops, best of 3: 674 ns per loop

In [5]: timeit tup1 == tup2 or tup1 == tup2[::-1] # my solution above1000000 loops, best of 3: 348 ns per loop

In [6]: timeit fs1 == fs2 # frozensets10000000 loops, best of 3: 120 ns per loop

In [7]: timeit sorted_tup1 == sorted_tup2 # pre-sorted tuples10000000 loops, best of 3: 83.4 ns per loop

So assuming that you don't care about the creation time of the edges, storing them as a sorted tuple is the fastest for doing the comparisons. In this case, you only have to do a simple comparison and do not have to compare the backwards case, since the order is guaranteed by the pre-sorting.

Solution 4:

Python tuples are ordered, while python sets are not. You could simply convert the tuples to sets before comparison using set.

(A,B) == (B,A))          # evaluates tofalseset((A,B)) == set((B,A)) # evaluates totrueset((A,B) == set((A,C))  # evaluates tofalse

If you want to use a function, you could do something like this:

defundirected_comp(a,b):
     return (set(a) == set(b))

Edit: I was using cmp() to do comparisons, which was incorrect since it returns 1 if true and -1 if false, rather than boolean. Changed the function to use ==, which should return boolean - if you want 1 and -1, use return cmp(set(a), set(b)).