no way to compare when less than two revisions
Differences
This shows you the differences between two versions of the page.
— | documentation:master:graph [2024/03/29 05:43] (current) – created - external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== application graph ====== | ||
+ | The application graph deals with directed and undirected graphs. They can be defined abstractly as a set of nodes and '' | ||
+ | |||
+ | imports from: | ||
+ | * application [[.: | ||
+ | |||
+ | ===== Objects ===== | ||
+ | ** '' | ||
+ | ** '' | ||
+ | ** '' | ||
+ | ** '' | ||
+ | ** '' | ||
+ | ** '' | ||
+ | |||
+ | ===== Functions ===== | ||
+ | |||
+ | ==== Combinatorics ==== | ||
+ | | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Calculate all spanning trees for a connected graph along the lines of | ||
+ | > Donald E. Knuth: The Art of Computer Programming, | ||
+ | .. 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: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? 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)-> | ||
+ | < | ||
+ | {1 2} | ||
+ | {0 2} | ||
+ | > | ||
+ | (1 0) (2 0) (2 1) | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Creates the __complement graph__ of a graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the adjancency matrix of the complement graph of the star graph with 4 nodes: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print complement_graph($g)-> | ||
+ | {} | ||
+ | {2 3} | ||
+ | {1 3} | ||
+ | {1 2} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Compute the '' | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: Compute the connectivity of the vertex-edge graph of the square: | ||
+ | :: <code perl> > print connectivity(cube(2)-> | ||
+ | 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. | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Compute the eigenvalues of the discrete Laplacian of a graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: <code perl> > $v = eigenvalues_laplacian(cycle_graph(4)); | ||
+ | > print $v; | ||
+ | 4 2 2 0 | ||
+ | </ | ||
+ | ? **'' | ||
+ | :: Compute the eigenvalues of the discrete Laplacian of a graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: <code perl> > $v = eigenvalues_laplacian(cycle_graph(4)-> | ||
+ | > print $v; | ||
+ | 4 2 2 0 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Enumerate all homomorphisms (edge-preserving maps) from one graph to another | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Compute the unsigned vertex-edge incidence matrix of the graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: <code perl> > $I = incidence_matrix(cycle_graph(4)); | ||
+ | > print $I | ||
+ | 1 0 1 0 | ||
+ | 1 1 0 0 | ||
+ | 0 1 0 1 | ||
+ | 0 0 1 1 | ||
+ | </ | ||
+ | ? **'' | ||
+ | :: Compute the unsigned vertex-edge incidence matrix of the graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: <code perl> > $I = incidence_matrix(cycle_graph(4)-> | ||
+ | > print $I; | ||
+ | 1 0 1 0 | ||
+ | 1 1 0 0 | ||
+ | 0 1 0 1 | ||
+ | 0 0 1 1 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Compute the Laplacian matrix of a graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: <code perl> > $I = laplacian(cycle_graph(4)); | ||
+ | > print $I; | ||
+ | 2 -1 0 -1 | ||
+ | -1 2 -1 0 | ||
+ | 0 -1 2 -1 | ||
+ | -1 0 -1 2 | ||
+ | </ | ||
+ | ? **'' | ||
+ | :: Compute the Laplacian matrix of a graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: <code perl> > $I = laplacian(cycle_graph(4)-> | ||
+ | > print $I; | ||
+ | 2 -1 0 -1 | ||
+ | -1 2 -1 0 | ||
+ | 0 -1 2 -1 | ||
+ | -1 0 -1 2 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: For a given lattice, this computes the lattice of chains from bottom to top node. The result always includes an artificial top node. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? 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): | ||
+ | :: <code perl> > print lattice_of_chains(simplex(0)-> | ||
+ | ({-1} 3) | ||
+ | ({0 1} 2) | ||
+ | ({0} 1) | ||
+ | ({1} 1) | ||
+ | ({} 0) | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Creates the __line graph__ of a graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the adjacency matrix of the line graph of the star graph with 4 nodes: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > print line_graph($g-> | ||
+ | {1 2} | ||
+ | {0 2} | ||
+ | {0 1} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Computes the set of maximal chains of a lattice. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints all maximal chains of the face lattice of the 1-simplex (an edge): | ||
+ | :: <code perl> > print maximal_chains_of_lattice(simplex(1)-> | ||
+ | {0 1 3} | ||
+ | {0 2 3} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Return a random spanning tree of a graph | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $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 | ||
+ | </ | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: <code perl> > $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 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ==== Comparing ==== | ||
+ | | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Find the automorphism group of the graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | ? Example: | ||
+ | :: We first create the vertex-edge graph of the square and then print its automorphism group: | ||
+ | :: <code perl> > $g=new GraphAdjacency(cube(2)-> | ||
+ | > 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. | ||
+ | ? **'' | ||
+ | :: 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/ | ||
+ | :: <code perl> > print automorphisms(cube(3)-> | ||
+ | | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | :: 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. | ||
+ | ? **'' | ||
+ | :: Find the automorphism group of the symmetric incidence matrix. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Find a canonical representation of a graph //g//. Warning: This representation can depend on the extension (bliss/ | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Compute a hash for a graph //g// independent of the node ordering. Warning: This hash can depend on the extension (bliss/ | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | ? **'' | ||
+ | :: Compute a hash for an incidence matrix //I// independent of the row ordering. Warning: This hash can depend on the extension (bliss/ | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Find the node permutation mapping //graph1// to //graph2//. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Find the permutations mapping the non-symmetric incidence matrix //m1// to //m2//. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | ? Example: | ||
+ | :: <code perl> > $m1 = new IncidenceMatrix([1, | ||
+ | > $m2 = new IncidenceMatrix([4, | ||
+ | > print find_row_col_permutation($m1, | ||
+ | <1 0> <0 1 4 3 5 2> | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: true if // | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | ? Example: | ||
+ | :: Compare the incidence matrices of the 2-dimensional cube and cross polytope: | ||
+ | :: <code perl> > $I1 = cube(2)-> | ||
+ | > $I2 = cross(2)-> | ||
+ | > print isomorphic($I1, | ||
+ | true | ||
+ | </ | ||
+ | ? **'' | ||
+ | :: true if //graph1// and //graph2// are isomorphic. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | ? Example: | ||
+ | :: Compare the vertex-edge graph of the square with the cycle graph on 4 nodes: | ||
+ | :: <code perl> > $g1 = cube(2)-> | ||
+ | > $g2 = cycle_graph(4)-> | ||
+ | > print isomorphic($g1, | ||
+ | true | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Find the order of the automorphism group of the graph. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? depends on extension: | ||
+ | : [[: | ||
+ | ? Example: | ||
+ | :: <code perl> > print n_automorphisms(cycle_graph(5)-> | ||
+ | 2 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ==== Posets ==== | ||
+ | | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Construct the covering relations of a poset | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Construct the poset of order preserving maps from one poset to another | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? **'' | ||
+ | :: Construct the poset of order preserving maps from one poset to another | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Construct the inclusion poset from a given container. The elements of the container are interpreted as sets. They define a poset by inclusion. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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. | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Constructs a __complete graph__ on //n// nodes. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: To print the adjacency representation of the complete graph on 3 nodes, type this: | ||
+ | :: <code perl> > print complete(3)-> | ||
+ | {1 2} | ||
+ | {0 2} | ||
+ | {0 1} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Constructs a __complete bipartite graph__ on //k// + //l// nodes. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: To print the adjacency representation of a complete bipartite graph with two nodes per partition, type this: | ||
+ | :: <code perl> > print complete_bipartite(2, | ||
+ | {2 3} | ||
+ | {2 3} | ||
+ | {0 1} | ||
+ | {0 1} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Constructs a __cycle graph__ on //n// nodes. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: To print the adjacency representation of the cycle graph on four nodes, type this: | ||
+ | :: <code perl> > $g = cycle_graph(4); | ||
+ | > print $g-> | ||
+ | {1 3} | ||
+ | {0 2} | ||
+ | {1 3} | ||
+ | {0 2} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Create the __generalized Johnson graph__ on parameters (n, | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the adjacency representation of the generalized johnson graph with the parameters 4,2,1: | ||
+ | :: <code perl> > print generalized_johnson_graph(4, | ||
+ | {1 2 3 4} | ||
+ | {0 2 3 5} | ||
+ | {0 1 4 5} | ||
+ | {0 1 4 5} | ||
+ | {0 2 3 5} | ||
+ | {1 2 3 4} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Create the __Johnson graph__ on parameters (n, | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the adjacency representation of the johnson graph with the parameters 4,3: | ||
+ | :: <code perl> > print johnson_graph(4, | ||
+ | {1 2 3} | ||
+ | {0 2 3} | ||
+ | {0 1 3} | ||
+ | {0 1 2} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Create the __Kneser graph__ on parameters (n, | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the adjacency representation of the kneser graph with the parameters 3,1: | ||
+ | :: <code perl> > print kneser_graph(3, | ||
+ | {1 2} | ||
+ | {0 2} | ||
+ | {0 1} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Maximal ranked partially ordered set. See Ahmad, Fourier, Joswig, arXiv: | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Constructs the __neighborhood graph__ of a point set //S// given a parameter //delta//. The set is passed as its so-called " | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the neighborhood graph of a distance matrix with a limit of 3.3, producing the graph of a square: | ||
+ | :: <code perl> > $D = new Matrix< | ||
+ | > print neighborhood_graph($D, | ||
+ | {1 2} | ||
+ | {0 3} | ||
+ | {0 3} | ||
+ | {1 2} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Constructs a __path graph__ on //n// nodes. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Constructs the __Petersen graph__. | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: The following prints the adjacency matrix of the petersen graph: | ||
+ | :: <code perl> > print petersen()-> | ||
+ | 10 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? 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. | ||
+ | :: <code perl> > $g = random_graph(10, | ||
+ | > print $g-> | ||
+ | 9 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Constructs a __wheel graph__ with //n// spokes. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: To print the adjacency representation of the wheel graph with five spokes, type this: | ||
+ | :: <code perl> > $g = wheel_graph(5); | ||
+ | > print $g-> | ||
+ | {1 4 5} | ||
+ | {0 2 5} | ||
+ | {1 3 5} | ||
+ | {2 4 5} | ||
+ | {0 3 5} | ||
+ | {0 1 2 3 4} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ==== Visualization ==== | ||
+ | These functions are for visualization. | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Write a graph in LEDA input format. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Clip a graph with respect to a given bounding box. Used for the visualization of Voronoi diagrams. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Draw the given graph or face lattice object using [[: | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | ? Example: | ||
+ | :: The following creates a star graph with 4 nodes and visualizes it via graphviz with default options: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > graphviz($g-> | ||
+ | </ | ||
+ | :: The following shows some modified visualization style of the same graph: | ||
+ | :: <code perl> > $g = new Graph< | ||
+ | > graphviz($g-> | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Produce a MetaPost input file with given visual objects. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : | ||
+ | :: '' | ||
+ | ? Example: | ||
+ | :: The following prints a metapost description of the complete graph with 3 nodes in the console: | ||
+ | :: <code perl> > metapost(complete(3)-> | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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: | ||
+ | :: '' | ||
+ | ? Options: | ||
+ | : affecting the desired picture | ||
+ | |||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | : calculation fine-tuning | ||
+ | |||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Example: | ||
+ | :: The following prints a 3-dimensional embedding of the complete graph on 3 nodes using a specific seed and scaled edge lengths: | ||
+ | :: <code perl> > print spring_embedder(complete(3)-> | ||
+ | | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ==== Other ==== | ||
+ | | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Compute the lengths of all edges of a given graph //G// from the coordinates //coords// of its nodes. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? 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: | ||
+ | :: <code perl> > print edge_lengths(complete(3)-> | ||
+ | 1 1 1.414213562 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Creates a graph from a given list of //edges//. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? Example: | ||
+ | :: <code perl> > $g = graph_from_edges([[1, | ||
+ | > print $g-> | ||
+ | {} | ||
+ | {2 3 4} | ||
+ | {1} | ||
+ | {1} | ||
+ | {1} | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ==== no category ==== | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Computes optimal transport plan of a transportation problem. Comment what mcf types are used. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? **'' | ||
+ | :: Computes optimal transport plan of a transportation problem. | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Find the shortest path in a graph | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | :: '' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ===== 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. | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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. | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: 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. | ||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Minimal required data associated with '' | ||
+ | ? Methods of BasicDecoration: | ||
+ | : | ||
+ | ? **'' | ||
+ | ::face represented by the node | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? **'' | ||
+ | ::node rank | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: Mapping of lattice nodes to their ranks. | ||
+ | ? Type Parameters: | ||
+ | :: '' | ||
+ | ? Methods of InverseRankMap: | ||
+ | : | ||
+ | ? **'' | ||
+ | :: | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? **'' | ||
+ | :: | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? **'' | ||
+ | :: | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | ? Returns: | ||
+ | :'' | ||
+ | ? **'' | ||
+ | :: | ||
+ | ? Parameters: | ||
+ | :: '' | ||
+ | :: '' | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | ==== no category ==== | ||
+ | {{anchor: | ||
+ | ? **'' | ||
+ | :: | ||
+ | |||
+ | |||
+ | ---- | ||