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 vertexedge graph of a polytope.
Objects


Lattice represented as a directed acyclic graph.
Properties of FaceLattice

DIMS: common::Array<Int>
Indices of the first nodes in each level. Intended for internal use only; please use nodes_of_dim instead.

FACES: common::NodeMap<Directed, Set<Int>>
Each node of the FaceLattice corresponds to a face. The node attribute is a set of vertices comprising the face. Incident edges lead to the containing faces of the next (higher) dimension.
User Methods of FaceLattice

bottom_node () → Int

nodes_of_dim (dim) → Set<Int>

VISUAL () → Visual::Lattice
Visualize the FaceLattice.
Options
Int seed random seed value for the node placementoption list: Visual::Lattice::decorations Returns
Visual::Lattice 
VISUAL_DUAL () → Visual::Lattice
Visualize the dual FaceLattice.
Options
Int seed random seed value for the node placementoption list: Visual::Lattice::decorations Returns
Visual::Lattice


An undirected graph with given node coordinates and a bounding box.
Properties of GeometricGraph

BOUNDING_BOX: common::Matrix
Since a Voronoi polyhedron is unbounded it must be artificially bounded for visualization purposes. Allowed is any set of hyperplanes which makes the projection onto the last d1 coordinates bounded. By default, these are the vertical facets of a suitably scaled cube.



A graph with optional node and edge attributes.
Specializations of Graph
Properties of Graph



CHARACTERISTIC_POLYNOMIAL: common::UniPolynomial<Rational, Int>
Characteristic polynomial of the adjacency matrix; its roots are the eigenvalues



CONNECTIVITY: common::Int
Only defined for Graph<Undirected>Node connectivity of the graph, that is, the minimal number of nodes to be removed from the graph such that the result is disconnected.

DEGREE_SEQUENCE: common::Map<Int, Int>
Only defined for Graph<Undirected>How many times a node of a given degree occurs


MAX_CLIQUES: common::PowerSet<Int>
Only defined for Graph<Undirected>The maximal cliques of the graph, encoded as node sets.


NODE_IN_DEGREES: common::Array<Int>
Only defined for Graph<Directed>The number of incoming edges of the graph nodes.


NODE_OUT_DEGREES: common::Array<Int>
Only defined for Graph<Directed>The number of outgoing edges of the graph nodes.




SIGNATURE: common::Int
Only defined for Graph<Undirected>Difference of the black and white nodes if the graph is BIPARTITE. Otherwise 1.

SIGNED_INCIDENCE_MATRIX: common::SparseMatrix<Int, NonSymmetric>
Signed vertexedge incidence matrix; for undirected graphs, the orientation comes from the lexicographic order of the nodes.

TRIANGLE_FREE: common::Bool
Only defined for Graph<Undirected>Determine whether the graph has triangles or not.
User Methods of Graph

EDGES () → Array<Set<Int>>

VISUAL () → Visual::Graph
Visualizes the graph. Decorations may include
Coord
, disabling the default spring embedder.Options
Int seed random seed value for the spring embedderoption list: Visual::Graph::decorations Returns
Visual::Graph
Permutations of Graph

NodePerm
UNDOCUMENTED
Properties of NodePerm


Category: Visualizationderived from: Visual::Object
Collection of nodes and edges of an abstract graph amended with visual decoration attributes and an optional embedding in 3d.

Category: Visualizationderived from: Visual::Graph
Collection of nodes (representing faces of a face lattice) and edges (representing the inclusion relation) amended with visual decoration attributes and an optional embedding in 2d.
User Functions

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

connectivity (graph) → Int
Compute the CONNECTIVITY of a given graph using the FordFulkerson flow algorithm.
Example: Compute the connectivity of the vertexedge 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 vertexedge incidence matrix of the graph.
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

line_graph (G) → Graph

