473,320 Members | 1,814 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

querying the number of connected components

I have graph
x y
- -
1 2
2 3
3 1
4 5
and would like to query how many connected components it has (two in
the example -- {1,2,3} and {4,5}). Is it doable with "recursive with"?

Nov 12 '05 #1
9 1956
I don't know graph theory. So, there must be more sophiscated
algorithm.
Anyway, here is a trial code. It will be better to test with more data.

CREATE TABLE connected
(x SMALLINT NOT NULL
,y SMALLINT NOT NULL
)
;

INSERT INTO connected
VALUES
(1, 2)
,(2, 3)
,(3, 1)
,(4, 5)
;

------------------------- Commands Entered -------------------------
WITH
OrderedNumber (n) AS (
SELECT n1*10 + n2
FROM (VALUES 0,1,2,3,4,5,6,7,8,9) p1(n1)
, (VALUES 0,1,2,3,4,5,6,7,8,9) p2(n2)
WHERE n1*10 + n2 < 100
)
,
Recurse (seq, y, con) AS (
SELECT 0, y
, CAST(CASE
WHEN x < y THEN
'00,' || SUBSTR(DIGITS(x),4,2) || ',' ||
SUBSTR(DIGITS(y),4,2)
ELSE '00,' || SUBSTR(DIGITS(y),4,2) || ',' ||
SUBSTR(DIGITS(x),4,2)
END
AS VARCHAR(20)
)
FROM connected
UNION ALL
SELECT seq + 1
, new.y
, SUBSTR(con,1,ni-1) || ',' || SUBSTR(DIGITS(new.y),4,2) ||
SUBSTR(con,ni)
FROM Recurse old
, connected new
, TABLE
(SELECT MAX((n+1)*3)
FROM OrderedNumber odn
WHERE
LOCATE(SUBSTR(DIGITS(new.y),4,2),con) = 0
AND (CASE
WHEN n < (LENGTH(con)+1)/3 THEN
SMALLINT(SUBSTR(con,n*3+1,2))
ELSE 99
END) < new.y
) p(ni)
WHERE seq < 100
AND old.y = new.x
AND p.ni IS NOT NULL
)
,ContainedNode AS (
SELECT s
, con
, SUBSTR(con,n*3+1,2) node
, (LENGTH(c.con)+1)/3 max_n
FROM (SELECT con
, INT(ROWNUMBER() OVER()) s
FROM (SELECT DISTINCT SUBSTR(a.con,4)
FROM Recurse a
) b(con)
) c(con, s)
, TABLE
(SELECT n
FROM OrderedNumber d
WHERE d.n <= LENGTH(c.con)/3
) e
)
SELECT DISTINCT con AS Connected
FROM ContainedNode a
WHERE
NOT EXISTS
(SELECT *
FROM ContainedNode c
WHERE c.s <> a.s
AND c.node = a.node
AND c.max_n >= a.max_n
)
ORDER BY
con
;
--------------------------------------------------------------------

CONNECTED
--------------------
01,02,03
04,05

2 record(s) selected.

Nov 12 '05 #2
If I added following data, previous sample code produced incorrect
rsults.
INSERT INTO connected
VALUES
(6, 8)
,(7, 8)
,(8, 9)
,(8,10)
,(9,10)
;

This is a revised sample. I hope that no more error exist.
------------------------- Commands Entered -------------------------
WITH
OrderedNumber (n) AS (
SELECT n1*10 + n2
FROM (VALUES 0,1,2,3,4,5,6,7,8,9) p1(n1)
, (VALUES 0,1,2,3,4,5,6,7,8,9) p2(n2)
WHERE n1*10 + n2 < 100
)
,
Biconnected (x, y) AS (
SELECT *
FROM connected
UNION
SELECT y, x
FROM connected
)
,
Recurse (seq, y, nodes, link) AS (
SELECT 0, y
, CAST(CASE
WHEN x < y THEN
'00,' || SUBSTR(DIGITS(x),4,2) || ',' ||
SUBSTR(DIGITS(y),4,2)
ELSE '00,' || SUBSTR(DIGITS(y),4,2) || ',' ||
SUBSTR(DIGITS(x),4,2)
END
AS VARCHAR(20)
)
, CAST('0000,'||SUBSTR(DIGITS(x),4,2)||SUBSTR(DIGITS (y),4,2) AS
VARCHAR(100))
FROM Biconnected
UNION ALL
SELECT seq + 1
, new.y
, SUBSTR(nodes,1,(n+1)*3-1)
|| CASE
WHEN SMALLINT(SUBSTR(nodes,n*3+1,2)) = new.y THEN
''
ELSE ',' || SUBSTR(DIGITS(new.y),4,2)
END
|| SUBSTR(nodes,(n+1)*3)
, link || ',' ||
SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(new.y),4, 2)
FROM Recurse old
, Biconnected new
, TABLE
(SELECT MAX(n)
FROM OrderedNumber odn
WHERE

LOCATE(SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(ne w.y),4,2),link) = 0
AND
(CASE
WHEN n < (LENGTH(nodes)+1)/3 THEN
SMALLINT(SUBSTR(nodes,n*3+1,2))
ELSE 99
END) <= new.y
) p(n)
WHERE seq < 100
AND old.y = new.x
AND p.n IS NOT NULL
)
,
ContainedNode AS (
SELECT s
, nodes
, SUBSTR(nodes,n*3+1,2) node
, (LENGTH(c.nodes)+1)/3 max_n
FROM (SELECT nodes
, INT(ROWNUMBER() OVER()) s
FROM (SELECT DISTINCT SUBSTR(a.nodes,4)
FROM Recurse a
) b(nodes)
) c(nodes, s)
, TABLE
(SELECT n
FROM OrderedNumber d
WHERE d.n <= LENGTH(c.nodes)/3
) e
)
SELECT DISTINCT nodes AS Connected_Nodes
FROM ContainedNode a
WHERE
NOT EXISTS
(SELECT *
FROM ContainedNode c
WHERE c.s <> a.s
AND c.node = a.node
AND c.max_n >= a.max_n
)
ORDER BY
Connected_Nodes
;
-------------------------------------------------------------------------

