Help with Recursion and Circular References

[=?Utf-8?B?Qm9i?=]

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]

On Jul 10, 4:07*pm, Bob <[e-mail]:

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?

[=?Utf-8?B?Qm9i?=]

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

"Pavel Minaev" wrote:

On Jul 10, 4:07 pm, Bob <[e-mail]:

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?

[Fred Mellender]

1. Push the first element to a stack.
2. Pull the first element, X, from the stack. If stack is empty, DONE.
If X is "marked", you have a circular reference: QUIT. Else "mark" the
element X.
3. Push all the elements that have a link in X on the stack.
4. Go to 2.

To "mark" an element either set an attribute in the object, or if this is
not possible, just keep the marked elements (or their id's) in a list and
check the list
to determine if an element has been "marked".

"Bob" <Bo*@discussions.microsoft.comwrote in message
news:B3**********************************@microsof t.com...

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

[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

"Bob" <Bo*@discussions.microsoft.comwrote in message
news:B3**********************************@microsof t.com...

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

[=?Utf-8?B?a2s=?=]

oracle has 'connect by'
http://www.databasejournal.com/featu...le.php/3552521

for ms sql
http://blogs.conchango.com/christian...11/09/234.aspx

also in old tran-sql books there was store proc simulating connct by
--
kk
"Bob" wrote:

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)