Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
    
for some tasks it is good approach. –  Yola Mar 7 '13 at 9:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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