Oracle sql hierarchical or recursive query on table data with graph nodes

Question

Here is my table "graphtable" having graph nodes. Each tuple represents an undirected edge.

╔═════════╦═════════╗
║ NODEONE ║ NODETWO ║
╠═════════╬═════════╣
║ A       ║ A       ║
║ A       ║ A       ║
║ A       ║ B       ║
║ A       ║ B       ║
║ A       ║ A       ║
║ C       ║ D       ║
║ C       ║ A       ║
║ D       ║ E       ║
║ A       ║ E       ║
║ D       ║ A       ║
║ G       ║ K       ║
║ G       ║ G       ║
║ K       ║ K       ║
║ K       ║ L       ║
║ L       ║ M       ║
║ Y       ║ M       ║
║ G       ║ L       ║
║ G       ║ L       ║
║ X       ║ Z       ║
║ D       ║ D       ║
║ I       ║ I       ║
╚═════════╩═════════╝

As you can see, there are four distinct undirected graphs in this table.

1. nodes(A,B,C,D,E)
2. nodes(L,K,G,M,Y)
3. nodes(I)
4. nodes(X,Z)

I tried queries similar to one posted below;

select nodeone,nodetwo
from
graphtable
start with NODEONE='D'
connect by nocycle prior nodeone=nodetwo

I can use recursive query also to traverse through the graphs.

But, I need to get all the tuples involved in the particular graph if I start with any of the nodes in that particular graph. However, I am not getting that result from any of my queries.

start with nodeone='A'; seemed to return all the edges, but edge 'D-D' wasnt present. start with nodeone='D'; doesnt seem to return anything near to previous result.

Please help.. I appreciate any help in advance. Thank you.

Answer 1

Each tuple represents an undirected edge.

You are not treating it as an undirected edge - you are treating it as a directed edge as you only check that prior nodeone=nodetwo and do not check that either end of the current edge can match to either end of the previous edge.

SQL Fiddle

Oracle 11g R2 Schema Setup:

CREATE TABLE graphtable ( NODEONE, NODETWO ) AS
  SELECT 'A', 'A' FROM DUAL UNION ALL
  SELECT 'A', 'A' FROM DUAL UNION ALL
  SELECT 'A', 'B' FROM DUAL UNION ALL
  SELECT 'A', 'B' FROM DUAL UNION ALL
  SELECT 'A', 'A' FROM DUAL UNION ALL
  SELECT 'C', 'D' FROM DUAL UNION ALL
  SELECT 'C', 'A' FROM DUAL UNION ALL
  SELECT 'D', 'E' FROM DUAL UNION ALL
  SELECT 'A', 'E' FROM DUAL UNION ALL
  SELECT 'D', 'A' FROM DUAL UNION ALL
  SELECT 'G', 'K' FROM DUAL UNION ALL
  SELECT 'G', 'G' FROM DUAL UNION ALL
  SELECT 'K', 'K' FROM DUAL UNION ALL
  SELECT 'K', 'L' FROM DUAL UNION ALL
  SELECT 'L', 'M' FROM DUAL UNION ALL
  SELECT 'Y', 'M' FROM DUAL UNION ALL
  SELECT 'G', 'L' FROM DUAL UNION ALL
  SELECT 'G', 'L' FROM DUAL UNION ALL
  SELECT 'X', 'Z' FROM DUAL UNION ALL
  SELECT 'D', 'D' FROM DUAL UNION ALL
  SELECT 'I', 'I' FROM DUAL;

Query 1:

SELECT DISTINCT
       nodeone,
       nodetwo,
       rowid    -- Included as a unique id to differentiate edges with the
                -- same start/end points.
FROM   graphtable
START WITH NODEONE = 'D'
CONNECT BY NOCYCLE
   PRIOR nodeone IN ( nodeone, nodetwo )
OR PRIOR nodetwo IN ( nodeone, nodetwo )
ORDER SIBLINGS BY nodeone, nodetwo

Results:

| NODEONE | NODETWO |                     ROWID |
|---------|---------|---------------------------|
|       A |       A | oracle.sql.ROWID@57528909 |
|       A |       A | oracle.sql.ROWID@3d7f5c9c |
|       A |       A | oracle.sql.ROWID@777a44ea |
|       A |       B | oracle.sql.ROWID@1ca773d6 |
|       A |       B | oracle.sql.ROWID@5f7ebb8a |
|       A |       E | oracle.sql.ROWID@18229745 |
|       C |       A | oracle.sql.ROWID@3d5acdbf |
|       C |       D | oracle.sql.ROWID@1ac42001 |
|       D |       A | oracle.sql.ROWID@30cc6a38 |
|       D |       D | oracle.sql.ROWID@3cd85bdb |
|       D |       E | oracle.sql.ROWID@57845eca |