CODEWITHSUNDEEP
c#dependencies
Amir Popovich
Amir Popovich

Reputation: 29836

How should I resolve logic dependencies I have in a "flat" data structure?

I currently have a Dictionary<string, List<string> or dependencies.

The key is the properties name and the value is a list of dependency properties.

Here's a simple example:

{key: "a", value: ["b", "d"]},
{key: "b", value: null},
{key: "c", value: ["a"]},
{key: "d", value: ["b", "e", "f"]},
{key: "e", value: null},
{key: "f", value: null}

The first level dependencies look like:

a -> b,d
b -> nothing
c -> a
d -> b,e,f
e -> nothing
f -> nothing

After finding the first level dependencies the second level dependencies will look like:

a -> b,d,e,f (d has a dependency to e and f).
b -> nothing
c -> a,b,d (a has a dependency to b and d).
d -> b,e,f
e -> nothing
f -> nothing

The third and last level (in this case) will look like:

a -> b,d,e,f
b -> nothing
c -> a,b,d,e,f
d -> b,e,f
e -> nothing
f -> nothing

Now my dictionary has a lot more entries then I've shown in this example(Over a thousand).

My thought was to do something similar to angularjs's digest. I would create a threshold of let's say 10 or 20 runs. In each run, I'll check each properties dependency and update the model. If there was at least one update, then perform a recursive call.

I'm pretty sure this is a "known problem" with a better approach.

Anyway:

  1. How should I approach this problem?
  2. How do I know the number of levels I need to iterate until I will have no more dependencies.
  3. How will I know if there's a circular dependency? I have lot's of data and it's not something easy to analyze?

Upvotes: 1

Views: 45

Answers (1)

astef
astef

Reputation: 9498

All you need is to write few recursive algorithms. Look here:

internal static class Program
{
    private static Dictionary<string, List<string>> _dependencies;

    static void Main(string[] args)
    {
        _dependencies = new Dictionary<string, List<string>>
        {
            {"a", new List<string>{"b","d"}},
            {"b", new List<string>()},
            {"c", new List<string>{"a"}},
            {"d", new List<string>{"b","e","f"}},
            {"e", new List<string>()},
            {"f", new List<string>()}
        };
        Console.WriteLine(string.Join(",", DeepWalkDependencies("a", new HashSet<string>())));
        Console.ReadLine();
    }

    static IEnumerable<string> DeepWalkDependencies(string key, HashSet<string> alreadyVisitedKeys)
    {
        foreach (var d in _dependencies[key])
        {
            if (alreadyVisitedKeys.Add(d))
            {
                yield return d;
                foreach (var dd in DeepWalkDependencies(d, alreadyVisitedKeys))
                {
                    yield return dd;
                }
            }
        }
    }
}

Detecting a circular dependency can be achieved similarly. Instead of HashSet<string> alreadyVisitedKeys you need List<string> currentPath which will be re-created before every call to a recursive function. It is a good exercise to implement this algorithm. Enjoy!

Upvotes: 1

Related Questions