Skip to content

Instantly share code, notes, and snippets.

View MHenderson's full-sized avatar

Matthew Henderson MHenderson

View GitHub Profile
@MHenderson
MHenderson / Makefile
Last active August 29, 2015 14:01
Greedy colouring of Queen Graphs.
src_dir:=~/workspace/graphs-collection/src/Colouring/Trick
generate_seeds:=./generate_seeds
simulation:=./simulation2
get_colours:=get_colours.sed
output:=output.txt
approx:=chromatic_approx.txt
seeds:=seeds.txt
problem_file:=$(src_dir)/queen16_16.col
result_file=$(addsuffix .res, $(problem_file))
@MHenderson
MHenderson / colour
Last active August 29, 2015 14:01
Apply a colouring from Culberson's colouring programs output to a file in DOT format.
!#/bin/bash
r=1 # colouring number. Look at row 2r of the .res file.
n=1
p=$(( 2 * r ))
s=`sed "$p!d" $1` #generalise from 2 to 2r
while [ -n "$s" ]
do
temp=${s#?}
char=${s%"$temp"}
@MHenderson
MHenderson / Makefile
Created May 30, 2014 10:29
Drawing Coloured Queen Graphs
output_dir:=./output
svg_options:=-s\
-Tsvg\
-Gsize=4,4\!\
-Nwidth=1\
-Nheight=1\
-Nfixedsize=true\
-Nlabel=\
-Nshape=box\
@MHenderson
MHenderson / Makefile
Created June 5, 2014 13:33
Colouring the Frucht graph with gvpr.
output_dir:=./output
src_dir=.
svg_options:=-s\
-Tsvg\
-Gsize=4,4\!\
-Groot=3\
-Nwidth=0.3\
-Nfixedsize=true\
-Nlabel=\
@MHenderson
MHenderson / graph-colouring-noteboook.ipynb
Last active November 2, 2015 16:55
Graph colouring IPython Notebook.
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@MHenderson
MHenderson / colouring-simulation-notebook.ipynb
Last active October 19, 2015 13:11
Investigating colourings of graphs on seven or fewer vertices.
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@MHenderson
MHenderson / simulation
Created June 27, 2014 11:01
Improved greedy colouring of small graphs with ccli.
#!/bin/bash
orders=( 0 0 1 3 10 33 155 1043 12345 274667 )
type=simple
for ordering in random incdeg decdeg inorder
do
for n in {2..8}
do
src_folder=/home/matthew/workspace/graphs-collection/src/Small/$n
@MHenderson
MHenderson / recursive-colouring.ipynb
Last active August 29, 2015 14:03
Vertex colouring by recursive maximal independent set extraction.
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@MHenderson
MHenderson / chromatic-polynomial-notebook.ipynb
Last active August 29, 2015 14:03
Chromatic polynomials via NetworkX and tutte_bhkk.
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@MHenderson
MHenderson / chromatic.sh
Last active July 2, 2019 21:24
A script to compute the chromatic number of graphs in Graphviz DOT format.
#!/bin/bash
file_gv=$1
n_edges_re='s/\([0-9]*\) %.*/\1/p'
n_edges=`gc -e $file_gv\
| sed -n "${n_edges_re}"\
| tr -d ' '`