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 whether there is a tuple operation that performs an undirected comparison of tuples like this:
exp1 = undirected_comp((A,B), (B,A)) #exp1 should evaluate to True
exp2 = undirected_comp((A,B), (A,C)) #exp2 should evaluate to False
not exactly, but in general, you can do this kind of comparison with
set (A,B) == set (B, A)
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
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]: True
In [3]: undirected_comp(('A','B'), ('A','C'))
Out[3]: False
In [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 solution
1000000 loops, best of 3: 674 ns per loop
In [5]: timeit tup1 == tup2 or tup1 == tup2[::-1] # my solution above
1000000 loops, best of 3: 348 ns per loop
In [6]: timeit fs1 == fs2 # frozensets
10000000 loops, best of 3: 120 ns per loop
In [7]: timeit sorted_tup1 == sorted_tup2 # pre-sorted tuples
10000000 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.
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 to false
set((A,B)) == set((B,A)) # evaluates to true
set((A,B) == set((A,C)) # evaluates to false
If you want to use a function, you could do something like this:
def undirected_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)).
