Hi Mark,

since opinions about aesthetics can differ widely, could you please post an example of a particularly ugly result? (Perhaps with a short critique.)

Here's the netlist:

dbm

.tran 1.0000e-08 5.0000e-06 0.0000e+00

*#iplot all

*#run

*#quit

.print tran v(8) v(10) v(1) i(v1)

.model bc214 pnp bf=140 isc=15e-9

+tf=2n tr=7n vaf=45 cje=5pf vje=0.6 cjc=2pf ikf=0.01

r1 1 0 22

r2 11 2 22

v1 7 0 dc 12

v2 6 0 dc 7.5

v3 8 0 sin 12 50e-3 10meg

v4 9 0 dc 7.5

v5 10 0 sin 7.5 50e-3 1meg

v6 11 0 dc 15

q1 4 8 2 bc214

q2 0 9 4 bc214

q3 0 10 3 bc214

q4 3 7 2 bc214

q5 1 6 3 bc214

q6 1 10 4 bc214

.end

The first picture is the original, the second is the reverse-engineered version. The actual layout doesn't matter, as long as the wires don't overlap, go through components or over pins (basically the same criteria as would apply to a PCB). However, it would be nice if the layout could be a bit more 2-dimensional.

Hi Mark,

in a first version of a program, I didn't care to produce graphical output; instead, the numerical coordinates of the elements are generated. In order to permit a simple impression of the result, I manually made a sketch according to the numbers.

What's your opinion of the result? One wire crosses Q6, connected to its basis, but this is sometimes seen even in professional schematics of ICs. Q4 could be shifted to the left, and the sources V1, V2, and V5 could be placed nearer to the respective transistor. IMHO, at least it's less ugly than your output. :-)

Compared to my output, it's downright beautiful. I don't mind the bases connected in that manner, as there's no ambiguity there and, as you say, some schematic drawing standards actually permit that.

Do you prefer the graphical output on screen or as a file?

I'd rather know how the algorithm works...

If I understand correctly, this will be part of a commercial product, so I planned to exchange my C program for a four week holiday in Australia, but now Olatunji A Shobande seems to be interested in the algorithm, too, and I guess I cannot expect him to pay for my holiday in Scotland as well :-) ... so, since this is RG let's make the algorithm open source:

There are two main points:

1. Being a visual thinker myself, often I advice my students to redraw the schematics given in exercises in such a way that the height of the electrical potential is reflected by the height in the drawing, i. e. by the y value (not always to scale, of course).

So, first the electrical potentials of the wires are determined or at least upper and lower limits estimated. With sources, this is straightforward; with transistors, we can apply the polarities and VBE in normal operation. With resistors in series, one can apply the voltage divider rule. Finally, in cases where only voltage ranges apply the mean value between upper and lower limit is taken. In the example, we get:

p0 = 0V, p1 = 3.7 V, p2 = 12.6 V, p3 = 8.1 V, p4 = 8.1 V, p6 = 7.5 V, p7 = 12 V, p8 = 12 V, p9 = 7.5 V, p10 = 7.5 V, p11 = 15 V

Then y values are assigned to the wires, in the order of increasing potential, the step width being determined by the maximum height of the drawn components. I chose a step width of 2, resulting in:

y0 = 0, y1 = 2, y2 = 18, y3 = 10, y4 = 12, y6 = 4, y7 = 14, y8 = 16, y9 = 6, y10 = 8, y11 = 20

This gives 11 horizontal rails with sufficient distance between adjacent rails for the placement of elements.

The extension of the rails in x dimension has to be larger than the number of components (transistors counting 2).

2. Usually, the signal path will start on the left side, and will run through the active components to the right. Therefore, placing starts with the active components. The first transistor placed is simply the first one in the netlist. This placing is triggered by a function which just scans all transistors in the netlist not yet placed. But the placing itself is done by a recursive function which determines if there are further transistors connected directly to the current transistor, and if so, where the largest number of transistors is. Then the function calls itself for one of these transistors.

In order to avoid backtracking to already completely harvested wires, one function parameter is the number of the wire connecting the current transistor to the next, and another parameter is a number which is compared to the number of adjacent transistors at the current wire. During the first call it is set to 2, during further calls it is incremented by 1. If this number equals the number of transistors then the current wire is abandoned.

In the example, the series is: Q1, Q2, Q6, Q5, Q3, Q4

Each transistor is placed on increasing x values, at the moment with step width 2. However, a considerably larger step width might be preferable in conjunction with the final x compression (see below).

If there were further clusters of transistors, the placing would continue with Q7.

The recursive function described above could be supplemented by another one with the ability to "look" beyond one resistor or capacitor for further transistors. In this way, the signal path could be traced even if the active components are coupled by passive ones. (end of point 2)

The placing of the passive components is done in such a way as to avoid increasing the length of wires if possible. The placing of the sources is done last.

Two steps remain which are not yet completely implemented: x compression (decreasing the distances in x dimension) and y compression (placing several rails on the same y value if they are non-overlapping).

Three linked lists are employed: A 1D one for the components and a second 1D one for the wires. The third one is 2D for the placement.

Placing and routing is not my field of expertise, so I don't know how my solution compares to existing ones. Anyway, this was a nice exercise.

Actually, it's not a commercial product. We give the analog tools away for free. Check this page:

www.designsim.com.au/dssdnld.html

If you circuit is a digital circuit or have digital application . Then write your code verilog and use cadence or synopsis tools. They provide result with accuracy and if it analog then go with open source tool electric or mentor graphics or virtuoso.

I am not planning (or volunteering) to write it, however, my first attempt would be to approach it as an adaptive neural net. These nets adjust the location of their nodes such that the sum of all branch lengths is minimized. One still could have crossed wires. In Numerical Recipes in C, the autors describe the metropole algorithm: adding constraints to prevent getting Gordian knots (main cause: multiple crossed wires). However, with nowadays computer power, it might be better to use simulated annealing and throw away solutions with crossed wires, or heavily penalize them. Algorithms to find crossed wires do exist.