Simulating digital circuits with clique graphs (supplementary media)

by Carmen Cedillo and Miguel Pizaña.
January 18, 2019.

This web page and associated files are supplementary media to a paper, with the same title and by the same authors, published in Matemática Contemporânea 46 (2019) 185-193, the special number of Matemática Contemporânea dedicated to the Latin and American Workshop of Cliques in Graphs 2018.

This web page and associated files provide data and functionality to explore several 'gadgets' that can be constructed using graphs and clique graphs to simulate digital electronic circuits (including channels, signal carriers, splitters, splices, OR gates and 'dirty'-AND gates).

The code in the following files is YAGS/GAP code and requires GAP 4.5+ and YAGS 0.0.3:

Download: gadgets.g - added functionality for exploring the gadgets in GAP+YAGS.
Download: GadgetData.g - the gadgets themselves.

A typical GAP session start using these files is:

 > gap  
 --- some GAP info here ---  
 gap> RequirePackage("yags");  
 Loading  YAGS - Yet Another Graph System 0.0.3.  
 Copyright (C) 2016 by the YAGS authors; for details type: ?yags:authors  
 This is free software under GPLv3; for details type: ?yags:copyright  
 true  
 gap> Read("gadgets.g");
 gap> Draw(gg4c3,Neckties(gg4c2,gg4c3));

The file GadgetData.g is loaded from gadgets.g. Both should be present in the same directory as GAP's working directory.

Alternatively, the file AllGadgets.g contains adjacencies and coordinates for all gadgets in case you do not want to use GAP+YAGS and just want the raw data to import the graphs into another system (probably writing an importing routine). Note, however, that with these descriptions, all the info concerning which vertex corresponds to which clique is lost and it is then difficult to identify the vertices that should be painted red to match our examples.

Below we provide drawings for all the graphs defined in GadgetData.g, the names of the gadgets below are the ones used in GadgetData.g.

The basic building block is graph $gg1$ which is shown below. It contains dominated vertices which is undesirable for our purposes (because they tend to disappear), hence we add some extra vertices whenever necessary (as in $gg2$) to prevent that.

$gg1$

$gg2$

With several basic building blocks, we can construct channels (or wires, or optic fibers, etc.) to transport signals, like this:

gg3

$gg3$

Then we can place a photon on it and apply the clique operator to see it moving (click on the buttons and see):

$gg3a0$

$gg3a1:=K^2(gg3a0)$

$gg3a2:=K^4(gg3a0)$

$gg3a3:=K^6(gg3a0)$

We can now encode binary digits with photons: a binary 1 is encoded as by the presence of a photon and a binary 0 is encoded by its absence.

An OR-gate looks as follows:

gg4

$gg4$

And it performs as expected in each case. We can start by placing a photon on the upper input pin:

$gg4a0$

$gg4a1:=K^2(gg4a0)$

$gg4a2:=K^4(gg4a0)$

$gg4a3:=K^6(gg4a0)$

$gg4a4:=K^8(gg4a0)$

$gg4a5:=K^{10}(gg4a0)$

$gg4a6:=K^{12}(gg4a0)$

$gg4a7:=K^{14}(gg4a0)$

If the photon is placed on the lower input pin it works as expected:

$gg4b0$

$gg4b1:=K^2(gg4b0)$

$gg4b2:=K^4(gg4b0)$

$gg4b3:=K^6(gg4b0)$

$gg4b4:=K^8(gg4b0)$

$gg4b5:=K^{10}(gg4b0)$

$gg4b6:=K^{12}(gg4b0)$

$gg4b7:=K^{14}(gg4b0)$

Finally, placing both photons also works well:

$gg4c0$

$gg4c1:=K^2(gg4c0)$

$gg4c2:=K^4(gg4c0)$

$gg4c3:=K^6(gg4c0)$

$gg4c4:=K^8(gg4c0)$

$gg4c5:=K^{10}(gg4c0)$

$gg4c6:=K^{12}(gg4c0)$

$gg4c7:=K^{14}(gg4c0)$

A splitter is also useful to divide a signal for various other components... and it is just a reversed OR-gate:

gg5

$gg5$

It does what it should:

$gg5a0$

$gg5a1:=K^2(gg5a0)$

$gg5a2:=K^4(gg5a0)$

$gg5a3:=K^6(gg5a0)$

$gg5a4:=K^8(gg5a0)$

$gg5a5:=K^{10}(gg5a0)$

$gg5a6:=K^{12}(gg5a0)$

$gg5a7:=K^{14}(gg5a0)$

But a three-way splice needs its own design:

gg6

$gg6$

We put the three cases side by side, for easier comparison:

gg6a0
$gg6a0$

gg6a1
$gg6a1:=K^2(gg6a0)$

gg6a2
$gg6a2:=K^4(gg6a0)$

gg6a3
$gg6a3:=K^6(gg6a0)$

gg6a4
$gg6a4:=K^8(gg6a0)$

gg6a5
$gg6a5:=K^{10}(gg6a0)$

gg6b0
$gg6b0$

gg6b1
$gg6b1:=K^2(gg6b0)$

gg6b2
$gg6b2:=K^4(gg6b0)$

gg6b3
$gg6b3:=K^6(gg6b0)$

gg6b4
$gg6b4:=K^8(gg6b0)$

gg6b5
$gg6b5:=K^{10}(gg6b0)$

gg6c0
$gg6c0$

gg6c1
$gg6c1:=K^2(gg6c0)$

gg6c2
$gg6c2:=K^4(gg6c0)$

gg6c3
$gg6c3:=K^6(gg6c0)$

gg6c4
$gg6c4:=K^8(gg6c0)$

gg6c5
$gg6c5:=K^{10}(gg6c0)$

The last thing we show here is a dirty AND-gate, it performs the AND function in the sense that there is a vertex in $gg7d5:=K^{10}(gg7d0)$ which is present there only because of the presence of both photons on the input pins of $gg7d0$, indeed the orders of the corresponding graphs are: $|gg7a5|=|gg7b5|=93$, $|gg7c5|=94$ and $|gg7d5|=95$. We say that it is 'dirty' for obvious reasons. It has two outputs (at the right side), for technical reasons, but THE output is considered to be the upper right 'channel'. This gadget is the only one that is not $K^2$-invariant and it does produces quite a fuss by its own: