An algorithm for finding converse duplicates of ordered pairs

Question

Given an array of ordered pairs of values, what algorithm will find converse duplicates? [Converse meaning the same values, but in the opposite order.]

That is, given [ab,ac,ad,bc,bd,ca,db] is there an efficient way to find ca and db, being the converse duplicates for ac and bd?

The application is simple enough: the ordered pairs are edges in a directed graph and if there is a converse edge then a single double-ended edge is to be drawn rather than one edge in each direction. The values are strings, being node names.

It can be viewed as a lookup in a sparse array. Given coordinates (a,b), check whether (b,a) exists. However, common programming languages do not (appear to) provide sparse 2d arrays.

I have written a solution in ruby using hash-of-hash, but it's about 20 lines of awkward code and an unsatisfying outcome. Writing the same code in a language like C# or Java would be longer. A better solution is sought, in pseudocode or a description (steps) of the algorithm. Either way, I am seeking an answer that describes how to find the solution as well as the benefits and drawbacks of the particular algorithm.

---

I haven't attempted to define 'efficient' or 'better', and performance is not an overriding consideration for a drawing of a few hundred nodes.

The nodes are not sorted, so the default algorithm would be, for each pair, to form the converse and brute-force search the preceding half. A binary search would require a prior sort. A solution based on hash indexing should be much faster.

Answer 1

Just collect the pairs in a set. (In Ruby, it will be a Set of two-element Arrays.)

let Set s = {}
for each pair [a,b]
   if s contains [a,b]
      // duplicate, do nothing
   else if s contains [b,a] // converse duplicate
      ...
   else
      add [a,b] to S

If you are writing Ruby, it is already capable of using arrays

Answer 2

This is the code for my ruby implementation. The output is in a format intended for Graphviz.

  graph_edges = {}
  fmap.keys.sort.each do |srckey|
    forms = fmap[srckey]
    fsrc = $1 if srckey =~ /---/
    forms.keys.each do |fkey|
      fdest = $1 if fkey =~ /---/
      if fdest
        if graph_edges[fdest] && graph_edges[fdest][fsrc]
          graph_edges[fdest][fsrc] = :both
        else
          graph_edges[fsrc] ||= {}
          graph_edges[fsrc][fdest] ||= :only
        end
      end
    end if fsrc
  end
  fout3.puts "digraph {"
  graph_edges.each do |fsrc,h| 
    h.each_pair do |fdest,dir| 
      dirs = " [dir = both]" if dir == :both
      fout3.puts "  #{fsrc} -> #{fdest}#{dirs};" 
    end
  end
  fout3.puts "}"

Hopefully there is something useful here. I shall be working on something better based on a tuple value hash.

Answer 3

Here's a working solution with decent performance.

ordered = lambda x, y: (x, y) if x <= y else (y, x)

def makeArrows(edges):
  """
  input: a sequence of (src, dst) pairs, maybe some reciprocal.
  output: generator yielding (src, dst, is_double_ended) triples.
  """
  undirected_edges = set()
  for src, dst in edges:
    edge = ordered(src, dst)  # both 'ab' and 'ba' become ('a', 'b') here
    if edge in undirected_edges:
      # we found a reciprocal; there can only be one pair like 'ab' + 'ba',
      # so we remove it and output as double-ended
      undirected_edges.remove(edge)
      yield (src, dst, True)
    else:
      # accumulate an edge and wait; a reciprocal might be ahead
      undirected_edges.add(edge)
  # all edges not removed by now are one-ended
  for (src, dst) in undirected_edges:
    yield (src, dst, False)

Now we can try it. Since Python strings are sequences, here I short-cut 'ab' instead of ('a', 'b').

raw_edges = ['ab', 'ac', 'ad', 'bc', 'bd', 'ca', 'db']

>>> list(makeArrows(raw_edges))
[('c', 'a', True), ('d', 'b', True), ('b', 'c', False), ('a', 'b', False), ('a', 'd', False)]

Answer 4

Here's a way...in python

ordered = lambda x, y: (x, y) if x <= y else (y, x)

def make_hash(edges):
    edge_hash = {}
    for x,y in edges:
        edge = ordered(x, y)
        edge_hash[edge] = edge_hash.setdefault(edge, 0) + 1
    return edge_hash

edges = ['ab', 'ac', 'ad', 'bc', 'bd', 'ca', 'db']

for edge, count in make_hash(edges).items():
    print ''.join(edge), 'uni' if count == 1 else 'bi'

It creates a dictionary (hash) that is indexed by the sorted order of the edges. If there are two entries, we know it is has a converse duplicate. If only one, it is not. The dictionary is returned and the count of matching (in any order) entries.