------------------------------------------------------------------------------------ -- SQLPEDIA.pl Jakub Kasprzak 2014-05-08 -- grafy cykliczne ------------------------------------------------------------------------------------ ---- dane testowe use tempdb go create table dbo.Node ( Name char(1) PRIMARY KEY, X int, Y int, FO bit ) go create table dbo.Edge ( Id int Identity(1,1) PRIMARY KEY, Node1 char(1), Node2 char(1), Metric int ) go Insert into Node(Name,FO,X,Y) VALUES ('A',1,9,12),('B',0,10,4),('C',0,17,17),('D',0,26,15),('E',0,30,9),('F',0,2,7),('G',0,27,2),('H',1,34,6),('I',0,37,11),('J',0,44,6),('Z',0,19,5); Insert into Edge(Node1,Node2,Metric) VALUES ('A','F',1),('A','B',1),('A','C',2),('A','Z',3),('C','Z',1),('C','D',1),('D','E',1),('Z','E',5), ('Z','B',1),('E','H',1),('H','I',1),('H','J',1),('Z','G',1) select * from NODE select * from EDGE ------------------------------------------------------------------------ ------ wizualizacja danych SPATIAL select *, GEOMETRY::STGeomFromText('LINESTRING(' + cast(n1.X as char(2)) + ' ' + cast(n1.Y as char(2))+ ', ' + cast(n2.X as char(2)) + ' ' + cast(n2.Y as char(2)) + ')', 4326) as Links FROM EDGE e inner join NODE n1 on e.Node1=n1.Name inner join NODE n2 on e.Node2=n2.Name order by n1.Name desc ------------------------------------------------------------------------ ------ wszystkie ścieżkie z A>Z set statistics IO ON; WITH Edges AS ( -- graf nieskierowany więc bierzemy pod uwagę A-Z i Z-A SELECT Node1 as Start, Node2 as Koniec, Metric from EDGE UNION SELECT Node2, Node1 , Metric from EDGE ), Paths as ( -- rekurencyjne CTE SELECT start , koniec , CAST('.' + start + '.' + koniec + '.' as varchar(max)) as paths, 1 as Dist FROM Edges UNION ALL SELECT f.start, t.koniec , CAST(f.paths + t.koniec + '.' as varchar(max)), F.dist+1 FROM Paths as F join Edges T on -- wykluczenie cykli, czyli nie przechodzimy przez żaden wierzchołek dwukrotnie case when F.paths like '%.' + T.koniec + '.%' then 1 else 0 end = 0 and f.koniec = T.start ) SELECT * FROM Paths WHERE Start = 'A' and Koniec = 'Z' ORDER BY Dist; WITH Edges AS ( -- graf nieskierowany więc bierzemy A-Z i Z-A SELECT Node1 as Start, Node2 as Koniec, Metric from EDGE ), Paths as ( select start , koniec , CAST('.' + start + '.' + koniec + '.' as varchar(max)) as paths, 1 as Dist, Metric from Edges UNION ALL select f.start, t.koniec , CAST(f.paths + t.koniec + '.' as varchar(max)), F.dist+1, F.Metric + T.Metric from Paths as F join Edges T on case when F.paths like '%.' + T.koniec + '.%' then 1 else 0 end = 0 and f.koniec = T.start ), PathRanking as ( select *, DENSE_RANK() OVER(Partition BY Start, Koniec Order by Metric, Dist) as RNK from Paths) Select * from PathRanking where start = 'A' and koniec = 'Z'; drop table dbo.Node drop table dbo.Edge