algorithm - DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent-6ren

algorithm - DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent

转载作者：塔克拉玛干更新时间：2023-11-03 03:02:17

我有电路原理图的网表(子电路的集合)，通常是由一些 SPICE 模拟器创建的。它通常具有层次结构(顶级子电路调用或实例化不同的子电路并通过引脚定义它们之间的一些连接)。示例网表如下所示:

subckt AN2D0 A1 A2 VDD VSS Z

    M_u2 (net5 A2 VDD VDD) pch 
    M_u1 (net5 A1 VDD VDD) pch 
    M_u3 (Z net5 VDD VDD) pch 
    M_u4 (net17 A2 VSS VSS) nch 
    M_u2 (Z net5 VSS VSS) nch 

ends AN2D0

subckt LS_RX_CONTROLLER VDD VSS burst_start_or_sys burst_start_out pd pd_pwm_det pd_pwm_det_TII std_by std_by_or_sys sys_en sys_out

    I2 (burst_start_or_sys std_by VDD VSS burst_start_out) AN2D2
    I1 (net22 std_by_bar VDD VSS sys_out) AN2D2
    I5 (net022 pd VDD VSS pd_pwm_det) OR2D2
    I10 (net026 pd VDD VSS std_by_or_sys) NR2D2
    I9 (sys_en std_by VDD VSS net026) NR2D0
    I6 (std_by VDD VSS std_by_bar) INVD0
    I3 (pd_pwm_det_TII net037 VDD VSS net022) OR2D0
    I11 (sys_en std_by VDD VSS net037) OR2D0
    I0 (burst_start_or_sys sys_en VDD VSS net22) AN2D0

ends LS_RX_CONTROLLER

现在可以在不同的层次结构中实例化相同的子电路。每个被调用的子电路都在调用子电路之前定义。这种图称为Directed Acyclic GRAPH。我已经从网表中创建了一个自引用哈希表以节省空间。如果子电路正在调用某个子电路实例，则它指向引脚。在最后一层，我们将得到一个 MOSFET D 或 S 或 G 或 B 节点(因为已定义 AN2D0 子电路)。如果任何网络(实例引脚之间的连接)从层次结构(除了调用子电路，例如 net5)到父调用子电路，它被称为引脚(例如 Z)，并且将始终列在当前的子电路定义行中通过其名称 (subckt AN2D0 A1 A2 VDD VSS Z)。我创建了一个哈希的哈希。

GRAPH --> subckt1--->p1
                     p2
                     net1
                     net2
          subckt2--->p1
                     p2
                     net1
                     net2
          subckt3--->p1 ---->I1.subckt1.p1--->pointing to value of p1 key of subckt1.
                             I2.subckt1.p2
                     p2
                     net1
                     net2

对于目前的情况，GRAPH 看起来像:

the name of subcircuit-->AN2D0

     name of pin or net-->Z
         name of instant connected to it-->M_u2.nch.D
         name of instant connected to it-->M_u3.pch.D
     name of pin or net-->VDD
         name of instant connected to it-->M_u1.pch.S
         name of instant connected to it-->M_u1.pch.B
         name of instant connected to it-->M_u2.pch.S
         name of instant connected to it-->M_u3.pch.S
         name of instant connected to it-->M_u2.pch.B
         name of instant connected to it-->M_u3.pch.B
     name of pin or net-->A1
         name of instant connected to it-->M_u3.nch.G
         name of instant connected to it-->M_u1.pch.G
     name of pin or net-->VSS
         name of instant connected to it-->M_u2.nch.S
         name of instant connected to it-->M_u4.nch.B
         name of instant connected to it-->M_u2.nch.B
         name of instant connected to it-->M_u3.nch.B
         name of instant connected to it-->M_u4.nch.S
     name of pin or net-->net5
         name of instant connected to it-->M_u3.nch.D
         name of instant connected to it-->M_u3.pch.G
         name of instant connected to it-->M_u1.pch.D
         name of instant connected to it-->M_u2.pch.D
         name of instant connected to it-->M_u2.nch.G
     name of pin or net-->A2
         name of instant connected to it-->M_u4.nch.G
         name of instant connected to it-->M_u2.pch.G
     name of pin or net-->net17
         name of instant connected to it-->M_u3.nch.S
         name of instant connected to it-->M_u4.nch.D

