Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 General SQL Server Forums
 Script Library
 Finding all minimal cyclic paths in the graph

Author  Topic 

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-01 : 05:52:33
Here a code for finding all minimal loops (cyclic paths) in a graph
with vertexes of degree >= 3. Almost obviously that before seeking
for loops we should eliminate from the graph all its vertexes of degree < 3
(degree of a vertex is the number of edges outcoming from the vertex).
Note: there are no any 'parent' - 'child' nodes here. All vertexes are
absolutely equitable.
if object_id('g3')>0 drop table g3
if object_id('g3x')>0 drop table g3x
if object_id('g3y')>0 drop table g3y
if object_id('g3l')>0 drop table g3l
GO
create table g3y(v1 int, v2 int) -- ancillary table
GO
create table g3x(n int, v1 int, v2 int) -- ancillary table
GO
create table g3l(nl int, v1 int, v2 int)
-- table for storing of 'detected' loops
GO
create table g3(v1 int, v2 int)
-- table of test data with pairs of adjoining vertexes
-- each vertex is named by an arbitrary number
GO
insert into g3
select  2,  3 union all
select  2,  4 union all
select  1,  4 union all
select  3,  5 union all
select  5,  6 union all
select  1,  6 union all
select  4,  7 union all
select  6,  8 union all
select  3,  9 union all
select  1,  7 union all
select  2,  7 union all
select  1,  8 union all
select  5,  8 union all
select  2,  9 union all
select  5,  9 ----union all
/*
select  2, 13 union all
select  3, 13 union all
select 13, 14 union all
select 12, 14 union all
select 12, 15 union all
select 11, 15 union all
select 11, 13 union all
select 10, 11 union all
select 10, 12 union all
select 10, 14 union all
select 10, 15
*/
GO
insert into g3 select v2, v1 from g3

declare @i int, @n int, @v1 int, @v2 int
set @i=1

while 0=0
begin
set @n=1
truncate table g3x truncate table g3y
select top 1 @v1=g3.v1, @v2=g3.v2 from g3 left join g3l on
(g3.v1=g3l.v1 and g3.v2=g3l.v2)or(g3.v1=g3l.v2 and g3.v2=g3l.v1)
where g3l.nl is null if @@rowcount=0 break
insert into g3x select @n, @v1, @v2

while @v1<>(select top 1 v2 from g3x order by n desc)
begin
set @n=@n+1
insert into g3x select top 1 @n, v1, v2 from g3 where v2=@v1
and v1<>@v2 and v1=(select top 1 v2 from g3x order by n desc)

if @@rowcount=0
begin
insert into g3x select top 1 @n, v1, v2 from g3 where
v2 not in (select v1 from g3x union all select v2 from g3x) and
v1=(select top 1 v2 from g3x order by n desc) and not exists
(select 0 from g3y where g3y.v1=g3.v1 and g3y.v2=g3.v2)
  if @@rowcount=0
    if @n>2
        begin
        insert into g3y select v1, v2 from g3x where n=@n-1
        delete from g3x where n=@n-1
        set @n=@n-2
        end
     else
        begin insert into g3l select 0, v1, v2 from g3x break end
end
else
   begin
    insert into g3l select @i, v1, v2 from g3x set @i=@i+1
   end
end
end
select * from g3l order by nl

Below is what we get:

nl          v1          v2          
----------- ----------- ----------- 
1           2           3
1           3           5
1           5           6
1           6           8
1           8           1
1           1           4
1           4           2

2           1           6
2           6           8
2           8           1

3           4           7
3           7           1
3           1           4

4           3           9
4           9           2
4           2           3

5           2           7
5           7           4
5           4           2

6           5           8
6           8           6
6           6           5

7           5           9
7           9           3
7           3           5

Of course, in general case not all found by the code loops are minimal.
But this is exactly my approach:
firstly find any possible loops (avoiding excessiveness!!),
then, in WHILE loop, try to mark out minimal loop(s) from intersection of
two non-minimal loops... seems it will be an interesting t-sql job.

X002548
Not Just a Number

