Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

9 Visualising and IO
 9.1 Visualising a digraph
 9.2 Reading and writing digraphs to a file

9 Visualising and IO

9.1 Visualising a digraph

9.1-1 Splash
‣ Splash( str[, opts] )( function )

Returns: Nothing.

This function attempts to convert the string str into a pdf document and open this document, i.e. to splash it all over your monitor.

The string str must correspond to a valid dot or LaTeX text file and you must have have GraphViz and pdflatex installed on your computer. For details about these file formats, see https://www.latex-project.org and https://www.graphviz.org.

This function is provided to allow convenient, immediate viewing of the pictures produced by the function DotDigraph (9.1-2).

The optional second argument opts should be a record with components corresponding to various options, given below.

path

this should be a string representing the path to the directory where you want Splash to do its work. The default value of this option is "~/".

directory

this should be a string representing the name of the directory in path where you want Splash to do its work. This function will create this directory if does not already exist.

The default value of this option is "tmp.viz" if the option path is present, and the result of DirectoryTemporary (Reference: DirectoryTemporary) is used otherwise.

filename

this should be a string representing the name of the file where str will be written. The default value of this option is "vizpicture".

viewer

this should be a string representing the name of the program which should open the files produced by GraphViz or pdflatex.

type

this option can be used to specify that the string str contains a LaTeX or dot document. You can specify this option in str directly by making the first line "%latex" or "//dot". There is no default value for this option, this option must be specified in str or in opt.type.

engine

this option can be used to specify the GraphViz engine to use to render a dot document. The valid choices are "dot", "neato", "circo", "twopi", "fdp", "sfdp", and "patchwork". Please refer to the GraphViz documentation for details on these engines. The default value for this option is "dot", and it must be specified in opt.engine.

filetype

this should be a string representing the type of file which Splash should produce. For LaTeX files, this option is ignored and the default value "pdf" is used.

This function was written by Attila Egri-Nagy and Manuel Delgado with some minor changes by J. D. Mitchell.

gap> Splash(DotDigraph(RandomDigraph(4)));

9.1-2 DotDigraph
‣ DotDigraph( digraph )( attribute )
‣ DotColoredDigraph( digraph, vert, edge )( operation )
‣ DotVertexLabelledDigraph( digraph )( operation )
‣ DotVertexColoredDigraph( digraph, vert )( operation )
‣ DotEdgeColoredDigraph( digraph, edge )( operation )

Returns: A string.

DotDigraph produces a graphical representation of the digraph digraph. Vertices are displayed as circles, numbered consistently with digraph. Edges are displayed as arrowed lines between vertices, with the arrowhead of each line pointing towards the range of the edge.

DotColoredDigraph differs from DotDigraph only in that the values in given in the two lists are used to color the vertices and edges of the graph when displayed. The list for vertex colours should be a list of length equal to the number of vertices, containing strings that are accepted by the graphviz software, which is the one used for graph representation. The list for edge colours should be a list of lists with the same shape of the outneighbours of the digraph that contains strings that correspond to colours accepted by the graphviz software. If the lists are not the appropriate size, or have holes then the function will return an error.

DotVertexColoredDigraph differs from DotDigraph only in that the values in given in the list are used to color the vertices of the graph when displayed. The list for vertex colours should be a list of length equal to the number of vertices, containing strings that are accepted by the graphviz software, which is the one used for graph representation. If the list is not the appropriate size, or has holes then the function will return an error.

DotEdgeColoredDigraph differs from DotDigraph only in that the values in given in the list are used to color the vertices and edges of the graph when displayed. The list for edge colours should be a list of lists with the same shape of the outneighbours of the digraph that contains strings that correspond to colours accepted by the graphviz software. If the list is not the appropriate size, or has holes then the function will return an error.

DotVertexLabelledDigraph differs from DotDigraph only in that the values in DigraphVertexLabels (5.1-10) are used to label the vertices in the produced picture rather than the numbers 1 to the number of vertices of the digraph.

The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see https://www.graphviz.org.

The string returned by DotDigraph or DotVertexLabelledDigraph can be written to a file using the command FileString (GAPDoc: FileString).

