====== application graph ====== The application graph deals with directed and undirected graphs. They can be defined abstractly as a set of nodes and ''[[.:graph:Graph#EDGES |EDGES]]'' or as part of a larger structure for instance as the [[.:polytope:Polytope#GRAPH |vertex-edge graph]] of a polytope. imports from: * application [[.:common|common]] ===== Objects ===== ** ''[[.:graph:GeometricGraph |GeometricGraph]]'':\\ An undirected graph with given node coordinates and a bounding box. ** ''[[.:graph:Graph |Graph]]'':\\ A graph with optional node and edge attributes. ** ''[[.:graph:PartiallyOrderedSet |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™). ** ''[[.:graph:PhylogeneticTree |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. ** ''[[.:graph:Visual_Graph |Visual::Graph]]'':\\ Collection of nodes and edges of an abstract graph amended with visual decoration attributes and an optional embedding in 3-d. ** ''[[.:graph:Visual_Lattice |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. ---- {{anchor:all_spanningtrees:}} ? **''all_spanningtrees([[.:graph:Graph |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: :: > print all_spanningtrees(complete(3)->ADJACENCY); <{0 1} {1 2} {0 2} > (1 0) (2 0) (2 1) ---- {{anchor:complement_graph:}} ? **''complement_graph([[.:graph:Graph |Graph]] G)''** :: Creates the __complement graph__ of a graph. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' ? Returns: :''[[.:graph:Graph |Graph]]'' ? Example: :: The following prints the adjancency matrix of the complement graph of the star graph with 4 nodes: :: > $g = new Graph(ADJACENCY=>[[],[0],[0],[0]]); > print complement_graph($g)->ADJACENCY; {} {2 3} {1 3} {1 2} ---- {{anchor:connectivity:}} ? **''connectivity([[.:common#GraphAdjacency |GraphAdjacency]]<[[.:common#Undirected |Undirected]]> graph)''** :: Compute the ''[[.:graph:Graph#CONNECTIVITY |CONNECTIVITY]]'' of a given //graph// using the Ford-Fulkerson flow algorithm. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]<[[.:common#Undirected |Undirected]]>'' ''graph'' ? Returns: :''[[.:common#Int |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. ---- {{anchor:eigenvalues_laplacian:}} ? **''eigenvalues_laplacian([[.:graph:Graph |Graph]] G)''** :: Compute the eigenvalues of the discrete Laplacian of a graph. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' ? Returns: :''[[.:common#Vector |Vector]]<[[.:common#Float |Float]]>'' ? Example: :: > $v = eigenvalues_laplacian(cycle_graph(4)); > print $v; 4 2 2 0 ? **''eigenvalues_laplacian([[.:graph:Graph |Graph]] G)''** :: Compute the eigenvalues of the discrete Laplacian of a graph. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' ? Returns: :''[[.:common#Vector |Vector]]<[[.:common#Float |Float]]>'' ? Example: :: > $v = eigenvalues_laplacian(cycle_graph(4)->ADJACENCY); > print $v; 4 2 2 0 ---- {{anchor:find_lattice_permutation:}} ? **''find_lattice_permutation([[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]] L1, [[.:graph:PartiallyOrderedSet |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: :: ''[[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]]'' ''L1'': A lattice :: ''[[.:graph:PartiallyOrderedSet |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'' ---- {{anchor:graph_homomorphisms:}} ? **''graph_homomorphisms([[.:graph:Graph |Graph]] G, [[.:graph:Graph |Graph]] H)''** :: Enumerate all homomorphisms (edge-preserving maps) from one graph to another ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' :: ''[[.:graph:Graph |Graph]]'' ''H'' ? Options: : :: ''[[.:common#Bool |Bool]]'' ''allow_loops'': Should edges of G be allowed to collapse to a loop when mapped to H? Default 0 :: ''[[.:common#Array |Array]]<[[.:common#Int |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: :''[[.:common#Array |Array]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%%'' ---- {{anchor:incidence_matrix:}} ? **''incidence_matrix([[.:graph:Graph |Graph]] G)''** :: Compute the unsigned vertex-edge incidence matrix of the graph. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' ? Returns: :''[[.:common#SparseMatrix |SparseMatrix]]<[[.:common#Int |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([[.:common#GraphAdjacency |GraphAdjacency]] G)''** :: Compute the unsigned vertex-edge incidence matrix of the graph. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''G'' ? Returns: :''[[.:common#SparseMatrix |SparseMatrix]]<[[.:common#Int |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 ---- {{anchor:laplacian:}} ? **''laplacian([[.:graph:Graph |Graph]] G)''** :: Compute the Laplacian matrix of a graph. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' ? Returns: :''[[.:common#SparseMatrix |SparseMatrix]]<[[.:common#Rational |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:Graph |Graph]] G)''** :: Compute the Laplacian matrix of a graph. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' ? Returns: :''[[.:common#SparseMatrix |SparseMatrix]]<[[.:common#Rational |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 ---- {{anchor:lattice_of_chains:}} ? **''lattice_of_chains([[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]] 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: :: ''[[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]]'' ''lattice'' ? Returns: :''[[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]]<[[.:graph#BasicDecoration |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) ---- {{anchor:line_graph:}} ? **''line_graph([[.:graph:Graph |Graph]] G)''** :: Creates the __line graph__ of a graph. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' ? Returns: :''[[.:graph:Graph |Graph]]'' ? Example: :: The following prints the adjacency matrix of the line graph of the star graph with 4 nodes: :: > $g = new Graph(ADJACENCY=>[[],[0],[0],[0]]); > print line_graph($g->ADJACENCY); {1 2} {0 2} {0 1} ---- {{anchor:maximal_chains_of_lattice:}} ? **''maximal_chains_of_lattice([[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]] F)''** :: Computes the set of maximal chains of a lattice. ? Parameters: :: ''[[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]]'' ''F'' ? Options: : :: ''[[.:common#Bool |Bool]]'' ''ignore_bottom_node'': If true, the bottom node is not included in the chains. False by default :: ''[[.:common#Bool |Bool]]'' ''ignore_top_node'': If true, the top node is not included in the chains. False by default ? Returns: :''[[.:common#IncidenceMatrix |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} ---- {{anchor:n_graph_homomorphisms:}} ? **''n_graph_homomorphisms([[.:graph:Graph |Graph]] G, [[.:graph:Graph |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:Graph |Graph]]'' ''G'' :: ''[[.:graph:Graph |Graph]]'' ''H'' ? Options: : :: ''[[.:common#Bool |Bool]]'' ''allow_loops'': Should edges of G be allowed to collapse to a loop when mapped to H? Default 0 :: ''[[.:common#Array |Array]]<[[.:common#Int |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: :''[[.:common#Int |Int]]'' ---- {{anchor:random_spanningtree:}} ? **''random_spanningtree([[.:graph:Graph |Graph]] G)''** :: Return a random spanning tree of a graph ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'': being connected ? Returns: :''[[.:common#Array |Array]]<[[.:common#Pair |Pair]]<[[.:common#Int |Int]],[[.:common#Int |Int]]%%>>%%'' ---- {{anchor:signed_incidence_matrix:}} ? **''signed_incidence_matrix([[.:graph:Graph |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:Graph |Graph]]'' ''G'' ? Returns: :''[[.:common#SparseMatrix |SparseMatrix]]<[[.:common#Int |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([[.:common#GraphAdjacency |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: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''G'' ? Returns: :''[[.:common#SparseMatrix |SparseMatrix]]<[[.:common#Int |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 ---- ==== Comparing ==== Functions dealing with automorphisms of graphs and determining whether graphs are isomorphic. ---- {{anchor:automorphisms:}} ? **''automorphisms([[.:common#GraphAdjacency |GraphAdjacency]] graph)''** :: Find the automorphism group of the graph. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''graph'' ? Returns: :''[[.:common#Array |Array]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%%'' ? depends on extension: : [[:external_software|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([[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#NonSymmetric |NonSymmetric]]> m)''** :: Find the automorphism group of the non-symmetric incidence matrix. ? Parameters: :: ''[[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#NonSymmetric |NonSymmetric]]>'' ''m'' ? Returns: :''[[.:common#Array |Array]]<[[.:common#Pair |Pair]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]>,[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%%>'' ? depends on extension: : [[:external_software|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([[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#Symmetric |Symmetric]]> m)''** :: Find the automorphism group of the symmetric incidence matrix. ? Parameters: :: ''[[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#Symmetric |Symmetric]]>'' ''m'' ? Returns: :''[[.:common#Array |Array]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%%'' ? depends on extension: : [[:external_software|bliss or nauty]] ---- {{anchor:canonical_form:}} ? **''canonical_form([[.:common#GraphAdjacency |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: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''g'' ? Returns: :''[[.:common#GraphAdjacency |GraphAdjacency]]'' ? depends on extension: : [[:external_software|bliss or nauty]] ---- {{anchor:canonical_hash:}} ? **''canonical_hash([[.:common#GraphAdjacency |GraphAdjacency]] g, [[.:common#Int |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: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''g'' :: ''[[.:common#Int |Int]]'' ''k'': a key for the hash computation, default value 2922320 ? Returns: :''[[.:common#Int |Int]]'' ? depends on extension: : [[:external_software|bliss or nauty]] ? **''canonical_hash([[.:common#IncidenceMatrix |IncidenceMatrix]] M, [[.:common#Int |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: :: ''[[.:common#IncidenceMatrix |IncidenceMatrix]]'' ''M'' :: ''[[.:common#Int |Int]]'' ''k'': a key for the hash computation, default value 2922320 ? Returns: :''[[.:common#Int |Int]]'' ? depends on extension: : [[:external_software|bliss or nauty]] ---- {{anchor:find_node_permutation:}} ? **''find_node_permutation([[.:common#GraphAdjacency |GraphAdjacency]] graph1, [[.:common#GraphAdjacency |GraphAdjacency]] graph2)''** :: Find the node permutation mapping //graph1// to //graph2//. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''graph1'' :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''graph2'' ? Returns: :''[[.:common#Array |Array]]<[[.:common#Int |Int]]>'' ? depends on extension: : [[:external_software|bliss or nauty]] ---- {{anchor:find_row_col_permutation:}} ? **''find_row_col_permutation([[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#NonSymmetric |NonSymmetric]]> m1, [[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#NonSymmetric |NonSymmetric]]> m2)''** :: Find the permutations mapping the non-symmetric incidence matrix //m1// to //m2//. ? Parameters: :: ''[[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#NonSymmetric |NonSymmetric]]>'' ''m1'' :: ''[[.:common#IncidenceMatrix |IncidenceMatrix]]<[[.:common#NonSymmetric |NonSymmetric]]>'' ''m2'' ? Returns: :''[[.:common#Pair |Pair]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]>,[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%%'' ? depends on extension: : [[:external_software|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> ---- {{anchor:isomorphic:}} ? **''isomorphic([[.:common#IncidenceMatrix |IncidenceMatrix]] IncidenceMatrix1, [[.:common#IncidenceMatrix |IncidenceMatrix]] IncidenceMatrix2)''** :: true if //IncidenceMatrix1// and //IncidenceMatrix2// are isomorphic. ? Parameters: :: ''[[.:common#IncidenceMatrix |IncidenceMatrix]]'' ''IncidenceMatrix1'' :: ''[[.:common#IncidenceMatrix |IncidenceMatrix]]'' ''IncidenceMatrix2'' ? Returns: :''[[.:common#Bool |Bool]]'' ? depends on extension: : [[:external_software|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([[.:common#GraphAdjacency |GraphAdjacency]] graph1, [[.:common#GraphAdjacency |GraphAdjacency]] graph2)''** :: true if //graph1// and //graph2// are isomorphic. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''graph1'' :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''graph2'' ? Returns: :''[[.:common#Bool |Bool]]'' ? depends on extension: : [[:external_software|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 ---- {{anchor:n_automorphisms:}} ? **''n_automorphisms([[.:common#GraphAdjacency |GraphAdjacency]] graph)''** :: Find the order of the automorphism group of the graph. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''graph'' ? Returns: :''[[.:common#Int |Int]]'' ? depends on extension: : [[:external_software|bliss or nauty]] ? Example: :: > print n_automorphisms(cycle_graph(5)->ADJACENCY); 2 ---- ==== Posets ==== Functions dealing with posets represented as directed graphs ---- {{anchor:covering_relations:}} ? **''covering_relations([[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]> P)''** :: Construct the covering relations of a poset ? Parameters: :: ''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''P'' ? Returns: :''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ---- {{anchor:hom_poset:}} ? **''hom_poset([[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]> P, [[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]> Q)''** :: Construct the poset of order preserving maps from one poset to another ? Parameters: :: ''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''P'' :: ''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''Q'' ? Returns: :''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ? **''hom_poset([[.:common#Array |Array]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%% homs, [[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]> Q)''** :: Construct the poset of order preserving maps from one poset to another ? Parameters: :: ''[[.:common#Array |Array]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%%'' ''homs'' :: ''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''Q'' ? Returns: :''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ---- {{anchor:n_poset_homomorphisms:}} ? **''n_poset_homomorphisms([[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]> P, [[.:graph:Graph |Graph]]<[[.:common#Directed |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:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''P'' :: ''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''Q'' ? Options: : :: ''[[.:common#Array |Array]]<[[.:common#Int |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: :''[[.:common#Int |Int]]'' ---- {{anchor:poset_by_inclusion:}} ? **''poset_by_inclusion([[.:common#Array |Array]] 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: :: ''[[.:common#Array |Array]]'' ''P'' ? Returns: :''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ---- {{anchor:poset_homomorphisms:}} ? **''poset_homomorphisms([[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]> P, [[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]> Q)''** :: Enumerate all order preserving maps from one poset to another ? Parameters: :: ''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''P'' :: ''[[.:graph:Graph |Graph]]<[[.:common#Directed |Directed]]>'' ''Q'' ? Options: : :: ''[[.:common#Array |Array]]<[[.:common#Int |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: :''[[.:common#Array |Array]]<[[.:common#Array |Array]]<[[.:common#Int |Int]]%%>>%%'' ---- ==== Producing a graph ==== With these functions you can create special examples of graphs, graphs belonging to parameterized families and random graphs. ---- {{anchor:complete:}} ? **''complete([[.:common#Int |Int]] n)''** :: Constructs a __complete graph__ on //n// nodes. ? Parameters: :: ''[[.:common#Int |Int]]'' ''n'' ? Returns: :''[[.:graph:Graph |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} ---- {{anchor:complete_bipartite:}} ? **''complete_bipartite([[.:common#Int |Int]] k, [[.:common#Int |Int]] l)''** :: Constructs a __complete bipartite graph__ on //k// + //l// nodes. ? Parameters: :: ''[[.:common#Int |Int]]'' ''k'' :: ''[[.:common#Int |Int]]'' ''l'' ? Returns: :''[[.:graph:Graph |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} ---- {{anchor:cycle_graph:}} ? **''cycle_graph([[.:common#Int |Int]] n)''** :: Constructs a __cycle graph__ on //n// nodes. ? Parameters: :: ''[[.:common#Int |Int]]'' ''n'' ? Returns: :''[[.:graph:Graph |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} ---- {{anchor:generalized_johnson_graph:}} ? **''generalized_johnson_graph([[.:common#Int |Int]] n, [[.:common#Int |Int]] k, [[.:common#Int |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: :: ''[[.:common#Int |Int]]'' ''n'': the size of the ground set :: ''[[.:common#Int |Int]]'' ''k'': the size of the subsets :: ''[[.:common#Int |Int]]'' ''i'': the size of the subsets ? Returns: :''[[.:graph:Graph |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} ---- {{anchor:johnson_graph:}} ? **''johnson_graph([[.:common#Int |Int]] n, [[.:common#Int |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: :: ''[[.:common#Int |Int]]'' ''n'': the size of the ground set :: ''[[.:common#Int |Int]]'' ''k'': the size of the subsets ? Returns: :''[[.:graph:Graph |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} ---- {{anchor:kneser_graph:}} ? **''kneser_graph([[.:common#Int |Int]] n, [[.:common#Int |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: :: ''[[.:common#Int |Int]]'' ''n'': the size of the ground set :: ''[[.:common#Int |Int]]'' ''k'': the size of the subsets ? Returns: :''[[.:graph:Graph |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} ---- {{anchor:maximal_ranked_poset:}} ? **''maximal_ranked_poset([[.:common#Array |Array]]<[[.:common#Int |Int]]> tau)''** :: Maximal ranked partially ordered set. See Ahmad, Fourier, Joswig, arXiv:2309.01626 ? Parameters: :: ''[[.:common#Array |Array]]<[[.:common#Int |Int]]>'' ''tau'' ? Returns: :''[[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]]<[[.:graph#BasicDecoration |BasicDecoration]],[[.:graph#Sequential |Sequential]]>'' ---- {{anchor:neighborhood_graph:}} ? **''neighborhood_graph([[.:common#Matrix |Matrix]]<[[.:common#Rational |Rational]]> D, [[.:common#Rational |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: :: ''[[.:common#Matrix |Matrix]]<[[.:common#Rational |Rational]]>'' ''D'': input point cloud distance matrix (can be upper triangular) :: ''[[.:common#Rational |Rational]]'' ''delta'': the maximal distance of neighbored vertices ? Returns: :''[[.:graph:Graph |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([[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} ---- {{anchor:path_graph:}} ? **''path_graph([[.:common#Int |Int]] n)''** :: Constructs a __path graph__ on //n// nodes. ? Parameters: :: ''[[.:common#Int |Int]]'' ''n'' ? Returns: :''[[.:graph:Graph |Graph]]'' ---- {{anchor:petersen:}} ? **''petersen()''** :: Constructs the __Petersen graph__. ? Returns: :''[[.:graph:Graph |Graph]]'' ? Example: :: The following prints the adjacency matrix of the petersen graph: :: > print petersen()->N_NODES; 10 ---- {{anchor:random_graph:}} ? **''random_graph([[.:common#Int |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: :: ''[[.:common#Int |Int]]'' ''n'' ? Options: : :: ''[[.:common#Rational |Rational]]'' ''p'': the probability of an edge occurring; default 1/2 :: ''[[.:common#Int |Int]]'' ''M'': the number of edges in the graph :: ''[[.:common#Bool |Bool]]'' ''try_connected'': whether to try to generate a connected graph, default 1 :: ''[[.:common#Int |Int]]'' ''max_attempts'': If //connected// is set, specifies how many times to try to make a connected random graph before giving up. :: ''[[.:common#Int |Int]]'' ''seed'': controls the outcome of the random number generator; fixing a seed number guarantees the same outcome. ? Returns: :''[[.:graph:Graph |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 ---- {{anchor:wheel_graph:}} ? **''wheel_graph([[.:common#Int |Int]] n)''** :: Constructs a __wheel graph__ with //n// spokes. ? Parameters: :: ''[[.:common#Int |Int]]'' ''n'' ? Returns: :''[[.:graph:Graph |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} ---- ==== Visualization ==== These functions are for visualization. ---- {{anchor:leda_graph:}} ? **''LEDA_graph([[.:common#GraphAdjacency |GraphAdjacency]] G)''** :: Write a graph in LEDA input format. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]'' ''G'' ---- {{anchor:clip_graph:}} ? **''clip_graph([[.:graph:Graph |Graph]] G, [[.:common#Matrix |Matrix]] V, [[.:common#Matrix |Matrix]] BB)''** :: Clip a graph with respect to a given bounding box. Used for the visualization of Voronoi diagrams. ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'' :: ''[[.:common#Matrix |Matrix]]'' ''V'' :: ''[[.:common#Matrix |Matrix]]'' ''BB'' ? Returns: :''[[.:graph:GeometricGraph |GeometricGraph]]'' ---- {{anchor:graphviz:}} ? **''graphviz([[.:common:Visual_Object |Visual::Object]] vis_obj ...)''** :: Draw the given graph or face lattice object using [[:external_software#graphviz|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: :: ''[[.:common:Visual_Object |Visual::Object]]'' ''vis_obj ...'': objects to display ? Options: : :: ''[[.:common#String |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(ADJACENCY=>[[],[0],[0],[0]]); > graphviz($g->VISUAL); :: The following shows some modified visualization style of the same graph: :: > $g = new Graph(ADJACENCY=>[[],[0],[0],[0]]); > graphviz($g->VISUAL(NodeColor=>"green",EdgeColor=>"purple",EdgeThickness=>5)); ---- {{anchor:hd_embedder:}} ? **''hd_embedder([[.:common#Array |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: :: ''[[.:common#Array |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: : :: ''[[.:common#Bool |Bool]]'' ''dual'': the node representing the empty face is put on the topmost level :: ''[[.:common#Float |Float]]'' ''eps'': calculation accuracy. :: ''[[.:common#Int |Int]]'' ''seed'': effects the initial placement of the nodes. ---- {{anchor:metapost:}} ? **''metapost([[.:common:Visual_Object |Visual::Object]] vis_obj ...)''** :: Produce a MetaPost input file with given visual objects. ? Parameters: :: ''[[.:common:Visual_Object |Visual::Object]]'' ''vis_obj ...'': objects to display ? Options: : :: ''[[.:common#String |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=>"-"); ---- {{anchor:spring_embedder:}} ? **''spring_embedder([[.:common#GraphAdjacency |GraphAdjacency]]<[[.:common#Undirected |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 :: ''[[.:common#EdgeMap |EdgeMap]]'' ''edge_weights'': relative edge lengths. By default the embedding algorithm tries to stretch all edges to the same length. :: ''[[.:common#Vector |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. :: ''[[.:common#Float |Float]]'' ''z-factor'': gain coefficient applied to the //z-ordering// force. :: ''[[.:common#Int |Int]]'' ''seed'': random seed for initial node placement on a unit sphere. : calculation fine-tuning :: ''[[.:common#Float |Float]]'' ''scale'': enlarges the ideal edge length :: ''[[.:common#Float |Float]]'' ''balance'': changes the balance between the edge contraction and node repulsion forces :: ''[[.:common#Float |Float]]'' ''inertion'': affects how the nodes are moved, can be used to restrain oscillations :: ''[[.:common#Float |Float]]'' ''viscosity'': idem :: ''[[.:common#Float |Float]]'' ''eps'': a threshold for point movement between iterations, below that it is considered to stand still :: ''[[.:common#Int |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 ---- ==== Other ==== Special purpose functions. ---- {{anchor:edge_lengths:}} ? **''edge_lengths([[.:common#GraphAdjacency |GraphAdjacency]]<[[.:common#Directed |Directed]]> G, [[.:common#Matrix |Matrix]] coords)''** :: Compute the lengths of all edges of a given graph //G// from the coordinates //coords// of its nodes. ? Parameters: :: ''[[.:common#GraphAdjacency |GraphAdjacency]]<[[.:common#Directed |Directed]]>'' ''G'': the input graph :: ''[[.:common#Matrix |Matrix]]'' ''coords'': the coordinates of the nodes ? Returns: :''[[.:common#EdgeMap |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 ---- {{anchor:graph_from_edges:}} ? **''graph_from_edges([[.:common#Array |Array]]<[[.:common#Set |Set]]<[[.:common#Int |Int]]%%>>%% edges)''** :: Creates a graph from a given list of //edges//. ? Parameters: :: ''[[.:common#Array |Array]]<[[.:common#Set |Set]]<[[.:common#Int |Int]]%%>>%%'' ''edges'' ? Returns: :''[[.:graph:Graph |Graph]]'' ? Example: :: > $g = graph_from_edges([[1,2],[1,3],[1,4]]); > print $g->ADJACENCY; {} {2 3 4} {1} {1} {1} ---- ==== no category ==== {{anchor:graph_from_cycles:}} ? **''graph_from_cycles''** ::UNDOCUMENTED ---- {{anchor:optimal_transport_plan:}} ? **''optimal_transport_plan([[.:common#Matrix |Matrix]] m, [[.:common#Vector |Vector]] m, [[.:common#Vector |Vector]] n)''** :: Computes optimal transport plan of a transportation problem. Comment what mcf types are used. ? Parameters: :: ''[[.:common#Matrix |Matrix]]'' ''m'': -by-n matrix containing the transportation costs :: ''[[.:common#Vector |Vector]]'' ''m'': -vector containing the supply :: ''[[.:common#Vector |Vector]]'' ''n'': -vector containing the demand ? Returns: :''[[.:common#Matrix |Matrix]]'' ? **''optimal_transport_plan([[.:common#Matrix |Matrix]] m, [[.:common#Vector |Vector]] m, [[.:common#Vector |Vector]] n)''** :: Computes optimal transport plan of a transportation problem. ? Parameters: :: ''[[.:common#Matrix |Matrix]]'' ''m'': -by-n matrix containing the transportation costs :: ''[[.:common#Vector |Vector]]'' ''m'': -vector containing the supply :: ''[[.:common#Vector |Vector]]'' ''n'': -vector containing the demand ? Returns: :''[[.:common#Matrix |Matrix]]'' ---- {{anchor:shortest_path_dijkstra:}} ? **''shortest_path_dijkstra([[.:graph:Graph |Graph]] G, [[.:common#EdgeMap |EdgeMap]] weights, [[.:common#Int |Int]] source, [[.:common#Int |Int]] target, [[.:common#Bool |Bool]] if)''** :: Find the shortest path in a graph ? Parameters: :: ''[[.:graph:Graph |Graph]]'' ''G'': a graph without parallel edges :: ''[[.:common#EdgeMap |EdgeMap]]'' ''weights'': edge weights :: ''[[.:common#Int |Int]]'' ''source'': the source node :: ''[[.:common#Int |Int]]'' ''target'': the target node :: ''[[.:common#Bool |Bool]]'' ''if'': true, perform backward search ---- ===== 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:nonsequential:}} ? **''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. ---- {{anchor:sequential:}} ? **''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. ---- {{anchor:basicdecoration:}} ? **''BasicDecoration''** :: Minimal required data associated with ''[[.:graph:PartiallyOrderedSet |PartiallyOrderedSet]]'' nodes. ? Methods of BasicDecoration: : ? **''face()''** ::face represented by the node ? Returns: :''[[.:common#Set |Set]]<[[.:common#Int |Int]]>'' ? **''rank()''** ::node rank ? Returns: :''[[.:common#Int |Int]]'' ---- {{anchor:inverserankmap:}} ? **''InverseRankMap''** :: 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 ''[[.:graph#Sequential |Sequential]]'' or ''[[.:graph#Nonsequential |Nonsequential]]''. ? Methods of InverseRankMap: : ? **''get_map()''** :: ? Returns: :''[[.:common#Map |Map]]<[[.:common#Int |Int]],[[.:common#List |List]]<[[.:common#Int |Int]]%%>>%%'' ? **''nodes_of_rank([[.:common#Int |Int]] r)''** :: ? Parameters: :: ''[[.:common#Int |Int]]'' ''r'' ? Returns: :''[[.:common#List |List]]<[[.:common#Int |Int]]>'' ? **''nodes_of_rank_range([[.:common#Int |Int]] r1, [[.:common#Int |Int]] r2)''** :: ? Parameters: :: ''[[.:common#Int |Int]]'' ''r1'' :: ''[[.:common#Int |Int]]'' ''r2'' ? Returns: :''[[.:common#List |List]]<[[.:common#Int |Int]]>'' ? **''set_rank([[.:common#Int |Int]] r, [[.:common#Int |Int]] n)''** :: ? Parameters: :: ''[[.:common#Int |Int]]'' ''r'' :: ''[[.:common#Int |Int]]'' ''n'': Set the rank of a given node ---- ==== no category ==== {{anchor:doublyconnectededgelist:}} ? **''DoublyConnectedEdgeList''** ::UNDOCUMENTED ----