# application: graph

The application graph deals with directed and undirected graphs. They can be defined abstractly as a set of nodes and EDGES or as part of a larger structure for instance as the vertex-edge graph of a polytope.

imports from: common

## User Functions

•

### Combinatorics

These functions capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

•
complement_graph (G) → Graph

Creates the complement graph of a graph.

##### Parameters
 Graph G
##### Returns
 Graph
•
connectivity (graph) → Int

Compute the CONNECTIVITY of a given graph using the Ford-Fulkerson flow algorithm.

##### Parameters
 props::Graph graph
##### Returns
 Int

Example:
• Compute the connectivity of the vertex-edge graph of the square:`> print connectivity(cube(2)->GRAPH->ADJACENCY);`` 2` This means that at least two nodes or edges need to be removed in order for the resulting graoh not to be connected anymore.
•
incidence_matrix (G) → SparseMatrix<Int>

Compute the unsigned vertex-edge incidence matrix of the graph.

##### Parameters
 Graph G
##### Returns
 SparseMatrix

Example:
• `> \$I = incidence_matrix(cycle_graph(4));``> print \$I;`` 1 0 1 0`` 1 1 0 0`` 0 1 0 1`` 0 0 1 1`
•
laplacian (G) → Matrix

Creates the Laplacian matrix of a graph.

##### Parameters
 Graph G
##### Returns
 Matrix

Example:
• `> \$M = laplacian(cycle_graph(4));``> print \$M;`` 2 -1 0 -1`` -1 2 -1 0`` 0 -1 2 -1`` -1 0 -1 2`
•
line_graph (G) → Graph

Creates the line graph of a graph.

##### Parameters
 Graph G
##### Returns
 Graph
•
signed_incidence_matrix (G) → SparseMatrix<Int>

Compute the signed vertex-edge incidence matrix of the graph. in case of undirected graphs, the orientation of the edges is induced by the order of the nodes.

##### Parameters
 Graph G
##### Returns
 SparseMatrix

Example:
• `> \$I = signed_incidence_matrix(cycle_graph(4));``> print \$I;`` 1 0 1 0`` -1 1 0 0`` 0 -1 0 1`` 0 0 -1 -1`
•

### Comparing

These clients are concerned with automorphisms of graphs and determining whether graphs are isomorphic.

•
automorphisms (graph) → Array<Array<Int>>

Find the automorphism group of the graph.

##### Parameters
 props::Graph graph
##### Returns
 Array> each element encodes a node permutation.

Example:
• We first create the vertex-edge graph of the square and then print its automorphism group:`> \$g=new props::Graph(cube(2)->GRAPH->ADJACENCY);``> print automorphisms(\$g);`` 0 2 1 3`` 1 0 3 2` These two permutations generate the group of all node permutations that preserve vertex-edge connectivity.
Depends on: bliss or nauty
•
automorphisms (m) → Array<Pair<Array<Int>,Array<Int>>>

Find the automorphism group of the non-symmetric incidence matrix.

##### Parameters
 IncidenceMatrix m
##### Returns
 Array,Array>> each element encodes a permutation of its rows (`first`) and columns (`second`).

Example:
• The group of combinatorial automorphisms of the 3-cube coincides with the group of (bipartite) graph automorphisms of the vertex/facet incidences. To print this group, type this:`> print automorphisms(cube(3)->VERTICES_IN_FACETS);`` (<0 1 4 5 2 3> <0 1 4 5 2 3 6 7>)`` (<2 3 0 1 4 5> <0 2 1 3 4 6 5 7>)`` (<1 0 2 3 4 5> <1 0 3 2 5 4 7 6>)` This means that the group is generated by three elements, one per line in the output. Each is written as a pair of permutations. The first gives the action on the facets, the second the action on the vertices.
Depends on: bliss or nauty
•
automorphisms (m) → Array<Array<Int>>

Find the automorphism group of the symmetric incidence matrix.

##### Parameters
 IncidenceMatrix m
##### Returns
 Array> each element encodes a permutation of its rows (=columns).
Depends on: bliss or nauty
•
find_node_permutation (graph1, graph2) → Array<Int>

Find the node permutation mapping graph1 to graph2. If the given graphs are not isomorphic, throw an expection.

##### Parameters
 props::Graph graph1 props::Graph graph2
##### Returns
 Array
Depends on: bliss or nauty
•
find_row_col_permutation (m1, m2) → Pair<Array<Int>,Array<Int>>

Find the permutations mapping the non-symmetric incidence matrix m1 to m2. If the given matrices are not isomorphic, throw an expection.

##### Parameters
 IncidenceMatrix m1 IncidenceMatrix m2