signed_incidence_matrix (G) → SparseMatrix<Int>
Compute the signed vertexedge incidence matrix of the graph. in case of undirected graphs, the orientation of the edges is induced by the order of the nodes.
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


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.
Example: We first create the vertexedge 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 vertexedge connectivity.
Depends on: bliss or nauty 
automorphisms (m) → Array<Pair<Array<Int>,Array<Int>>>
Find the automorphism group of the nonsymmetric incidence matrix.
Parameters
IncidenceMatrix<NonSymmetric> m Returns
Array<Pair<Array<Int>,Array<Int>>> each element encodes a permutation of its rows (first
) and columns (second
).Example: The group of combinatorial automorphisms of the 3cube 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<Symmetric> m Returns
Array<Array<Int>> 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.
Depends on: bliss or nauty 
find_row_col_permutation (m1, m2) → Pair<Array<Int>,Array<Int>>
Find the permutations mapping the nonsymmetric incidence matrix m1 to m2. If the given matrices are not isomorphic, throw an expection.
Parameters
IncidenceMatrix<NonSymmetric> m1 IncidenceMatrix<NonSymmetric> m2 Returns
Pair<Array<Int>,Array<Int>> first
permutation applies to the rows,second
applies to the columnsExample:> $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.
Example: Compare the incidence matrices of the 2dimensional 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.
Example: Compare the vertexedge 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.
Example:> print n_automorphisms(cycle_graph(5)>ADJACENCY);
2
Depends on: bliss or nauty


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<Directed> G the input graphMatrix coords the coordinates of the nodesReturns
EdgeMap 
graph_from_edges (edges) → Graph
Creates a graph from a given list of edges.
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.
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


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

complete_bipartite (k, l) → Graph

cycle_graph (n) → Graph

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.

johnson_graph (n, k) → Graph

kneser_graph (n, k) → Graph

path_graph (n) → Graph

random_graph (n) → Graph
Constructs a random graph with n nodes according to the ErdosRenyi model. Each edge is chosen uniformly with probability p.
Parameters
Int n Options
Rational p the probability of an edge occurring; default 1/2Bool try_connected whether to try to generate a connected graph, default 1Int 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

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.

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 yspace 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 levelFloat eps calculation accuracy.Int seed effects the initial placement of the nodes. 
LEDA_graph (G)

metapost (vis_obj ...)
Produce a MetaPost input file with given visual objects.
Parameters
Visual::Object vis_obj ... objects to displayOptions
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 theopen
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 3d embedding for the graph using the spring embedding algorithm along the lines of
Thomas Fruchtermann and Edward Reingold:Graph Drawing by Forcedirected Placement.Software Practice and Experience Vol. 21, 11291164 (1992), no. 11.Parameters
props::Graph<Undirected> graph to be embedded.Options
affecting the desired pictureEdgeMap edge_weights relative edge lengths. By default the embedding algorithm tries to stretch all edges to the same length.Vector zordering an objective function provides an additional force along the zaxis, trying to rearrange nodes in the order of the function growth.Float zfactor gain coefficient applied to the zordering force.Int seed random seed for initial node placement on a unit sphere.calculation finetuningFloat scale enlarges the ideal edge lengthFloat balance changes the balance between the edge contraction and node repulsion forcesFloat inertion affects how the nodes are moved, can be used to restrain oscillationsFloat viscosity idemFloat eps a threshold for point movement between iterations, below that it is considered to stand stillInt maxiterations hard limit for computational efforts. The algorithm terminates at latest after that many iterations regardless of the convergence achieved so far.

Common Option Lists

These options are for visualization.

Visual::Graph::decorationsimports from: Visual::Wire::decorations, Visual::PointSet::decorations
Attributes modifying the appearance of graphs
Options
Matrix<Float> Coord 2d or 3d coordinates of the nodes. If not specified, a random embedding is generated using a pseudophysical spring modelFlexible<RGB> NodeColor alias for PointColorFlexible<Float> NodeThickness alias for PointThicknessFlexible<RGB> NodeBorderColor alias for PointBorderColorFlexible<Float> NodeBorderThickness alias for PointBorderThicknessFlexible<String> NodeStyle alias for PointStyleString NodeLabels alias for PointLabels 
Visual::Lattice::decorationsimports from: Visual::Graph::decorations, Visual::Wire::decorations, Visual::PointSet::decorations
Attributes modifying the appearance of face lattices
Options
Flexible<Int> 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<String> AtomLabels Labels of atoms, to use as building blocks for node labels. By default the ordinal numbers are taken.
