1

我对类似的主题进行了搜索，但是对于我的理解和理解水平而言，答案太模糊了，而且我认为它们对我的问题不够具体。

类似的线程：
树（有向无环图）实现
表示一个DAG（有向无环图）

问题：

我已经格式化了一个文本文件，其中包含以下格式的数据...
示例数据集：
GO:0000109#is_a: GO:0000110#is_a: GO:0000111#is_a: GO:0000112#is_a: GO:0000113#is_a: GO :0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622
GO:0000112#part_of: GO:0000442
GO:00000168#is_a: GO: #is_a: GO:0034967#is_a: GO:0070210#is_a: GO:0070211#is_a: GO:0070822#is_a: GO:0070823#is_a: GO:0070824
GO:0000120#is_a: GO:0000500#is_a: GO: 0005668#is_a: GO:0070860
GO:0000123#is_a: GO:0005671#is_a: GO:0043189#is_a: GO:0070461#is_a: GO:0070775#is_a: GO:0072487
GO:0000126#is_a: GO#0 is_a: GO:0034733
GO:0000127#part_of: GO:0034734#part_of: GO:0034735
GO:0000133#is_a: GO:0031560#is_a: GO:0031561#is_a: GO:0031562#is_a: GO:0031563#part_of: GO:0031500
GO:0000137#part_of: GO:0000136

我希望从这些数据中构建一个加权的有向 DAG（上面只是一个片段）。106kb的整个数据集在这里：Source

--------------------------------------------------

逐行考虑，每行数据说明如下... 以
第一行为例：
GO:0000109#is_a: GO:0000110#is_a: GO:0000111#is_a: GO:0000112#is_a : GO:0000113#is_a: GO:0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622

'#' 是行数据的分隔符/标记器。
第一项，GO:0000109 是节点名称。
is_a: GO:xxxxxxx OR part_of: GO:xxxxxxx 后面的项是连接到 GO:0000109 的节点。
如数据集中所述，随后的一些术语也有联系。
当为is_a时，边的权重为0.8。
为part_of时，边的权重为0.6。

--------------------------------------------------

我有关于 DAG 的 Google-d，我理解这个概念。但是，我仍然不知道如何将其放入代码中。我正在使用 Java。
据我了解，图通常由节点和弧组成。这个图是否需要邻接表来确定连接的方向？如果是这样，我不确定如何结合图形和邻接表来相互通信。构建完图后，我的次要目标是从根节点中找出每个节点的度数。数据集中有一个根节点。

为了说明，我画了下面第一行数据的连接示例：
图片链接

我希望你们能理解我在这里想要达到的目标。感谢您浏览我的问题。:)

4

2 回答 2

1

因为它更容易思考，所以我更愿意将它表示为一棵树。（还可以更轻松地遍历地图并保持中间度数。）

你可以有一个Node类，它有一个子Node对象的集合。如果必须，您还可以将子关系表示为一个Relationship对象，该对象将具有权重和Node指针，并且您可以存储Relationship对象的集合。

然后你可以从根开始在树上走一走，并用它的度数标记每个访问过的节点。

class Node{
    String name;
    List<Relationship> children;
}

class Relationship{
    Node child;
    double weight;
}

class Tree{
    Node root;
}

在这里，Tree大概应该有这样的方法：

public Node findNodeByName(String name);

并且Node可能应该有这样的方法：

public void addChild(Node n, double weight);

然后，当您解析每一行时，您调用 Tree.findNodeByName() 来查找匹配节点（如果不存在则创建一个......但如果您的数据很好，那不应该发生），并将后续项目附加到到那个节点的线。

正如您所指出的，DAG 不能真正转换为树，特别是因为某些节点有多个父节点。您可以做的是插入与多个父节点的子节点相同的节点，可能使用哈希表来确定是否已遍历特定节点。

于 2011-12-15T08:45:22.057 回答
0

阅读评论，您似乎对节点如何包含关系感到困惑，而每个关系又包含一个节点。这是一种相当常见的策略，通常称为复合模式。

在树的情况下的想法是，树可以被认为是由多个子树组成的——如果你要断开一个节点及其所有祖先与树的连接，断开连接的节点仍然会形成一棵树，尽管树更小。因此，表示树的一种自然方式是让每个节点包含其他节点作为子节点。这种方法可以让你递归地做很多事情，在树的情况下，这通常是自然的。

让一个节点跟踪它的子节点，而不是树的其他部分也模拟了数学有向图——每个顶点只“知道”它的边，而没有其他任何东西。

递归树实现示例

例如，要在二叉搜索树中搜索元素，您将调用根的搜索方法。然后根检查寻找的元素是否等于、小于或大于自身。如果相等，则搜索以适当的返回值退出。如果它小于或大于，根会分别调用左子或右子的搜索，它们会做完全相同的事情。

类似地，要将新节点添加到树中，您可以调用根的 add 方法，并将新节点作为参数。根决定它是应该采用新节点还是将其传递给它的一个子节点。在后一种情况下，它将选择一个子节点并以新节点作为参数调用其 add 方法。

于 2011-12-20T00:52:03.947 回答