Combining match groups
I have a table that represents a series of matches between IDs from another table like this:
CREATE TABLE #matches (
asid1 int,
asid2 int
)
insert into #matches values (1,2)
insert into #matches values (1,3)
insert into #matches values (3,1)
insert into #matches values (3,4)
insert into #matches values (7,6)
insert into #matches values (5,7)
insert into #matches values (8,1)
insert into #matches values (1,8)
insert into #matches values (8,9)
insert into #matches values (8,3)
insert into #matches values (10,11)
insert into #matches values (12,10)
and I want to find groups of matches that are directly or indirectly related to each other.
The result will look like this:
group asid
1 1
1 2
1 3
1 4
1 8
1 9
2 5
2 6
2 7
3 10
3 11
3 12
if I added one more line:
insert into #matches values (7,8)
then that would mean 2 of the above groups would be linked, so I would need an output:
group asid
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 10
2 11
2 12
Any ideas?
Edit: Further research leads me to think that a recursive generic table expression should do the trick ... if I figure out something elegant, I'll post it
source to share
It looks like Disjoint-set is what you need to solve. Here is a list of C # and C ++ implementations.
source to share
If you are using Oracle the CONNECT TO command is great. Tom Keith has a good entry on this, answering what seems to be essentially the same question:
http://www.oracle.com/technology/oramag/oracle/05-may/o35asktom.html
Check out the Expanding the Hierarchy section.
source to share