CONNECTED_NODES
--------------------
01,02,03
04,05
06,07,08,09,10

3 record(s) selected.

Nov 12 '05 #3
Tonkuma wrote:
If I added following data, previous sample code produced incorrect
rsults.
INSERT INTO connected
VALUES
(6, 8)
,(7, 8)
,(8, 9)
,(8,10)
,(9,10)
;

This is a revised sample. I hope that no more error exist.
------------------------- Commands Entered -------------------------
WITH
OrderedNumber (n) AS (
SELECT n1*10 + n2
FROM (VALUES 0,1,2,3,4,5,6,7,8,9) p1(n1)
, (VALUES 0,1,2,3,4,5,6,7,8,9) p2(n2)
WHERE n1*10 + n2 < 100
)
,
Biconnected (x, y) AS (
SELECT *
FROM connected
UNION
SELECT y, x
FROM connected
)
,
Recurse (seq, y, nodes, link) AS (
SELECT 0, y
, CAST(CASE
WHEN x < y THEN
'00,' || SUBSTR(DIGITS(x),4,2) || ',' ||
SUBSTR(DIGITS(y),4,2)
ELSE '00,' || SUBSTR(DIGITS(y),4,2) || ',' ||
SUBSTR(DIGITS(x),4,2)
END
AS VARCHAR(20)
)
, CAST('0000,'||SUBSTR(DIGITS(x),4,2)||SUBSTR(DIGITS (y),4,2) AS
VARCHAR(100))
FROM Biconnected
UNION ALL
SELECT seq + 1
, new.y
, SUBSTR(nodes,1,(n+1)*3-1)
|| CASE
WHEN SMALLINT(SUBSTR(nodes,n*3+1,2)) = new.y THEN
''
ELSE ',' || SUBSTR(DIGITS(new.y),4,2)
END
|| SUBSTR(nodes,(n+1)*3)
, link || ',' ||
SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(new.y),4, 2)
FROM Recurse old
, Biconnected new
, TABLE
(SELECT MAX(n)
FROM OrderedNumber odn
WHERE

LOCATE(SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(ne w.y),4,2),link) = 0
AND
(CASE
WHEN n < (LENGTH(nodes)+1)/3 THEN
SMALLINT(SUBSTR(nodes,n*3+1,2))
ELSE 99
END) <= new.y
) p(n)
WHERE seq < 100
AND old.y = new.x
AND p.n IS NOT NULL
)
,
ContainedNode AS (
SELECT s
, nodes
, SUBSTR(nodes,n*3+1,2) node
, (LENGTH(c.nodes)+1)/3 max_n
FROM (SELECT nodes
, INT(ROWNUMBER() OVER()) s
FROM (SELECT DISTINCT SUBSTR(a.nodes,4)
FROM Recurse a
) b(nodes)
) c(nodes, s)
, TABLE
(SELECT n
FROM OrderedNumber d
WHERE d.n <= LENGTH(c.nodes)/3
) e
)
SELECT DISTINCT nodes AS Connected_Nodes
FROM ContainedNode a
WHERE
NOT EXISTS
(SELECT *
FROM ContainedNode c
WHERE c.s <> a.s
AND c.node = a.node
AND c.max_n >= a.max_n
)
ORDER BY
Connected_Nodes
;
-------------------------------------------------------------------------

CONNECTED_NODES
--------------------
01,02,03
04,05
06,07,08,09,10

3 record(s) selected.


Hmm. Too much formatting and string manipulations obfuscate your
solution. Here is some attemt (I have to translate from my RDBMS of
choice to db2):