15586 Posts
Posted - 2003-10-01 : 11:02:54
Damn...now my head hurts...

How about a brief (and really simple...use small words please) description as to what this is doing...and why..

Practical applications?



Brett

8-)

SELECT @@POST FROM Brain ORDER BY NewId()

That's correct! It's an AlphaNumeric!
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2003-10-01 : 12:27:14
I think he's working up to Hopcroft & Tarjan's graph planarity test in T-SQL (I never understood how that one worked).
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-01 : 15:17:37
LOL, guys... for the last 40-50 minutes I was trying to 'concoct'
an understandable description of what's going on in the code and
failed. Just because my English grows quite messy by the night (only?
I really envy Owais' English :))
Practical applications? No!! I can't even think up any appliance for that.

BTW, my test graph is made of two 'main' triangles (the second one is
commented) and these triangles are joined to each other by two
edges: (2, 13) and (3, 13). If you remove one of these edges then
you get two sub-graphs (I don't know right math's terms) joined
by one 'bad' edge which is not owned by any loop. And my code
neatly recognizes such 'bad' edges, otherwise it would get stuck
in deadlock state... omg I'm going crazy on this stuff...
Go to Top of Page

X002548
Not Just a Number

15586 Posts
Posted - 2003-10-01 : 15:20:13
Stoad....

Dude...

You need to go down to a local bar and talk to the first woman you find...



Brett

8-)

SELECT @@POST FROM Brain ORDER BY NewId()

That's correct! It's an AlphaNumeric!
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-01 : 16:31:03
quote:
and talk to the first woman you find...

Talk about cyclic paths in the graph???
Hm... Seems this kind of talking will cost me a sum,
plus, it may turn out to be a quite dangerous conversation... LOL
Go to Top of Page

robvolk
Most Valuable Yak

15732 Posts
Posted - 2003-10-01 : 20:38:42
You never know, you might bump into a hot mathematician babe.
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-02 : 07:15:16
LOL, Rob,

two wet blankets in one barroom... it's too much :)

Now back to our loops. Suppose we got the following two loops
(along with many other ones):

(1, 2)(2, 3)(3, 4)(4, 5)(5, 6)(6, 7)(7, 1)

and

(2, 3)(3, 4)(4, 5)(5, 2)

'Subtracting' lesser-length loop from another loop we get some new
chain of edges. And, if length of this chain is lesser than the length
of the bigger loop, then, obviously, this new chain is a loop as well.
And, if the length of this new loop is lesser than the length of the
bigger loop, then we can safely delete the bigger old loop from the
table of loops (g3l) and replace it with the new smaller loop.
It's just our sample case:

Loop1 - Loop2 = (1, 2)(2, 5)(5, 6)(6, 7)(7, 1)

Processing in this manner, in WHILE cycle, all possible combinations
of two loops, in the long run we get only minimal loops of the graph.

This is my basic idea, not implemented so far.
Go to Top of Page

mohdowais
Sheikh of Yak Knowledge

1456 Posts
Posted - 2003-10-02 : 14:58:03
WOW, Vit, you really flatter me . I go away for a week and this is what I come back to, people pulling my leg...I think my English is pretty mediocre, if you really want to envy someone, it should be Rob, Jeff or Sam

Btw, I really can't comprehend what you've done here (I am a business grad), but it sure looks complicated, must be one of those astronomy things!

Owais


Make it idiot proof and someone will make a better idiot
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-02 : 15:19:08
OMG, Owais,

I can't tell your written English from rrb's poetic English.

Secondly, seems I should draw this unhappy graph on a sheet of
paper, then scan it and post here the picture :)
Go to Top of Page

mohdowais
Sheikh of Yak Knowledge

1456 Posts
Posted - 2003-10-03 : 07:37:29
I dont think rrb's gonna be very happy about that comparision...

