# application: graph

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

imports from: common

## User Functions

•

### Calculating data

UNDOCUMENTED
•
degree_sequence (G)

Calculate the degree sequence and the average degree. The degree sequence is encoded as a map with entries (degree, multiplicity)

##### Parameters
 Graph G
•

### Combinatorics

UNDOCUMENTED
•
incidence_matrix () → SparseMatrix<Int>

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

##### Returns
 SparseMatrix
•
laplacian (G) → Matrix

creates the Laplacian matrix of a graph

##### Parameters
 Graph G
##### Returns
 Matrix
•
line_graph (G) → Graph

creates the line graph of a graph

##### Parameters
 Graph G
##### Returns
 Graph
•
signed_incidence_matrix () → 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.

##### Returns
 SparseMatrix
•

### Comparing

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

Find the automorphism group of the graph.

##### Parameters
 props::Graph graph
##### Returns
 Array> each element encodes a node permutation.
•
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).
•
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`).
•
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
•
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.
•
isomorphic (IncidenceMatrix1, IncidenceMatrix2) → Bool

true if IncidenceMatrix1 and IncidenceMatrix2 are isomorphic.

##### Parameters
 IncidenceMatrix IncidenceMatrix1 IncidenceMatrix IncidenceMatrix2
##### Returns
 Bool
•
isomorphic (graph1, graph2) → Bool

true if graph1 and graph2 are isomorphic.

##### Parameters
 props::Graph graph1 props::Graph graph2
##### Returns
 Bool
•
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
•

### Creating from scratch

UNDOCUMENTED
•
kneser_graph (n, k)

Create the Kneser graph on parameters (n,k) It has one node for each set in binomial{[n]}{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
•

### Other

UNDOCUMENTED
•
connectivity (graph) → Int

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

##### Parameters
 props::Graph graph
##### Returns
 Int
•
edge_lengths (G, coords) → EdgeMap

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

##### Parameters
 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
•

### Producing from scratch

UNDOCUMENTED
•
complete (n) → Graph

Constructs a complete graph with n nodes.

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

Constructs a complete bipartite graph with k + l nodes.

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

Constructs a cycle graph with n nodes.

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

Constructs a path graph with 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
•

### Producing perfect matching for weight matrix

UNDOCUMENTED
•
hungarian_perfect_matching (weights) → Array

vector representation of permutation corresponding to perfect matching in bipartite weighted graph.

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

### Visualization

UNDOCUMENTED
•
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
•
graphviz (vis_obj ...)

Draw the given graph or face lattice object using graphviz program `neato` or `dot` respectively. The output is rendered in PostScript format and fed into a viewer program, if one is configured. If you prefer to produce another output format, please use the File option and call the `neato` or `dot` program manually.

##### Parameters
 Visual::Object vis_obj ... objects to display
##### Options
 String File "filename" or "AUTO" Store the graph description in a DOT source file without starting the interactive GUI. The `.dot` suffix is automatically added to the file name. Specify AUTO if you want the filename be automatically derived from the drawing title. You can also use any expression allowed for the `open` function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe.
•
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 ()

Write a graph in LEDA input format.

•
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

UNDOCUMENTED
•
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.