##### Returns
 Pair,Array> `first` permutation applies to the rows, `second` applies to the columns

Example:
• `> \$m1 = new IncidenceMatrix([1,2],[5,3]);``> \$m2 = new IncidenceMatrix([4,3],[1,5]);``> print find_row_col_permutation(\$m1,\$m2);`` <1 0> <0 1 4 3 5 2>`
Depends on: bliss or nauty
•
isomorphic (IncidenceMatrix1, IncidenceMatrix2) → Bool

true if IncidenceMatrix1 and IncidenceMatrix2 are isomorphic.

##### Parameters
 IncidenceMatrix IncidenceMatrix1 IncidenceMatrix IncidenceMatrix2
##### Returns
 Bool

Example:
• Compare the incidence matrices of the 2-dimensional cube and cross polytope:`> \$I1 = cube(2)->VERTICES_IN_FACETS;``> \$I2 = cross(2)->VERTICES_IN_FACETS;``> print isomorphic(\$I1,\$I2);`` 1`
Depends on: bliss or nauty
•
isomorphic (graph1, graph2) → Bool

true if graph1 and graph2 are isomorphic.

##### Parameters
 props::Graph graph1 props::Graph graph2
##### Returns
 Bool

Example:
• Compare the vertex-edge graph of the square with the cycle graph on 4 nodes:`> \$g1 = cube(2)->GRAPH->ADJACENCY;``> \$g2 = cycle_graph(4)->ADJACENCY;``> print isomorphic(\$g1,\$g2);`` 1`
Depends on: bliss or nauty
•
n_automorphisms (graph) → Int

Find the order of the automorphism group of the graph.

##### Parameters
 props::Graph graph
##### Returns
 Int the order of the automorphism group

Example:
• `> print n_automorphisms(cycle_graph(5)->ADJACENCY);`` 2`
Depends on: bliss or nauty
•

### Other

Special purpose functions.

•
edge_lengths (G, coords) → EdgeMap

Compute the lengths of all edges of a given graph G from the coordinates coords of its nodes.

##### Parameters
 props::Graph G the input graph Matrix coords the coordinates of the nodes
##### Returns
 EdgeMap
•
graph_from_edges (edges) → Graph

Creates a graph from a given list of edges.

##### Parameters
 Array> edges
##### Returns
 Graph

Example:
• `> \$g = graph_from_edges([[1,2],[1,3],[1,4]]);``> print \$g->ADJACENCY;`` {}`` {2 3 4}`` {1}`` {1}`` {1}`
•
hungarian_perfect_matching (weights) → Array

Vector representation of the permutation corresponding to a perfect matching in a weighted bipartite graph.

##### Parameters
 Matrix weights
##### Returns
 Array

Example:
• The following computes a matching in a small bipartite weighted graph:`> \$M = new Matrix(['inf',2,'inf',1],[2,'inf',1,'inf'],['inf',1,'inf',8],[1,'inf',8,'inf']);``> print hungarian_perfect_matching(\$M);`` 3 2 1 0`
•

### Producing a graph

With these clients you can create special examples of graphs, graphs belonging to parameterized families and random graphs.

•
complete (n) → Graph

Constructs a complete graph on n nodes.

##### Parameters
 Int n
##### Returns
 Graph
•
complete_bipartite (k, l) → Graph

Constructs a complete bipartite graph on k + l nodes.

##### Parameters
 Int k Int l
##### Returns
 Graph
•
cycle_graph (n) → Graph

Constructs a cycle graph on n nodes.

##### Parameters
 Int n
##### Returns
 Graph

Example:
• To print the adjacency representation of the cycle graph on four nodes, type this:`> \$g = cycle_graph(4);``> print \$g->ADJACENCY;`` {1 3}`` {0 2}`` {1 3}`` {0 2}`
•
generalized_johnson_graph (n, k, i) → Graph

Create the generalized Johnson graph on parameters (n,k,i). It has one node for each set in \({[n]}\choose{k}\), and an edge between two nodes iff the intersection of the corresponding subsets is of size i.

##### Parameters
 Int n the size of the ground set Int k the size of the subsets Int i the size of the subsets
##### Returns
 Graph
•
johnson_graph (n, k) → Graph

Create the Johnson graph on parameters (n,k). It has one node for each set in \({[n]}\choose{k}\), and an edge between two nodes iff the intersection of the corresponding subsets is of size k-1.

##### Parameters
 Int n the size of the ground set Int k the size of the subsets
##### Returns
 Graph
•
kneser_graph (n, k) → Graph

