-------------------
-- Package Header
-------------------
-- Forked from Nauty:
-- Copyright 2010, 2011 David W. Cook II
-- You may redistribute this file under the terms of the GNU General Public
-- License as published by the Free Software Foundation, either version 2
-- of the License, or any later version.
-- Copyright 2011, 2013 David W. Cook II
-- You may redistribute this file under the terms of the GNU General Public
-- License as published by the Free Software Foundation, either version 2
-- of the License, or any later version.
newPackage select((
"NautyGraphs",
Version => "1.4.3.1",
Date => "01. March 2013",
Authors => {{Name => "David Cook II",
Email => "dcook8@nd.edu",
HomePage => "http://www.nd.edu/~dcook8"}},
Headline => "interface to nauty (Graphs fork)",
Keywords => {"Graph Theory", "Interfaces"},
Configuration => {"path" => ""},
PackageExports => {"Graphs"},
DebuggingMode => false,
), x -> x =!= null)
-------------------
-- Configuration
-------------------
-- for backward compatibility
if not programPaths#?"nauty" and NautyGraphs#Options#Configuration#"path" != ""
then programPaths#"nauty" = NautyGraphs#Options#Configuration#"path"
-------------------
-- Exports
-------------------
export {
-- Methods
"addEdges",
"areIsomorphic",
"buildGraphFilter",
"countGraphs",
"filterGraphs",
"generateBipartiteGraphs",
"generateGraphs",
"generateRandomGraphs",
"generateRandomRegularGraphs",
"graph6ToSparse6",
"graphComplement",
"graphToString",
"isPlanar",
"neighborhoodComplements",
"newEdges",
"onlyPlanar",
"relabelBipartite",
"relabelGraph",
"removeEdges",
"removeIsomorphs",
"sparse6ToGraph6",
"stringToEdgeIdeal",
"stringToGraph",
-- Options
"Class2Degree2",
"Class2DistinctNeighborhoods",
"Class2MaxCommonNeighbors",
"MaxDegree",
"MinDegree",
"NoNew3Cycles",
"NoNew4Cycles",
"NoNew5Cycles",
"NoNewOddCycles",
"NoNewSmallCycles",
"Only4CycleFree",
"OnlyBiconnected",
"OnlyBipartite",
"OnlyConnected",
"OnlyIfSmaller",
"OnlyTriangleFree",
"RandomSeed"
}
-------------------
-- Exported Code
-------------------
-- Finds all graphs of G with an extra edge added.
addEdges = method(Options => {MaxDegree => null, NoNewOddCycles => false, NoNew3Cycles => false, NoNew4Cycles => false, NoNew5Cycles => false, NoNewSmallCycles => null})
addEdges List := List => opts -> L -> (
cmdStr := "addedgeg -q" |
optionZZ(opts.MaxDegree, 0, "addEdges", "MaxDegree", "D") |
optionBoolean(opts.NoNewOddCycles, "addEdges", "NoNewOddCycles", "b") |
optionBoolean(opts.NoNew3Cycles, "addEdges", "NoNew3Cycles", "t") |
optionBoolean(opts.NoNew4Cycles, "addEdges", "NoNew4Cycles", "f") |
optionBoolean(opts.NoNew5Cycles, "addEdges", "NoNew5Cycles", "F") |
optionZZ(opts.NoNewSmallCycles, 0, "addEdges", "NoNewSmallCycles", "z");
callNauty(cmdStr, L)
)
addEdges String := List => opts -> S -> addEdges({S}, opts)
addEdges Graph := List => opts -> G -> stringToGraph \ addEdges({G}, opts)
-- Determines if two graphs are isomorphic.
areIsomorphic = method()
areIsomorphic (String, String) := Boolean => (G, H) -> (#callNauty("shortg -q", {G, H})) == 1
areIsomorphic (Graph, Graph) := Boolean => (G, H) -> areIsomorphic(graphToString G, graphToString H)
areIsomorphic (String, Graph) := Boolean => (G, H) -> areIsomorphic(G, graphToString H)
areIsomorphic (Graph, String) := Boolean => (G, H) -> areIsomorphic(graphToString G, H)
Graph == Graph := areIsomorphic
Graph == String := areIsomorphic
String == Graph := areIsomorphic
-- Builds a filter string for countGraphs and filterGraphs.
buildGraphFilter = method()
buildGraphFilter HashTable := String => h -> (
validType := (str, type) -> h#?str and instance(h#str, type);
propStart := str -> if validType(str, Boolean) and h#str then "-~" else "-";
propBuildBoolean := (str, flag) -> if validType(str, Boolean) then ((if h#str then "-" else "-~") | flag | " ") else "";
propBuildZZSeq := (str, flag) -> (
if validType(str, ZZ) and h#str >= 0 then (
propStart("Negate" | str) | flag | toString h#str | " "
) else if validType(str, Sequence) and #h#str == 2 then (
if instance(h#str#0, Nothing) and instance(h#str#1, ZZ) and h#str#1 >= 0 then (
propStart("Negate" | str) | flag | ":" | toString h#str#1 | " "
) else if instance(h#str#0, ZZ) and instance(h#str#1, Nothing) and h#str#0 >= 0 then (
propStart("Negate" | str) | flag | toString h#str#0 | ":" | " "
) else if instance(h#str#0, ZZ) and instance(h#str#1, ZZ) and h#str#0 >=0 and h#str#1 >= h#str#0 then (
propStart("Negate" | str) | flag | toString h#str#0 | ":" | toString h#str#1 | " "
) else ""
) else ""
);
concatenate {propBuildZZSeq("NumVertices", "n"), propBuildZZSeq("NumEdges", "e"),
propBuildZZSeq("MinDegree", "d"), propBuildZZSeq("MaxDegree", "D"),
propBuildBoolean("Regular", "r"), propBuildBoolean("Bipartite", "b"),
propBuildZZSeq("Radius", "z"), propBuildZZSeq("Diameter", "Z"),
propBuildZZSeq("Girth", "g"), propBuildZZSeq("NumCycles", "Y"),
propBuildZZSeq("NumTriangles", "T"), propBuildBoolean("Eulerian", "E"),
propBuildZZSeq("GroupSize", "a"), propBuildZZSeq("Orbits", "o"),
propBuildZZSeq("FixedPoints", "F"), propBuildBoolean("VertexTransitive", "t"),
propBuildZZSeq("Connectivity", "c"),
propBuildZZSeq("MinCommonNbrsAdj", "i"), propBuildZZSeq("MaxCommonNbrsAdj", "I"),
propBuildZZSeq("MinCommonNbrsNonAdj", "j"), propBuildZZSeq("MaxCommonNbrsNonAdj", "J")
}
)
buildGraphFilter List := String => L -> buildGraphFilter hashTable L
-- Count the graphs with certain properties.
countGraphs = method()
countGraphs (List, String) := ZZ => (L, filter) -> (
if #L == 0 or #filter == 0 then return #L;
r := callNauty("countg -q " | filter, L);
if not instance(r, List) or #r == 0 then return;
p := regex("g", first r);
if not instance(p, Nothing) then value substring((0, first first regex("g", first r)), first r)
else error("countGraphs: One or more of the input graphs was formatted incorrectly.")
)
countGraphs (List, HashTable) := ZZ => (L, fh) -> countGraphs(L, buildGraphFilter fh)
countGraphs (List, List) := ZZ => (L, fl) -> countGraphs(L, buildGraphFilter hashTable fl)
-- Filter a list of graphs for certain properties.
filterGraphs = method()
filterGraphs (List, String) := List => (L, filter) -> (
if #L == 0 or #filter == 0 then return L;
-- nauty outputs useful information to the stderr and (to us) junk on stdout
r := callNauty("pickg -qV " | filter, L, ReadError => true);
-- In nauty 2.4r2, the index is the first number.
for l in r list ( s := select("[[:digit:]]+", l); if #s == 0 then continue else L_(-1 + value first s) )
)
filterGraphs (List, HashTable) := List => (L, fh) -> filterGraphs(L, buildGraphFilter fh)
filterGraphs (List, List) := List => (L, fl) -> filterGraphs(L, buildGraphFilter hashTable fl)
-- Generates all bipartite graphs of a given type.
generateBipartiteGraphs = method(Options => {OnlyConnected => false, Class2DistinctNeighborhoods => false, Class2Degree2 => false, Class2MaxCommonNeighbors => null, MaxDegree => null, MinDegree => null})
generateBipartiteGraphs (ZZ, ZZ, ZZ, ZZ) := List => opts -> (n, m, le, ue) -> (
if n < 1 then error("generateBipartiteGraphs: nauty does not like graphs with non-positive numbers of vertices.");
if m < 0 then error("generateBipartiteGraphs: The first class cannot have a negative number of vertices.");
if m > n then error("generateBipartiteGraphs: The first class has too many vertices.");
if m == 0 then (
if n == 1 then return {"@"};
if opts.OnlyConnected then return {};
m = n;
);
if le > ue or le > m*(n-m) or ue < 0 then return {};
cmdStr := "genbg -q" |
optionBoolean(opts.OnlyConnected, "generateBipartiteGraphs", "OnlyConnected", "c") |
optionBoolean(opts.Class2DistinctNeighborhoods, "generateBipartiteGraphs", "Class2DistinctNeighborhoods", "z") |
optionBoolean(opts.Class2Degree2, "generateBipartiteGraphs", "Class2Degree2", "F") |
optionZZ(opts.Class2MaxCommonNeighbors, 0, "generateBipartiteGraphs", "Class2MaxCommonNeighbors", "Z") |
optionZZ(opts.MinDegree, 0, "generateBipartiteGraphs", "MinDegree", "d") |
optionZZ(opts.MaxDegree, 0, "generateBipartiteGraphs", "MaxDegree", "D") |
(" " | toString m | " " | toString(n-m) | " " | toString le | ":" | toString ue);
callNauty(cmdStr, {})
)
generateBipartiteGraphs (ZZ, ZZ, ZZ) := List => opts -> (n, m, e) -> generateBipartiteGraphs(n, m, e, e, opts)
generateBipartiteGraphs (ZZ, ZZ) := List => opts -> (n, m) -> generateBipartiteGraphs(n, m, 0, m * (n-m), opts)
generateBipartiteGraphs ZZ := List => opts -> n -> unique flatten apply(n, i -> generateBipartiteGraphs(n, i, opts))
-- Generates all graphs of a given type.
generateGraphs = method(Options => {OnlyConnected => false, OnlyBiconnected => false, OnlyTriangleFree => false, Only4CycleFree => false, OnlyBipartite => false, MinDegree => null, MaxDegree => null})
generateGraphs (ZZ, ZZ, ZZ) := List => opts -> (n, le, ue) -> (
if n < 1 then error("generateGraphs: nauty does not like graphs with non-positive numbers of vertices.");
if le > ue or le > binomial(n,2) or ue < 0 then return {};
le = max(le, 0);
cmdStr := "geng -q" |
optionBoolean(opts.OnlyConnected, "generateGraphs", "OnlyConnected", "c") |
optionBoolean(opts.OnlyBiconnected, "generateGraphs", "OnlyBiconnected", "C") |
optionBoolean(opts.OnlyTriangleFree, "generateGraphs", "OnlyTriangleFree", "t") |
optionBoolean(opts.Only4CycleFree, "generateGraphs", "Only4CycleFree", "f") |
optionBoolean(opts.OnlyBipartite, "generateGraphs", "OnlyBipartite", "b") |
optionZZ(opts.MinDegree, 0, "generateBipartiteGraphs", "MinDegree", "d") |
optionZZ(opts.MaxDegree, 0, "generateBipartiteGraphs", "MaxDegree", "D") |
(" " | toString n | " " | toString le | ":" | toString ue);
callNauty(cmdStr, {})
)
generateGraphs (ZZ, ZZ) := List => opts -> (n, e) -> generateGraphs(n, e, e, opts)
generateGraphs ZZ := List => opts -> n -> generateGraphs(n, 0, binomial(n, 2), opts)
-- Generate random graphs with given properties.
generateRandomGraphs = method(Options => {RandomSeed => null})
generateRandomGraphs (ZZ, ZZ, ZZ) := List => opts -> (n, num, p) -> (
if n < 1 then error("generateRandomGraphs: nauty does not like graphs with non-positive numbers of vertices.");
if p < 1 then error("generateRandomGraphs: Probability must be positive.");
if not instance(opts.RandomSeed, Nothing) and not instance(opts.RandomSeed, ZZ) then error("generateRandomGraphs: Option [RandomSeed] is not a valid type, i.e., ZZ or Nothing.");
if p > 100000000 then p = 100000000; --silently bound it
if num < 1 then return {};
rndSeed := if instance(opts.RandomSeed, ZZ) then " -S" | toString(opts.RandomSeed % 2^30) else "";
callNauty("genrang -qg -P" | toString p | " " | toString n | " " | toString num | rndSeed, {})
)
generateRandomGraphs (ZZ, ZZ, QQ) := List => opts -> (n, num, p) -> (
if n < 1 then error("generateRandomGraphs: nauty does not like graphs with non-positive numbers of vertices.");
if num < 1 then return {};
if p <= 0 or p > 1 then error("generateRandomGraphs: Probability must be between 0 and 1.");
if not instance(opts.RandomSeed, Nothing) and not instance(opts.RandomSeed, ZZ) then error("generateRandomGraphs: Option [RandomSeed] is not a valid type, i.e., ZZ or Nothing.");
rndSeed := if instance(opts.RandomSeed, ZZ) then " -S" | toString(opts.RandomSeed % 2^30) else "";
-- limit the precision to 1e-8
q := round(100000000 * p) / 100000000;
callNauty("genrang -qg -P" | toString q | " " | toString n | " " | toString num | rndSeed, {})
)
generateRandomGraphs (ZZ, ZZ, RR) := List => opts -> (n, num, p) -> generateRandomGraphs(n, num, promote(p, QQ), opts)
generateRandomGraphs (ZZ, ZZ) := List => opts -> (n, num) -> (
if n < 1 then error("generateRandomGraphs: nauty does not like graphs with non-positive numbers of vertices.");
if not instance(opts.RandomSeed, Nothing) and not instance(opts.RandomSeed, ZZ) then error("generateRandomGraphs: Option [RandomSeed] is not a valid type, i.e., ZZ or Nothing.");
if num < 1 then return {};
rndSeed := if instance(opts.RandomSeed, ZZ) then " -S" | toString(opts.RandomSeed % 2^30) else "";
callNauty("genrang -qg " | toString n | " " | toString num | rndSeed, {})
)
-- Generate random regular graphs in the Ring with given properties.
generateRandomRegularGraphs = method(Options => {RandomSeed => null})
generateRandomRegularGraphs (ZZ, ZZ, ZZ) := List => opts -> (n, num, reg) -> (
if n < 1 then error("generateRandomRegularGraphs: nauty does not like graphs with non-positive numbers of vertices.");
if not instance(opts.RandomSeed, Nothing) and not instance(opts.RandomSeed, ZZ) then error("generateRandomGraphs: Option [RandomSeed] is not a valid type, i.e., ZZ or Nothing.");
if num < 1 then return {};
if reg < 1 or reg >= n then error("generateRandomRegularGraphs: Regularity must be positive but less than the number of vertices.");
if odd n and odd reg then error("generateRandomRegularGraphs: There are no graphs with odd regularity on an odd number of vertices.");
rndSeed := if instance(opts.RandomSeed, ZZ) then " -S" | toString(opts.RandomSeed % 2^30) else "";
callNauty("genrang -qg -r" | toString reg | " " | toString n | " " | toString num | rndSeed, {})
)
-- Converts a Graph6 string to a Sparse6 string.
graph6ToSparse6 = method()
graph6ToSparse6 String := String => g6 -> first callNauty("copyg -qs", {g6})
-- Complements a graph.
graphComplement = method(Options => {OnlyIfSmaller => false})
graphComplement List := List => opts -> L -> (
cmdStr := "complg -q" | optionBoolean(opts.OnlyIfSmaller, "graphComplement", "OnlyIfSmaller", "r");
callNauty(cmdStr, L)
)
graphComplement String := String => opts -> S -> first graphComplement({S}, opts)
graphComplement Graph := Graph => opts -> G -> stringToGraph first graphComplement({G}, opts)
-- Converts a graph to a string in Graph6 format.
graphToString = method()
graphToString (List, ZZ) := String => (E, n) -> (
if n < 1 then error("graphToString: nauty does not like graphs with non-positive numbers of vertices.");
if n > 68719476735 then error("graphToString: nauty does not like too many vertices (more than 68719476735).");
if any(E, e -> #e != 2) or any(E, e -> first e == last e) or max(flatten E) >= n then error("graphToString: Edges are malformed.");
N := take(reverse apply(6, i -> (n // 2^(6*i)) % 2^6), if n < 63 then -1 else if n < 258047 then -3 else -6);
B := new MutableList from toList(6*ceiling(binomial(n,2)/6):0);
-- the edges must be in {min, max} order, so sort them
for e in sort \ E do B#(binomial(last e, 2) + first e) = 1;
ascii apply(N | apply(pack(6, toList B), b -> fold((i,j) -> i*2+j, b)), l -> l + 63)
)
graphToString MonomialIdeal := String => I -> graphToString(indices \ first entries generators I, #gens ring I)
graphToString Ideal := String => I -> graphToString monomialIdeal I
graphToString Graph := String => G -> (
V := vertices G;
idx := hashTable apply(#V, i-> V_i => i);
E := apply(toList \ edges G, e -> {idx#(e_0), idx#(e_1)});
graphToString(E, #V)
);
graphToString String := String => S -> S
-- Tests the planarity of a graph
isPlanar = method()
isPlanar String := Boolean => G -> (#callNauty("planarg -q", {G})) != 0
isPlanar Graph := Boolean => G -> isPlanar(graphToString G)
-- For each vertex, switch the edges between its neighborhood and its neighborhood's complement.
neighborhoodComplements = method()
neighborhoodComplements List := List => L -> callNauty("NRswitchg -q", L)
neighborhoodComplements String := List => S -> neighborhoodComplements {S}
neighborhoodComplements Graph := List => G -> stringToGraph \ neighborhoodComplements {G}
-- For each disjoint pair of edges (a,b), (c,d), replace the edges with
-- (a,e), (e,b), (c,f), (f,d), and add the edge (e,f), where {e,f} are
-- new vertices.
newEdges = method()
newEdges List := List => L -> callNauty("newedgeg -q", L)
newEdges String := List => S -> newEdges {S}
newEdges Graph := List => G -> stringToGraph \ newEdges {G}
-- Removes non-planar graphs from a list of graphs
onlyPlanar = method()
onlyPlanar (List, Boolean) := List => (L, non) -> (
cmdStr := "planarg -q " | if non then "-v" else "";
callNauty(cmdStr, L)
)
onlyPlanar List := List => L -> onlyPlanar(L, false)
-- Reorders a bipartite graph so all vertices of each color are contiguous.
relabelBipartite = method()
relabelBipartite List := List => L -> (
r := callNauty("biplabg -q", L);
if #r == #L then r else error("relabelBipartite: One of the graphs is not a bipartite graph.")
)
relabelBipartite String := String => S -> first relabelBipartite {S}
relabelBipartite Graph := Graph => G -> stringToGraph first relabelBipartite {G}
-- Relabels a graph using a canonical labelling.
relabelGraph = method()
relabelGraph (List, ZZ, ZZ) := List => (L, i, a) -> (
if i > 15 or i < 0 then error("relabelGraph: The invariant selected is invalid.");
if a < 0 then error("relabelGraph: The invariant argument must be nonnegative.");
callNauty("labelg -qg -i" | toString i | " -K" | toString a, L)
)
relabelGraph (String, ZZ, ZZ) := String => (S, i, a) -> first relabelGraph({S}, i, a)
relabelGraph (Graph, ZZ, ZZ) := Graph => (G, i, a) -> stringToGraph first relabelGraph({G}, i, a)
relabelGraph (List, ZZ) := String => (L, i) -> relabelGraph(L, i, 3)
relabelGraph (String, ZZ) := String => (S, i) -> first relabelGraph({S}, i, 3)
relabelGraph (Graph, ZZ) := Graph => (G, i) -> stringToGraph first relabelGraph({G}, i, 3)
relabelGraph List := String => L -> relabelGraph(L, 0, 3)
relabelGraph String := String => S -> first relabelGraph({S}, 0, 3)
relabelGraph Graph := Graph => G -> stringToGraph first relabelGraph({G}, 0, 3)
-- Finds all graphs defined by G with one edge removed.
removeEdges = method(Options => {MinDegree => null})
removeEdges List := List => opts -> L -> (
cmdStr := "deledgeg -q" | optionZZ(opts.MinDegree, 0, "removeEdges", "MinDegree", "d");
callNauty(cmdStr, L)
)
removeEdges String := List => opts -> S -> removeEdges({S}, opts)
removeEdges Graph := List => opts -> G -> stringToGraph \ removeEdges({G}, opts)
-- Removes all isomorphs from a list of graphs.
removeIsomorphs = method()
removeIsomorphs List := List => L -> (
if #L == 0 then return {};
-- nauty outputs useful information to the stderr and (to us) junk on stdout
r := callNauty("shortg -qv", L, ReadError => true);
-- for each line, check if it has a colon, if so, take the first graph
for l in r list (
s := separate(":", l);
if #s < 2 then continue else (
t := select("[[:digit:]]+", s_1);
if #t == 0 then continue else L_(-1 + value first t)
)
)
)
-- Converts a Sparse6 string to a Graph6 string.
sparse6ToGraph6 = method()
sparse6ToGraph6 String := String => (s6) -> (
r := callNauty("copyg -qg", {s6});
if #r != 0 then first r else error("sparse6ToGraph6: The graph format is incorrect.")
)
-- Converts a graph given by a string in either Sparse6 or Graph6 format to an edge ideal in the given ring.
stringToEdgeIdeal = method()
stringToEdgeIdeal (String, PolynomialRing) := MonomialIdeal => (str, R) -> (
L := stringToList str;
if first L != #gens R then error("stringToEdgeIdeal: Wrong number of variables in the ring.");
E := last L;
monomialIdeal if #E == 0 then 0_R else apply(E, e -> R_(e_0) * R_(e_1))
)
-- Converts a string to a graph object
stringToGraph = method()
stringToGraph String := Graph => str -> (
L := stringToList str;
V := toList(0..(first L - 1));
V' := unique flatten last L;
if #V' == #V then graph last L else graph(last L, Singletons => select(V, v -> not member(v, V')))
);
-------------------
-- Local-Only Code
-------------------
nauty = null
-- Sends a command and retrieves the results into a list of lines.
-- If ReadError is set to true and the command is successfully executed,
-- then the data from stderr is returned (filterGraphs and removeIsomorphs
-- use this).
protect ReadError;
callNauty = method(Options => {ReadError => false})
callNauty (String, List) := List => opts -> (cmdStr, dataList) -> (
if nauty === null then
nauty = findProgram("nauty", "complg --help",
Prefix => {(".*", "nauty-")}); -- debian/fedora
infn := temporaryFileName();
erfn := temporaryFileName();
-- output the data to a file
o := openOut infn;
scan(graphToString \ dataList, d -> o << d << endl);
close o;
exe := first separate(" ", cmdStr);
args := replace(exe | " ", "", cmdStr);
r := runProgram(nauty, exe, args | " < " | infn);
removeFile infn;
if opts.ReadError then lines r#"error" else lines r#"output"
)
-- Processes an option which should be a Boolean.
-- Throws an appropriate error if the type is bad, otherwise it returns the flag.
optionBoolean = (b, m, o, f) -> (
if instance(b, Nothing) then ""
else if not instance(b, Boolean) then error(m | ": Option [" | o | "] is not a valid type, i.e., Boolean or Nothing.")
else if b then " -" | f
else ""
)
-- Processes an option which should be an integer (ZZ).
-- Throws an appropriate error if the type is bad or the bound is bad, otherwise it returns the flag.
optionZZ = (i, b, m, o, f) -> (
if instance(i, Nothing) then ""
else if not instance(i, ZZ) then error(m | ": Option [" | o | "] is not a valid type, i.e., ZZ or Nothing.")
else if i < b then error(m | ": Option [" | o | "] is too small (minimum is " | toString b | ").")
else " -" | f | toString i
)
-- Converts a graph given by a string in either Sparse6 or Graph6 format to a list
stringToList = method()
stringToList String := List => str -> (
-- basic parse
if #str == 0 then return;
sparse := str_0 == ":";
A := apply(ascii str, l -> l - 63);
if sparse then A = drop(A, 1);
if min A < 0 or max A > 63 then error("stringToList: Not a Sparse6/Graph6 string.");
-- get number of vertices
p := 0;
n := if A_0 < 63 then (
p = 1;
A_0
) else if A_1 < 63 then (
if #A < 4 then error("stringToList: Not a Sparse6/Graph6 string.");
p = 4;
fold((i,j) -> i*2^6+j, take(A, {1,3}))
) else (
if #A < 8 then error("stringToList: Not a Sparse6/Graph6 string.");
p = 8;
fold((i,j) -> i*2^6+j, take(A, {2,7}))
);
bits := flatten apply(drop(A, p), n -> ( n = n*2; reverse for i from 1 to 6 list (n=n//2)%2 ));
c := 0;
{n, if sparse then (
-- Sparse6 format
k := ceiling(log(n) / log(2));
v := 0;
xi := 0;
while c + k < #bits list (
if bits_c == 1 then v = v + 1;
xi = fold((i,j) -> 2*i+j, take(bits, {c+1,c+k}));
c = c + k + 1;
if xi > v then ( v = xi; continue ) else {xi, v}
)
) else (
-- Graph6 format
if #A != p + ceiling(n*(n-1)/12) then error("stringToList: Not a Graph6 string.");
c = -1;
flatten for i from 1 to n - 1 list for j from 0 to i - 1 list ( c = c + 1; if bits_c == 1 then {i, j} else continue)
)}
)
-------------------
-- Documentation
-------------------
beginDocumentation()
doc ///
Key
NautyGraphs
Headline
Interface to nauty (Graphs fork)
Description
Text
This package provides an interface from Macaulay2 to many of the functions provided in
the software nauty by Brendan D. McKay, available at @HREF "http://cs.anu.edu.au/~bdm/nauty/"@.
The nauty package provides very efficient methods for determining whether
given graphs are isomorphic, generating all graphs with particular properties,
generating random graphs, and more.
Most methods can handle graphs in either the Macaulay2 @TO "Graph"@ type as provided by
the @TO "Graphs"@ package or as Graph6 and Sparse6 strings as used by nauty.
The purpose of this is that graphs stored as strings are greatly more efficient than
graphs stored as instances of the class @TO "Graph"@.
(See @TO "Comparison of Graph6 and Sparse6 formats"@.)
It is recommended to work with graphs represented as strings while using nauty-provided
methods and then converting the graphs to instances of the class @TO "Graph"@ for further work.
The theoretical underpinnings of nauty are in the paper:
B. D. McKay, "Practical graph isomorphism," Congr. Numer. 30 (1981), 45--87.
SeeAlso
"Comparison of Graph6 and Sparse6 formats"
"Example: Checking for isomorphic graphs"
"Example: Generating and filtering graphs"
///
doc ///
Key
addEdges
(addEdges, List)
(addEdges, String)
(addEdges, Graph)
[addEdges, MaxDegree]
[addEdges, NoNew3Cycles]
[addEdges, NoNew4Cycles]
[addEdges, NoNew5Cycles]
[addEdges, NoNewOddCycles]
[addEdges, NoNewSmallCycles]
Headline
creates a list of graphs obtained by adding one new edge to the given graph in all possible ways
Usage
Ll = addEdges L
Lg = addEdges G
Ls = addEdges S
Inputs
L:List
containing graphs in various formats
S:String
which describes a graph in Graph6 or Sparse6 format
G:Graph
MaxDegree=>ZZ
the maximum degree allowable for any vertex in the output graphs
NoNew3Cycles=>Boolean
whether graphs with new 3-cycles are allowed
NoNew4Cycles=>Boolean
whether graphs with new 4-cycles are allowed
NoNew5Cycles=>Boolean
whether graphs with new 5-cycles are allowed
NoNewOddCycles=>Boolean
whether graphs with new odd-cycles are allowed
NoNewSmallCycles=>ZZ
an upper bound on cycles which are not allowed
Outputs
Ll:List
the list of graphs obtained from the graphs in $L$ in Graph6 format
Lg:List
the list of graphs obtained from $G$
Ls:List
the list of strings (in Graph6 format) obtained from $S$
Description
Text
Simply creates a list, in the same format as the input, of all possible graphs
obtained by adding one new edge to the input graph.
Example
G = graph {{1,2},{2,3},{3,4},{4,5},{1,5}};
addEdges G
Text
If the List input format is used, then one should use care as
the list may contain isomorphic pairs.
SeeAlso
removeEdges
///
doc ///
Key
areIsomorphic
(areIsomorphic, String, String)
(areIsomorphic, Graph, Graph)
(areIsomorphic, String, Graph)
(areIsomorphic, Graph, String)
(symbol ==, Graph, Graph)
(symbol ==, Graph, String)
(symbol ==, String, Graph)
Headline
determines whether two graphs are isomorphic
Usage
b = areIsomorphic(G, H)
G == H
b = areIsomorphic(S, T)
b = areIsomorphic(S, H)
S == H
b = areIsomorphic(G, T)
G == T
Inputs
G:Graph
H:Graph
S:String
T:String
Outputs
b:Boolean
whether the two graphs are isomorphic
Description
Text
A very efficient method for determining whether two graphs (of the same format) are isomorphic.
Example
G = graph {{1,2},{2,3},{3,4},{4,5},{1,5}};
H = graph {{1,3},{3,5},{5,2},{2,4},{4,1}};
I = graph {{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}};
areIsomorphic(G, H)
G == H
areIsomorphic(G, I)
G == "Dhc"
I == "Dhc"
SeeAlso
"Example: Checking for isomorphic graphs"
removeIsomorphs
///
doc ///
Key
buildGraphFilter
(buildGraphFilter, HashTable)
(buildGraphFilter, List)
Headline
creates the appropriate filter string for use with filterGraphs and countGraphs
Usage
s = buildGraphFilter h
s = buildGraphFilter l
Inputs
h:HashTable
which describes the properties desired in filtering
l:List
which describes the properties desired in filtering
Outputs
s:String
which can be used with @TO "filterGraphs"@ and @TO "countGraphs"@
Description
Text
The @TO "filterGraphs"@ and @TO "countGraphs"@ methods both can use a tremendous number of constraints
which are described by a rather tersely encoded string. This method builds that string given information
in the @TO "HashTable"@ $h$ or the @TO "List"@ $l$. Any keys which do not exist are simply ignored and
any values which are not valid (e.g., exactly $-3$ vertices) are also ignored.
The values can either be @TO "Boolean"@ or in @TO "ZZ"@. @TO "Boolean"@ values are treated exactly
as expected. Numerical values are more complicated; we use an example to illustrate how numerical values
can be used, but note that this usage works for all numerically valued keys.
The key @TT "NumEdges"@ restricts to a specific number of edges in the graph. If the value is
the integer $n$, then only graphs with @EM "exactly"@ $n$ edges are returned.
Example
L = {graph {{1,2}}, graph {{1,2},{2,3}}, graph {{1,2},{2,3},{3,4}}, graph {{1,2},{2,3},{3,4},{4,5}}};
s = buildGraphFilter {"NumEdges" => 3};
filterGraphs(L, s)
Text
If the value is the @TO "Sequence"@ $(m,n)$, then all graphs with at least $m$ and at most $n$ edges are returned.
Example
s = buildGraphFilter {"NumEdges" => (2,3)};
filterGraphs(L, s)
Text
If the value is the @TO "Sequence"@ $(,n)$, then all graphs with at most $n$ edges are returned.
Example
s = buildGraphFilter {"NumEdges" => (,3)};
filterGraphs(L, s)
Text
If the value is the @TO "Sequence"@ $(m,)$, then all graphs with at least $m$ edges are returned.
Example
s = buildGraphFilter {"NumEdges" => (2,)};
filterGraphs(L, s)
Text
Moreover, the associated key @TT "NegateNumEdges"@, if true, causes the @EM "opposite"@ to occur.
Example
s = buildGraphFilter {"NumEdges" => (2,), "NegateNumEdges" => true};
filterGraphs(L, s)
Text
The following are the boolean options: "Regular", "Bipartite", "Eulerian", "VertexTransitive".
The following are the numerical options (recall all have the associate "Negate" option): "NumVertices", "NumEdges",
"MinDegree", "MaxDegree", "Radius", "Diameter", "Girth", "NumCycles", "NumTriangles", "GroupSize", "Orbits",
"FixedPoints", "Connectivity", "MinCommonNbrsAdj", "MaxCommonNbrsAdj", "MinCommonNbrsNonAdj", "MaxCommonNbrsNonAdj".
Caveat
@TT "Connectivity"@ only works for the values $0, 1, 2$ and uses the following definition of $k$-connectivity.
A graph is $k$-connected if $k$ is the minimum size of a set of vertices whose complement is not connected.
Thus, in order to filter for connected graphs, one must use @TT "{\"Connectivity\" => 0, \"NegateConnectivity\" => true}"@.
@TT "NumCycles"@ can only be used with graphs on at most $n$ vertices, where $n$ is the number of bits for which
nauty was compiled, typically $32$ or $64$.
SeeAlso
countGraphs
"Example: Generating and filtering graphs"
filterGraphs
///
doc ///
Key
"Comparison of Graph6 and Sparse6 formats"
Description
Text
The program nauty uses two string-based formats for storing graphs: Graph6 and Sparse6 format.
Each format has benefits and drawbacks.
In particular, the length of a Graph6 string representation of a graph depends only on the number of vertices.
However, this also means that graphs with few edges take as much space as graphs with many edges.
On the other hand, Sparse6 is a variable length format which can use dramatically less space for
sparse graphs but can have a much larger storage size for dense graphs.
Consider the 26-cycle, a rather sparse graph. Notice how Sparse6 format takes half the space
of the Graph6 format.
Example
C26 = graph append(apply(25, i -> {i, i+1}), {0, 25});
g6 = graphToString C26; #g6
s6 = graph6ToSparse6 g6; #s6
Text
However, the complete graph, which is as dense as possible, on 26 vertices is the opposite:
the Sparse6 format takes nearly six times the space of the Graph6 format.
Example
K26 = graph flatten for i from 0 to 25 list for j from i+1 to 25 list {i,j};
g6 = graphToString K26; #g6
s6 = graph6ToSparse6 g6; #s6
SeeAlso
graph6ToSparse6
graphToString
sparse6ToGraph6
stringToGraph
///
doc ///
Key
countGraphs
(countGraphs, List, String)
(countGraphs, List, HashTable)
(countGraphs, List, List)
Headline
counts the number of graphs in the list with given properties
Usage
n = countGraphs(L, s)
n = countGraphs(L, h)
n = countGraphs(L, l)
Inputs
L:List
containing graphs (mixed formats are allowed)
s:String
a filter, as generated by @TO "buildGraphFilter"@
h:HashTable
a filter, as used by @TO "buildGraphFilter"@
l:List
a filter, as used by @TO "buildGraphFilter"@
Outputs
n:ZZ
the number of graphs in $L$ satisfying the filter
Description
Text
Counts the number of graphs in a list that satisfy certain restraints as given in
the filter (see @TO "buildGraphFilter"@). Notice that the input list can be graphs
represented as instances of the class @TO "Graph"@ or in a nauty-based @TO "String"@ format.
Text
For example, we can count the number of connected graphs on five vertices.
Example
L = generateGraphs 5;
countGraphs(L, {"Connectivity" => 0, "NegateConnectivity" => true})
SeeAlso
buildGraphFilter
filterGraphs
///
doc ///
Key
"Example: Checking for isomorphic graphs"
Description
Text
The main use of nauty is to determine if two graphs are isomorphic. We can
demonstrate it for two given graphs with the method @TO "areIsomorphic"@.
Example
G = graph {{1,2},{2,3},{3,4},{4,5},{1,5}};
H = graph {{1,3},{3,5},{5,2},{2,4},{4,1}};
areIsomorphic(G, H)
Text
Further, a list of graphs can be reduced to only graphs that are non-isomorphic
with the method @TO "removeIsomorphs"@. Here we create a list of 120 different
labellings of the 5-cycle and use nauty to verify they are indeed all
the same.
Example
L = graphToString \ apply(permutations 5, P -> graph apply(5, i -> {P_i, P_((i+1)%5)}));
N = removeIsomorphs L
stringToGraph first N
SeeAlso
areIsomorphic
removeIsomorphs
///
doc ///
Key
"Example: Generating and filtering graphs"
Description
Text
The method @TO "generateGraphs"@ can generate all graphs with a given property.
For example, we can verify the number of graphs on a given number of vertices.
Compare these results to the Online Encyclopedia of Integer Sequences (@HREF "http://oeis.org/"@),
where the sequence name is also its OEIS identifier.
Example
A000088 = apply(1..9, n -> #generateGraphs n)
B = apply(1..12, n -> generateGraphs(n, OnlyBipartite => true));
Text
Further, we can use @TO "filterGraphs"@ to refine the set of generate graphs
for deeper properties.
Here we filter for forests, then for trees only,
Example
forestsOnly = buildGraphFilter {"NumCycles" => 0};
A005195 = apply(B, graphs -> #filterGraphs(graphs, forestsOnly))
treesOnly = buildGraphFilter {"NumCycles" => 0, "Connectivity" => 0, "NegateConnectivity" => true};
A000055 = apply(B, graphs -> #filterGraphs(graphs, treesOnly))
Text
Moreover, we can generate random graphs using the @TO "generateRandomGraphs"@ method. Here
we verify a result of Erdos and R\'enyi (see @HREF "http://www.ams.org/mathscinet-getitem?mr=120167"@),
which says that a random graph on $n$ vertices with edge probability $(1+\epsilon)$log$(n)/n$ is almost
always connected while a graph with edge probability $(1-\epsilon)$log$(n)/n$ is almost never connected,
at least as $n$ tends to infinity.
Example
connected = buildGraphFilter {"Connectivity" => 0, "NegateConnectivity" => true};
prob = n -> log(n)/n;
apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, 2*(prob n)), connected))
apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, (prob n)/2), connected))
SeeAlso
buildGraphFilter
filterGraphs
generateGraphs
generateRandomGraphs
///
doc ///
Key
filterGraphs
(filterGraphs, List, String)
(filterGraphs, List, HashTable)
(filterGraphs, List, List)
Headline
filters (i.e., selects) graphs in a list for given properties
Usage
F = filterGraphs(L, s)
F = filterGraphs(L, h)
F = filterGraphs(L, l)
Inputs
L:List
containing graphs (mixed formats are allowed)
s:String
a filter, as generated by @TO "buildGraphFilter"@
h:HashTable
a filter, as used by @TO "buildGraphFilter"@
l:List
a filter, as used by @TO "buildGraphFilter"@
Outputs
F:List
the graphs in $L$ satisfying the filter
Description
Text
Filters the graphs in a list which satisfy certain restraints as given in
the filter (see @TO "buildGraphFilter"@). Notice that the input list can be graphs
represented as instances of the class @TO "Graph"@ or in a nauty-based @TO "String"@ format.
Text
For example, we can filter for the connected graphs on five vertices.
Example
L = generateGraphs 5;
filterGraphs(L, {"Connectivity" => 0, "NegateConnectivity" => true})
SeeAlso
buildGraphFilter
countGraphs
"Example: Generating and filtering graphs"
///
doc ///
Key
generateBipartiteGraphs
(generateBipartiteGraphs, ZZ)
(generateBipartiteGraphs, ZZ, ZZ)
(generateBipartiteGraphs, ZZ, ZZ, ZZ)
(generateBipartiteGraphs, ZZ, ZZ, ZZ, ZZ)
[generateBipartiteGraphs, Class2Degree2]
[generateBipartiteGraphs, Class2DistinctNeighborhoods]
[generateBipartiteGraphs, Class2MaxCommonNeighbors]
[generateBipartiteGraphs, MaxDegree]
[generateBipartiteGraphs, MinDegree]
[generateBipartiteGraphs, OnlyConnected]
Headline
generates the bipartite graphs with a given bipartition
Usage
G = generateBipartiteGraphs n
G = generateBipartiteGraphs(n, m)
G = generateBipartiteGraphs(n, m, e)
G = generateBipartiteGraphs(n, m, le, ue)
Inputs
n:ZZ
the number of vertices of the graphs, must be positive (see caveat)
m:ZZ
the number of vertices in the first class of the bipartition
e:ZZ
the number of edges in the graphs
le:ZZ
a lower bound on the number of edges in the graphs
ue:ZZ
an upper bound on the number of edges in the graphs
Class2Degree2=>Boolean
whether the vertices in the second class must have at least two neighbors of degree at least 2
Class2DistinctNeighborhoods=>Boolean
whether all vertices in the second class must have distinct neighborhoods
Class2MaxCommonNeighbors=>ZZ
an upper bound on the number of common neighbors of vertices in the second class
MaxDegree=>ZZ
an upper bound on the degrees of the vertices
MinDegree=>ZZ
a lower bound on the degrees of the vertices
OnlyConnected=>Boolean
whether to only allow connected graphs
Outputs
G:List
the bipartite graphs satisfying the input conditions
Description
Text
This method generates all bipartite graphs on $n$ vertices.
The size of the bipartition is specified by giving the size of
one class; the other class is determined automatically from the
number of vertices.
Text
If only one integer argument is given, then the method generates
all bipartite graphs on that number of vertices with first class
of sizes $0$ to $n$.
Caveat
The number of vertices $n$ must be positive as nauty cannot handle
graphs with zero vertices.
SeeAlso
generateGraphs
///
doc ///
Key
generateGraphs
(generateGraphs, ZZ)
(generateGraphs, ZZ, ZZ)
(generateGraphs, ZZ, ZZ, ZZ)
[generateGraphs, MaxDegree]
[generateGraphs, MinDegree]
[generateGraphs, Only4CycleFree]
[generateGraphs, OnlyBiconnected]
[generateGraphs, OnlyBipartite]
[generateGraphs, OnlyConnected]
[generateGraphs, OnlyTriangleFree]
Headline
generates the graphs on a given number of vertices
Usage
G = generateGraphs n
G = generateGraphs(n, e)
G = generateGraphs(n, le, ue)
Inputs
n:ZZ
the number of vertices of the graphs, must be positive (see caveat)
e:ZZ
the number of edges in the graphs
le:ZZ
a lower bound on the number of edges in the graphs
ue:ZZ
an upper bound on the number of edges in the graphs
MaxDegree=>ZZ
an upper bound on the degrees of the vertices
MinDegree=>ZZ
a lower bound on the degrees of the vertices
Only4CycleFree=>Boolean
whether to only allow graphs without 4-cycles
OnlyBiconnected=>Boolean
whether to only allow biconnected graphs
OnlyBipartite=>Boolean
whether to only allow bipartite graphs
OnlyConnected=>Boolean
whether to only allow connected graphs
OnlyTriangleFree=>Boolean
whether to only allow graphs without triangles (3-cycles)
Outputs
G:List
the graphs satisfying the input conditions
Description
Text
This method generates all graphs on $n$ vertices subject to the
constraints on the number of edges. It uses numerous options
to allow further constraining of the output.
Example
generateGraphs(5, 4, 6, OnlyConnected => true)
Caveat
The number of vertices $n$ must be positive as nauty cannot handle
graphs with zero vertices.
SeeAlso
"Example: Generating and filtering graphs"
generateBipartiteGraphs
///
doc ///
Key
generateRandomGraphs
(generateRandomGraphs, ZZ, ZZ)
(generateRandomGraphs, ZZ, ZZ, ZZ)
(generateRandomGraphs, ZZ, ZZ, QQ)
(generateRandomGraphs, ZZ, ZZ, RR)
[generateRandomGraphs, RandomSeed]
Headline
generates random graphs on a given number of vertices
Usage
G = generateRandomGraphs(n, num)
G = generateRandomGraphs(n, num, pq)
G = generateRandomGraphs(n, num, pz)
Inputs
n:ZZ
the number of vertices of the graphs, must be positive (see caveat)
num:ZZ
the number of random graphs to generate
pq:QQ
the edge probability (between 0 and 1)
pq:RR
the edge probability (between 0 and 1)
pz:ZZ
the reciprocal of the edge probability (positive)
RandomSeed=>ZZ
the specified random seed is passed to nauty
Outputs
G:List
the randomly generated graphs
Description
Text
This method generates a specified number of random graphs with a given
number of vertices. Note that some graphs may be isomorphic.
Text
If the input $pq$ is included, then the edges are chosen to be
included with probability $pq$. If the input $pz$ is included
and is positive, then the edges are chosen to be included with
probability $1/pz$.
Example
generateRandomGraphs(5, 5, RandomSeed => 314159)
generateRandomGraphs(5, 5)
generateRandomGraphs(5, 5, RandomSeed => 314159)
Caveat
The number of vertices $n$ must be positive as nauty cannot handle
graphs with zero vertices. Further, if the probability $pq$ is included,
then it is rounded to a precision of one-hundred millionth.
SeeAlso
"Example: Generating and filtering graphs"
generateRandomRegularGraphs
///
doc ///
Key
generateRandomRegularGraphs
(generateRandomRegularGraphs, ZZ, ZZ, ZZ)
[generateRandomRegularGraphs, RandomSeed]
Headline
generates random regular graphs on a given number of vertices
Usage
G = generateRandomRegularGraphs(n, num, reg)
Inputs
n:ZZ
the number of vertices of the graphs, must be positive (see caveat)
num:ZZ
the number of random graphs to generate
reg:ZZ
the regularity of the generated graphs
RandomSeed=>ZZ
the specified random seed is passed to nauty
Outputs
G:List
the randomly generated regular graphs
Description
Text
This method generates a specified number of random graphs on
a given number of vertices with a given regularity.
Note that some graphs may be isomorphic.
Example
generateRandomRegularGraphs(5, 3, 2)
Caveat
The number of vertices $n$ must be positive as nauty cannot handle
graphs with zero vertices.
SeeAlso
generateRandomGraphs
///
doc ///
Key
graph6ToSparse6
(graph6ToSparse6, String)
Headline
converts a Graph6 string to a Sparse6 string
Usage
s6 = graph6ToSparse6 g6
Inputs
g6:String
a string in nauty's Graph6 format
Outputs
s6:String
a string in nauty's Sparse6 format
Description
Text
This method converts a graph stored in nauty's Graph6 format
to a graph stored in nauty's Sparse6 format. For graphs with
very few edges, the Sparse6 format can use dramatically less
space. However, for graphs with many edges, the Sparse6
format can increase the storage requirements.
Example
graph6ToSparse6 "Dhc"
graph6ToSparse6 "M????????????????"
SeeAlso
"Comparison of Graph6 and Sparse6 formats"
graphToString
stringToEdgeIdeal
stringToGraph
sparse6ToGraph6
///
doc ///
Key
graphComplement
(graphComplement, List)
(graphComplement, String)
(graphComplement, Graph)
[graphComplement, OnlyIfSmaller]
Headline
computes the complement of a graph
Usage
L' = graphComplement L
T = graphComplement S
H = graphComplement G
Inputs
L:List
containing graphs in various formats
S:String
a graph encoded in either Sparse6 or Graph6 format
G:Graph
OnlyIfSmaller=>Boolean
when true, then the smaller (fewer edges) of the graph and its complement are returned
Outputs
L':List
the graph complement of the elements of $L$ stored in Graph6 format
T:String
the graph complement of $S$ stored in the same format at $S$
H:Graph
the graph complement of $G$
Description
Text
This method computes the graph complement of the input graph
and returns the result in the same format.
Example
graphComplement "Dhc"
graphComplement graph {{1,2},{2,3},{3,4},{4,5},{1,5}}
Text
Batch calls can be performed considerably faster when using the
List input format. However, care should be taken as the returned
list is entirely in Graph6 or Sparse6 format.
Example
G = generateBipartiteGraphs 7;
time graphComplement G;
time (graphComplement \ G);
///
doc ///
Key
graphToString
(graphToString, List, ZZ)
(graphToString, MonomialIdeal)
(graphToString, Ideal)
(graphToString, Graph)
(graphToString, String)
Headline
converts a graph to a string in the Graph6 format
Usage
S = graphToString(E, n)
S = graphToString I
S = graphToString G
S = graphToString T
Inputs
E:List
a list of edge pairs
n:ZZ
the number of vertices in the graph, must be positive (see caveat)
I:Ideal
the edge ideal of a graph
G:Graph
T:String
a string containing a graph; the string automatically passes through untouched
Outputs
S:String
the graph converted to a Graph6 format string
Description
Text
This method converts various ways of representing a graph into
nauty's Graph6 string format. Note that if the @TO "Ideal"@
(or @TO "MonomialIdeal"@) passed to the method is not squarefree and monomial, then the
method may have unknown and possibly undesired results.
In this example, all graphs are the 5-cycle.
Example
graphToString({{0,1}, {1,2}, {2,3}, {3,4}, {0,4}}, 5)
R = QQ[a..e];
graphToString monomialIdeal (a*c, a*d, b*d, b*e, c*e)
graphToString graph {{0,1}, {1,2}, {2,3}, {3,4}, {0,4}}
graphToString "Dhc"
Text
We note that if the input is a string, then the output is simply that string returned,
regardless of format or correctness.
Caveat
Notice that if using a @TO "List"@ and number of vertices input to create
the string, then the @TO "List"@ must have vertices labeled $0$ to
$n-1$.
The number of vertices $n$ must be positive as nauty cannot handle
graphs with zero vertices.
SeeAlso
"Comparison of Graph6 and Sparse6 formats"
graph6ToSparse6
sparse6ToGraph6
stringToGraph
///
doc ///
Key
isPlanar
(isPlanar, Graph)
(isPlanar, String)
Headline
determines if a given graph is planar
Usage
p = isPlanar G
p = isPlanar S
Inputs
S:String
a graph encoded in either Sparse6 or Graph6 format
G:Graph
Outputs
p:Boolean
whether the given graph is planar
Description
Text
A graph is planar if the graph can be embedded in the plane, i.e.,
the vertices can be arranged such that no edges cross except at
vertices.
Example
isPlanar graph {{0,1}, {1,2}, {2,3}, {3,4}, {0,4}}
isPlanar graph flatten for i from 0 to 4 list for j from i+1 to 4 list {i,j}
Text
This method uses the program @TT "planarg"@. The
code was written by Paulette Lieby for the Magma project and
used with permission in the software nauty.
SeeAlso
onlyPlanar
///
doc ///
Key
neighborhoodComplements
(neighborhoodComplements, List)
(neighborhoodComplements, String)
(neighborhoodComplements, Graph)
Headline
complements the neighborhood for each vertex, individually
Usage
N' = neighborhoodComplements L
N = neighborhoodComplements S
N = neighborhoodComplements G
Inputs
L:List
containing graphs in various formats
S:String
a graph encoded in either Sparse6 or Graph6 format
G:Graph
Outputs
N':List
containing graphs in either Graph6 or Sparse6 format, modified as described below
N:List
containing graphs, in the same format as the input, modified as described below
Description
Text
The method creates a list of graphs, one for each vertex of the
original graph $G$. The graph associated to a vertex $v$
of $G$ has the neighborhood of $v$ complemented.
The method does not remove isomorphs.
Example
neighborhoodComplements graph {{1,2},{1,3},{2,3},{3,4},{4,5}}
SeeAlso
graphComplement
neighbors
///
doc ///
Key
newEdges
(newEdges, List)
(newEdges, String)
(newEdges, Graph)
Headline
replaces disjoint pairs of edges by disjoint pairs of two-chains
Usage
N' = newEdges L
N = newEdges S
N = newEdges G
Inputs
L:List
containing graphs in various formats
S:String
a graph encoded in either Sparse6 or Graph6 format
G:Graph
Outputs
N':List
containing graphs in either Graph6 or Sparse6 format, modified as described below
N:List
a list of graphs, in the same format as the input, modified as described below
Description
Text
The list of "new edge" graphs are formed as follows:
Let $ab$ and $cd$ be disjoint edges of $G$. Then the
associated "new edge" graph $H$ is $G$ with the edges
$ab$ and $cd$ removed, the vertices $e$ and $f$ added,
and the new edges $ae, be, cf, df,$ and $ef$ added.
Example
newEdges graph {{a,b},{c,d}}
Text
If the List input format is used, then one should use care as
the list may contain isomorphic pairs.
///
doc ///
Key
onlyPlanar
(onlyPlanar, List, Boolean)
(onlyPlanar, List)
Headline
removes non-planar graphs from a list
Usage
P = onlyPlanar L
P = onlyPlanar(L, non)
Inputs
L:List
containing graphs in various formats
non:Boolean
whether to return non-planar graphs
Outputs
P:List
containing the planar graphs of $L$ in Graph6 or Sparse6 format
Description
Text
A graph is planar if the graph can be embedded in the plane, i.e.,
the vertices can be arranged such that no edges cross except at
vertices.
Text
The only non-planar graph on five vertices is the complete graph.
Example
K5 = graph flatten for i from 0 to 4 list for j from i+1 to 4 list {i,j};
P = onlyPlanar(generateGraphs 5, true)
areIsomorphic(first P, K5)
Text
This method uses the program @TT "planarg"@. The
code was written by Paulette Lieby for the Magma project and
used with permission in the software nauty.
SeeAlso
isPlanar
///
doc ///
Key
relabelBipartite
(relabelBipartite, List)
(relabelBipartite, String)
(relabelBipartite, Graph)
Headline
relabels a bipartite graph so all vertices of a given class are contiguous
Usage
L' = relabelBipartite L
T = relabelBipartite S
H = relabelBipartite G
Inputs
L:List
a list of bipartite graphs in various formats
S:String
a bipartite graph encoded in either Sparse6 or Graph6 format
G:Graph
a bipartite graph
Outputs
L':List
a list of graphs isomorphic to $S$
T:String
a graph isomorphic to $S$ encoded in either Sparse6 or Graph6 format
H:Graph
a graph isomorphic to $G$
Description
Text
A bipartite graph can be labeled so all vertices of a given
class are contiguous. This method does precisely that to a
bipartite graph.
Example
G = graph {{1,2},{1,4},{1,6},{3,2},{3,4},{3,6},{5,2},{5,4},{5,6}};
relabelBipartite G
Text
If any of the inputs are not bipartite graphs, then the method
throws an error.
SeeAlso
relabelGraph
///
doc ///
Key
relabelGraph
(relabelGraph, List, ZZ, ZZ)
(relabelGraph, List, ZZ)
(relabelGraph, List)
(relabelGraph, String, ZZ, ZZ)
(relabelGraph, String, ZZ)
(relabelGraph, String)
(relabelGraph, Graph, ZZ, ZZ)
(relabelGraph, Graph, ZZ)
(relabelGraph, Graph)
Headline
applies a vertex invariant based refinement to a graph
Usage
L' = relabelGraph(L, i, a)
L' = relabelGraph(L, i)
L' = relabelGraph L
T = relabelGraph(S, i, a)
T = relabelGraph(S, i)
T = relabelGraph S
H = relabelGraph(G, i, a)
H = relabelGraph(G, i)
H = relabelGraph G
Inputs
L:List
a list of graphs in various formats
S:String
a graph encoded in either Sparse6 or Graph6 format
G:Graph
i:ZZ
a choice of invariant to order by ($0 \leq i \leq 15$, default is $0$)
a:ZZ
a non-negative argument passed to nauty, (default is $3$)
Outputs
L':List
a list of graphs isomorphic to $S$
T:String
a graph isomorphic to $S$ encoded in either Sparse6 or Graph6 format
H:Graph
a graph isomorphic to $G$
Description
Text
This method applies one of sixteen vertex invariant based refinements to a
graph. See the nauty documentation for a more complete description
of each and how the argument $a$ is used.
The sixteen vertex invariants are:
@UL ({
"$i = 0$: none,",
"$i = 1$: twopaths,",
"$i = 2$: adjtriang(K),",
"$i = 3$: triples,",
"$i = 4$: quadruples,",
"$i = 5$: celltrips,",
"$i = 6$: cellquads,",
"$i = 7$: cellquins,",
"$i = 8$: distances(K),",
"$i = 9$: indsets(K),",
"$i = 10$: cliques(K),",
"$i = 11$: cellcliq(K),",
"$i = 12$: cellind(K),",
"$i = 13$: adjacencies,",
"$i = 14$: cellfano, and",
"$i = 15$: cellfano2."
} / TEX) @
Example
G = graph {{0,1},{1,2},{2,3},{3,4},{0,4}}
relabelGraph G
Text
Note that on most small graphs, all sixteen orderings produce the same result.
SeeAlso
relabelBipartite
///
doc ///
Key
removeEdges
(removeEdges, List)
(removeEdges, String)
(removeEdges, Graph)
[removeEdges, MinDegree]
Headline
creates a list of graphs obtained by removing one edge from the given graph in all possible ways
Usage
R' = removeEdges L
R = removeEdges S
R = removeEdges G
Inputs
L:List
containing graphs in various formats
S:String
a graph encoded in either Sparse6 or Graph6 format
G:Graph
MinDegree=>ZZ
the minimum degree which a returned graph can have
Outputs
R':List
a list of all graphs obtained by removed one edge from the given graphs; it contains graphs in Graph6 or Sparse6 format
R:List
a list of all graphs obtained by removed one edge from the given graph; it contains graphs in the same format as the input
Description
Text
This method creates a list of all possible graphs obtainable from
the given graph by removing one edge. Notice that isomorphic graphs
are allowed within the list.
Example
removeEdges graph {{1,2},{1,3},{2,3},{3,4},{4,5}}
Text
If the List input format is used, then one should use care as
the list may contain isomorphic pairs.
SeeAlso
"addEdges"
///
doc ///
Key
removeIsomorphs
(removeIsomorphs, List)
Headline
removes all isomorphs from a list of graphs
Usage
M = removeIsomorphs L
Inputs
L:List
containing graphs (mixed formats allowed)
Outputs
M:List
containing the sub-list of non-isomorphic graphs of the input list, retaining format
Description
Text
This method returns the sublist of $L$ giving all
non-isomorphic graphs with selection based on which comes
first in $L$. The format of the graph is retained.
Example
G = {"EhEG", graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}}, "DhC", graph {{0,1}}};
removeIsomorphs G
SeeAlso
areIsomorphic
"Example: Checking for isomorphic graphs"
///
doc ///
Key
sparse6ToGraph6
(sparse6ToGraph6, String)
Headline
converts a Sparse6 string to a Graph6 string
Usage
g6 = sparse6ToGraph6 s6
Inputs
s6:String
a string in nauty's Sparse6 format
Outputs
g6:String
a string in nauty's Graph6 format
Description
Text
This method converts a graph stored in nauty's Sparse6 format
to a graph stored in nauty's Graph6 format. The Graph6 format
has the benefit of being a constant length dependent only
on the number of vertices.
Example
sparse6ToGraph6 ":DaY_~"
sparse6ToGraph6 ":M"
SeeAlso
"Comparison of Graph6 and Sparse6 formats"
graph6ToSparse6
graphToString
stringToEdgeIdeal
stringToGraph
///
doc ///
Key
stringToEdgeIdeal
(stringToEdgeIdeal, String, PolynomialRing)
Headline
converts a Sparse6 or Graph6 String to an edge ideal in the given polynomial ring
Usage
I = stringToEdgeIdeal(S, R)
Inputs
S:String
a string in nauty's Sparse6 or Graph6 format
R:PolynomialRing
a polynomial ring
Outputs
I:Ideal
an ideal in the given polynomial ring
Description
Text
This method converts a Sparse6 or Graph6 string $S$ to an edge
ideal $I$ in the given polynomial ring $R$. That is, for
each edge $(a,b)$ in the graph given by $S$, the monomial
$a*b$ is added as a generator to $I$.
Note, this method requires that the number of variables of $R$
be the same as the number of vertices of $S$.
Example
R = QQ[a..e];
stringToEdgeIdeal("Dhc", R)
Text
This method is almost always faster than converting the string to
a graph and then to an edge ideal using the @TO "edgeIdeal"@ method.
SeeAlso
graphToString
stringToGraph
///
doc ///
Key
stringToGraph
(stringToGraph, String)
Headline
converts a Sparse6 or Graph6 String to a Graph
Usage
G = stringToEdgeIdeal S
Inputs
S:String
a string in nauty's Sparse6 or Graph6 format
Outputs
G:Graph
Description
Text
This method converts a Sparse6 or Graph6 string $S$ to an instance
of the class Graph, stored in $G$.
Example
stringToGraph "Dhc"
SeeAlso
graphToString
stringToEdgeIdeal
///
-- Each of these are documented within the documentation for the
-- methods which use them.
undocumented {
"Class2Degree2",
"Class2DistinctNeighborhoods",
"Class2MaxCommonNeighbors",
"MaxDegree",
"MinDegree",
"NoNew3Cycles",
"NoNew4Cycles",
"NoNew5Cycles",
"NoNewOddCycles",
"NoNewSmallCycles",
"Only4CycleFree",
"OnlyBiconnected",
"OnlyBipartite",
"OnlyConnected",
"OnlyIfSmaller",
"OnlyTriangleFree",
"RandomSeed"
};
-------------------
-- Tests
-------------------
-- addEdges
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
K6 = graph flatten for i from 0 to 5 list for j from i+1 to 5 list {i,j}
assert(#addEdges C6 == 9);
assert(#addEdges {C6} == 9);
assert(#addEdges K6 == 0);
assert(#addEdges {K6} == 0);
-- "E???" is the empty graph
assert(#addEdges "E???" == binomial(6, 2));
///
-- areIsomorphic
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
C = graph {{0,2},{2,4},{4,1},{1,3},{3,5},{0,5}};
K6 = graph flatten for i from 0 to 5 list for j from i+1 to 5 list {i,j}
assert(areIsomorphic(C6, C));
assert(not areIsomorphic(C6, K6));
///
-- buildGraphFilter
TEST ///
assert(buildGraphFilter {"NumVertices" => 3} == "-n3 ");
assert(buildGraphFilter {"NumVertices" => (3,4)} == "-n3:4 ");
assert(buildGraphFilter {"NumVertices" => (3,)} == "-n3: ");
assert(buildGraphFilter {"NumVertices" => (,4)} == "-n:4 ");
assert(buildGraphFilter hashTable {"NumVertices" => 3, "NegateNumVertices" => true} == "-~n3 ");
assert(buildGraphFilter hashTable {"Regular" => true} == "-r ");
assert(buildGraphFilter hashTable {"Regular" => false} == "-~r ");
assert(buildGraphFilter hashTable {} == "");
///
-- countGraphs
TEST ///
G = {graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}},
graph flatten for i from 0 to 5 list for j from i+1 to 5 list {i,j},
graph({}, Singletons => {0,1,2,3,4,5}),
graph {{0,1},{2,3},{3,4}},
graph({{0,1},{1,2},{2,3},{3,4}}, Singletons => {5})};
-- Connected?
assert(countGraphs(G, {"Connectivity" => 0, "NegateConnectivity" => true}) == 2);
-- Bipartite?
assert(countGraphs(G, {"Bipartite" => true}) == 4);
-- At least 4 edges?
assert(countGraphs(G, hashTable {"NumEdges" => (4,)}) == 3);
///
-- filterGraphs
TEST ///
G = {graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}},
graph flatten for i from 0 to 5 list for j from i+1 to 5 list {i,j},
graph({}, Singletons => {0,1,2,3,4,5}),
graph {{0,1},{2,3},{3,4}},
graph({{0,1},{1,2},{2,3},{3,4}}, Singletons => {5})};
-- Connected?
assert(filterGraphs(G, {"Connectivity" => 0, "NegateConnectivity" => true}) === G_{0, 1});
-- Bipartite?
assert(filterGraphs(G, {"Bipartite" => true}) === G_{0, 2, 3, 4});
-- At least 4 edges?
assert(filterGraphs(G, hashTable {"NumEdges" => (4,)}) === G_{0, 1, 4});
///
-- generateBipartiteGraphs
TEST ///
-- All bipartite graphs in R.
assert(#generateBipartiteGraphs(6) == 57);
-- All bipartite graphs in R with Class1 of size 3.
assert(#generateBipartiteGraphs(6, 3) == 36);
-- All bipartite graphs in R with Class1 of size 3 and 2 edges.
assert(#generateBipartiteGraphs(6, 3, 2) == 3);
-- All bipartite graphs in R with Class1 of size 3 and 1-2 edges.
assert(#generateBipartiteGraphs(6, 3, 1, 2) == 4);
assert(apply(toList(1..8), n -> #removeIsomorphs generateBipartiteGraphs n) == {1, 2, 3, 7, 13, 35, 88, 303}); --A033995
assert(apply(toList(1..8), n -> #removeIsomorphs generateBipartiteGraphs(n, OnlyConnected => true)) == {1, 1, 1, 3, 5, 17, 44, 182}); --A005142
///
-- generateGraphs
TEST ///
assert(#generateGraphs(6) == 156);
assert(#generateGraphs(6, OnlyConnected => true) == 112);
assert(#generateGraphs(6, 7) == 24);
assert(#generateGraphs(6, 7, 8, OnlyConnected => true) == 19+22);
assert(apply(toList(1..8), n -> #generateGraphs n) == {1, 2, 4, 11, 34, 156, 1044, 12346}); -- A000088
///
-- generateRandomGraphs
TEST ///
assert(#generateRandomGraphs(6, 10) == 10);
assert(#generateRandomGraphs(6, 17, 1/4) == 17);
assert(#generateRandomGraphs(6, 42, 4) == 42);
///
-- generateRandomRegularGraphs
TEST ///
assert(#generateRandomRegularGraphs(6, 10, 3) == 10);
-- There is only one regular graph on 6 vertices with regularity degree 5--K6.
assert(#unique generateRandomRegularGraphs(6, 10, 5) == 1);
///
-- graph6ToSparse6
TEST ///
assert(graph6ToSparse6 "Dhc" == ":DaY_~");
assert(graph6ToSparse6 "M????????????????" == ":M");
///
-- graphComplement
TEST ///
C5 = graph {{0,1},{1,2},{2,3},{3,4},{0,4}};
assert(#edges graphComplement C5 == 5);
G = graph {{1,2},{2,3},{3,4},{4,5}};
assert(areIsomorphic(graphComplement(G, OnlyIfSmaller => true), G));
assert(#edges graphComplement G == 6);
L = generateGraphs 6;
assert(#graphComplement L == #L);
///
-- graphToString
TEST ///
C5 = graph {{0,1},{1,2},{2,3},{3,4},{0,4}};
K5 = graph flatten for i from 0 to 4 list for j from i+1 to 4 list {i,j}
R = ZZ[a..e];
assert(graphToString C5 == "Dhc");
assert(graphToString ideal (a*b, b*c, c*d, d*e, a*e) == "Dhc");
assert(graphToString monomialIdeal (a*b, b*c, c*d, d*e, a*e) == "Dhc");
assert(graphToString "Dhc" == "Dhc");
assert(graphToString ({{0,1}, {1,2}, {2,3}, {3,4}, {0,4}}, 5) == "Dhc");
assert(graphToString K5 == "D~{");
C100 = graph append(apply(99, i -> {i, i+1}), {0, 99});
assert(graphToString C100 == "?@chCGGC@?G?_@?@??_?G?@??C??G??G??C??@???G???_??@???@????_???G???@????C????G????G????C????@?????G?????_????@?????@??????_?????G?????@??????C??????G??????G??????C??????@???????G???????_??????@???????@????????_???????G???????@????????C????????G????????G????????C????????@?????????G?????????_????????@?????????@??????????_?????????G?????????@??????????C??????????G??????????G??????????C??????????@???????????G???????????_??????????@???????????@????????????_???????????G???????????@????????????C????????????G????????????G????????????C????????????@?????????????G?????????????_????????????@?????????????@??????????????_?????????????G?????????????@??????????????C??????????????G??????????????G??????????????C??????????????@???????????????G???????????????_??????????????@???????????????@????????????????_???????????????K???????????????@");
///
-- isPlanar
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
K6 = graph flatten for i from 0 to 5 list for j from i+1 to 5 list {i,j}
assert(isPlanar "Dhc");
assert(isPlanar C6);
assert(not isPlanar K6);
///
-- neighborhoodComplements
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
assert(#neighborhoodComplements C6 == 6);
assert(#neighborhoodComplements {C6} == 6);
///
-- newEdges
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
K6 = graph flatten for i from 0 to 5 list for j from i+1 to 5 list {i,j}
-- There are nine pairs of disjoint edges in C6.
assert(#newEdges C6 == 9);
-- There are 45 pairs of disjoint edges in K6.
assert(#newEdges K6 == 45);
assert(#newEdges {K6} == 45);
///
-- onlyPlanar
TEST ///
L = generateGraphs 5;
assert(#onlyPlanar L == #L - 1);
K5 = graph flatten for i from 0 to 4 list for j from i+1 to 4 list {i,j}
assert(areIsomorphic(K5, first onlyPlanar(L, true)));
///
-- relabelBipartite
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
G = graph {{0,3},{3,1},{1,4},{4,2},{2,5},{5,0}};
-- assert(relabelBipartite C6 === G);
assert(relabelBipartite {"EhEG"} == {"EEY_"});
///
-- relabelGraph
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
assert(#apply(0..15, i -> relabelGraph(C6, i)) == 16);
L = generateGraphs 5;
assert(#relabelGraph L == #L);
///
-- removeEdges
TEST ///
C6 = graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}};
K6 = graph flatten for i from 0 to 5 list for j from i+1 to 5 list {i,j}
assert(#removeEdges C6 == 6);
assert(#removeEdges {C6} == 6);
assert(#removeEdges K6 == binomial(6,2));
///
-- removeIsomorphs
TEST ///
G = {"EhEG", graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}}, "DhC", graph {{0,1}}};
assert(#removeIsomorphs G == 3);
L = graphToString \ apply(permutations 5, P -> graph apply(5, i -> {P_i, P_((i+1)%5)}));
assert(#removeIsomorphs L == 1);
///
-- sparse6ToGraph6
TEST ///
assert(sparse6ToGraph6 ":DaY_~" == "Dhc");
assert(sparse6ToGraph6 ":M" == "M????????????????");
///
-- stringToEdgeIdeal
TEST ///
R = ZZ[a..f];
assert(stringToEdgeIdeal("EhEG", R) == monomialIdeal (a*b, b*c, c*d, d*e, a*f, e*f));
assert(stringToEdgeIdeal("E???", R) == monomialIdeal (0_R));
///
-- stringToGraph
TEST ///
A := sort(sort@@toList \ edges graph {{0,1},{1,2},{2,3},{3,4},{4,5},{0,5}});
B := sort(sort@@toList \ edges stringToGraph "EhEG");
assert(A == B);
assert(stringToGraph "E???" === graph({}, Singletons => {0,1,2,3,4,5}));
///
-------------------
-- HappyHappyJoyJoy
-------------------
end
restart
uninstallPackage "Nauty"
installPackage "Nauty"
check "Nauty"
-----------------------
-- For J-SAG Manuscript
-----------------------
restart
needsPackage "Nauty";
R = QQ[a..e];
graphToString cycle R
graphToString completeGraph R
edges stringToGraph("Dhc", R)
G = graph {{a, c}, {c, e}, {e, b}, {b, d}, {d, a}};
areIsomorphic(cycle R, G)
removeIsomorphs apply(permutations gens R,
P -> graphToString graph apply(5, i-> {P_i, P_((i+1)%5)}))
A000088 = apply(1..9, n -> #generateGraphs n)
B = apply(1..12, n -> generateGraphs(n, OnlyBipartite => true));
forestsOnly = buildGraphFilter {"NumCycles" => 0};
A005195 = apply(B, graphs -> #filterGraphs(graphs, forestsOnly))
treesOnly = buildGraphFilter {"NumCycles" => 0,
"Connectivity" => 0, "NegateConnectivity" => true};
A000055 = apply(B, graphs -> #filterGraphs(graphs, treesOnly))
connected = buildGraphFilter {"Connectivity" => 0,
"NegateConnectivity" => true};
prob = n -> log(n)/n;
apply(2..30, n-> #filterGraphs(generateRandomGraphs(n, 100, 2*(prob n)), connected))
apply(2..30, n-> #filterGraphs(generateRandomGraphs(n, 100, (prob n)/2), connected))