1

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.

  • I don't fully understand the question. So you want to find a pair of pairs of values (x,y) and (z,t) such that z, t are the lexicographical inverse of x and y? – InformedA Jul 2 '14 at 8:05
  • 2
    How fast do you want it to be? simply checking each edge for its converse with a binary search is O(n log n), which is usually considered efficient. So what complexity are you trying to achieve? – Frank Jul 2 '14 at 10:22
  • @randomA: No, I want to find all pairs of pairs such as (x,y) and (y,x), and handle them differently (draw double-ended arrow). – david.pfx Jul 2 '14 at 14:01
  • @Frank: See edit. – david.pfx Jul 2 '14 at 14:02
  • 2
    Create two hash values from each tuple. First hash is computed from an ordered-tuple hash function; Second hash is computed from the reversed tuple using the same ordered-tuple hash function. (This is actually a quite elementary algorithm design question.) – rwong Jul 2 '14 at 14:02
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

  • We must have different definitions of trivial. I do not see that f() performs any sorting function. I do not see explanations of the xxx-edge() functions. I do not see any output of converse duplicates. In short, I do not see a solution. – david.pfx Oct 2 '14 at 23:05
-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.

-2

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)]
-2

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.

  • 3
    Programmers.SE encourages questions that explain the why behind the how. Your answer would be much stronger if you stated how your suggested algorithm addresses the OP's concerns and how this approach is superior to other approaches. – GlenH7 Apr 2 '15 at 1:14

protected by gnat Apr 2 '15 at 11:24

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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