Available versions of this document: latest release, release 4.13, release 4.12, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, release 3.5, nightly master
Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2
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:
- application common
Objects
GeometricGraph
:
An undirected graph with given node coordinates and a bounding box.Graph
:
A graph with optional node and edge attributes.Lattice
:
A Lattice is a poset where join and meet exist for any two elements. It is realized as a directed graph.Visual::Graph
:
Collection of nodes and edges of an abstract graph amended with visual decoration attributes and an optional embedding in 3-d.Visual::Lattice
:
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 2-d.
Functions
Combinatorics
Combinatorial functions.
-
all_spanningtrees(Graph G)
Calculate all spanning trees for a connected graph along the lines of
> Donald E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 4, 24-31, 2006, Pearson Education Inc.
.. Every spanning tree is represented as a set of indices of the edges used. The result is a pair of an array of the spanning trees and an array translating the indices used into actual edges, i.e. the i-th entry of the dictionary is a pair of integers representing the end nodes of the i-th edge. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'': being connected ? Returns: :''[[.:common#Pair |Pair]]<[[.:common#Array |Array]]<[[.:common#Set |Set]]<[[.:common#Int |Int]]%%>>%%,[[.:common#Array |Array]]<[[.:common#Pair |Pair]]<[[.:common#Int |Int]],[[.:common#Int |Int]]%%>>%%>'' ? Example: :: The following prints all spanning trees of the complete graph with 3 nodes, whereby each line represents a single spanning tree as an edge set: :: <code perl> > print all_spanningtrees(complete(3)->ADJACENCY);
<{0 1} {1 2} {0 2} > (1 0) (2 0) (2 1) </code>
-
complement_graph(Graph G)
Creates the complement graph of a graph.
-
connectivity(GraphAdjacency<Undirected> graph)
Compute the
CONNECTIVITY
of a given graph using the Ford-Fulkerson flow algorithm.- Parameters:
GraphAdjacency<Undirected>
graph
- Returns:
- 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 graph not to be connected anymore.
-
eigenvalues_laplacian(Graph G)
Compute the eigenvalues of the discrete Laplacian of a graph.
-
eigenvalues_laplacian(Graph G)
Compute the eigenvalues of the discrete Laplacian of a graph.
-
find_lattice_permutation(Lattice L1, Lattice L2, Permutation permutation)
This takes two lattices and checks whether they are isomorphic, possibly after applying a permutation to the faces. This function only compares faces and ranks of nodes to determine isomorphism
-
graph_homomorphisms(Graph G, Graph H)
Enumerate all homomorphisms (edge-preserving maps) from one graph to another
-
incidence_matrix(Graph G)
Compute the unsigned vertex-edge incidence matrix of the graph.
-
incidence_matrix(GraphAdjacency G)
Compute the unsigned vertex-edge incidence matrix of the graph.
- Parameters:
- Returns:
- Example:
> $I = incidence_matrix(cycle_graph(4)->ADJACENCY); > print $I; 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1
-
laplacian(Graph G)
Compute the Laplacian matrix of a graph.
-
laplacian(Graph G)
Compute the Laplacian matrix of a graph.
-
lattice_of_chains(Lattice<Decoration> lattice)
For a given lattice, this computes the lattice of chains from bottom to top node. The result always includes an artificial top node.
-
line_graph(Graph G)
Creates the line graph of a graph.
-
maximal_chains_of_lattice(Lattice F)
Computes the set of maximal chains of a Lattice object.
- Parameters:
Lattice
F
- Options:
Bool
ignore_bottom_node
: If true, the bottom node is not included in the chains. False by defaultBool
ignore_top_node
: If true, the top node is not included in the chains. False by default- Returns:
- Example:
The following prints all maximal chains of the face lattice of the 1-simplex (an edge):
> print maximal_chains_of_lattice(simplex(1)->HASSE_DIAGRAM); {0 1 3} {0 2 3}
-
n_graph_homomorphisms(Graph G, Graph H)
Count all homomorphisms (edge-preserving maps) from one graph to another. They are in fact enumerated, but only the count is kept track of using constant memory.
-
random_spanningtree(Graph G)
Return a random spanning tree of a graph
- Parameters:
Graph
G
: being connected- Returns:
-
signed_incidence_matrix(Graph G)
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.
-
signed_incidence_matrix(GraphAdjacency G)
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:
- Returns:
- Example:
> $I = signed_incidence_matrix(cycle_graph(4)->ADJACENCY); > print $I; 1 0 1 0 -1 1 0 0 0 -1 0 1 0 0 -1 -1
Comparing
Functions dealing with automorphisms of graphs and determining whether graphs are isomorphic.
-
automorphisms(GraphAdjacency graph)
Find the automorphism group of the graph.
- Parameters:
GraphAdjacency
graph
- Returns:
- depends on extension:
- Example:
We first create the vertex-edge graph of the square and then print its automorphism group:
> $g=new GraphAdjacency(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.
-
automorphisms(IncidenceMatrix<NonSymmetric> m)
Find the automorphism group of the non-symmetric incidence matrix.
- Parameters:
- Returns:
- depends on extension:
- 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.
-
automorphisms(IncidenceMatrix<Symmetric> m)
Find the automorphism group of the symmetric incidence matrix.
- Parameters:
- Returns:
- depends on extension:
-
canonical_form(GraphAdjacency g)
Find a canonical representation of a graph g. Warning: This representation can depend on the extension (bliss/nauty) used, its version and configuration, as well as the hardware!
- Parameters:
- Returns:
- depends on extension:
-
canonical_hash(GraphAdjacency g, Int k)
Compute a hash for a graph g independent of the node ordering. Warning: This hash can depend on the extension (bliss/nauty) used, its version and configuration, as well as the hardware! Nauty requires an integer key k as input, bliss will ignore the key.
- Parameters:
Int
k
: a key for the hash computation, default value 2922320- Returns:
- depends on extension:
-
canonical_hash(IncidenceMatrix M, Int k)
Compute a hash for an incidence matrix I independent of the row ordering. Warning: This hash can depend on the extension (bliss/nauty) used, its version and configuration, as well as the hardware! Nauty requires an integer key k as input, bliss will ignore the key.
- Parameters:
Int
k
: a key for the hash computation, default value 2922320- Returns:
- depends on extension:
-
find_node_permutation(GraphAdjacency graph1, GraphAdjacency graph2)
Find the node permutation mapping graph1 to graph2.
- Parameters:
GraphAdjacency
graph1
GraphAdjacency
graph2
- Returns:
- depends on extension:
-
find_row_col_permutation(IncidenceMatrix<NonSymmetric> m1, IncidenceMatrix<NonSymmetric> m2)
Find the permutations mapping the non-symmetric incidence matrix m1 to m2.
- Parameters:
- Returns:
- depends on extension:
- 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>
-
isomorphic(IncidenceMatrix IncidenceMatrix1, IncidenceMatrix IncidenceMatrix2)
true if IncidenceMatrix1 and IncidenceMatrix2 are isomorphic.
- Parameters:
IncidenceMatrix
IncidenceMatrix1
IncidenceMatrix
IncidenceMatrix2
- Returns:
- depends on extension:
- 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); true
-
isomorphic(GraphAdjacency graph1, GraphAdjacency graph2)
true if graph1 and graph2 are isomorphic.
- Parameters:
GraphAdjacency
graph1
GraphAdjacency
graph2
- Returns:
- depends on extension:
- 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); true
-
n_automorphisms(GraphAdjacency graph)
Find the order of the automorphism group of the graph.
- Parameters:
GraphAdjacency
graph
- Returns:
- depends on extension:
- Example:
> print n_automorphisms(cycle_graph(5)->ADJACENCY); 2
Posets
Functions dealing with posets represented as directed graphs
-
covering_relations(Graph<Directed> P)
Construct the covering relations of a poset
- Parameters:
- Returns:
-
hom_poset(Graph<Directed> P, Graph<Directed> Q)
Construct the poset of order preserving maps from one poset to another
- Parameters:
- Returns:
-
hom_poset(Array<Array<Int>> homs, Graph<Directed> Q)
Construct the poset of order preserving maps from one poset to another
- Parameters:
- Returns:
-
n_poset_homomorphisms(Graph<Directed> P, Graph<Directed> Q)
Count all order preserving maps from one poset to another. They are in fact enumerated, but only the count is kept track of using constant memory.
- Parameters:
- Options:
- Returns:
-
poset_by_inclusion(Array<T> P)
Construct the inclusion poset from a given container. The elements of the container are interpreted as sets. They define a poset by inclusion. The function returns this poset encoded as a directed graph. The direction is towards to larger sets. All relations are encoded, not only the covering relations. For details see Assarf, Joswig & Pfeifle: Webs of stars or how to triangulate sums of polytopes, to appear
- Parameters:
Array<T>
P
- Returns:
-
poset_homomorphisms(Graph<Directed> P, Graph<Directed> Q)
Enumerate all order preserving maps from one poset to another
- Parameters:
- Options:
- Returns:
Producing a graph
With these functions you can create special examples of graphs, graphs belonging to parameterized families and random graphs.
-
complete(Int n)
Constructs a complete graph on n nodes.
-
cycle_graph(Int n)
Constructs a cycle graph on n nodes.
-
generalized_johnson_graph(Int n, Int k, Int i)
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 setInt
k
: the size of the subsetsInt
i
: the size of the subsets- Returns:
- Example:
The following prints the adjacency representation of the generalized johnson graph with the parameters 4,2,1:
> print generalized_johnson_graph(4,2,1)->ADJACENCY; {1 2 3 4} {0 2 3 5} {0 1 4 5} {0 1 4 5} {0 2 3 5} {1 2 3 4}
-
johnson_graph(Int n, Int k)
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.
-
kneser_graph(Int n, Int k)
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.
-
neighborhood_graph(Matrix<Rational> D, Rational delta)
Constructs the neighborhood graph of a point set S given a parameter delta. The set is passed as its so-called “distance matrix”, whose (i,j)-entry is the distance between point i and j. This matrix can e.g. be computed using the distance_matrix function. Two vertices will be adjacent if the distance of the corresponding points is less than delta.
- Parameters:
Rational
delta
: the maximal distance of neighbored vertices- Returns:
- Example:
The following prints the neighborhood graph of a distance matrix with a limit of 3.3, producing the graph of a square:
> $D = new Matrix<Rational>([[0,17/10,21/10,42/10],[0,0,79/10,31/10],[0,0,0,6/10],[0,0,0,0]]); > print neighborhood_graph($D,3.3)->ADJACENCY; {1 2} {0 3} {0 3} {1 2}
-
petersen()
Constructs the Petersen graph.
- Returns:
- Example:
The following prints the adjacency matrix of the petersen graph:
> print petersen()->N_NODES; 10
-
random_graph(Int n)
Constructs a random graph with n nodes according to the Erdős-Renyi model. The default is the G(n, p) model: Each edge is chosen uniformly with probability p. Optionally one can switch to the G(n, M) model to get a random graph on n nodes with exactly M edges. See P. Erdős and A. Rényi. On random graphs. Publ. Math. 6, 290–297 (1959; Zbl 0092.15705)
- Parameters:
Int
n
- Options:
Rational
p
: the probability of an edge occurring; default 1/2Int
M
: the number of edges in the graphBool
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:
- Example:
The following produces a connected graph on 10 nodes using a specific seed for a random graph model, where an edge between two nodes occurs with probabilty 0.1.
> $g = random_graph(10,p=>0.1,try_connected=>1,max_attempts=>50,seed=>100000); > print $g->N_EDGES; 9
-
wheel_graph(Int n)
Constructs a wheel graph with n spokes.
Visualization
These functions are for visualization.
-
LEDA_graph(GraphAdjacency G)
Write a graph in LEDA input format.
- Parameters:
-
clip_graph(Graph G, Matrix V, Matrix BB)
Clip a graph with respect to a given bounding box. Used for the visualization of Voronoi diagrams.
-
graphviz(Visual::Object vis_obj …)
Draw the given graph or face lattice object using graphviz program
neato
ordot
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 theneato
ordot
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 theopen
function, including “-” for terminal output, “&HANDLE” for an already opened file handle, or “| program” for a pipe.- Example:
The following creates a star graph with 4 nodes and visualizes it via graphviz with default options:
> $g = new Graph<Undirected>(ADJACENCY=>[[],[0],[0],[0]]); > graphviz($g->VISUAL);
The following shows some modified visualization style of the same graph:
> $g = new Graph<Undirected>(ADJACENCY=>[[],[0],[0],[0]]); > graphviz($g->VISUAL(NodeColor=>"green",EdgeColor=>"purple",EdgeThickness=>5));
-
hd_embedder(Array label_width)
Create an embedding of the Lattice 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 levelFloat
eps
: calculation accuracy.Int
seed
: effects the initial placement of the nodes.
-
metapost(Visual::Object 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 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.- Example:
The following prints a metapost description of the complete graph with 3 nodes in the console:
> metapost(complete(3)->VISUAL,File=>"-");
-
spring_embedder(GraphAdjacency<Undirected> 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: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]<[[.:common#Undirected |Undirected]]>'' ''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 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
max-iterations
: hard limit for computational efforts. The algorithm terminates at latest after that many iterations regardless of the convergence achieved so far.- Example:
The following prints a 3-dimensional embedding of the complete graph on 3 nodes using a specific seed and scaled edge lengths:
> print spring_embedder(complete(3)->ADJACENCY, scale=>5, seed=>123); 0.9512273649 -10.00210559 10.36309695 10.61947526 1.391783824 -9.666627553 -11.57070263 8.610321763 -0.6964693941
Other
Special purpose functions.
-
edge_lengths(GraphAdjacency<Directed> G, Matrix coords)
Compute the lengths of all edges of a given graph G from the coordinates coords of its nodes.
- Parameters:
GraphAdjacency<Directed>
G
: the input graphMatrix
coords
: the coordinates of the nodes- Returns:
- Example:
The following prints the edge length of the complete graph with 3 nodes and edge lengths given by the coordiantes of the standard 2-simplex:
> print edge_lengths(complete(3)->ADJACENCY,simplex(2)->VERTICES); 1 1 1.414213562
-
graph_from_edges(Array<Set<Int>> edges)
Creates a graph from a given list of edges.
- Parameters:
- Returns:
- Example:
> $g = graph_from_edges([[1,2],[1,3],[1,4]]); > print $g->ADJACENCY; {} {2 3 4} {1} {1} {1}
no category
-
graph_from_cycles
UNDOCUMENTED
-
shortest_path_dijkstra(Graph G, EdgeMap weights, Int source, Int target, Bool if)
Find the shortest path in a graph
Small Object Types
Artificial
These types are auxiliary artifacts helping to build other classes, primarily representing template parameters or enumeration constants. They should not be used alone as property types or function arguments. In the most cases they won't even have user-accessible constructors.
-
Nonsequential
Designates a non-sequential lattice, that is, having nodes in arbitrary order. This flavor should only be used if an algorithm creating the lattice can't guarantee node ordering by rank.
-
Sequential
Designates a sequential lattice, that is, having all nodes sorted by rank. This is a preferred flavor, because it allows more compact and efficient persistent storage.
Combinatorics
These property_types capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.
-
BasicDecoration
Minimal required data associated with
Lattice
nodes.- Methods of BasicDecoration:
-
face()
face represented by the node
- Returns:
-
rank()
node rank
- Returns:
-
-
InverseRankMap<SeqType>
Mapping of lattice nodes to their ranks.
- Type Parameters:
SeqType
: tag describing node order, must beSequential
orNonsequential
.- Methods of InverseRankMap: