如何解析模块实例树中的端口方向
How to resolve port directions in a module instance tree
在电气工程中，我们经常处理模块实例的层次结构，它可以表示为一棵树，其中每个树节点都是模块的一个实例。这些模块通过信号连接，这些信号可以是输出、输入或输入（bi-directional 驱动方向）。通常，以下规则适用：
每个节点可以有零个或多个sub-nodes (children)。
每个节点可以有一个或多个端口将它们连接到树中的其他节点。
每个端口可以有三个（驱动）方向之一：输入（从节点到 child）、输出（从 child 到节点）和 inout（双向） ).
给定一棵包含叶节点及其端口方向的树，我一直在寻找一种简单的算法来解析中间端口方向，即目标是了解树中连接给定节点的所有节点的端口方向叶节点。
按信号过滤树简化了问题，这样一棵给定的树是原始树的子集，除了一个信号外，所有的树都被删除了。这将规则 2 更改为
- （过滤树的）每个节点都有一个端口将其连接到树的所有其他节点。
关于传播方向的规则：
- 如果所有children方向相同，则当前节点的方向相同
- 如果至少有一个child是inout 或至少有一个有输入和一个有输出，这取决于当前节点指向的其他节点会得到（这就是它变得棘手的地方）。
使用符号<X（节点X是输出节点），>Y（节点Y是输入节点）和<>Z（Z是bidir节点），这里是一些例子：
1:
B-<D <B-<D
/ /
A ==> A
\ \
C->E >C->E
2:
<B <B
/ /
A A
\ >D \ >D
\ / ==> \ /
C->E >C->E
\ \
>F >F
3:
<D <D
/ /
B <>B
/ \ / \
/ >E / >E
A ==> A
\ <G \ <G
\ / \ /
C-F->H <>C-<>F->H
\ \
>I >I
4:
<D <D
/ /
B <B
/ \ / \
/ >E / >E
A ==> A
\ \
C->F >C->F
5:
<D <D
/ /
B >B
/ \ / \
/ >E / >E
A ==> A
\ \
C-<F <C-<F
我认为该算法可能会从叶子开始并向根传播 (A)，应用上面的传播规则 1。如果我们遇到规则 2 的情况（例如示例 3 节点 B、F 以及可能稍后的 C），我目前不确定如何进一步进行，也许继续传播其他节点直到（什么时候？）确定当前节点的方向？
编辑 2019-08-14
由于评论者询问在某些示例中解析方向时适用哪些规则，这里是（我希望涵盖所有情况）：
- 如上所述，如果一个节点的所有children方向相同，则parent继承它（见示例1、2C、4C和5C）。
- 如果一个节点的children有混合方向，这取决于：
- 如果有其他节点混合方向（比如3B和3F之间），节点会有inouts。
- 如果所有其他节点都具有单一方向（如示例 4 和 5 中，在节点 B 和 F 之间），则确定具有混合方向 children 的节点的端口方向。
我们将从左到右遍历树，有限数量的节点可能需要第二次访问。在每个节点中，我们将存储其状态：输入、输出、双向或待定。考虑这个例子：
-- A --
/ \
B C
/ \ / \
D E >F >G
/ \ / \
>H >I J> K>
我们遍历到最左边的叶子H，发现它是一个输入，再次向上移动到它的parentD，暂时将D标记为输入。然后我们看另外一个child I，也是一个输入，我们再次上移到D，再次临时标记为输入。然后我们注意到 D 没有更多的 children，并且仅被标记为输入，因此我们可以将其永久标记为输入。
D的children中所有可以确定状态的就不用再访问了，以后可以忽略了。所以现在我们有：
-- A --
/ \
B C
/ \ / \
>D E >F >G
/ \
J> K>
我们向上移动到B，并临时标记为输入，然后继续访问它的另一个child E。与D类似，我们发现E的状态可以确定为输出，并且它的 children J 和 K 将不必再次访问：
-- A --
/ \
B C
/ \ / \
>D E> >F >G
我们再次上移到B，暂时标记为output；它现在被标记为输入和输出，因此我们将其状态更改为 "to be determined"。不必再次访问 D 和 E。所以现在我们有：
-- A --
/ \
?B? C
/ \
>F >G
我们向上移动到A，临时设置它的状态为"to be determined"，因为它还有待确定child，然后向下移动到下一个节点F。检查F和G我们发现C是一个输入，所以我们得到：
-- ?A? --
/ \
?B? >C
我们回到A，发现我们访问了它所有的children，还有一个未确定的child，其他的children都是输入.这意味着未确定的 child 成为输出。然后我们将 B 的状态作为输出传播到它可能具有的任何 children 也具有未确定的状态（在示例中有 none）。这种向下传播意味着在最坏的情况下，整个树被遍历两次。
-- ?A? --
/ \
B> >C
这里有一些不确定性。如果A有3个children：一个输入，一个输出，一个待定，你还没有定义待定child.会发生什么的规则
再看一个例子：
-- A --
/ \
B C
/ \ / \
D E F> >G
/ \ / \
>H I> J> >K
我们发现B有两个children都待定：
-- A --
/ \
?B? C
/ \ / \
?D? ?E? F> >G
所以我们使 B 成为双向的并将其传播到其待确定的后代，最终得到：
-- A --
/ \
>B> C
/ \
F> >G
如果我正确理解规则，则此双向状态将传播到树其余部分中的每个未确定节点，而无需额外遍历：
-- A --
/ \
>B> >C>
所以算法是：
- 访问每个节点，从根节点开始
- 如果节点是叶节点，记住它的状态，向上移动到它的parent，并临时给parent那个状态。
- 如果你访问了一个节点的每个child，看看它的临时状态：如果只标记了输入或输出，那么该节点就成为输入或输出。如果输入和输出都被标记了，那么就变成了待定。如果不止一个 child 有待确定的状态，则该节点变为双向节点，并向下传播到其所有未确定的后代。然后我们临时将此状态提升到 parent。
- 一旦我们将任何节点的状态设置为双向，树中每个未确定的节点都会变为双向（如果我理解正确的话）。
实用细节：
当您升到 parent 时，如何记住 child 的状态有几种方法。您可以存储输入和输出的布尔标志，以及未确定的计数（以便您知道是否有多个），并且可能存储一个单独的双向布尔标志（以防双向 child 影响 parent 与混合输入和输出 children 不同的方式。但是你也可以不把状态存储在parent节点中，当你发现你已经访问了所有children时，再查看children的状态。
一个节点自身的状态只有4种状态：输入、输出、双向和未确定，所以可以只用两个布尔值存储，其中两个都是false表示未确定。
您可以在每个节点中存储关于当状态向下传播到未确定的节点时必须访问哪些 children 的信息，但这也不是绝对必要的；您可以只查看每个 child 的状态来更新未确定的。只有未确定的节点可以有未确定的后代，所以您知道您不必访问 children 的节点不是未确定的。
你在评论中提到的规则，其中具有输入、输出和未定三个 children 的节点将意味着未定 child 变为双向，确实是一个附加规则。但在点你已经访问了一个节点的所有 children，你如何将 children 的状态组合成 parent 的状态的细节可以很容易地修改以包括任何额外的规则.如果您决定未确定的 child 必须变成双向的，那么您会将此状态传播给 child 的未确定的后代，并且（如果我理解正确的话）从那时起在每个未确定的节点上在树的其余部分中查找将自动变为双向。
在电气工程中，我们经常处理模块实例的层次结构，它可以表示为一棵树，其中每个树节点都是模块的一个实例。这些模块通过信号连接，这些信号可以是输出、输入或输入（bi-directional 驱动方向）。通常，以下规则适用：
每个节点可以有零个或多个sub-nodes (children)。
每个节点可以有一个或多个端口将它们连接到树中的其他节点。
每个端口可以有三个（驱动）方向之一：输入（从节点到 child）、输出（从 child 到节点）和 inout（双向） ).
给定一棵包含叶节点及其端口方向的树，我一直在寻找一种简单的算法来解析中间端口方向，即目标是了解树中连接给定节点的所有节点的端口方向叶节点。
按信号过滤树简化了问题，这样一棵给定的树是原始树的子集，除了一个信号外，所有的树都被删除了。这将规则 2 更改为
- （过滤树的）每个节点都有一个端口将其连接到树的所有其他节点。
关于传播方向的规则：
- 如果所有children方向相同，则当前节点的方向相同
- 如果至少有一个child是inout 或至少有一个有输入和一个有输出，这取决于当前节点指向的其他节点会得到（这就是它变得棘手的地方）。
使用符号<X（节点X是输出节点），>Y（节点Y是输入节点）和<>Z（Z是bidir节点），这里是一些例子：
1:
B-<D <B-<D
/ /
A ==> A
\ \
C->E >C->E
2:
<B <B
/ /
A A
\ >D \ >D
\ / ==> \ /
C->E >C->E
\ \
>F >F
3:
<D <D
/ /
B <>B
/ \ / \
/ >E / >E
A ==> A
\ <G \ <G
\ / \ /
C-F->H <>C-<>F->H
\ \
>I >I
4:
<D <D
/ /
B <B
/ \ / \
/ >E / >E
A ==> A
\ \
C->F >C->F
5:
<D <D
/ /
B >B
/ \ / \
/ >E / >E
A ==> A
\ \
C-<F <C-<F
我认为该算法可能会从叶子开始并向根传播 (A)，应用上面的传播规则 1。如果我们遇到规则 2 的情况（例如示例 3 节点 B、F 以及可能稍后的 C），我目前不确定如何进一步进行，也许继续传播其他节点直到（什么时候？）确定当前节点的方向？
编辑 2019-08-14
由于评论者询问在某些示例中解析方向时适用哪些规则，这里是（我希望涵盖所有情况）：
- 如上所述，如果一个节点的所有children方向相同，则parent继承它（见示例1、2C、4C和5C）。
- 如果一个节点的children有混合方向，这取决于：
- 如果有其他节点混合方向（比如3B和3F之间），节点会有inouts。
- 如果所有其他节点都具有单一方向（如示例 4 和 5 中，在节点 B 和 F 之间），则确定具有混合方向 children 的节点的端口方向。
我们将从左到右遍历树，有限数量的节点可能需要第二次访问。在每个节点中，我们将存储其状态：输入、输出、双向或待定。考虑这个例子：
-- A --
/ \
B C
/ \ / \
D E >F >G
/ \ / \
>H >I J> K>
我们遍历到最左边的叶子H，发现它是一个输入，再次向上移动到它的parentD，暂时将D标记为输入。然后我们看另外一个child I，也是一个输入，我们再次上移到D，再次临时标记为输入。然后我们注意到 D 没有更多的 children，并且仅被标记为输入，因此我们可以将其永久标记为输入。
D的children中所有可以确定状态的就不用再访问了，以后可以忽略了。所以现在我们有：
-- A --
/ \
B C
/ \ / \
>D E >F >G
/ \
J> K>
我们向上移动到B，并临时标记为输入，然后继续访问它的另一个child E。与D类似，我们发现E的状态可以确定为输出，并且它的 children J 和 K 将不必再次访问：
-- A --
/ \
B C
/ \ / \
>D E> >F >G
我们再次上移到B，暂时标记为output；它现在被标记为输入和输出，因此我们将其状态更改为 "to be determined"。不必再次访问 D 和 E。所以现在我们有：
-- A --
/ \
?B? C
/ \
>F >G
我们向上移动到A，临时设置它的状态为"to be determined"，因为它还有待确定child，然后向下移动到下一个节点F。检查F和G我们发现C是一个输入，所以我们得到：
-- ?A? --
/ \
?B? >C
我们回到A，发现我们访问了它所有的children，还有一个未确定的child，其他的children都是输入.这意味着未确定的 child 成为输出。然后我们将 B 的状态作为输出传播到它可能具有的任何 children 也具有未确定的状态（在示例中有 none）。这种向下传播意味着在最坏的情况下，整个树被遍历两次。
-- ?A? --
/ \
B> >C
这里有一些不确定性。如果A有3个children：一个输入，一个输出，一个待定，你还没有定义待定child.会发生什么的规则
再看一个例子：
-- A --
/ \
B C
/ \ / \
D E F> >G
/ \ / \
>H I> J> >K
我们发现B有两个children都待定：
-- A --
/ \
?B? C
/ \ / \
?D? ?E? F> >G
所以我们使 B 成为双向的并将其传播到其待确定的后代，最终得到：
-- A --
/ \
>B> C
/ \
F> >G
如果我正确理解规则，则此双向状态将传播到树其余部分中的每个未确定节点，而无需额外遍历：
-- A --
/ \
>B> >C>
所以算法是：
- 访问每个节点，从根节点开始
- 如果节点是叶节点，记住它的状态，向上移动到它的parent，并临时给parent那个状态。
- 如果你访问了一个节点的每个child，看看它的临时状态：如果只标记了输入或输出，那么该节点就成为输入或输出。如果输入和输出都被标记了，那么就变成了待定。如果不止一个 child 有待确定的状态，则该节点变为双向节点，并向下传播到其所有未确定的后代。然后我们临时将此状态提升到 parent。
- 一旦我们将任何节点的状态设置为双向，树中每个未确定的节点都会变为双向（如果我理解正确的话）。
实用细节：
当您升到 parent 时，如何记住 child 的状态有几种方法。您可以存储输入和输出的布尔标志，以及未确定的计数（以便您知道是否有多个），并且可能存储一个单独的双向布尔标志（以防双向 child 影响 parent 与混合输入和输出 children 不同的方式。但是你也可以不把状态存储在parent节点中，当你发现你已经访问了所有children时，再查看children的状态。
一个节点自身的状态只有4种状态：输入、输出、双向和未确定，所以可以只用两个布尔值存储，其中两个都是false表示未确定。
您可以在每个节点中存储关于当状态向下传播到未确定的节点时必须访问哪些 children 的信息，但这也不是绝对必要的；您可以只查看每个 child 的状态来更新未确定的。只有未确定的节点可以有未确定的后代，所以您知道您不必访问 children 的节点不是未确定的。
你在评论中提到的规则，其中具有输入、输出和未定三个 children 的节点将意味着未定 child 变为双向，确实是一个附加规则。但在点你已经访问了一个节点的所有 children，你如何将 children 的状态组合成 parent 的状态的细节可以很容易地修改以包括任何额外的规则.如果您决定未确定的 child 必须变成双向的，那么您会将此状态传播给 child 的未确定的后代，并且（如果我理解正确的话）从那时起在每个未确定的节点上在树的其余部分中查找将自动变为双向。