StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POA DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent
primarykey
Id
6327650
data
AcceptedAnswerId
0
AnswerCount
1
ClosedDate
CommentCount
5
CommunityOwnedDate
CreationDate
2011-06-13T07:24:22.527
FavoriteCount
0
LastActivityDate
2012-01-26T20:32:32.097
LastEditDate
2011-07-06T22:16:16.233
LastEditorUserId
18850
OwnerUserId
795539
ParentId
0
PostTypeId
1
Score
4
ViewCount
431
LastEditorDisplayName
text
Body
I have netlist (collection of subcircuits) of circuit schematic, generally is created by some SPICE simulator. It generally has hierarchy (A top level subcircuit calls or instantiates different subcircuits and defines some connectivities amongst them through pins). A sample netlist looks like: <pre><code>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 </code></pre> Now in different hierarchies same subcircuit can be instantiated. Every called subcircuit is defined before the calling subcircuit. This kind of graph is called Directed Acyclic GRAPH. I have made a self referencing HASH table from a netlist to save the space. If a subcircuit is calling some subcircuit instance it is then pointing the pin. At the very last hierarchy we will get a MOSFET D or S or G or B node (as the AN2D0 subcircuit has been defined). If any net (connection between to instances' pin) is brought out form the hierarchy (nothing but calling subcircuit, e.g. net5) to parent calling subcircuit it is called pin(e.g. Z) and will always be listed in the present subcircuit definition line followed by its name (subckt AN2D0 A1 A2 VDD VSS Z). I have created a hash of hashes of hashes. <pre><code>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 </code></pre> For the present case the GRAPH looks like: <pre><code>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 </code></pre> After this a subcircuit name and a pin of the same will be given which may be instantiated from any level hierarchy and we have to find the parent i.e. trace back the parent till the net has been pulled up as pin. And then stress back all the leaves(MOSFETS D or G or S or B pin). Please suggest what kind of algorithm will be best suitable for this and whether the storing them in a Self referencing hash table is efficient or not.
Tags
<algorithm><perl><perl-data-structures>
Title
A DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. UShexcoder
UserOwnerUserId
1. USTamal Das
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POA DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POA DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 POA DAG : Self referencing HASH: searching the first level parent from any level child and then search leaves of that parent
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.