By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,424 Members | 1,382 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,424 IT Pros & Developers. It's quick & easy.

Help with Recursion and Circular References

P: n/a
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)
Jul 10 '08 #1
Share this Question
Share on Google+
5 Replies


P: n/a
On Jul 10, 4:07*pm, Bob <B...@discussions.microsoft.comwrote:
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?

Jul 10 '08 #2

P: n/a
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 <B...@discussions.microsoft.comwrote:
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?

Jul 10 '08 #3

P: n/a
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)

Jul 10 '08 #4

P: n/a
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)
Jul 10 '08 #5

P: n/a
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)
Jul 11 '08 #6

This discussion thread is closed

Replies have been disabled for this discussion.