Make it idiot proof and someone will make a better idiot
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-03 : 07:51:54
LOL, Owais, here a picture for you. Does it look like night starry sky?
This is a sample graph with 12 vertexes marked by numbers from 1 to 12.
It has 18 following edges:
(4, 7) (7, 1) (1, 10) (10, 2) (2, 9) (9, 4) (4, 6) (7, 8) (1, 12)
(5, 12) (2, 11) (9, 3) (10, 12) (5, 8) (5, 11) (3, 11) (3, 6) (6, 8)
You can easily see that the graph has 7 minimal cyclic paths in it.
For example, the loop going along sides of the inner pentagon:
(8, 5) (5, 11) (11, 3) (3, 6) (6, 8)
And we have to find all these 7 loops of this graph.
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-03 : 09:38:42
INCREDIBLE!!
Honestly speaking, up to the last moment I didn't believe that it can be done.
My new code finds all minimal (only) loops + (as extra bonus) the loop along
edges of the outer border of a graph. BTW, seems it can be also used for
checking of planarity of a graph (cheers, Arnold!), because only for planar
graphs there is the simple equation:
(Number of Loops) = (Number of Edges) - (Number of Vertexes) + 1
Here the result of the new code below for the sample graph on the picture:
nl          ce
----------- ---------------------------------
1           (1 10)(10 12)(12 1)
2           (2 9)(9 3)(3 11)(11 2)
3           (3 6)(6 4)(4 9)(9 3)
4           (4 7)(7 8)(8 6)(6 4)
5           (5 8)(8 7)(7 1)(1 12)(12 5)
6           (5 11)(11 2)(2 10)(10 12)(12 5)
7           (4 7)(7 1)(1 10)(10 2)(2 9)(9 4)
8           (6 8)(8 5)(5 11)(11 3)(3 6)
---------------------------------------------

if object_id('g3')>0 drop table g3
if object_id('g3x')>0 drop table g3x
if object_id('g3y')>0 drop table g3y
if object_id('g3l')>0 drop table g3l
GO
create table g3y(n int, v1 int, v2 int)
GO
create table g3x(n int, ne int, v1 int, v2 int)
GO
create table g3l(nl int, ne int, v1 int, v2 int, ce varchar(80))
GO
create table g3(ne int, v1 int, v2 int)
GO
insert into g3 (v1, v2)
select  4,  7 union all
select  7,  1 union all
select  1, 10 union all
select 10,  2 union all
select  2,  9 union all
select  9,  4 union all
select  4,  6 union all
select  7,  8 union all
select  6,  8 union all
select  1, 12 union all
select  5, 12 union all
select  2, 11 union all
select  9,  3 union all
select 10, 12 union all
select  5,  8 union all
select  5, 11 union all
select  3, 11 union all
select  3,  6
GO
update g3 set ne=(select count(*) from g3 g
where (g.v1=g3.v1 and g.v2<=g3.v2) or g.v1<g3.v1)
insert into g3 select ne, v2, v1 from g3
declare @i int, @n int, @nemax int, @ne int, @ns int,
@v1 int, @v2 int, @ce varchar(80), @f int
set @nemax=(select max(ne) from g3)
set @ns=2 set @i=1

while 0=0
begin
set @f=0 set @ns=@ns+1 set @ne=0

while @ne<@nemax
begin
set @ne=@ne+1
select @v1=v1, @v2=v2 from g3 where ne=@ne and v1<v2 and
not exists (select 0 from g3l where ne=@ne)

if @@rowcount>0
begin
set @f=1 set @n=1
truncate table g3x truncate table g3y
insert into g3x select @n, @ne, @v1, @v2

while 0=0
begin
set @n=@n+1
       insert into g3x select top 1 @n, ne, v1, v2 from g3 where
       v2 not in (select v1 from g3x union all select v2 from g3x) and
       v1=(select top 1 v2 from g3x order by n desc) and not exists
       (select 0 from g3y where g3y.v1=g3.v1 and g3y.v2=g3.v2)
   if @@rowcount=0
       if @n>2
          begin
          insert into g3y select n, v1, v2 from g3x where n=@n-1
          delete from g3x where n=@n-1 delete from g3y where n>@n-1
          set @n=@n-2
          end
        else break
   else
      if @n=@ns-1
        begin
        insert into g3x select top 1 @n, ne, v1, v2 from g3 where v2=@v1
        and v1<>@v2 and v1=(select top 1 v2 from g3x order by n desc)
           if @@rowcount=0
                begin
                insert into g3y select n, v1, v2 from g3x where n=@n
                delete from g3x where n=@n
                set @n=@n-1
                end
            else
               begin
                 insert into g3l select @i, ne, v1, v2, '' from g3x
                 set @i=@i+1 break
               end
        end
