Finding out folder cyclic references

Question

Suppose I have an app that transfers files placed inside a main folder to some other location.

For example, user can configure the app as below:

If placed in C:\X\A Transfer to C:\Z\A
If placed in C:\Y\B Transfer to C:\Z\B
. . .
. . .

Till now, all is well. But the following configuration would create endless transfer loops:

if placed in C:\X\A Transfer to C:\Z\A
if placed in C:\Z\A Transfer to C:\Z\B
if placed in C:\Z\B Transfer to C:\X\A

Such hierarchies can get quite complex. What would be the best way to predict them and prevent such configurations in the first place?

Simple and obvious solution is to only follow the rules from top-down per file. — Mooing Duck, Jun 06 '12 at 22:31

score 4 · Answer 1 · edited Jun 07 '12 at 05:22

4

Assume that there is a class like this:

class Rule
{
    public string sourceDir; // dir file placed
    public string targetDir; // dir to move to
}

And a dictionary that contains all your rules indexed by the sourceDir named rules.

You can write a function like this:

public bool RuleCausesCycle(Rule rule)
{
    return RuleCausesCycle(rule, new HashSet(CaseInsensitiveComparer.Default));
}

private bool RuleCausesCycle(Rule rule, Set visited)
{
     Rule targetRule;

     if (visited.Contains(rule.sourceDir))
     {
         return true;
     }

     if (rules.TryGetValue(rule.targetDir, out targetRule))
     {
         visited.Add(rule.sourceDir);

         return RuleCausesCycle(targetRule, visited);
     }

     return false;
}

edited Jun 07 '12 at 05:22

Filip

2,166
1
18
24

answered Jun 06 '12 at 22:39

tumtumtum

1,051
9
11

1

If the assumption that there is only one target dir per one source dir (you dont make two copies from the same source directory) holds, this is a better solution than the other answer. If it does not hold, you can add a loop (and not use a dictionary), but it can get very resource-expensive very fast. – Filip Jun 06 '12 at 23:04
A dictionary with a list would be required if you had multiple rules with the same source. It wouldn't get resource intensive nor slow unless you had millions of rules – tumtumtum Aug 21 '12 at 09:20

score 3 · Accepted Answer · answered Jun 06 '12 at 22:25

3

You are basically looking for cycles in a directed graph. I would use a graph Library like QuickGraph: http://quickgraph.codeplex.com/wikipage?title=Strongly%20Connected%20Components&referringTitle=Documentation

answered Jun 06 '12 at 22:25

nw.

4,350
7
35
41

Agreed. See also this SO topic: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph – Ethan Brown Jun 06 '12 at 22:26

Finding out folder cyclic references

2 Answers2