SQL を使用して無向グラフ内のすべての接続されたサブグラフを検索する方法

無向グラフの接続されたすべての部分グラフを見つける方法

問題定義:
与えられた無向グラフIdentifier1 と Identifier2 の 2 つの列を持つテーブルで表されます。各行は 2 つの識別子間のエッジを表します。タスクは、グラフ内の接続されているすべてのサブグラフを見つけることです。接続されたサブグラフは、他の識別子によって直接または間接的にリンクされた識別子のセットです。出力には各サブグラフの識別子が含まれ、各サブグラフに一意のグループ ID が割り当てられる必要があります。

接続されたサブグラフを検索するためのクエリ:

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

説明:

• CTE_Idents: この共通テーブル式 (CTE) は、Identifier1 と Identifier2 columns.
• CTE_Pairs: EdgeTable からエッジを抽出して結合し、すべての一意の識別子のペアを表します。
• CTE_Recursive: この再帰的 CTE は、各一意の識別子から開始してグラフを横断し、接続された識別子のカンマ区切りのパスを構築します。ループが検出されると停止します。
• CTE_CleanResult: CTE_Recursive からの関連情報のみを保持し、各 AnchorIdent.
• Final SELECT

  :

  結果を結合して、識別子とその接続コンポーネントを生成します。
  • Null
  GroupMembers
  • の値は識別子に置き換えられます。一意の
  GroupID
  • は、DENSE_RANK() を使用して各接続コンポーネントに割り当てられます。

以上がSQL を使用して無向グラフ内のすべての接続されたサブグラフを検索する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。