Counting distinct undirected edges in a directed graph in SQL

Question

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.

Ringhals

Is it the case that for every edge there is a reciprocal edge? I.e., for every (1,2), there must exist a (2,1)? – Louanneloucks

@Thomas: No, directed-edge-(1,2) does not imply directed-edge-(2,1), both of those directed edges may appear but only one is necessary. An edge set like {(1,2),(1,3),(2,1)} should yield a count of 2 (i.e. undirect the edges, collapse duplicates, compute undirected degree of the node in question). – Ringhals

Ok. Then my second solution should give you what you want. – Louanneloucks

Answer 1

select count(*) from (
  select to_there from edges where from_here = 1
  union
  select from_here from edges where to_there = 1
) as whatever

Cordalia

Right, "The result of UNION does not contain any duplicate rows unless the ALL option is specified." (postgresql.org/docs/current/static/sql-select.html#SQL-UNION). That'll teach me not to RTFM. – Ringhals

PostgreSQL (at least my version) wants an alias for the "(... union ...)" but I'll add that and go with this one as this UNION is simpler than Thomas's EXCEPT. – Ringhals

Answer 2

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

Louanneloucks

+10 for teaching me something new (i.e. EXCEPT) but I'm going to go with the UNION as it is a bit simpler. – Ringhals

Answer 3

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) */

Crichton