Create the Kneser graph on parameters (n,k). It has one node for each set in \({[n]}\choose{k}\), and an edge between two nodes iff the corresponding subsets are disjoint.

##### Parameters
 Int n the size of the ground set Int k the size of the subsets
##### Returns
 Graph
•
path_graph (n) → Graph

Constructs a path graph on n nodes.

##### Parameters
 Int n
##### Returns
 Graph
•
petersen () → Graph

Constructs the Petersen graph.

##### Returns
 Graph
•
random_graph (n) → Graph

Constructs a random graph with n nodes according to the Erdos-Renyi model. Each edge is chosen uniformly with probability p.

##### Parameters
 Int n
##### Options
 Rational p the probability of an edge occurring; default 1/2 Bool try_connected whether to try to generate a connected graph, default 1 Int max_attempts If connected is set, specifies how many times to try to make a connected random graph before giving up. Int seed controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
##### Returns
 Graph
•

### Visualization

These functions are for visualization.

•
clip_graph (G, V, BB) → GeometricGraph

Clip a graph with respect to a given bounding box. Used for the visualization of Voronoi diagrams.

##### Parameters
 Graph G Matrix V Matrix BB
##### Returns
 GeometricGraph
•
hd_embedder (label_width)

Create an embedding of the Hasse diagram as a layered graph. The embedding algorithm tries to minimize the weighted sum of squares of edge lengths, starting from a random distribution. The weights are relative to the fatness of the layers. The y-space between the layers is constant.

##### Parameters
 Array label_width estimates (better upper bounds) of the label width of each node. The computed layout guarantees that the distances between the nodes in a layer are at least equal to the widest label in this layer.
##### Options
 Bool dual the node representing the empty face is put on the topmost level Float eps calculation accuracy. Int seed effects the initial placement of the nodes.
•
LEDA_graph (G)

Write a graph in LEDA input format.

##### Parameters
 props::Graph G
•
metapost (vis_obj ...)

Produce a MetaPost input file with given visual objects.

##### Parameters
 Visual::Object vis_obj ... objects to display
##### Options
 String File "filename" or "AUTO" The MetaPost description always has to be stored in a file, there is no interactive viewer for this kind of visualization. For the file name you can use any expression allowed for the `open` function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe. Real file names are automatically completed with the `.mp` suffix if needed. The default setting "AUTO" lets the file name be derived from the drawing title. The automatically generated file name is displayed in the verbose mode.
•
spring_embedder (graph)

Produce a 3-d embedding for the graph using the spring embedding algorithm along the lines of

Thomas Fruchtermann and Edward Reingold:
Graph Drawing by Force-directed Placement.
Software Practice and Experience Vol. 21, 1129-1164 (1992), no. 11.
##### Parameters
 props::Graph graph to be embedded.
##### Options
affecting the desired picture
 EdgeMap edge_weights relative edge lengths. By default the embedding algorithm tries to stretch all edges to the same length. Vector z-ordering an objective function provides an additional force along the z-axis, trying to rearrange nodes in the order of the function growth. Float z-factor gain coefficient applied to the z-ordering force. Int seed random seed for initial node placement on a unit sphere.
calculation fine-tuning
 Float scale enlarges the ideal edge length Float balance changes the balance between the edge contraction and node repulsion forces Float inertion affects how the nodes are moved, can be used to restrain oscillations Float viscosity idem Float eps a threshold for point movement between iterations, below that it is considered to stand still Int max-iterations hard limit for computational efforts. The algorithm terminates at latest after that many iterations regardless of the convergence achieved so far.

## Common Option Lists

•

### Visualization

These options are for visualization.

•
Visual::Graph::decorations

Attributes modifying the appearance of graphs

imports from: Visual::Wire::decorations, Visual::PointSet::decorations

##### Options
 Matrix Coord 2-d or 3-d coordinates of the nodes. If not specified, a random embedding is generated using a pseudo-physical spring model Flexible NodeColor alias for PointColor Flexible NodeThickness alias for PointThickness Flexible NodeBorderColor alias for PointBorderColor Flexible NodeBorderThickness alias for PointBorderThickness Flexible NodeStyle alias for PointStyle String NodeLabels alias for PointLabels
•
Visual::Lattice::decorations

Attributes modifying the appearance of face lattices

imports from: Visual::Graph::decorations, Visual::Wire::decorations, Visual::PointSet::decorations

##### Options
 Flexible ArrowStyle How to draw directed edges: 0 (like undirected), 1 (with an arrow pointing towards the edge), or -1 (with an arrow pointing against the edge). Default is 1. Array AtomLabels Labels of atoms, to use as building blocks for node labels. By default the ordinal numbers are taken.