Coding with Graphs graph theory in code

Tips & Tricks

command-line arithmetic

Generate the integers from 1 to 10 using seq and use paste to create a string of + delimited values:

$ seq 1 10 | paste -s -d+
1+2+3+4+5+6+7+8+9+10

The output here is ripe for computation using bc:

$ seq 1 10 | paste -s -d+ | bc
55

Evaluate the product ∏k=1252k−1:

$ seq 1 2 50 | paste -s -d* | bc
58435841445947272053455474390625

draw

Generate a graph with geng and draw it with circo:

$ geng -q 6\
  | tail -n 15\
  | head -n 1\
  | listg -y\
  | circo -Tsvg -O

Drawing of a graph

The same but with a few style options:

$ options="-Gsize=5,5!
           -Nfixedsize=true
           -Nlabel=
           -Nshape=circle
           -Nheight=0.2
           -Nwidth=0.2
           -Nstyle=filled
           -Nfillcolor=black"

$ geng -q 6\
  | tail -n 15\
  | head -n 1\
  | listg -y\
  | circo -Tsvg -O $options

Drawing of a graph

generate regular graphs

To generate all 3-regular graphs on at most ten vertices in graph6 format:

$ seq 4 2 10 | xargs -L1 geng -q -d3D3
C~
EFz_
EUxo
G?zTb_
GCrb`o
GCZJd_
GCXmd_
GCY^B_
GQhTQg
I?BeeOwM?
I?Bcu`gM?
I?bFB_wF?
I?bEHow[?
I?`bfAWF?
I?`cu`oJ?
I?`cspoX?
I?`bM_we?
I?`cm`gM?
I?`cmPoM?
I?`amQoM?
I?`c]`oM?
I?aKZ`o[?
ICOfBaKF?
ICOf@pSb?
ICOef?kF?
ICOedPKL?
ICOedO[X?
ICQRD_kQ_
ICQRD_iR?
ICQRChgI_

split DOT data

Consider all connected graphs of order four, as generated by geng:

$ geng -qc 4
CF
CU
CV
C]
C^
C~

To transform these six graph strings into six graph files in DOT format combine listg with the -y option and csplit:

$ geng -qc 4
  | listg -y
  | csplit -sz -b '%d.gv' -f '' - '/^graph.*/' '{*}'