Re: [X] Tree/Graph structure in many-to-many relationship, avoiding/detecting circularity

From: cmk <ckushni1_at_san.rr.com>
Date: Mon, 04 Mar 2002 19:59:18 GMT
Message-ID: <qmQg8.6153$Gu6.3167082@typhoon.san.rr.com>

Here's a stored proc that traces out from a starting point and finds all connected items without getting caught in loops. You can add code to the 'continue' condition to trap all loop points and a level column to the stack/list to track how far an item is from the start (for your tree view).

CREATE PROCEDURE cmk_TraceUfid

    @ufid binary(12)
AS
BEGIN
    SET NOCOUNT ON

• ----------------------------------------------------
• create stack (to be traced) and list (found in trace) temp tables create table #stack ( ufid binary(12) ) create table #list ( ufid binary(12) ) create unique clustered index idx_list on #list (ufid)
• seed stack with starting fac insert into #stack values( @ufid )
• ----------------------------------------------------

    while( 1=1 )
    begin

• break if nothing left to trace if( not exists( select ufid from #stack ) ) break
• pop next fac off stack select @ufid = ufid from #stack delete from #stack where ufid = @ufid
• if already in list then skip (loop) if( exists( select ufid from #list where ufid = @ufid ) ) continue
• add fac to list insert into #list values( @ufid )
• ------------------------------------------------
• add all ufids connected to @ufid to stack insert into #stack select rdb_ufidc from rdb_lconn where rdb_ufid = @ufid union select rdb_ufid from rdb_lconn where rdb_ufidc = @ufid end
  • ----------------------------------------------------

    SET NOCOUNT OFF

• return number of fac found in trace select count(*) as NbrUfid from #list

END For C++ code to display the tree without using a stored proc you could use somethnig like :

void CkGnDlgShowConn::LoadTree( CkGnRec &R ) {

    m_Tree.BeginWaitCursor();
    m_Tree.DeleteAllItems();

    ufids.Empty(); // list of CkGnRec put into tree     AddRec(TVI_ROOT, R, depth); // depth is max depth to trace     ufids.Empty();

    m_Tree.SelectItem(NULL);

    m_Tree.EndWaitCursor();
}

// P is parent - default = NULL
void CkGnDlgShowConn::AddRec( HTREEITEM T, CkGnRec &R, short D, CkGnRec *P ) {

    ...

    CString s = <formated string describing R>     HTREEITEM t = m_Tree.InsertItem(s, T);

    ...

    // if found loop then stop tracing this branch and back up     if( ufids.Contains(R.Ufid) ) return;     ufids.Add(R.Ufid);

    ...

    if( D < 1 ) return; // reached max allowable trace depth

    ...

    CkGnRec *r = NULL;
    <loop>

        r = <Next connected item>
        AddRec(t, *r, D-1, &R);  // recursive trace - try to minimize

function state information

    <end loop>
    ...
}

...cmk Received on Mon Mar 04 2002 - 13:59:18 CST