gap> adj := List([1 .. 4], x -> [1, 1, 1, 1]);
[ [ 1, 1, 1, 1 ], [ 1, 1, 1, 1 ], [ 1, 1, 1, 1 ], [ 1, 1, 1, 1 ] ]
gap> adj[1][3] := 0;
0
gap> gr := DigraphByAdjacencyMatrix(adj);
<immutable digraph with 4 vertices, 15 edges>
gap> D := CompleteDigraph(4);
<immutable complete digraph with 4 vertices>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";; vertcolors[2] := "red";; 
gap> vertcolors[3] := "green";; vertcolors[4] := "yellow";;
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];;
gap> edgecolors[3] := [];; edgecolors[4] := [];; 
gap> edgecolors[1][2] := "lightblue";;
gap> edgecolors[1][3] := "pink";;
gap> edgecolors[1][4] := "purple";;
gap> edgecolors[2][1] := "lightblue";;
gap> edgecolors[2][3] := "pink";; 
gap> edgecolors[2][4] := "purple";; 
gap> edgecolors[3][1] := "lightblue";; 
gap> edgecolors[3][2] := "pink";; 
gap> edgecolors[3][4] := "purple";;
gap> edgecolors[4][1] := "lightblue";; 
gap> edgecolors[4][2] := "pink";;
gap> edgecolors[4][3] := "purple";;
gap> Print(DotColoredDigraph(D, vertcolors, edgecolors));
//dot
digraph hgn{
node [shape=circle]
1[color=blue, style=filled]
2[color=red, style=filled]
3[color=green, style=filled]
4[color=yellow, style=filled]
1 -> 2[color=lightblue]
1 -> 3[color=pink]
1 -> 4[color=purple]
2 -> 1[color=lightblue]
2 -> 3[color=pink]
2 -> 4[color=purple]
3 -> 1[color=lightblue]
3 -> 2[color=pink]
3 -> 4[color=purple]
4 -> 1[color=lightblue]
4 -> 2[color=pink]
4 -> 3[color=purple]
}
gap> D := EmptyDigraph(3);
<immutable empty digraph with 3 vertices>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";; vertcolors[2] := "red";;
gap> vertcolors[3] := "green";;
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];; 
gap> edgecolors[3] := [];;
gap> Print(DotColoredDigraph(D, vertcolors, edgecolors));
//dot
digraph hgn{
node [shape=circle]
1[color=blue, style=filled]
2[color=red, style=filled]
3[color=green, style=filled]
}
gap> D := Digraph([[2], [1, 3], [2]]);
<immutable digraph with 3 vertices, 4 edges>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";;
gap> vertcolors[2] := "pink";;
gap> vertcolors[3] := "purple";;
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];;
gap> edgecolors[3] := [];;
gap> edgecolors[1][2] := "green";; edgecolors[2][1] := "green";;
gap> edgecolors[2][3] := "red";; edgecolors[3][2] := "red";;
gap> Print(DotSymmetricColoredDigraph(D, vertcolors, edgecolors));
//dot
graph hgn{
node [shape=circle]

1[color=blue, style=filled]
2[color=pink, style=filled]
3[color=purple, style=filled]
1 -- 2[color=green]
2 -- 3[color=red]
}
gap> D := Digraph([[2, 3], [1, 3], [1]]);
<immutable digraph with 3 vertices, 5 edges>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";; vertcolors[2] := "red";;
gap> vertcolors[3] := "green";;
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];;
gap> edgecolors[3] := [];;
gap> edgecolors[1][2] := "orange";; edgecolors[1][3] := "yellow";;
gap> edgecolors[2][1] := "orange";; edgecolors[2][3] := "pink";;
gap> edgecolors[3][1] := "yellow";;
gap> Print(DotColoredDigraph(D, vertcolors, edgecolors));;
//dot
digraph hgn{
node [shape=circle]
1[color=blue, style=filled]
2[color=red, style=filled]
3[color=green, style=filled]
1 -> 2[color=orange]
1 -> 3[color=yellow]
2 -> 1[color=orange]
2 -> 3[color=pink]
3 -> 1[color=yellow]
}
gap> D := Digraph(IsMutableDigraph, [[2, 3], [1, 3], [1]]);
<mutable digraph with 3 vertices, 5 edges>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";; vertcolors[2] := "red";;
gap> vertcolors[3] := "green";;
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];;
gap> edgecolors[3] := [];;
gap> edgecolors[1][2] := "orange";; edgecolors[1][3] := "yellow";;
gap> edgecolors[2][1] := "orange";; edgecolors[2][3] := "pink";;
gap> edgecolors[3][1] := "yellow";;
gap> Print(DotColoredDigraph(D, vertcolors, edgecolors));;
//dot
digraph hgn{
node [shape=circle]
1[color=blue, style=filled]
2[color=red, style=filled]
3[color=green, style=filled]
1 -> 2[color=orange]
1 -> 3[color=yellow]
2 -> 1[color=orange]
2 -> 3[color=pink]
3 -> 1[color=yellow]
}
gap> D;
<mutable digraph with 3 vertices, 5 edges>
gap> DotSymmetricDigraph(gr2){[12 .. 70]};
" hgn{\nnode [shape=circle]\n\n1\n2\n3\n4\n1 -- 2\n2 -- 3\n3 -- 3\n3 -"
gap> DotSymmetricDigraph(gr1);
Error, the argument <D> must be a symmetric digraph,
gap> D := CompleteDigraph(4);
<immutable complete digraph with 4 vertices>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";; vertcolors[2] := "red";; 
gap> vertcolors[3] := "green";; vertcolors[4] := "yellow";;
gap> Print(DotVertexColoredDigraph(D, vertcolors));
//dot
digraph hgn{
node [shape=circle]
1[color=blue, style=filled]
2[color=red, style=filled]
3[color=green, style=filled]
4[color=yellow, style=filled]
1 -> 2
1 -> 3
1 -> 4
2 -> 1
2 -> 3
2 -> 4
3 -> 1
3 -> 2
3 -> 4
4 -> 1
4 -> 2
4 -> 3
}
gap> D := CompleteDigraph(4);
<immutable complete digraph with 4 vertices>
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];;
gap> edgecolors[3] := [];; edgecolors[4] := [];; 
gap> edgecolors[1][2] := "lightblue";;
gap> edgecolors[1][3] := "pink";;
gap> edgecolors[1][4] := "purple";;
gap> edgecolors[2][1] := "lightblue";;
gap> edgecolors[2][3] := "pink";; 
gap> edgecolors[2][4] := "purple";; 
gap> edgecolors[3][1] := "lightblue";; 
gap> edgecolors[3][2] := "pink";; 
gap> edgecolors[3][4] := "purple";;
gap> edgecolors[4][1] := "lightblue";; 
gap> edgecolors[4][2] := "pink";;
gap> edgecolors[4][3] := "purple";;
gap> Print(DotEdgeColoredDigraph(D, edgecolors));
//dot
digraph hgn{
node [shape=circle]
1
2
3
4
1 -> 2[color=lightblue]
1 -> 3[color=pink]
1 -> 4[color=purple]
2 -> 1[color=lightblue]
2 -> 3[color=pink]
2 -> 4[color=purple]
3 -> 1[color=lightblue]
3 -> 2[color=pink]
3 -> 4[color=purple]
4 -> 1[color=lightblue]
4 -> 2[color=pink]
4 -> 3[color=purple]
}
gap> FileString("dot/k4.dot", DotDigraph(gr));
154

