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

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

9 голосов
/ 10 марта 2011

Учитывая таблицу, содержащую ребра в ориентированном графе, как это: 

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 решения подходят для этого.

Ответы [ 3 ]

7 голосов
/ 10 марта 2011

Если бы для каждого ребра имелось обратное значение (например, если (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
6 голосов
/ 10 марта 2011 
select count(*) from (
  select to_there from edges where from_here = 1
  union
  select from_here from edges where to_there = 1
) as whatever
1 голос
/ 27 апреля 2012 
SELECT COUNT(DISTINCT CASE to_here WHEN 1 THEN from_here ELSE to_here END)
FROM edges
WHERE from_here = 1
   OR to_here = 1
/* or WHERE 1 IN (from_here, to_here) */
...