R-Type using SPQR-Tree decomposition

[ghost]

I start a new discussion here because discord seem to be not the best way to include code. So, I let you a little update here about my research on the circuit to r-type process.

Finding Split Components / SPQR Tree decomposition

For the proof-of-concept, I've use the 'Fender Bassman Tone Stack' example found page 99 / figure 2.8 of the Kurt James Werner dissertation : 'Virtual Analog Modeling of Audio Circuitry using Wave Digital Filters' (2016).

I've test various implementation of the corrected version of Tarjan's SPQR-Tree decomposition algorithm. But all the implementations fails to produce the same result as the (manual?) decomposition found in the reference paper. After testing some C++ implementation (OGDF/ wailea / ...) that produce [ 3 S | 1 R ] not the [ 4 S | 1 R ] of the Werner paper. I've test the python implementation of sagemath that allow me to show you where is the problem:

This is the log of the sage console for the test on the reference circuit:

sage: from sage.graphs.connectivity import TriconnectivitySPQR
sage: from sage.graphs.connectivity import spqr_tree_to_graph
sage: G = Graph([(1,2,"1"),(2,3,"2"),(2,4,"3"),(3,6,"4"),(3,8,"5"),(4,5,"6"),(5,6,"7"),(6,7,"8"),(7,8,"9"),(8,1,"10")])
sage: G.order()
8
sage: G.size()
10
sage: list(G)
[1, 2, 3, 4, 5, 6, 7, 8]
sage: list(G.edge_iterator())
[(1, 2, '1'),
 (1, 8, '10'),
 (2, 3, '2'),
 (2, 4, '3'),
 (3, 6, '4'),
 (3, 8, '5'),
 (4, 5, '6'),
 (5, 6, '7'),
 (6, 7, '8'),
 (7, 8, '9')]

sage: tric = TriconnectivitySPQR(G)
sage: tric.print_triconnected_components()
Polygon: [(6, 7, '8'), (7, 8, '9'), (6, 8, 'newVEdge0')]
Polygon: [(4, 5, '6'), (2, 4, '3'), (5, 6, '7'), (6, 2, 'newVEdge2')]
Triconnected: [(2, 3, '2'), (3, 6, '4'), (6, 2, 'newVEdge2'), (6, 8, 'newVEdge0'), (3, 8, '5'), (2, 8, 'newVEdge3')]
Polygon: [(1, 8, '10'), (2, 8, 'newVEdge3'), (1, 2, '1')]

sage: T = tric.get_spqr_tree()
sage: list(T)
[('S', Multi-graph on 3 vertices),
 ('S', Multi-graph on 4 vertices),
 ('R', Multi-graph on 4 vertices),
 ('S', Multi-graph on 3 vertices)]

Rewriting the components with the node's letter (and the primes for the virtual edges) used in the Werner paper we found:

(c) Finding Split Components.

S3 : [(f, g, 8), (g, h, 9), (f, h, 3')]
S24: [(d, e, 6), (b, d, 3), (e, f, 7), (f, b, 2')]
R  : [(b, c, 2), (c, f, 4), (f, b, 2'), (f, h, 3'), (c, h, 5'), (b, h, 1')]
S1 : [(a, h, 10), (b, h, 1'), (a, b, 1)]

All seem ok except that S2 and S4 are concatenated into a single S (S24 here) component, we loose the 4' virtual edge. That explain why all the implementation of the 2001 paper : A linear time implementation of SPQR-trees produce the same result : 3xS vs. 4xS for the (manual?) decomposition.

So, the first constatation is that the automatic triconnected components decomposition fail to follow the WDF's scientific litterature for the generalized SPQR-Tree decomposition.

But. Because there's a but. We can found the pseudo-code of the Tarjan's algorithm (corrected in the 2001 paper) in the header of wailea C++ implementation : spqr_decomposer.hpp and more, the process is explain in the 2017's PDF : Explaining Hopcroft, Tarjan, Gutwenger, and Mutzel’s SPQR Decomposition Algorithm

I'm really not a graph-theory expert, but maybe it's possible to recursively recall the triconnected components split to the S24 subgraph ? Or if not, maybe it's possible to adapt the current algorithm (following the pseudo-code for a specific implementation) to limit the path search to a maximum of 3 edges (including the generated virtual edge) for the 'polygon' components. I need expertise to know if theses assertions are correct or not.

The following process : MNA to R-Type

Thank's to your starring of the SHARC WDF Library repo, we have an idea to the process following the previously identified procedure. So, a quick look to the code allow us to understand that before the MNA process the circuit need to be adapted following the chapter 2.2.1 Thévenin Adaptors (Werner 2016 dissertation page 102) that is pre-requise for the MNA procedure.

It seem to be a 'generic' method that can be automatised if however the previous method (SQPR decomposition) is solved. This nevertheless requires a more in-depth analysis of the literature on the subject.

Sincerely,
Max