the name of subcircuit-->LS_RX_CONTROLLER

     name of pin or net-->burst_start_or_sys
         name of instant connected to it-->I2.AN2D2.A1
            M_u3.nch.G
            M_u1.pch.G
         name of instant connected to it-->I0.AN2D0.A1
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->burst_start_out
         name of instant connected to it-->I2.AN2D2.Z
            M_u2.nch.D
            M_u3.pch.D
     name of pin or net-->net037
         name of instant connected to it-->I11.OR2D0.Z
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I3.OR2D0.A2
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->net026
         name of instant connected to it-->I10.NR2D2.A1
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I9.NR2D0.ZN
            M_u3.nch.D
            M_u2.pch.D
            M_u4.nch.D
     name of pin or net-->std_by
         name of instant connected to it-->I9.NR2D0.A2
            M_u3.nch.G
            M_u1.pch.G
         name of instant connected to it-->I6.INVD0.I
            M_u3.pch.G
            M_u2.nch.G
         name of instant connected to it-->I2.AN2D2.A2
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I11.OR2D0.A2
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->sys_en
         name of instant connected to it-->I11.OR2D0.A1
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I0.AN2D0.A2
            M_u4.nch.G
            M_u2.pch.G
         name of instant connected to it-->I9.NR2D0.A1
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->VDD
         name of instant connected to it-->I2.AN2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.S
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I10.NR2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.B
         name of instant connected to it-->I0.AN2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.S
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I6.INVD0.VDD
            M_u3.pch.S
            M_u3.pch.B
         name of instant connected to it-->I9.NR2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.B
         name of instant connected to it-->I1.AN2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u2.pch.S
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I11.OR2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I3.OR2D0.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
         name of instant connected to it-->I5.OR2D2.VDD
            M_u1.pch.S
            M_u1.pch.B
            M_u3.pch.S
            M_u2.pch.B
            M_u3.pch.B
     name of pin or net-->sys_out
         name of instant connected to it-->I1.AN2D2.Z
            M_u2.nch.D
            M_u3.pch.D
     name of pin or net-->net022
         name of instant connected to it-->I3.OR2D0.Z
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I5.OR2D2.A1
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->pd_pwm_det_TII
         name of instant connected to it-->I3.OR2D0.A1
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->std_by_or_sys
         name of instant connected to it-->I10.NR2D2.ZN
            M_u3.nch.D
            M_u2.pch.D
            M_u4.nch.D
     name of pin or net-->net22
         name of instant connected to it-->I0.AN2D0.Z
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I1.AN2D2.A1
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->pd
         name of instant connected to it-->I10.NR2D2.A2
            M_u3.nch.G
            M_u1.pch.G
         name of instant connected to it-->I5.OR2D2.A2
            M_u3.nch.G
            M_u1.pch.G
     name of pin or net-->std_by_bar
         name of instant connected to it-->I6.INVD0.ZN
            M_u2.nch.D
            M_u3.pch.D
         name of instant connected to it-->I1.AN2D2.A2
            M_u4.nch.G
            M_u2.pch.G
     name of pin or net-->VSS
         name of instant connected to it-->I11.OR2D0.VSS
            M_u3.nch.S
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I5.OR2D2.VSS
            M_u3.nch.S
            M_u4.nch.B
            M_u2.nch.S
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I3.OR2D0.VSS
            M_u3.nch.S
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I6.INVD0.VSS
            M_u2.nch.S
            M_u2.nch.B
         name of instant connected to it-->I0.AN2D0.VSS
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I2.AN2D2.VSS
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I1.AN2D2.VSS
            M_u2.nch.S
            M_u4.nch.B
            M_u2.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I9.NR2D0.VSS
            M_u3.nch.S
            M_u4.nch.B
            M_u3.nch.B
            M_u4.nch.S
         name of instant connected to it-->I10.NR2D2.VSS
            M_u3.nch.S
            M_u4.nch.B
            M_u3.nch.B
            M_u4.nch.S
     name of pin or net-->pd_pwm_det
         name of instant connected to it-->I5.OR2D2.Z
            M_u2.nch.D
            M_u3.pch.D

在此之后，将给出一个子电路名称和一个相同的引脚，它们可以从任何级别层次结构中实例化，我们必须找到父级，即追溯父级，直到网络作为引脚被拉起。然后将所有叶子(MOSFETS D or G or S or B pin)压回。

请建议哪种算法最适合这种情况，以及将它们存储在自引用哈希表中是否有效。

最佳答案

根据我的经验，最好使用索引过程来生成图形中节点的唯一标识，然后创建一个平面散列，其中键是这个 id。使用 id 创建链接。例如:

a => b, b => c, c => d, d => a

翻译成

% 图 = ( 一个 => { 内容 => ..., 链接 => [ b ] }, b => { 内容 => ..., 链接 => [ c ] }, c => { 内容 => ..., 链接 => [ d ] }, d => { 内容 => ..., 链接=> [ a ] } );

关于algorithm - DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6327650/

文章推荐： algorithm - 水平/垂直20~30度人脸识别方向

文章推荐： java - 带有 CXF : How to use the ResponseWrapper? 的 Web 服务

文章推荐： algorithm - 这是一个线性规划问题吗？

文章推荐： java - 用java设置音量

