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

• GeometricGraph:
  An undirected graph with given node coordinates and a bounding box.

• Graph:
  A graph with optional node and edge attributes.

• PartiallyOrderedSet:
  A PartiallyOrderedSet is a poset where join and meet exist for any two elements. It is realized as a directed graph. Some implementations currently restricted to ranked posets (will be fixed soon™).

• PhylogeneticTree:
  Contains a rooted phylogenetic tree (see Definition 2.2.1 from [C. Semple, M. Steel: Phylogenetics]) with edge lengths. Every edge must have a positive length. They can be defined in terms of the distance matrix and the taxa only if the distance is ultrametric; see Section 7.2 from [C. Semple, M. Steel: Phylogenetics]. The root has always index 0.

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

Parameters:

Graph G

Returns:

Graph

Example:

The following prints the adjancency matrix of the complement graph of the star graph with 4 nodes:

 > $g = new Graph<Undirected>(ADJACENCY=>[[],[0],[0],[0]]);
 > print complement_graph($g)->ADJACENCY;
 {}
 {2 3}
 {1 3}
 {1 2}

connectivity(GraphAdjacency<Undirected> graph)

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

Parameters:

GraphAdjacency<Undirected> 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 graph not to be connected anymore.

eigenvalues_laplacian(Graph G)

Compute the eigenvalues of the discrete Laplacian of a graph.

Parameters:

Graph G

Returns:

Vector<Float>

Example:

 > $v = eigenvalues_laplacian(cycle_graph(4));
 > print $v;
 4 2 2 0

eigenvalues_laplacian(Graph G)

Compute the eigenvalues of the discrete Laplacian of a graph.

Parameters:

Graph G

Returns:

Vector<Float>

Example:

 > $v = eigenvalues_laplacian(cycle_graph(4)->ADJACENCY);
 > print $v;
 4 2 2 0

