A shortest circuit algorithm
download program
download Delphi project

Introduction

This Delphi project isolates circuits in a network.
In the network below, elements are painted as circles with their name(A, B, C) inside.
The elements are connected to contacts, painted as black dots with their number (1,2,3).

In time this algorithm will be implemented in an AC network application.
Elements are resistors, coils, capacitors and voltage sources.
The circuits are needed to apply the Kirchhoff laws to built a system of equations.
Solving these equations shows currents and voltages in the network.



The algorithm

Starting from an element the shortest circuit is searched for.
This is done by calculating a level for each contact.
At first level 99 is applied to all contacts. Level 99 is regarded infinite.
Then, the first element is chosen, say A.
The output contact (2) of A is set to the lowest level which is 1.
Now all elements are tested for being connected to a contact with a lower level then 99.
K is such an element which input contact 2 having level 1.
The output contact (3) of K is now set to the next higher level of 1, so level 2.
Etcetera.
As long as new levels are assigned to a contact,
all elements are tested for a connection to a contact with lower level then 99.
An element which connects to a contact with level 6 sets it's other contact to level 7
only if this level was higher than 7.
Looking at element A we see levels 1 and 5 at it's contacts.
So the circuit implies 5 elements: A and 4 others.
This is the result after scanning all elements (levels have color red)



Element C has input level 2, so output level 3 is applied to contact 5.
Element D has input level 3 so output level 4.
However contact 5 has a lower level already (obtained from element C) so no change takes place for contact 5.
While applying the level to a contact, the element causing this level is recorded.
Working backward from A the circuit becomes AKCGH,
being the elements that provided to lowest level to the circuit contacts.
Now the first circuit is found, the first element (A) is disabled before the search repeats to find more circuits.
Other circuits may not include element A.
Note: not every element provides a circuit.
With A removed, there is no circuit possible containing element K.
The search is completed when all elements are disabled.
See next picture for all elements found:



The program




The red dot indicates the contact where the circuit starts.
This contact is assigned level 1. Disabled elements (horizontal lines) are painted in grey.
Vertical grid lines are contacts.



Next search starts at element B. (A) disabled.
Element D sets contact 5 to level 2.
Element C sets contact 3 to level 3.



Contact 7 (element E) starts with level 1.
F sets contact 6 to level 2.
H sets contact 1 to level 3.
So, this network is dissolved in circuits AKGCH, BCD, EFH.

The project

Elements names are preset in a Tstringgrid component where the connecting contact numbers are added.
Elements that are properly connected get the status "valid".
After entering the contacts, press restart to paint the elements in a grid (Paintbox1).
Press go to get the first circuit.
If no circuit results, press go again until the message appears : "no more elements" .
Below the grid, per contact the level is displayed together with the element that caused this level.
type TElement = record
                 valid : boolean;
                 enabled : boolean;//part of search
                 active : boolean; //not blocked 
                 ctIn,ctOut : byte;//contact in, out
                end;
     Tcontact = record
                 level : byte;
                 source : byte; //element nr
                end;
     Tcircuit = record
                 elmt : byte;    
                 sign : shortInt;//1:in>out;-1:out>in
                end;
var element : array[1..15] of Telement;
    contact : array[1..15] of Tcontact;
    circuit : array[1..15] of Tcircuit;
    circL   : byte;     //circuit length
    elmntsOK : boolean; //elements OK flag
A valid element means that it exists and is properly connected.
Enabled means that it is part of the search for circuits.
After being used as start element it is disabled to prevent it becoming part of another circuit.
Active means that the element is part of the search and may lower the level of a contact.
After done so, the active status is dropped.
At restart, all valid elements are set to enabled.
At pressing go all enabled elements are set to the active state.
Most procedures are too long to be published.
Please refer to the source code.
Finally, I mention some specific procedures and their purpose:

procedure TForm1.okBtnClick(Sender: TObject);
This is the restart button.
It checks the stringgrid contacts (no equal contacts, not out of range).

function procGo : byte;
Called by a click event on the go button it finds the circuits by scanning
the elements and checking the contacts.
The result (0,1,2) indicates "new circuit", "no circuit" or "out of elements".
ProcGo calls procedure InitSearch(var n : byte);

n is the first enabled element, from where the search will start.

function extractCircuit(ct : byte) : byte;
ct is the contact to start.
Works backward in the contact list to get the circuit.

procedure Hline(var x1,x2,y: word; el : byte);
procedure Vline(var x,y1,y2 : word; n1,n2 : byte);

supply the grid coordinates (x,y) to paint horizontal- (element) or vertical- (contacts) lines.

Four demo's are added.
 Type TDemo = record
               ch : char;//A,B,C
               c1 : byte;//input contact
               c2 : byte;//output contact
              end;
const demo1 : array[1..4] of Tdemo =
      ((ch:'A'; c1: 1; c2: 2),
       (ch:'B'; c1: 2; c2: 3),
       (ch:'C'; c1: 3; c2: 4),
       (ch:'D'; c1: 4; c2: 1));
	   	      
procedure TForm1.demoBtn1Click(Sender: TObject);//common for demo's 1..4
var p : PAdemo; //pointer to array[1..15] of TElement;
       elcount,n,nr,tg : byte;
begin
 p := nil;
 elcount := 0;
 tg := Tspeedbutton(sender).tag;
 case tg of
  1 : begin
       p := @demo1;
       elcount := high(demo1);
      end;
  2 : begin
       p := @demo2;
       elcount := high(demo2);
      end;
  3 : begin
       p := @demo3;
       elcount := high(demo3);
      end;
  4 : begin
       p := @demo4;
       elcount := high(demo4);
      end;
 end;
 clearElements;
 clearcontacts;
 clearcircuit;
 paintgrid;
 msgtext.caption := 'loaded demo '+inttostr(tg);
 for n := 1 to elcount do
  with p^[n] do
   begin
    nr := pos(ch,elmntnames)-1;
    stringgrid1.cells[1,nr] := inttostr(c1);
    stringgrid1.cells[2,nr] := inttostr(c2);
   end;
end;
This concludes the shortest circuit algorithm description.
Please refer to the source code for more details.