9.1-3 DotSymmetricDigraph
‣ DotSymmetricDigraph( digraph )( attribute )
‣ DotSymmetricColoredDigraph( digraph, vert, edge )( operation )
‣ DotSymmetricVertexColoredDigraph( digraph, vert )( operation )
‣ DotSymmetricEdgeColoredDigraph( digraph, edge )( operation )

Returns: A string.

This function produces a graphical representation of the symmetric digraph digraph. DotSymmetricDigraph will return an error if digraph is not a symmetric digraph. See IsSymmetricDigraph (6.2-14).

The function DotSymmetricColoredDigraph differs from DotDigraph only in that the values given in the two lists are used to color the vertices and edges of the graph when displayed. The list for vertex colours should be a list of length equal to the number of vertices, containing strings that are accepted by the graphviz software, which is the one used for graph representation. The list for edge colours should be a list of lists with the same shape of the outneighbours of the digraph that contains strings that correspond to colours accepted by the graphviz software. If the list is not the appropriate size, or has holes then the function will return an error.

The function DotSymmetricVertexColoredDigraph differs from DotDigraph only in that the values in given in the list is used to color the vertices of the graph when displayed. The list for vertex colours should be a list of length equal to the number of vertices, containing strings that are accepted by the graphviz software, which is the one used for graph representation. If the list is not the appropriate size, or has holes then the function will return an error.

The function DotSymmetricEdgeColoredDigraph differs from DotDigraph only in that the values given in the list are used to color the edges of the graph when displayed. The list for edge colours should be a list of lists with the same shape of the outneighbours, containing strings that are accepted by the graphviz software, which is the one used for graph representation. If the list is not the appropriate size, or has holes then the function will return an error.

Vertices are displayed as circles, numbered consistently with digraph. Since digraph is symmetric, for every non-loop edge there is a complementary edge with opposite source and range. DotSymmetricDigraph displays each pair of complementary edges as a single line between the relevant vertices, with no arrowhead.

The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see https://www.graphviz.org.

The string returned by DotSymmetricDigraph can be written to a file using the command FileString (GAPDoc: FileString).

gap> star := Digraph([[2, 2, 3, 4], [1, 1], [1], [1, 4]]);
<immutable multidigraph with 4 vertices, 9 edges>
gap> IsSymmetricDigraph(star);
true
gap> FileString("dot/star.dot", DotSymmetricDigraph(gr));
gap> D := Digraph([[2], [1, 3], [2]]);
<immutable digraph with 3 vertices, 4 edges>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";;
gap> vertcolors[2] := "pink";;
gap> vertcolors[3] := "purple";;
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];;
gap> edgecolors[3] := [];;
gap> edgecolors[1][2] := "green";; edgecolors[2][1] := "green";;
gap> edgecolors[2][3] := "red";; edgecolors[3][2] := "red";;
gap> Print(DotSymmetricColoredDigraph(D, vertcolors, edgecolors));
//dot
graph hgn{
node [shape=circle]

1[color=blue, style=filled]
2[color=pink, style=filled]
3[color=purple, style=filled]
1 -- 2[color=green]
2 -- 3[color=red]
}
gap> D := Digraph([[2], [1, 3], [2]]);
<immutable digraph with 3 vertices, 4 edges>
gap> vertcolors := [];;
gap> vertcolors[1] := "blue";;
gap> vertcolors[2] := "pink";;
gap> vertcolors[3] := "purple";;
gap> Print(DotSymmetricVertexColoredDigraph(D, vertcolors));
//dot
graph hgn{
node [shape=circle]

1[color=blue, style=filled]
2[color=pink, style=filled]
3[color=purple, style=filled]
1 -- 2
2 -- 3
}
gap> D := Digraph([[2], [1, 3], [2]]);
<immutable digraph with 3 vertices, 4 edges>
gap> edgecolors := [];;
gap> edgecolors[1] := [];; edgecolors[2] := [];;
gap> edgecolors[3] := [];;
gap> edgecolors[1][2] := "green";; edgecolors[2][1] := "green";;
gap> edgecolors[2][3] := "red";; edgecolors[3][2] := "red";;
gap> Print(DotSymmetricEdgeColoredDigraph(D, edgecolors));
//dot
graph hgn{
node [shape=circle]

1
2
3
1 -- 2[color=green]
2 -- 3[color=red]
}
83

9.1-4 DotPartialOrderDigraph
‣ DotPartialOrderDigraph( digraph )( attribute )

Returns: A string.

This function produces a graphical representation of a partial order digraph digraph. DotPartialOrderDigraph will return an error if digraph is not a partial order digraph. See IsPartialOrderDigraph (6.4-2).

Since digraph is a partial order, it is both reflexive and transitive. The output of DotPartialOrderDigraph is the DotDigraph (9.1-2) of the DigraphReflexiveTransitiveReduction (3.3-14) of digraph.

