Help with Recursion and Circular References

[Bob]

I have a table of dependencies and want to check to see if the dependencies
cause a circular reference. Any sugesstions on how to do this using c#.

Example,

ID DependsOnID
1 2
1 4
2 3
3 1 (circular reference)

 

[Pavel Minaev]

I have a table of dependencies and want to check to see if the dependencies
cause a circular reference.  Any sugesstions on how to do this using c#..

Example,

ID      DependsOnID
1       2
1       4
2       3
3       1  (circular reference)

What is the nature of the "table"? Is it an array of objects of some
sort, or a table in an SQL database?

 

[Bob]

I will probably pull the values from the SQL table into an array because it
will be faster to process programmatically.

 

[Michel Walsh]

Starting with the set of nodes {S}, with attributes (From, To), find all
S.from NOT IN S.to. These nodes, {u} correspond to nodes having no parent.
Remove {u} from {S} to make the new {S} set. Repeat until {S} is empty. If
{u} happens to be empty while {S} is not, you have at least one cycle.


Now, do you really remove objects from a list, or do you just tag them (like
I would do for a database based algorithm) is up to you.

You can also start from all nodes S.to NOT IN S.from and obtain a LATEST
sequence instead of an EARLIEST sequence (if nodes are jobs, the first
sequence pops the jobs as soon as they are possible, while the second
sequence pop the jobs as late as possible).


Vanderghast, Access MVP

 

[kk]

oracle has 'connect by'
http://www.databasejournal.com/features/oracle/article.php/3552521

for ms sql
http://blogs.conchango.com/christianwade/archive/2004/11/09/234.aspx

also in old tran-sql books there was store proc simulating connct by