Writing a function to map edges to positive integers

Question

I'm currently writing a program that deals with the manipulation of graphs. For simplicity, the label of each vertex is a positive integer (i.e. 1, 2, ...). For one of the algorithms I'm trying to implement, I need to write a function edgeId(u, v) that takes two vertex numbers u and v and maps the edge (u, v) to a unique positive integer.

Since my algorithm must handle directed and undirected graphs, I have the following stipulations. For directed graphs, edgeId(u, v) must be injective (i.e. edgeId(a, b) = edgeId(c, d) if and only if a = c and b = d). For undirected graphs, it must be symmetric (i.e. edgeId(u, v) = edgeId(v, u), but only those two can map to that positive integer).

Does anyone have an idea on how to implement such a function? Every idea I've had so far has failed because I have no knowledge of the number of vertices in the graph.

Any help would be greatly appreciated!

Keep a dictionary of nodes and the number you assigned to a edge between them? — Lasse V. Karlsen, Dec 04 '14 at 11:58
Wouldn't that be inefficient for a very large number of vertices? — Ryan, Dec 04 '14 at 11:59
Is the number of nodes constant? Or is it an evolving graph? — amit, Dec 04 '14 at 12:00
If you can "know" that the number of nodes/edges will never exceed N, you can calculate a unique integer by using `a*N + b` where `a` and `b` here is a unique number you get from the node itself. — Lasse V. Karlsen, Dec 04 '14 at 12:00
There's Cantors old trick `((x + y)*(x + y + 1)/2) + y` but it has serious downsides — harold, Dec 04 '14 at 12:00
What you need is a hash for two numbers. see [this answer][1] [1]: http://stackoverflow.com/a/919661/159060 — Muhammad Soliman, Dec 04 '14 at 14:59

Bartosz Marcinkowski · Answer 1 · 2014-12-04T15:31:53.140

def undirectedEdgeId(u, v):
    M = max(u, v)
    m = min(u, v)
    return M * (M - 1) / 2 + m

def directedEdgeId(u, v):
    d = undirectedEdgeId(u, v)
    if u < v:
        return 2 * d
    else:
        return 2 * d - 1

What undirectedEdgeId does can be visualised with a table:

3 | 4  5  6
2 | 2  3  5
1 | 1  2  4
u  -- -- --
  v 1  2  3

or in terms of m and M

3 |       6
2 |    3  5
1 | 1  2  4
m  -- -- --
  M 1  2  3

The good thing about these functions is that both can be reversed quite easily.

Writing a function to map edges to positive integers

1 Answers1