algorithm for finding dependency

Question

0.00/5 (No votes)

See more:

Hi,

I am in need of an alogorithm. I have an xml document that contains dependency information of some objects. The dependency can be chained. Here is how the xml file look like:

XML

<?xml version="1.0" encoding="utf-8" ?>
<ObjectDependency>
   <Object Name="A" DependsOn="B, C" />
   <Object Name="B" DependsOn="D, C" />
   <Object Name="E" DependsOn="A" />

  <!-- 
  THIS WILL NOT HAPPEN (Circular Reference)
  <Object Name="X" DependsOn="Y" />
  <Object Name="Y" DependsOn="X" />
  
  AND THIS ALSO WILL NOT HAPPEN (Duplicate Entry)
  <Object Name="Z" DependsOn="X" />
  <Object Name="Z" DependsOn="Y" />
  -->
</ModuleDependency>

From the XML, we can conclude the dependencies like this:
A depends on "B, C, D"
B depends on "D, C"
C depends on nothing.
D depends on nothing.
E depends on "A, B, C, D"

What I need an algorithm that can create the dependency list given an object name. Can any one help me?
The function could look like this:

C#

public List<String> GetDependentList(XmlDocument doc, string sValue)
{

}

In this sample case, if "A" is passed in the function, the returned List<string> should contain "B", "C", and "D". if "C" is passed in the function, the the retur list sould be empty.

Any help would be highly appriciated.

Best regards,
Mizan

Posted 18-Apr-13 2:22am

Mizan Rahman

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

E.F. Nijboer · Accepted Answer · 2013-04-18T02:27:00

Simply create a dictionary and add the dependencies to it, all with a value of false (indicating if you visited the entry). Then visit each item in the list and add all dependencies of it if they were not already present in the dictionary. Repeat until all items are visited. This way you won't even have any trouble with duplicates or circular references.

Good luck!

Stefano Manni · Accepted Answer · 2013-04-18T02:53:00

you colud create a recursive method. use a dictionary to store objects already visited.
here's a template: note use of HashSet in order to have no duplicate items at no cost

C#

List< HashSet> GetDeps(XmlDocument doc, string item,  List<string> entriesAlreadyVisited) {
   var deps= new List<string>();
   if(entriesAlreadyVisited.Contains(item))
     return deps;
 
  entriesAlreadyVisited.Add(iem);

  //add code to  find direct dependenices and add them to the list
  foreach(var firstLevelDep in deps) {
     var subDependencies= GetDeps(doc,firstLevelDep ,entriesAlreadyVisited);
     foreach(var subDep in subDependencies) {
         deps.Add(subDep );
     }
  }
  return deps;
}
</string></string>

I hope it helps you

algorithm for finding dependency

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0