Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Counting distinct undirected edges in a directed graph in SQL

Given a table holding edges in a directed graph like this:

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

What's the nicest way to get the number of distinct undirected links for a specific node? There aren't any duplicate directed edges nor are any nodes directly linked to themselves, I just want to avoid counting duplicate undirected edges (such as (1,2) and (2,1)) twice.

This works but the NOT IN smells bad to me:

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-specific solutions are fine for this.

like image 539
mu is too short Avatar asked Mar 10 '11 19:03

mu is too short


2 Answers

If it were the case that for every edge, there was a reciprocal (e.g. if (1,2) exists, then (2,1) must exist), then you could simply narrow your list like so:

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

If we cannot assume that a reciprocal edge always exists, then you could use the Except predicate:

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
like image 158
Thomas Avatar answered Sep 20 '22 17:09

Thomas


select count(*) from (
  select to_there from edges where from_here = 1
  union
  select from_here from edges where to_there = 1
) as whatever
like image 21
araqnid Avatar answered Sep 16 '22 17:09

araqnid