with SymmetricInput as (
select x,y from input
union
select y,x from input
), TransitiveClosure as (
select x,y, '['||x||','||y||')' AS path from input
union all
select tc.x,i.y, path||'-'||'['||i.x||','||i.y||')'
from input i,TransitiveClosure tc
where tc.y=i.x
-- TO DO: the recursion has to cut off the cycles
-- (don't have Graemes DB2 cookbook printout at hand)
), MonotonicPaths as (
select x,y, '['||x||','||y||')' AS path from TransitiveClosure
where x<y
union all
select tc.x,i.y, path||'-'||'['||i.x||','||i.y||')'
from TransitiveClosure i,MonotonicPaths tc
where tc.y=i.x and i.x<i.y
-- Monotonic paths are acyclic
) select distinct path from MonotonicPaths
where x not in (
select x from MonotonicPaths oo where
length(oo.path)>length(o.path)
) and y not in (
select y from MonotonicPaths oo where
length(oo.path)>length(o.path)
);

Nov 12 '05 #4
You are right.
One of my poor design may be to define data type as number(SMALLINT).
So, I need many conversion from number to char.
Another issue would be that I used two near same information(nodes
column information is contained in link column).

Nov 12 '05 #5
Instead of following the chains, how about working backwards COUNTing
rows that are not part of EXISTSing rows?

Assuming Y will always be more than X:

DECLARE GLOBAL TEMPORARY TABLE Connected (X SMALLINT, Y SMALLINT)
INSERT INTO SESSION.Connected VALUES (1, 2), (2, 3), (3, 1), (4, 5),
(6, 8), (7, 8), (8, 9), (8, 10), (9, 10)

SELECT \
COUNT(*) \
FROM \
SESSION.Connected Outer \
WHERE \
NOT EXISTS \
( \
SELECT \
* \
FROM \
SESSION.Connected Inner \
WHERE \
Inner.Y = Outer.X \
AND Inner.Y > Inner.X \
)
Or

SELECT \
COUNT(*) \
FROM \
( \
SELECT \
X \
FROM \
SESSION.Connected \
EXCEPT \
SELECT \
Y \
FROM \
SESSION.Connected \
WHERE \
Y > X
) A

B.

Nov 12 '05 #6
Try

(1,2)
(1,3)

Your first query returns 2. In general, it is very suspicious that you
can do graph queries with plain (non recursive) SQL.
Brian Tkatch wrote:
Instead of following the chains, how about working backwards COUNTing
rows that are not part of EXISTSing rows?

Assuming Y will always be more than X:

DECLARE GLOBAL TEMPORARY TABLE Connected (X SMALLINT, Y SMALLINT)
INSERT INTO SESSION.Connected VALUES (1, 2), (2, 3), (3, 1), (4, 5),
(6, 8), (7, 8), (8, 9), (8, 10), (9, 10)

SELECT \
COUNT(*) \
FROM \
SESSION.Connected Outer \
WHERE \
NOT EXISTS \
( \
SELECT \
* \
FROM \
SESSION.Connected Inner \
WHERE \
Inner.Y = Outer.X \
AND Inner.Y > Inner.X \
)
Or

SELECT \
COUNT(*) \
FROM \
( \
SELECT \
X \
FROM \
SESSION.Connected \
EXCEPT \
SELECT \
Y \
FROM \
SESSION.Connected \
WHERE \
Y > X
) A

B.


Nov 12 '05 #7
Actually, i have no idea what a graph query is. I was just looking at
the lists for chains as you provided in the original message.

I guess i misunderstood.

B.

Nov 12 '05 #8
Brian Tkatch wrote:
Actually, i have no idea what a graph query is.


"Graph query" is a sloppy name for a "query on a graph structure". A
typical graph query is finding transitive closure. It is will known
that graph queries such as transitive closure can't be answered with
standard SQL means -- you have to use recursive SQL. I can't prove the
same for the number of connected components, though; this is why I was
"suspicious" rather than "sure".

Nov 12 '05 #9
Ah, ok, thanx.

I was just trying a different approach, that is, looking for breaks
rather than chains.

B.

Nov 12 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Ravi Shankar | last post by:
Hi all, I have a calendar application( like Microsoft Outlook) writtn in Java.Whenever an event is created, we can set SMS/EMAIL notification. Hence when an event is created, I am storing that...
6
by: Greg | last post by:
I am working on a project that will have about 500,000 records in an XML document. This document will need to be queried with XPath, and records will need to be updated. I was thinking about...
5
by: Shane | last post by:
I wonder if someone has any ideas about the following. I am currently producing some reports for a manufacturing company who work with metal. A finished part can contain multiple sub-parts to...
1
by: Darren | last post by:
I have a solution that has a number of projects. Each project generates a component and each component depends on a number of other components. What is the best way of managing this dependency so...
4
by: Steve Le Monnier | last post by:
The ADO.NET DataSet is idea for application development, especially if you need disconnected data. DataReader objects are great in the connected environment but are forward only. What do you do...
0
by: roiavidan | last post by:
Hi, I'm having a bit of a problem with a small application I wrote in C#, which uses an Access database (mdb file) for storing financial data. After looking for a similiar topic and failing to...
5
by: alingsjtu | last post by:
Hello, every body. When execute dynamic generated multiple OPENQUERY statements (which linkes to DB2) in SQLServer, I always got SQL1040N The maximum number of applications is already connected...
4
by: Vikrant Pendurkar | last post by:
When i tried to access my application its gives me below error. Microsoft OLE DB Provider for Oracle error '80004005' Oracle client and networking components were not found. These components...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.