Click here to Skip to main content
15,566,394 members
Please Sign up or sign in to vote.
5.00/5 (2 votes)
I'm trying to find a way to get a most granular vertex based on criteria in the path of the graph.

Giving the following tree:

and the following metadata description: (test)
label     h
---------------
h         1
a         1
p         2
b         2
s         3
q         4
z         4

and the following relationship table: (test_rel)
l       p          Hops
-----------------------------
H       Null            Null
A       Null            Null
P       H               1
B       A               1
S       P               1
S       B               1
Q       S               1
Z       S               1
Q       P               2
Q       H               3
Z       B               2
Z       A               3
S       H               2
S       A               2

Note: there is no route from z to h or q to a.

I'm trying to write a SQL query that will allow me have a temp table that define a level in the graph, and the ID (or 0 for all) and find all the children.

Here is what I came up with (which is not working) :(


    -- Insert statements for procedure here
create table #aa (id varchar(10), h int)
insert into #aa values ('h',1)
insert into #aa values ('p',2)
insert into #aa values ('0',3)
insert into #aa values ('0',4)
;


WITH GHierarchy (id, parentID, HierarchyLevel) AS
(
   -- Base case
   SELECT distinct 
		l,
		
		'',
		
		1
   FROM test_rel inner join test on label = l
	inner join #aa on test_rel.l = case when #aa.id='0' then test.label else #aa.id end  and #aa.h = 1
   
   WHERE 
	
	test.h = 1 
	
	
   UNION ALL

   -- Recursive step
   SELECT
      e.l,
      e.p,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM GHierarchy eh inner join test_rel e on eh.id = e.p
	
		inner join test_rel hops on hops.p = eh.id and hops.hops = 4 - eh.HierarchyLevel 
		inner join #aa on  e.l = case when #aa.id='0' then e.l else #aa.id end  and HierarchyLevel+1 = #aa.h
	where e.hops = 1
	
	  

)

select distinct * from GHierarchy
order by HierarchyLevel

drop table #aa


With this query - I get both 'q' and 'z' however - there is no path for h->p->s->z

Thanks!!

Rimon
Posted
Updated 2-May-10 12:17pm
v3

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900