Computing minimum path lengths in an SQL table

Question

I'm having a problem with this exercise:

Table Friend:

 Friend1     Friend2

Table Relationship:

 Friend1     Friend2      GradeOfFriendship

I need to create a trigger in which I must obtain symmetric tuple, for example:

Luc    Mark

Mark   Luc

in both tables.

If there is a direct contact between two people then their GradeOfFriendship = 1

If there is no contact between a pair of people then GradeOfFriendship = 0.

In other cases the GradeOfFriendship must be calculated as the minimum distance over all possible paths connecting these two people (we must consider this table as a directed graph)

My problem is not to obtain a symmetric tuple, but how to calculate all the possible paths between two people. For example:

   Luc     Marc 1
   Marc    John 1
   Luc     John 2

I am using SQL Server. At the moment I don't have any idea how solve this problem - I think that I must use some recursive function but I don't know how....

Answer 1

This is an outer join between friends and grades

Answer 2

This is one way to create recursive fried network:

;with DATA as (
  select Person1, Person2, 1 as Grade from Friends
  union
  select Person2, Person1, 1 as Grade from Friends
),
CTE as (
  select Person1, Person2, Grade,
    convert(varchar(max), '|' + Person1 + '|' + Person2 +'|') as Path
    from DATA
  union all
  select C.Person1, D.Person2, C.Grade+1, C.Path+D.Person2+'|' 
  from CTE C join DATA D on C.Person2 = D.Person1
  where C.Person1 <> D.Person2 and C.Path not like '|%'+D.Person2 +'%|'
)

select Person1, Person2, min(Grade)
from CTE
group by Person1, Person2
order by 1,3,2

The first CTE called DATA is there so that there's no need to have friedships entered both ways into friend table. If you have them that way already, you can leave it out.

The second CTE called CTE is recursive, and it fetches all the paths from one person to another. The path -column with names separated by | is there to prevent endless loops when friendships make circles.

The final select picks only the shortest path between friends.

Example in SQL Fiddle