# How to find index of ordered pair

Suppose i have an undirected graph with V vertices, i need to store somehow flags for all possible edges, for now i have chosen bit-array of length $\tbinom n2$.

So, question is, how to find index of an edge if i have two indices of vertices?

I can assume what all edges have first vertex with lower index than second.

Manually i have built this formula $\left [V(v_1 - 1) - \frac{v_1(v_1 - 1)}{2}\right ] + v_2,$ where $v_2 < v_1.$ But may be there some theory in behind and exists nicer and easier to calculate formula, i need it for programming reasons and need best possible performance. Thanks.

-

In a more general setting, the problem can be described as follows: Assume $X$ is some set of size $n$. To deal with the elements of $X$ on a computer, we want to uniquely associate each element of $X$ a "rank", which is number in $\{0,\ldots,n-1\}$. For the computation of the rank there should be a fast algorithm, and moreover we also want a fast algorithm "unrank" which translates the rank number back to the associated object.

For many combinatorial sets $X$, suitable algorithms can be found in the book Combinatorial Algorithms: Generation, Enumeration and Search by Donald L. Kreher and Douglas R. Stinson. Often, for a given set $X$ more than one rank function is discussed (since the requirements may not always be the same, like lexicographic order, Gray Code order etc.).

In your case, $X$ is the set of all two-element subsets of the vertex set $\{1,\ldots,n\}$. This is discussed in Section 2.3 "$k$-element subsets" in the book.

-

Just store the graph as an adyacency matrix, and be done. Unless the number of vertices is astronomical, this should work fine.

-
for some tasks it is good approach. – Yola Mar 7 '13 at 9:07