Запись функции для привязки ребер к целым положительным числам

Question

В настоящее время я пишу программу, которая занимается манипуляцией графиками. Для простоты метка каждой вершины является положительным целым числом (т.е. 1, 2, ...). Для одного из алгоритмов, которые я пытаюсь реализовать, мне нужно написать функцию edgeId(u, v), которая принимает два вершинных номера u и v и отображает ребро (u, v) на уникальное положительное целое число.

Поскольку мой алгоритм должен обрабатывать направленные и неориентированные графики, у меня есть следующие положения. Для ориентированных графов edgeId(u, v) должен быть инъективным (то есть edgeId(a, b) = edgeId(c, d) тогда и только тогда, когда a = c и b = d). Для неориентированных графов он должен быть симметричным (т. Е. edgeId(u, v) = edgeId(v, u), но только эти два могут отображать это положительное целое число).

У кого-нибудь есть идея о том, как реализовать такую ​​функцию? Каждая идея, которая у меня была до сих пор, потерпела неудачу, потому что я не знаю количества вершин на графике.

Любая помощь была бы принята с благодарностью!

Answer 1

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 

Что undirectedEdgeId это может быть визуализированы с таблицей:

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

или с точки зрения m и M

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

Хорошая вещь об этих функциях является то, что оба могут быть отменены довольно легко.