Подсчет различных неориентированных ребер в ориентированном графе в SQL

Дана таблица, содержащая ребра в ориентированном графе, например:

CREATE TABLE edges ( 
    from_here int not null, 
    to_there  int not null
)

Каков наилучший способ получить количество различных ненаправленных ссылок для определенного узла? Нет ни дублирующих направленных ребер, ни узлов, напрямую связанных друг с другом, я просто хочу избежать двойного подсчета повторяющихся неориентированных ребер (таких как (1,2) и (2,1)).

Это работает, но NOT IN плохо пахнет для меня:

SELECT COUNT(*)
FROM edges
WHERE from_here = 1
   OR (to_there = 1 AND from_here NOT IN (
        SELECT to_there 
        FROM edges 
        WHERE from_here = 1
   ))

Для этого подходят решения, специфичные для PostgreSQL.


postgresql sql directed-graph
person mu is too short    schedule 10.03.2011    source источник
comment
Верно ли, что для каждого ребра существует обратное ребро? То есть для каждого (1,2) должен существовать (2,1)?   -  person Thomas    schedule 10.03.2011
comment
@Thomas: Нет, направленное ребро-(1,2) не означает направленное ребро-(2,1), могут появиться оба этих направленных ребра, но необходим только один. Набор ребер, например {(1,2),(1,3),(2,1)}, должен давать счетчик, равный 2 (т. е. перенаправить ребра, свернуть дубликаты, вычислить неориентированную степень рассматриваемого узла).   -  person mu is too short    schedule 10.03.2011
comment
В порядке. Тогда мое второе решение должно дать вам то, что вы хотите.   -  person Thomas    schedule 10.03.2011

Ответы (2)


arrow_upward
7
arrow_downward

Если бы для каждого ребра существовало обратное (например, если существует (1,2), то должно существовать и (2,1)), то вы могли бы просто сузить свой список следующим образом:

 Select Count(*)
 From edges
 Where from_here < to_here
    And from_here = 1

Если мы не можем предположить, что обратное ребро всегда существует, вы можете использовать предикат Except:

Select Count(*)
From    (
        Select from_here, to_there
        From edges
        Where from_here = 1
            Or to_there = 1
        Except
        Select to_there, from_here
        From edges
        Where from_here = 1
        ) As Z
person Thomas    schedule 10.03.2011
comment
+10 за то, что научил меня чему-то новому (т.е. ЗА ИСКЛЮЧЕНИЕМ), но я выберу СОЮЗ, так как он немного проще. - person mu is too short; 10.03.2011

arrow_upward

arrow_downward

person    schedule
comment
Верно, результат UNION не содержит повторяющихся строк, если не указана опция ALL. (postgresql.org/docs/current/static/sql -select.html#SQL-ОБЪЕДИНЕНИЕ). Это научит меня не использовать RTFM. - person mu is too short; 10.03.2011
comment
PostgreSQL (по крайней мере, моя версия) требует псевдоним для (... union...), но я добавлю его и пойду с этим, так как этот UNION проще, чем EXCEPT Томаса. - person mu is too short; 10.03.2011