寻找依赖的算法 [英] algorithm for finding dependency

问题描述

我需要一个alogorithm。我有一个xml文档，其中包含一些对象的依赖项信息。依赖关系可以链接。以下是xml文件的外观：

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 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>

从XML中，我们可以得出这样的依赖关系：

A取决于B，C，D

B取决于D，C

C取决于什么。

D取决于什么。

E取决于A，B，C，D


我需要一种能够在给定对象名称的情况下创建依赖关系列表的算法。任何人都可以帮助我吗？

功能可能如下所示：

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:

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

}

在此示例中，如果函数中传递了A，则返回的List< string>应包含B，C和D。如果在函数中传递了C，那么返回列表应该是空的。



任何帮助都会非常有用。



祝你好运，

Mizan

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

推荐答案

只需创建一个字典并添加依赖项，所有这些都是值false（表示您是否访问过该条目）。然后访问列表中的每个项目，并添加它的所有依赖项（如果它们尚未存在于字典中）。重复，直到访问所有项目。这样你就不会有重复或循环引用的任何麻烦。



祝你好运！

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!

你colud创建一个递归方法。使用字典来存储已经访问过的对象。

这里是模板：注意使用HashSet以免没有重复项目

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

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

这篇关于寻找依赖的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！