Circular Reference Pattern/Algorithm

[drdexter33]

I have a rather challenging problem (at least for me it is...)

I have a circular reference in a datastructure that I need to trap for and so far, I haven't been able to figure it out using recursion or been able to find an existing algorithm or design pattern that addresses the issue.

And example of the problem is that say we have 4 employees that each have a supervisor like this:

1. Dan
2. Kim
3. Jay
4. Bob

and

Kim reports to Dan
Jay reports to Kim
Bob reports to Jay
and our data might say that:

Dan reports to Bob, but that creates a circular reference that we want to trap for.

So that's the problem.

We're using C# in asp.net.

Thanks.

Doug.

[Zachm]

Look up Topological Sorting.
The algorithm described at the link I provided finds an ordering of elements based on relations.
Examples:
a. "reports to" is a relation between 2 people,
b. " < " is a relation between 2 numbers.

so, for you example you would say that:
1. Kim reports to Dan
2. Jay reports to Kim
3. Bob reports to Jay
4. Dan reports to Bob

"reports to" is the relation and the people are the elements. You might as well substitute the "reports to" with a "<" sign.

The purpose of topological sorting is to order all the people from left to right in a manner that if person a reports to person b, then a will stand to the left of b. If it is not possible to order all the people in such a manner, then there must be a circular reference and a topological sorting doesn't exist. This, I believe, is exactly the case you are after (marked in red in the pseudo-code quoted below):

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
   remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

Regards,
Zachm

[pm_kirkham]

Sorting will tell you if an existing structure is invalid. If you are creating the structure, it's very easy to check by walking up the reports-to tree until you either get to the top (in which case it's OK), or to the reporter (in which case it's a cycle).

(it might also be worth pointing out that in large organisations it's generally roles rather than people which report to each other, so you can get two people who report to each other in different aspects of their jobs)