472,805 Members | 3,586 Online

# 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 1920 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)
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

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)
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

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
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:
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... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 2 August 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central... 0 by: erikbower65 | last post by: Using CodiumAI's pr-agent is simple and powerful. Follow these steps: 1. Install CodiumAI CLI: Ensure Node.js is installed, then run 'npm install -g codiumai' in the terminal. 2. Connect to... 0 by: erikbower65 | last post by: Here's a concise step-by-step guide for manually installing IntelliJ IDEA: 1. Download: Visit the official JetBrains website and download the IntelliJ IDEA Community or Ultimate edition based on... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 6 Sept 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central... 0 by: Taofi | last post by: I try to insert a new record but the error message says the number of query names and destination fields are not the same This are my field names ID, Budgeted, Actual, Status and Differences ... 14 by: DJRhino1175 | last post by: When I run this code I get an error, its Run-time error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this - If... 0 by: Rina0 | last post by: I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in... 5 by: DJRhino | last post by: Private Sub CboDrawingID_BeforeUpdate(Cancel As Integer) If = 310029923 Or 310030138 Or 310030152 Or 310030346 Or 310030348 Or _ 310030356 Or 310030359 Or 310030362 Or... 2 by: DJRhino | last post by: Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...