find_lattice_permutation(PartiallyOrderedSet L1, PartiallyOrderedSet 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

Parameters:

PartiallyOrderedSet L1: A lattice

PartiallyOrderedSet L2: Another lattice, having the same decoration and sequential type

Permutation permutation: A permutation to be applied to the faces. If empty, the identity permutation is chosen

Returns:

Permutation

graph_homomorphisms(Graph G, Graph H)

Enumerate all homomorphisms (edge-preserving maps) from one graph to another

Parameters:

Graph G

Graph H

Options:

Bool allow_loops: Should edges of G be allowed to collapse to a loop when mapped to H? Default 0

Array<Int> prescribed_map: A vector of length G.nodes() with those images in G that should be fixed. Negative entries will be enumerated over.

Returns:

Array<Array<Int>>

incidence_matrix(Graph G)

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

Parameters:

Graph G

Returns:

SparseMatrix<Int>

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

incidence_matrix(GraphAdjacency G)

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

Parameters:

GraphAdjacency G

Returns:

SparseMatrix<Int>

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.

Parameters:

Graph G

Returns:

SparseMatrix<Rational>

Example:

 > $I = laplacian(cycle_graph(4));
 > print $I;
 2 -1 0 -1
 -1 2 -1 0
 0 -1 2 -1
 -1 0 -1 2

laplacian(Graph G)

Compute the Laplacian matrix of a graph.

Parameters:

Graph G

Returns:

SparseMatrix<Rational>

Example:

 > $I = laplacian(cycle_graph(4)->ADJACENCY);
 > print $I;
 2 -1 0 -1
 -1 2 -1 0
 0 -1 2 -1
 -1 0 -1 2

lattice_of_chains(PartiallyOrderedSet<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.

Parameters:

PartiallyOrderedSet<Decoration> lattice

Returns:

PartiallyOrderedSet<BasicDecoration>

Example:

The following prints all faces with their ranks of the lattice of chains of the face lattice of the 0-simplex (a single point):

 > print lattice_of_chains(simplex(0)->HASSE_DIAGRAM)->DECORATION;
 ({-1} 3)
 ({0 1} 2)
 ({0} 1)
 ({1} 1)
 ({} 0)

line_graph(Graph G)

Creates the line graph of a graph.

Parameters:

Graph G

Returns:

Graph

Example:

The following prints the adjacency matrix of the line graph of the star graph with 4 nodes:

 > $g = new Graph<Undirected>(ADJACENCY=>[[],[0],[0],[0]]);
 > print line_graph($g->ADJACENCY);
 {1 2}
 {0 2}
 {0 1}

maximal_chains_of_lattice(PartiallyOrderedSet F)

Computes the set of maximal chains of a lattice.

Parameters:

PartiallyOrderedSet F

Options:

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

Returns:

IncidenceMatrix

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.

Parameters:

Graph G

Graph H

Options:

Bool allow_loops: Should edges of G be allowed to collapse to a loop when mapped to H? Default 0

Array<Int> prescribed_map: A vector of length G.nodes() with those images in G that should be fixed. Negative entries will be enumerated over.

Returns:

Int

random_spanningtree(Graph G)

Return a random spanning tree of a graph

Parameters:

Graph G: being connected

Returns:

Array<Pair<Int,Int>>

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.

Parameters:

Graph G

Returns:

SparseMatrix<Int>

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

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:

GraphAdjacency G

Returns:

SparseMatrix<Int>

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

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:

Array<Array<Int>>

depends on extension:

bliss or nauty

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:

IncidenceMatrix<NonSymmetric> m

Returns:

Array<Pair<Array<Int>,Array<Int>>>

depends on extension:

bliss or nauty

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:

IncidenceMatrix<Symmetric> m

Returns:

Array<Array<Int>>

depends on extension:

bliss or nauty

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:

GraphAdjacency g

Returns:

GraphAdjacency

depends on extension:

bliss or nauty

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:

GraphAdjacency g

Int k: a key for the hash computation, default value 2922320

Returns:

Int

depends on extension:

bliss or nauty

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:

IncidenceMatrix M

Int k: a key for the hash computation, default value 2922320

Returns:

Int

depends on extension:

bliss or nauty

find_node_permutation(GraphAdjacency graph1, GraphAdjacency graph2)

Find the node permutation mapping graph1 to graph2.

Parameters:

GraphAdjacency graph1

GraphAdjacency graph2

Returns:

Array<Int>

depends on extension:

bliss or nauty

find_row_col_permutation(IncidenceMatrix<NonSymmetric> m1, IncidenceMatrix<NonSymmetric> m2)

Find the permutations mapping the non-symmetric incidence matrix m1 to m2.

Parameters:

IncidenceMatrix<NonSymmetric> m1

IncidenceMatrix<NonSymmetric> m2

Returns:

Pair<Array<Int>,Array<Int>>

depends on extension:

bliss or nauty

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:

Bool

depends on extension:

bliss or nauty

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:

Bool

depends on extension:

bliss or nauty

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:

Int

depends on extension:

bliss or nauty

Example:

 > 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

Parameters:

Graph<Directed> P

Returns:

Graph<Directed>

hom_poset(Graph<Directed> P, Graph<Directed> Q)

Construct the poset of order preserving maps from one poset to another

Parameters:

Graph<Directed> P

Graph<Directed> Q

Returns:

Graph<Directed>

hom_poset(Array<Array<Int>> homs, Graph<Directed> Q)

Construct the poset of order preserving maps from one poset to another

Parameters:

Array<Array<Int>> homs

Graph<Directed> Q

Returns:

Graph<Directed>

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:

Graph<Directed> P

Graph<Directed> Q

Options:

Array<Int> prescribed_map: A vector of length P.nodes() with those images in Q that should be fixed. Negative entries will be enumerated over.

Returns:

Int

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:

Graph<Directed>

poset_homomorphisms(Graph<Directed> P, Graph<Directed> Q)

Enumerate all order preserving maps from one poset to another

Parameters:

Graph<Directed> P

Graph<Directed> Q

Options:

Array<Int> prescribed_map: A vector of length P.nodes() with those images in Q that should be fixed. Negative entries will be enumerated over.

Returns:

Array<Array<Int>>

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.

Parameters:

Int n

Returns:

Graph

Example:

To print the adjacency representation of the complete graph on 3 nodes, type this:

 > print complete(3)->ADJACENCY
 {1 2}
 {0 2}
 {0 1}

complete_bipartite(Int k, Int l)

Constructs a complete bipartite graph on k + l nodes.

Parameters:

Int k

Int l

Returns:

Graph

Example:

To print the adjacency representation of a complete bipartite graph with two nodes per partition, type this:

 > print complete_bipartite(2,2)->ADJACENCY;
 {2 3}
 {2 3}
 {0 1}
 {0 1}

cycle_graph(Int n)

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(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 set

Int k: the size of the subsets

Int i: the size of the subsets

Returns:

Graph

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.

Parameters:

Int n: the size of the ground set

Int k: the size of the subsets

Returns:

Graph

Example:

The following prints the adjacency representation of the johnson graph with the parameters 4,3:

 > print johnson_graph(4,3)->ADJACENCY;
 {1 2 3}
 {0 2 3}
 {0 1 3}
 {0 1 2}

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.

Parameters:

Int n: the size of the ground set

Int k: the size of the subsets

Returns:

Graph

Example:

The following prints the adjacency representation of the kneser graph with the parameters 3,1:

 > print kneser_graph(3,1)->ADJACENCY;
 {1 2}
 {0 2}
 {0 1}

maximal_ranked_poset(Array<Int> tau)

Maximal ranked partially ordered set. See Ahmad, Fourier, Joswig, arXiv:2309.01626

Parameters:

Array<Int> tau

Returns:

PartiallyOrderedSet<BasicDecoration,Sequential>

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:

Matrix<Rational> D: input point cloud distance matrix (can be upper triangular)

Rational delta: the maximal distance of neighbored vertices

Returns:

Graph

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}

path_graph(Int n)

Constructs a path graph on n nodes.

Parameters:

Int n

Returns:

Graph

petersen()

Constructs the Petersen graph.

Returns:

Graph

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/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.

Returns:

Graph

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.

Parameters:

Int n

Returns:

Graph

Example:

To print the adjacency representation of the wheel graph with five spokes, type this:

 > $g = wheel_graph(5);
 > print $g->ADJACENCY;
 {1 4 5}
 {0 2 5}
 {1 3 5}
 {2 4 5}
 {0 3 5}
 {0 1 2 3 4}

These functions are for visualization.

LEDA_graph(GraphAdjacency G)

Write a graph in LEDA input format.

Parameters:

GraphAdjacency G

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.

Parameters:

Graph G

Matrix V

Matrix BB

Returns:

GeometricGraph

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.

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.

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

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.

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

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

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 graph

Matrix coords: the coordinates of the nodes

Returns:

EdgeMap

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:

Array<Set<Int>> edges

Returns:

Graph

Example:

 > $g = graph_from_edges([[1,2],[1,3],[1,4]]);
 > print $g->ADJACENCY;
 {}
 {2 3 4}
 {1}
 {1}
 {1}

graph_from_cycles

UNDOCUMENTED

optimal_transport_plan(Matrix m, Vector m, Vector n)

Computes optimal transport plan of a transportation problem. Comment what mcf types are used.

Parameters:

Matrix m: -by-n matrix containing the transportation costs

Vector m: -vector containing the supply

Vector n: -vector containing the demand

Returns:

Matrix

optimal_transport_plan(Matrix m, Vector m, Vector n)

Computes optimal transport plan of a transportation problem.

Parameters:

Matrix m: -by-n matrix containing the transportation costs

Vector m: -vector containing the supply

Vector n: -vector containing the demand

Returns:

Matrix

shortest_path_dijkstra(Graph G, EdgeMap weights, Int source, Int target, Bool if)

Find the shortest path in a graph

Parameters:

Graph G: a graph without parallel edges

EdgeMap weights: edge weights

Int source: the source node

Int target: the target node

Bool if: true, perform backward search

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.

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 PartiallyOrderedSet nodes.

Methods of BasicDecoration:

face()

face represented by the node

Returns:

Set<Int>

rank()

node rank

Returns:

Int

InverseRankMap<SeqType>

Mapping of lattice nodes to their ranks. A “rank map” for our purpose is any assignment of natural numbers to the elements of a poset such that the (total) ordering of the numbers refines the (partial) ordering of the corresponding elements.

Type Parameters:

SeqType: tag describing node order, must be Sequential or Nonsequential.

Methods of InverseRankMap:

get_map()

Returns:

Map<Int,List<Int>>

nodes_of_rank(Int r)

Parameters:

Int r

Returns:

List<Int>

nodes_of_rank_range(Int r1, Int r2)

Parameters:

Int r1

Int r2

Returns:

List<Int>

set_rank(Int r, Int n)

Parameters:

Int r

Int n: Set the rank of a given node

DoublyConnectedEdgeList

UNDOCUMENTED