end
end	
end
if @f=0 break
end

delete from g3 where ne in
(select ne from g3l group by ne having count(*)>1)

while 0=0
begin
set @n=1 truncate table g3x
insert into g3x select top 1 @n, ne, v1, v2 from g3 where v1<v2
if @@rowcount=0 break
delete from g3 where ne=(select ne from g3x)

while 0=0
begin
set @n=@n+1
       insert into g3x select top 1 @n, ne, v1, v2 from g3
       where v1=(select v2 from g3x where n=@n-1)
       delete from g3 where ne=(select ne from g3x where n=@n)
set @f=0
set @f=
(select n from g3x where v1=(select v2 from g3x where n=@n))
    if @f>0
     begin
       insert into g3l select @i, ne, v1, v2, '' from g3x
       where n>=@f set @i=@i+1
       delete from g3x where n>=@f set @n=@f-1
       if @n=0 break
     end
end
end

set @n=0
while @n<(select max(nl) from g3l)
begin
set @ce='' set @n=@n+1
select
@ce=@ce+'('+cast(v1 as varchar(8))+' '+cast(v2 as varchar(8))+')'
from g3l where nl=@n
update g3l set ce=@ce where nl=@n
end
select distinct nl, ce from g3l order by nl
Go to Top of Page

mohdowais
Sheikh of Yak Knowledge

1456 Posts
Posted - 2003-10-06 : 00:44:47
Cheers Stoad, you are now a real scientist!!

When was the last time you were on a date?

wais

Make it idiot proof and someone will make a better idiot
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-06 : 02:54:27
LOL, Owais,

... on a date? Guess it was (if any :)) somewhere in the last century...
Go to Top of Page

X002548
Not Just a Number

15586 Posts
Posted - 2003-10-14 : 11:29:15
Have you seen this site...
not only do the get in to some heavy duty math..it's all sql server baby

http://skyserver.sdss.org/en/skyserver/

EDIT AND they give you the ability through the browswer to query their database...

You can even get at the catalog...or used to...



Brett

8-)

EDIT: It took awhile to find it...but here it is...

http://skyserver.sdss.org/en/tools/search/sql.asp

The put a timelimit on queries so you don't hose the box....

They say it 818 gb with billions of rows...

Now that's scaling up...

or is it out?
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2003-10-14 : 16:18:20
LOL

Brett,

you scared me to my guts (?)... astronomy... maths... graphs... quazars.
Ugh... All these nice sites end up with Buy this excellent book, then Buy that
still better superb!! book... In short, I'm in the 451° F mood.
Today I googled 'algorithms' mistakingly typing 'algorythms' instead and it was
a narrow escape from the mob of dirty punks... guess I'm lucky having pictures
turned off in my browser.
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts
Posted - 2007-01-12 : 09:02:54
I have found a use or this (under the cirumstance that the paths are one-way only).

Assume you are responsible for an online apartment swap site. Every user has an apartment that he wants to get rif of by swapping to another (can be same city or another city).
Then you can have a button on the web page named "Get me all apartments that are suitable for me".
First you get all direct swaps (vertexes = 2).
The you can get all swaps with vertexes = 3.

For example:
You have an apartment in New York, but want to move to Los Angeles. You find an apartment in LA, but that user want to move to Miami. Luckily, there is a third user who has an apartment in Miami who wants to move to New York.
There you have a 3rd degree swap!


Peter Larsson
Helsingborg, Sweden
Go to Top of Page
   

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources

Articles

Forums

Blogs

Contact Us

About the Site