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:
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.
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.
GraphAdjacency<Undirected> graph
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.
> $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.
Lattice F
Bool ignore_bottom_node: If true, the bottom node is not included in the chains. False by default
Bool ignore_top_node: If true, the top node is not included in the chains. False by default
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
Graph G: being connected
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.
> $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
Functions dealing with automorphisms of graphs and determining whether graphs are isomorphic.
automorphisms(GraphAdjacency graph)Find the automorphism group of the graph.
GraphAdjacency graph
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.
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.
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!
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.
Int k: a key for the hash computation, default value 2922320
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.
Int k: a key for the hash computation, default value 2922320
find_node_permutation(GraphAdjacency graph1, GraphAdjacency graph2)Find the node permutation mapping graph1 to graph2.
GraphAdjacency graph1
GraphAdjacency graph2
find_row_col_permutation(IncidenceMatrix<NonSymmetric> m1, IncidenceMatrix<NonSymmetric> m2)Find the permutations mapping the non-symmetric incidence matrix m1 to m2.
> $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.
IncidenceMatrix IncidenceMatrix1
IncidenceMatrix IncidenceMatrix2
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.
GraphAdjacency graph1
GraphAdjacency graph2
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.
GraphAdjacency graph
> print n_automorphisms(cycle_graph(5)->ADJACENCY); 2
Functions dealing with posets represented as directed graphs
covering_relations(Graph<Directed> P)Construct the covering relations of a poset
hom_poset(Graph<Directed> P, Graph<Directed> Q)Construct the poset of order preserving maps from one poset to another
hom_poset(Array<Array<Int>> homs, Graph<Directed> Q)Construct the poset of order preserving maps from one poset to another
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.
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
Array<T> P
poset_homomorphisms(Graph<Directed> P, Graph<Directed> Q)Enumerate all order preserving maps from one poset to another
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.
Int n: the size of the ground set
Int k: the size of the subsets
Int i: the size of the subsets
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.
Rational delta: the maximal distance of neighbored vertices
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.
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)
Int n
Rational p: the probability of an edge occurring; default 1/2
Int M: the number of edges in the graph
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.
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.
These functions are for visualization.
LEDA_graph(GraphAdjacency G)Write a graph in LEDA input format.
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 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.
Visual::Object vis_obj …: objects to display
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.
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.
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.
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.
metapost(Visual::Object vis_obj …)Produce a MetaPost input file with given visual objects.
Visual::Object vis_obj …: objects to display
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.
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.
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.
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
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.
GraphAdjacency<Directed> G: the input graph
Matrix coords: the coordinates of the nodes
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.
> $g = graph_from_edges([[1,2],[1,3],[1,4]]); > print $g->ADJACENCY; {} {2 3 4} {1} {1} {1}
graph_from_cyclesUNDOCUMENTED
shortest_path_dijkstra(Graph G, EdgeMap weights, Int source, Int target, Bool if)Find the shortest path in a graph
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.
NonsequentialDesignates 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.
SequentialDesignates 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.
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.
face()face represented by the node
rank()node rank
InverseRankMap<SeqType>Mapping of lattice nodes to their ranks.
SeqType: tag describing node order, must be Sequential or Nonsequential.