The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see https://www.graphviz.org.

The string returned by DotPartialOrderDigraph can be written to a file using the command FileString (GAPDoc: FileString).

gap> poset := Digraph([[1, 4], [2], [2, 3, 4], [4]);
gap> IsPartialOrderDigraph(gr);
true
gap> FileString("dot/poset.dot", DotPartialOrderDigraph(gr));
83

9.1-5 DotPreorderDigraph
‣ DotPreorderDigraph( digraph )( attribute )
‣ DotQuasiorderDigraph( digraph )( attribute )

Returns: A string.

This function produces a graphical representation of a preorder digraph digraph. DotPreorderDigraph will return an error if digraph is not a preorder digraph. See IsPreorderDigraph (6.4-1).

A preorder digraph is reflexive and transitive but in general it is not anti-symmetric and may have strongly connected components containing more than one vertex. The QuotientDigraph (3.3-9) Q obtained by forming the quotient of digraph by the partition of its vertices into the strongly connected components satisfies IsPartialOrderDigraph (6.4-2). Thus every vertex of Q corresponds to a strongly connected component of digraph. The output of DotPreorderDigraph displays the DigraphReflexiveTransitiveReduction (3.3-14) of Q with vertices displayed as rounded rectangles labelled by all of the vertices of digraph in the corresponding strongly connected component.

The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see https://www.graphviz.org.

The string returned by DotPreorderDigraph can be written to a file using the command FileString (GAPDoc: FileString).

gap> preset := Digraph([[1, 2, 4, 5], [1, 2, 4, 5], [3, 4], [4], [1, 2, 4, 5]);
gap> IsPreorderDigraph(gr);
true
gap> FileString("dot/preset.dot", DotProrderDigraph(gr));
83

9.1-6 DotHighlightedDigraph
‣ DotHighlightedDigraph( digraph, verts[, colour1, colour2] )( operation )

Returns: A string.

DotHighlightedDigraph produces a graphical representation of the digraph digraph, where the vertices in the list verts, and edges between them, are drawn with colour colour1 and all other vertices and edges in digraph are drawn with colour colour2. If colour1 and colour2 are not given then DotHighlightedDigraph uses black and grey respectively.

Note that DotHighlightedDigraph does not validate the colours colour1 and colour2 - consult the GraphViz documentation to see what is available. See DotDigraph (9.1-2) for more details on the output.

gap> digraph := Digraph([[2, 3], [2], [1, 3]]);
<digraph with 3 vertices, 5 edges>
gap> FileString("dot/my_digraph.dot",
> DotHighlightedDigraph(digraph, [1, 2], "red", "black"));
264

9.2 Reading and writing digraphs to a file

This section describes different ways to store and read graphs from a file in the Digraphs package.

Graph6

Graph6 is a graph data format for storing undirected graphs with no multiple edges nor loops of size up to 2^36 - 1 in printable characters. The format consists of two parts. The first part uses one to eight bytes to store the number of vertices. And the second part is the upper half of the adjacency matrix converted into ASCII characters. For a more detail description see Graph6.

Sparse6

Sparse6 is a graph data format for storing undirected graphs with possibly multiple edges or loops. The maximal number of vertices allowed is 2^36 - 1. The format consists of two parts. The first part uses one to eight bytes to store the number of vertices. And the second part only stores information about the edges. Therefore, the Sparse6 format return a more compact encoding then Graph6 for sparse graph, i.e. graphs where the number of edges is much less than the number of vertices squared. For a more detail description see Sparse6.

Digraph6

Digraph6 is a new format based on Graph6 , but designed for digraphs. The entire adjacency matrix is stored, and therefore there is support for directed edges and single-vertex loops. However, multiple edges are not supported.

DiSparse6

DiSparse6 is a new format based on Sparse6 , but designed for digraphs. In this format the list of edges is partitioned into increasing and decreasing edges, depending whether the edge has its source bigger than the range. Then both sets of edges are written separately in Sparse6 format with a separation symbol in between.

9.2-1 String
‣ String( digraph )( attribute )
‣ PrintString( digraph )( operation )

Returns: A string.

Returns a string string such that EvalString(string) is equal to digraph, and has the same mutability. See EvalString (Reference: EvalString).

The methods installed for String make some attempts to ensure that string has as short a length as possible, but there may exist shorter strings that also evaluate to digraph.

It is possible that string may contain escaped special characters. To obtain a representation of digraph that can be entered as GAP input, please use Print (Reference: Print). Note that Print for a digraph delegates to PrintString, which delegates to String.

gap> D := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> Print(D);
CycleDigraph(3);
gap> G := PetersenGraph(IsMutableDigraph);
<mutable digraph with 10 vertices, 30 edges>
gap> String(G);
"DigraphFromGraph6String(IsMutableDigraph, \"IheA@GUAo\");"
gap> Print(last);
DigraphFromGraph6String(IsMutableDigraph, "IheA@GUAo");
gap> DigraphFromGraph6String(IsMutableDigraph, "IheA@GUAo");
<mutable digraph with 10 vertices, 30 edges>

9.2-2 DigraphFromGraph6String
‣ DigraphFromGraph6String( [filt, ]str )( operation )
‣ DigraphFromDigraph6String( [filt, ]str )( operation )
‣ DigraphFromSparse6String( [filt, ]str )( operation )
‣ DigraphFromDiSparse6String( [filt, ]str )( operation )

Returns: A digraph.

If str is a string encoding a graph in Graph6, Digraph6, Sparse6 or DiSparse6 format, then the corresponding function returns a digraph. In the case of either Graph6 or Sparse6, formats which do not support directed edges, this will be a digraph such that for every edge, the edge going in the opposite direction is also present.

Each of these functions takes an optional first argument filt, which should be either IsMutableDigraph (3.1-2) or IsImmutableDigraph (3.1-3), and which specifies whether the output digraph shall be mutable or immutable. If no first argument is provided, then an immutable digraph is returned by default.

gap> DigraphFromGraph6String("?");
<immutable empty digraph with 0 vertices>
gap> DigraphFromGraph6String("C]");
<immutable symmetric digraph with 4 vertices, 8 edges>
gap> DigraphFromGraph6String("H?AAEM{");
<immutable symmetric digraph with 9 vertices, 22 edges>
gap> DigraphFromDigraph6String("&?");
<immutable empty digraph with 0 vertices>
gap> DigraphFromDigraph6String(IsMutableDigraph, "&DOOOW?");
<mutable digraph with 5 vertices, 5 edges>
gap> DigraphFromDigraph6String("&CQFG");
<immutable digraph with 4 vertices, 6 edges>
gap> DigraphFromDigraph6String("&IM[SrKLc~lhesbU[F_");
<immutable digraph with 10 vertices, 51 edges>
gap> DigraphFromDiSparse6String(".CaWBGA?b");
<immutable multidigraph with 4 vertices, 9 edges>

9.2-3 Graph6String
‣ Graph6String( digraph )( operation )
‣ Digraph6String( digraph )( operation )
‣ Sparse6String( digraph )( operation )
‣ DiSparse6String( digraph )( operation )

Returns: A string.

These four functions return a highly compressed string fully describing the digraph digraph.

Graph6 and Digraph6 are formats best used on small, dense graphs, if applicable. For larger, sparse graphs use Sparse6 and Disparse6 (this latter also preserves multiple edges).

See WriteDigraphs (9.2-6).

gap> gr := Digraph([[2, 3], [1], [1]]);
<immutable digraph with 3 vertices, 4 edges>
gap> Sparse6String(gr);
":Bc"
gap> DiSparse6String(gr);
".Bc{f"

9.2-4 DigraphFile
‣ DigraphFile( filename[, coder][, mode] )( function )

Returns: An IO file object.

If filename is a string representing the name of a file, then DigraphFile returns an IO package file object for that file.

If the optional argument coder is specified and is a function which either encodes a digraph as a string, or decodes a string into a digraph, then this function will be used when reading or writing to the returned file object. If the optional argument coder is not specified, then the encoding of the digraphs in the returned file object must be specified in the the file extension. The file extension must be one of: .g6, .s6, .d6, .ds6, .txt, .p, or .pickle; more details of these file formats is given below.

If the optional argument mode is specified, then it must be one of: "w" (for write), "a" (for append), or "r" (for read). If mode is not specified, then "r" is used by default.

If filename ends in one of: .gz, .bz2, or .xz, then the digraphs which are read from, or written to, the returned file object are decompressed, or compressed, appropriately.

The file object returned by DigraphFile can be given as the first argument for either of the functions ReadDigraphs (9.2-5) or WriteDigraphs (9.2-6). The purpose of this is to reduce the overhead of recreating the file object inside the functions ReadDigraphs (9.2-5) or WriteDigraphs (9.2-6) when, for example, reading or writing many digraphs in a loop.

The currently supported file formats, and associated filename extensions, are:

graph6 (.g6)

A standard and widely-used format for undirected graphs, with no support for loops or multiple edges. Only symmetric graphs are allowed -- each edge is combined with its converse edge to produce a single undirected edge. This format is best used for "dense" graphs -- those with many edges per vertex.

sparse6 (.s6)

Unlike graph6, sparse6 has support for loops and multiple edges. However, its use is still limited to symmetric graphs. This format is better-suited to "sparse" graphs -- those with few edges per vertex.

digraph6 (.d6)

This format is based on graph6, but stores direction information - therefore is not limited to symmetric graphs. Loops are allowed, but multiple edges are not. Best compression with "dense" graphs.

disparse6 (.ds6)

Any type of digraph can be encoded in disparse6: directions, loops, and multiple edges are all allowed. Similar to sparse6, this has the best compression rate with "sparse" graphs.

plain text (.txt)

This is a human-readable format which stores graphs in the form 0 7 0 8 1 7 2 8 3 8 4 8 5 8 6 8 i.e. pairs of vertices describing edges in a graph. More specifically, the vertices making up one edge must be separated by a single space, and pairs of vertices must be separated by two spaces.

See ReadPlainTextDigraph (9.2-13) for a more flexible way to store digraphs in a plain text file.

pickled (.p or .pickle)

Digraphs are pickled using the IO package. This is particularly good when the DigraphGroup (7.2-10) is non-trivial.

gap> filename := Concatenation(DIGRAPHS_Dir(), "/tst/out/man.d6.gz");;
gap> file := DigraphFile(filename, "w");;
gap> for i in [1 .. 10] do
> WriteDigraphs(file, Digraph([[1, 3], [2], [1, 2]]));
> od;
gap> IO_Close(file);;
gap> file := DigraphFile(filename, "r");;
gap> ReadDigraphs(file, 9);
<immutable digraph with 3 vertices, 5 edges>
gap> IO_Close(file);;

9.2-5 ReadDigraphs
‣ ReadDigraphs( filename[, decoder][, n] )( function )

Returns: A digraph, or a list of digraphs.

If filename is a string containing the name of a file containing encoded digraphs or an IO file object created using DigraphFile (9.2-4), then ReadDigraphs returns the digraphs encoded in the file as a list. Note that if filename is a compressed file, which has been compressed appropriately to give a filename extension of .gz, .bz2, or .xz, then ReadDigraphs can read filename without it first needing to be decompressed.

If the optional argument decoder is specified and is a function which decodes a string into a digraph, then ReadDigraphs will use decoder to decode the digraphs contained in filename.

If the optional argument n is specified, then ReadDigraphs returns the nth digraph encoded in the file filename.

If the optional argument decoder is not specified, then ReadDigraphs will deduce which decoder to use based on the filename extension of filename (after removing the compression-related filename extensions .gz, .bz2, and .xz). For example, if the filename extension is .g6, then ReadDigraphs will use the graph6 decoder DigraphFromGraph6String (9.2-2).

The currently supported file formats, and associated filename extensions, are:

graph6 (.g6)

A standard and widely-used format for undirected graphs, with no support for loops or multiple edges. Only symmetric graphs are allowed -- each edge is combined with its converse edge to produce a single undirected edge. This format is best used for "dense" graphs -- those with many edges per vertex.

sparse6 (.s6)

Unlike graph6, sparse6 has support for loops and multiple edges. However, its use is still limited to symmetric graphs. This format is better-suited to "sparse" graphs -- those with few edges per vertex.

digraph6 (.d6)

This format is based on graph6, but stores direction information - therefore is not limited to symmetric graphs. Loops are allowed, but multiple edges are not. Best compression with "dense" graphs.

disparse6 (.ds6)

Any type of digraph can be encoded in disparse6: directions, loops, and multiple edges are all allowed. Similar to sparse6, this has the best compression rate with "sparse" graphs.

plain text (.txt)

This is a human-readable format which stores graphs in the form 0 7 0 8 1 7 2 8 3 8 4 8 5 8 6 8 i.e. pairs of vertices describing edges in a graph. More specifically, the vertices making up one edge must be separated by a single space, and pairs of vertices must be separated by two spaces.

See ReadPlainTextDigraph (9.2-13) for a more flexible way to store digraphs in a plain text file.

pickled (.p or .pickle)

Digraphs are pickled using the IO package. This is particularly good when the DigraphGroup (7.2-10) is non-trivial.

gap> ReadDigraphs(
> Concatenation(DIGRAPHS_Dir(), "/data/graph5.g6.gz"), 10);
<immutable symmetric digraph with 5 vertices, 8 edges>
gap> ReadDigraphs(
> Concatenation(DIGRAPHS_Dir(), "/data/graph5.g6.gz"), 17);
<immutable symmetric digraph with 5 vertices, 12 edges>
gap> ReadDigraphs(
> Concatenation(DIGRAPHS_Dir(), "/data/tree9.4.txt"));
[ <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges>, 
  <immutable digraph with 9 vertices, 8 edges> ]

9.2-6 WriteDigraphs
‣ WriteDigraphs( filename, digraphs[, encoder][, mode] )( function )

If digraphs is a list of digraphs or a digraph and filename is a string or an IO file object created using DigraphFile (9.2-4), then WriteDigraphs writes the digraphs to the file represented by filename. If the supplied filename ends in one of the extensions .gz, .bz2, or .xz, then the file will be compressed appropriately. Excluding these extensions, if the file ends with an extension in the list below, the corresponding graph format will be used to encode it. If such an extension is not included, an appropriate format will be chosen intelligently, and an extension appended, to minimise file size.

For more verbose information on the progress of the function, set the info level of InfoDigraphs to 1 or higher, using SetInfoLevel.

The currently supported file formats are:

graph6 (.g6)

A standard and widely-used format for undirected graphs, with no support for loops or multiple edges. Only symmetric graphs are allowed -- each edge is combined with its converse edge to produce a single undirected edge. This format is best used for "dense" graphs -- those with many edges per vertex.

sparse6 (.s6)

Unlike graph6, sparse6 has support for loops and multiple edges. However, its use is still limited to symmetric graphs. This format is better-suited to "sparse" graphs -- those with few edges per vertex.

digraph6 (.d6)

This format is based on graph6, but stores direction information - therefore is not limited to symmetric graphs. Loops are allowed, but multiple edges are not. Best compression with "dense" graphs.

disparse6 (.ds6)

Any type of digraph can be encoded in disparse6: directions, loops, and multiple edges are all allowed. Similar to sparse6, this has the best compression rate with "sparse" graphs.

plain text (.txt)

This is a human-readable format which stores graphs in the form 0 7 0 8 1 7 2 8 3 8 4 8 5 8 6 8 i.e. pairs of vertices describing edges in a graph. More specifically, the vertices making up one edge must be separated by a single space, and pairs of vertices must be separated by two spaces.

See ReadPlainTextDigraph (9.2-13) for a more flexible way to store digraphs in a plain text file.

pickled (.p or .pickle)

Digraphs are pickled using the IO package. This is particularly good when the DigraphGroup (7.2-10) is non-trivial.

gap> grs := [];;
gap> grs[1] := Digraph([]);
<immutable empty digraph with 0 vertices>
gap> grs[2] := Digraph([[1, 3], [2], [1, 2]]);
<immutable digraph with 3 vertices, 5 edges>
gap> grs[3] := Digraph([
> [6, 7], [6, 9], [1, 3, 4, 5, 8, 9],
> [1, 2, 3, 4, 5, 6, 7, 10], [1, 5, 6, 7, 10], [2, 4, 5, 9, 10],
> [3, 4, 5, 6, 7, 8, 9, 10], [1, 3, 5, 7, 8, 9], [1, 2, 5],
> [1, 2, 4, 6, 7, 8]]);
<immutable digraph with 10 vertices, 51 edges>
gap> filename := Concatenation(DIGRAPHS_Dir(), "/tst/out/man.d6.gz");;
gap> WriteDigraphs(filename, grs, "w");
IO_OK
gap> ReadDigraphs(filename);
[ <immutable empty digraph with 0 vertices>, 
  <immutable digraph with 3 vertices, 5 edges>, 
  <immutable digraph with 10 vertices, 51 edges> ]

9.2-7 IteratorFromDigraphFile
‣ IteratorFromDigraphFile( filename[, decoder] )( function )

Returns: An iterator.

If filename is a string representing the name of a file containing encoded digraphs, then IteratorFromDigraphFile returns an iterator for which the value of NextIterator (Reference: NextIterator) is the next digraph encoded in the file.

If the optional argument decoder is specified and is a function which decodes a string into a digraph, then IteratorFromDigraphFile will use decoder to decode the digraphs contained in filename.

The purpose of this function is to easily allow looping over digraphs encoded in a file when loading all of the encoded digraphs would require too much memory.

To see what file types are available, see WriteDigraphs (9.2-6).

gap> filename := Concatenation(DIGRAPHS_Dir(), "/tst/out/man.d6.gz");;
gap> file := DigraphFile(filename, "w");;
gap> for i in [1 .. 10] do
>   WriteDigraphs(file, Digraph([[1, 3], [2], [1, 2]]));
> od;
gap> IO_Close(file);;
gap> iter := IteratorFromDigraphFile(filename);
<iterator>
gap> for x in iter do od;

9.2-8 DigraphPlainTextLineEncoder
‣ DigraphPlainTextLineEncoder( delimiter1[, delimiter2], offset )( function )
‣ DigraphPlainTextLineDecoder( delimiter1[, delimiter2], offset )( operation )

Returns: A string.

These two functions return a function which encodes or decodes a digraph in a plain text format.

DigraphPlainTextLineEncoder returns a function which takes a single digraph as an argument. The function returns a string describing the edges of that digraph; each edge is written as a pair of integers separated by the string delimiter2, and the edges themselves are separated by the string delimiter1. DigraphPlainTextLineDecoder returns the corresponding decoder function, which takes a string argument in this format and returns a digraph.

If only one delimiter is passed as an argument to DigraphPlainTextLineDecoder, it will return a function which decodes a single edge, returning its contents as a list of integers.

The argument offset should be an integer, which will describe a number to be added to each vertex before it is encoded, or after it is decoded. This may be used, for example, to label vertices starting at 0 instead of 1.

Note that the number of vertices of a digraph is not stored, and so vertices which are not connected to any edge may be lost.

gap> gr := Digraph([[2, 3], [1], [1]]);
<immutable digraph with 3 vertices, 4 edges>
gap> enc := DigraphPlainTextLineEncoder("  ", " ", -1);;
gap> dec := DigraphPlainTextLineDecoder("  ", " ", 1);;
gap> enc(gr);
"0 1  0 2  1 0  2 0"
gap> dec(last);
<immutable digraph with 3 vertices, 4 edges>

9.2-9 TournamentLineDecoder
‣ TournamentLineDecoder( str )( operation )

Returns: A digraph.

This function takes a string str, decodes it, and then returns the tournament [see IsTournament (6.2-15)] which it defines, according to the following rules.

The characters of the string str represent the entries in the upper triangle of a tournament's adjacency matrix. The number of vertices n will be detected from the length of the string and will be as large as possible.

The first character represents the possible edge 1 -> 2, the second represents 1 -> 3 and so on until 1 -> n; then the following character represents 2 -> 3, and so on up to the character which represents the edge n-1 -> n.

If a character of the string with corresponding edge i -> j is equal to 1, then the edge i -> j is present in the tournament. Otherwise, the edge i -> j is present instead. In this way, all the possible edges are encoded one-by-one.

gap> gr := TournamentLineDecoder("100001");
<immutable digraph with 4 vertices, 6 edges>
gap> OutNeighbours(gr);
[ [ 2 ], [  ], [ 1, 2, 4 ], [ 1, 2 ] ]

9.2-10 AdjacencyMatrixUpperTriangleLineDecoder
‣ AdjacencyMatrixUpperTriangleLineDecoder( str )( operation )

Returns: A digraph.

This function takes a string str, decodes it, and then returns the topologically sorted digraph [see DigraphTopologicalSort (5.1-8)] which it defines, according to the following rules.

The characters of the string str represent the entries in the upper triangle of a digraph's adjacency matrix. The number of vertices n will be detected from the length of the string and will be as large as possible.

The first character represents the possible edge 1 -> 2, the second represents 1 -> 3 and so on until 1 -> n; then the following character represents 2 -> 3, and so on up to the character which represents the edge n-1 -> n. If a character of the string with corresponding edge i -> j is equal to 1, then this edge is present in the digraph. Otherwise, it is not present. In this way, all the possible edges are encoded one-by-one.

In particular, note that there exists no edge [i, j] if j ≤ i. In order words, the digraph will be topologically sorted.

gap> gr := AdjacencyMatrixUpperTriangleLineDecoder("100001");
<immutable digraph with 4 vertices, 2 edges>
gap> OutNeighbours(gr);
[ [ 2 ], [  ], [ 4 ], [  ] ]
gap> gr := AdjacencyMatrixUpperTriangleLineDecoder("111111x111");
<immutable digraph with 5 vertices, 9 edges>
gap> OutNeighbours(gr);
[ [ 2, 3, 4, 5 ], [ 3, 4 ], [ 4, 5 ], [ 5 ], [  ] ]

9.2-11 TCodeDecoder
‣ TCodeDecoder( str )( operation )

Returns: A digraph.

If str is a string consisting of at least two non-negative integers separated by spaces, then this function will attempt to return the digraph which it defines as a TCode string.

The first integer of the string defines the number of vertices v in the digraph, and the second defines the number of edges e. The following 2e integers should be vertex numbers in the range [0 .. v-1]. These integers are read in pairs and define the digraph's edges. This function will return an error if str has fewer than 2e+2 entries.

Note that the vertex numbers will be incremented by 1 in the digraph returned. Hence the string fragment 0 6 will describe the edge [1,7].

gap> gr := TCodeDecoder("3 2 0 2 2 1");
<immutable digraph with 3 vertices, 2 edges>
gap> OutNeighbours(gr);
[ [ 3 ], [  ], [ 2 ] ]
gap> gr := TCodeDecoder("12 3 0 10 5 2 8 8");
<immutable digraph with 12 vertices, 3 edges>
gap> OutNeighbours(gr);
[ [ 11 ], [  ], [  ], [  ], [  ], [ 3 ], [  ], [  ], [ 9 ], [  ], 
  [  ], [  ] ]

9.2-12 PlainTextString
‣ PlainTextString( digraph )( operation )
‣ DigraphFromPlainTextString( s )( operation )

Returns: A string.

PlainTextString takes a single digraph, and returns a string describing the edges of that digraph. DigraphFromPlainTextString takes such a string and returns the digraph which it describes. Each edge is written as a pair of integers separated by a single space. The edges themselves are separated by a double space. Vertex numbers are reduced by 1 when they are encoded, so that vertices in the string are labelled starting at 0.

Note that the number of vertices of a digraph is not stored, and so vertices which are not connected to any edge may be lost.

The operation DigraphFromPlainTextString takes an optional first argument IsMutableDigraph (3.1-2) or IsImmutableDigraph (3.1-3), which specifies whether the output digraph shall be mutable or immutable. If no first argument is provided, then an immutable digraph is returned by default.

gap> gr := Digraph([[2, 3], [1], [1]]);
<immutable digraph with 3 vertices, 4 edges>
gap> PlainTextString(gr);
"0 1  0 2  1 0  2 0"
gap> DigraphFromPlainTextString(last);
<immutable digraph with 3 vertices, 4 edges>

9.2-13 WritePlainTextDigraph
‣ WritePlainTextDigraph( filename, digraph, delimiter, offset )( function )
‣ ReadPlainTextDigraph( filename, delimiter, offset, ignore )( operation )

These functions write and read a single digraph in a human-readable plain text format as follows: each line contains a single edge, and each edge is written as a pair of integers separated by the string delimiter.

filename should be the name of a file which will be written to or read from, and offset should be an integer which is added to each vertex number as it is written or read. For example, if WritePlainTextDigraph is called with offset -1, then the vertices will be numbered in the file starting from 0 instead of 1 - ReadPlainTextDigraph would then need to be called with offset 1 to convert back to the original graph.

ignore should be a list of characters which will be ignored when reading the graph.

gap> gr := Digraph([[1, 2, 3], [1, 1], [2]]);
<immutable multidigraph with 3 vertices, 6 edges>
gap> filename := Concatenation(DIGRAPHS_Dir(), "/tst/out/plain.txt");;
gap> WritePlainTextDigraph(filename, gr, ",", -1);
gap> ReadPlainTextDigraph(filename, ",", 1, ['/', '%']);
<immutable multidigraph with 3 vertices, 6 edges>

9.2-14 WriteDIMACSDigraph
‣ WriteDIMACSDigraph( filename, digraph )( operation )
‣ ReadDIMACSDigraph( filename )( operation )

These operations write or read the single symmetric digraph digraph to or from a file in DIMACS format, as appropriate. The operation WriteDIMACSDigraph records the vertices and edges of digraph. The vertex labels of digraph will be recorded only if they are integers. See IsSymmetricDigraph (6.2-14) and DigraphVertexLabels (5.1-10).

The first argument filename should be the name of the file which will be written to or read from. A file can contain one symmetric digraph in DIMACS format. If filename ends in one of .gz, .bz2, or .xz, then the file is compressed, or decompressed, appropriately.

The DIMACS format is described as follows. Each line in the DIMACS file has one of four types:

A detailed definition of the DIMACS format can be found at http://mat.gsia.cmu.edu/COLOR/general/ccformat.ps, in Section 2.1. Note that optional descriptor lines, as described in Section 2.1, will be ignored.

gap> gr := Digraph([[2], [1, 3, 4], [2, 4], [2, 3]]);
<immutable digraph with 4 vertices, 8 edges>
gap> filename := Concatenation(DIGRAPHS_Dir(),
>                              "/tst/out/dimacs.dimacs");;
gap> WriteDIMACSDigraph(filename, gr);;
gap> ReadDIMACSDigraph(filename);
<immutable digraph with 4 vertices, 8 edges>
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind

generated by GAPDoc2HTML