ios - 是否需要使用无用的 object.self.self.. 或 Class.self.self.. ？
让我们写一个简单的类在我的脑海中解释: class SomeClass { var happyToUsed = 10 } 并创建一个对象 let someObject = SomeClass(
rust - 什么时候在方法中使用 self、&self 和 &mut self？
采用 self 的方法与采用 &self 甚至 &mut self 的方法有什么区别？例如 impl SomeStruct { fn example1(self) { } fn ex
python - 当在另一个函数(self)中声明函数(self)时，“self”丢失了一些东西
请观察以下代码(Win10上的python 3.6，PyCharm)，函数thread0(self)作为线程成功启动，但是 thread1(self)似乎与thread0(self)不同已设置。 se
javascript - JavaScript 中 self.self == self check 的目标是什么？
backbone.js 开始于: //Establish the root object, `window` (`self`) in the browser, or `global` on the s
objective-c - 是否执行 self = self init;返回 self ； Objective-C 中的效果与 swift 中 self.init() 的效果相同吗？
做的事: self = self.init; return self; 在 Objective-C 中具有相同的效果: self.init() 快速？例如，在这种情况下: else if([form
ios - 如果他们引用的对象被释放，守卫是否可以在使用 [weak self] 的闭包中让 `self` = self 导致崩溃？
我查看了关于堆栈溢出的一些关于使用[weak self]和[unowned self]的问题的评论。我需要确保我理解正确。我正在使用最新的 Xcode - Xcode 13.4，最新的 macOS
ios - 如何纠正在 "self' 调用或赋值给 'self.init' 之前使用 'self' 的错误？
我面临在以下模型类代码中的 self.init 调用或分配给 self 之前使用 self 的错误tableview单元格项目，它发生在我尝试获取表格单元格项目的文档ID之后。应该做什么？请推荐。
ios - 当 self 在转义闭包中很弱时，在 self 函数中调用 self 参数
晚上好。我对在 Swift 中转义(异步)闭包有疑问，我想知道哪种方法是解决它的最佳方法。有一个示例函数。 func exampleFunction() { functionWithEsca
swift - 我们是否需要在每个嵌套闭包内重复 `guard let self = self else { return }` 以保持强大的 self ？
我需要在内心深处保持坚强的自我。我知道声明[weak self]就够了外封闭仅一次。但是guard let self = self else { return }呢？，是否也足以为外部闭包声明一
rust - 由于多次使用 `use std::{fs::self, io::self}`，无法写入 `self`
代码 use std::{ fs::self, io::self, }; fn rmdir(path: impl AsRef) -> io::Result { fs::remo
ios - 在 'self' 调用之前使用的 'self.init' 错误或在不同模块的 init 上分配给 'self'
我检查了共享相同主题的问题，但没有一个解决我遇到的这种奇怪行为: 说我有一个简单的老学校struct : struct Person { var name: String var age:
python - Flask 邮件错误 : headers = [self. 发件人，self.reply_to] + self.recipients
我应该解释为什么我的问题不是重复的:TypeError: can only concatenate list (not “str”) to list ...所以它不是重复的，因为该帖子处理代码中出现的
Scala:非法继承； self 类型 Y 不符合 X 的 self 类型 SELF
我有一个 trait，它接受一个类型参数，我想说实现这个 trait 的对象也会符合这个类型参数(使用泛型，为了 Java 的兼容性) 以下代码: trait HandleOwner[SELF
jquery - 为什么要将 $ 与 $self 和 $body 放在一起？并且 self 与 $self 相同
这个问题在这里已经有了答案: Why would a JavaScript variable start with a dollar sign? [duplicate] (16 个答案) 关闭 8
javascript - 'self.fn.apply(self, message)' 和 'self.fn(message)' 之间有什么不同，为什么使用第一种方法？
我总是找到一些类似的代码newPromise.promiseDispatch.apply(newPromise, message)，我不明白为什么不使用newPromise.promiseDispat
python - 如何避免 __init__ 中的 "self.x = x; self.y = y; self.z = z"模式？
我看到类似的模式 def __init__(self, x, y, z): ... self.x = x self.y = y self.z = z ... 非
Doctrine2 Self Join，如何在没有关系列的情况下加入 self？
mysql查询示例: SELECT a1.* FROM agreement a1 LEFT JOIN agreement a2 on a1.agreementType = a2.agreementTy
iphone - self.delegate = self；这样做有什么问题吗？
self.delegate = self; 这样做有什么问题吗？正确的做法是什么？谢谢，尼尔。代码: (UITextField*)initWith:(id)sender:(float)X:(flo
swift - 为什么在类中需要声明 self 的结构中不需要声明 self ？
为什么要声明self在类中需要的结构中不需要？我不知道是否还有其他例子说明了这种情况，但在转义闭包的情况下，确实如此。如果闭包是非可选的(因此是非转义的)，则不需要声明 self在两者中的任何一个。
rust - &self 和 self 有什么区别？
这个问题已经有答案了: What does the ampersand (&) before `self` mean in Rust? (1 个回答) 已关闭去年。我不清楚 self 之间有什么区别

塔克拉玛干

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

algorithm - DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent