How to Find All Connected Subgraphs in an Undirected Graph Using SQL?

How to find all connected subgraphs of an undirected graph

Problem Definition:
Given an undirected graph represented by a table with two columns, Identifier1 and Identifier2, where each row represents an edge between the two identifiers, the task is to find all the connected subgraphs in the graph. A connected subgraph is a set of identifiers that are linked directly or indirectly by other identifiers. The output should include the identifiers in each subgraph and assign a unique group ID to each subgraph.

Query to Find Connected Subgraphs:

<code class="sql">WITH
CTE_Idents
AS
(
    SELECT DISTINCT
        CASE WHEN Ident1 IS NOT NULL THEN Ident1 ELSE Ident2 END AS Ident
    FROM EdgeTable
),
CTE_Pairs
AS
(
    SELECT Ident1, Ident2
    FROM EdgeTable
),
CTE_Recursive
AS
(
    SELECT
        CAST(AnchorIdent AS VARCHAR(8000)) AS AnchorIdent,
        Ident1,
        Ident2,
        CAST(',' + Ident1 + ',' + Ident2 + ',' AS VARCHAR(8000)) AS IdentPath,
        1 AS Level
    FROM CTE_Pairs
    INNER JOIN CTE_Idents ON CTE_Idents.Ident = CTE_Pairs.Ident1
    UNION ALL
    SELECT
        CTE_Recursive.AnchorIdent,
        CTE_Pairs.Ident1,
        CTE_Pairs.Ident2,
        CAST(CTE_Recursive.IdentPath + CTE_Pairs.Ident2 + ',' AS VARCHAR(8000)) AS IdentPath,
        CTE_Recursive.Level + 1
    FROM CTE_Pairs
    INNER JOIN CTE_Recursive ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE CTE_Recursive.IdentPath NOT LIKE CAST('%,' + CTE_Pairs.Ident2 + ',%' AS VARCHAR(8000))
)
SELECT
    CTE_Idents.Ident,
    CASE WHEN CA_Data.XML_Value IS NULL THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END AS GroupMembers,
    DENSE_RANK() OVER(ORDER BY CASE WHEN CA_Data.XML_Value IS NULL THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END) AS GroupID
FROM CTE_Idents
CROSS APPLY
(
    SELECT CTE_CleanResult.Ident + ','
    FROM CTE_CleanResult
    WHERE CTE_CleanResult.AnchorIdent = CTE_Idents.Ident
    ORDER BY CTE_CleanResult.Ident FOR XML PATH(''), TYPE
) AS CA_XML(XML_Value)
CROSS APPLY
(
    SELECT CA_XML.XML_Value.value('.', 'NVARCHAR(MAX)')
) AS CA_Data(XML_Value)
WHERE CTE_Idents.Ident IS NOT NULL
ORDER BY Ident;</code>

Explanation:

• CTE_Idents: This Common Table Expression (CTE) identifies all distinct unique identifiers in both the Identifier1 and Identifier2 columns.
• CTE_Pairs: It extracts and combines edges from the EdgeTable to represent all unique pairs of identifiers.
• CTE_Recursive: This recursive CTE traverses the graph starting from each unique identifier, building a comma-separated path of connected identifiers. It stops when a loop is detected.
• CTE_CleanResult: It retains only relevant information from CTE_Recursive, providing a distinct list of identifiers connected to each AnchorIdent.

• Final SELECT:

  • It combines the results to generate the identifiers and their connected components.
  • Null values in GroupMembers are replaced with the identifier.
  • A unique GroupID is assigned to each connected component using DENSE_RANK().

The above is the detailed content of How to Find All Connected Subgraphs in an Undirected Graph Using SQL?. For more information, please follow other related articles on the PHP Chinese website!