Finding vertices in an ordered set of a complete graph

Question

Problem: For an ordered set of edges E of a complete graph Kn, given an edge Ei, find the edge's vertices (v, w)_Ei.

Note: This is likely not a problem specific to graph theory, although it was chosen to express the problem solely because of familiarity. Apologies for any incorrect notation introduced.

Suppose that constructed from a complete graph K5 consisting of vertices 1, 2, 3, 4, 5, we have an ordered set E of the graph's edges, totalling 10 edges. The set E is known to always be ordered as follows:

Ei = (0 < v < n, v < w =< n)

E1 = (1, 2)
E2 = (1, 3)
E3 = (1, 4)
E4 = (1, 5)
E5 = (2, 3)
E6 = (2, 4)
E7 = (2, 5)
E8 = (3, 4)
E9 = (3, 5)
E10 = (4, 5)

For any given Ei, we must now find the vertices (v, w)_Ei using i alone. For example, given 6 we should obtain (2, 4).

Update: Another, perhaps simpler way of expressing this problem is:

n = 5
i = 0

for v = 1 to n - 1
    for w = v + 1 to n
        i++
        print "E" + i + " = " + v + ", " w 


print "E6 = " + findV(6) + ", " + findW(6)

How is this done?

Answer 1

To solve the problem in closed form, we need the formula for the sum of first k numbers: 1 + 2 + ... + k = (k + 1) * k / 2. This gives us a mapping from edge (i, j) to edge index:

from math import ceil, sqrt

def edge_to_index((i, j)):
    return n * (i - 1) + j - i * (i + 1) / 2

We can derive the inverse mapping:

def index_to_edge(k, n):
    b = 1.0 - 2 * n
    i = int(ceil((-b - sqrt(b**2 - 8 * k)) / 2))
    j = k - n * (i - 1) + i * (i + 1) / 2
    return (i, j)

A test:

n = 5

print "Edge to index and index to edge:"
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        k = edge_to_index((i, j))
        print (i, j), "->", k, "->", index_to_edge(k, n)

The output:

Edge to index and index to edge:
(1, 2) -> 1 -> (1, 2)
(1, 3) -> 2 -> (1, 3)
(1, 4) -> 3 -> (1, 4)
(1, 5) -> 4 -> (1, 5)
(2, 3) -> 5 -> (2, 3)
(2, 4) -> 6 -> (2, 4)
(2, 5) -> 7 -> (2, 5)
(3, 4) -> 8 -> (3, 4)
(3, 5) -> 9 -> (3, 5)
(4, 5) -> 10 -> (4, 5)

Answer 2

Let me restate the question I think you're asking so that if this is totally off-topic, you can let me know:

Given an integer k and the series (1, 2), (1, 3), ..., (1, k), (2, 3), (2, 4), ..., (2, k), (3, 4), ..., (k - 1, k) and an index n, return the value of the nth term of this series.

Here's a simple algorithm to solve this problem that is probably not asymptotically optimal. Notice that the first (k - 1) of the pairs start with 1, the next (k - 2) start with 2, the next (k - 3) with 3, etc. To determine what the value of the first element in the pair is, you can keep adding up these numbers (k - 1) + (k - 2) + ... until you end up with a value that is greater than or equal to your index. The number of times you could do this, plus one, gives you your first number:

E1 = (1, 2)
E2 = (1, 3)
E3 = (1, 4)
E4 = (1, 5)
E5 = (2, 3)
E6 = (2, 4)
E7 = (2, 5)
E8 = (3, 4)
E9 = (3, 5)
E10 = (4, 5)

Here, k = 5. To find the first number of term 8, we first add k - 1 = 4, which is less than eight. We then add k - 2 = 3 to get 7, which is still less than eight. However, adding k - 3 = 2 would give us nine, which is greater than eight, and so we stop. We added two numbers together, and so the first number must be a 3.

Once we know what the first number is, you can get the second number quite easily. When doing the step to get the first number, we're essentially listing off the indices of the pairs where the first number changes. For example, in our above case, we had the series 0, 4, 7. Adding one to each of these gives 1, 5, 8, which are indeed the first pairs that start with the numbers 1, 2, and 3, respectively. Once you know what the first number is, you also know where pairs with that number start, and so you can subtract out the index of your number from that position. This tells you, with a zero-index, how many steps you've taken forward from that element. Moreover, you know what the second value of that first element is, because it's one plus the first element, and so you can say that the second value is given by the first number, plus one, plus the number of steps your index is beyond the first pair starting with the given number. In our case, since we are looking at index 8 and we know the first pair starting with a three is at position 8, we get that the second number is 3 + 1 + 0 = 4, and our pair is (3, 4).

This algorithm is actually pretty fast. Given any k, this algorithm takes at most k steps to complete, and so runs in O(k). Compare this to the naive approach of scanning everything, which takes O(k²).

Answer 3

To make my life easier, I'm going to do my math 0-based, not 1-based as in your question.

First, we derive a formula for the index of the term (v,v+1) (the first that starts with v). This is just the arithmetic sum of n-1 + n-2 + ... + n-v, which is v(2n-v-1)/2.

So to find v given the index i, just solve the equation v(2n-v-1)/2 <= i for the largest integral v. Binary search would work well, or you could solve the quadratic using the quadratic formula and round down (maybe, have to think if that ends up working).

Finding the W is easy given V:

findW(i):
  v = findV(i)
  i_v = v(2n-v-1)/2
  return i - i_v + 1

Answer 4

Well, the simple way is to loop through and subtract values corresponding to the first vertex, as follows (in python):

def unpackindex(i,n):
  for v in range(1,n):
    if v+i<=n: return (v,v+i)
    i-= n-v
  raise IndexError("bad index")

If you're looking for a closed-form formula, rather than an algorithm, you will need to do a square root at some point, so it is likely to be messy and somewhat slow (though not as slow as the above loop, for large enough n...). For moderate values of n, you might want to consider a precomputed lookup table, if performance is important.