Navigation

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: common

Objects

User Functions

  •  

    Combinatorics

    These functions capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

    •  
      complement_graph (G) → Graph

      Creates the complement graph of a graph.

      Parameters
      GraphG
      Returns
      Graph
    •  
      connectivity (graph) → Int

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

      Parameters
      props::Graph<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 graoh not to be connected anymore.
    •  
      eigenvalues_laplacian (G) → Vector<Float>

      Compute the eigenvalues of the discrete laplacian a graph.

      Parameters
      GraphG
      Returns
      Vector<Float>

      Example:
      • > $v = eigenvalues_laplacian(cycle_graph(4));> print $v; 4 2 2 0
    •  
      incidence_matrix (G) → SparseMatrix<Int>

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

      Parameters
      GraphG
      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
    •  
      laplacian (G) → SparseMatrix<Rational>

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

      Parameters
      GraphG
      Returns
      SparseMatrix<Rational>

      Example:
      • > $I = laplacian(cycle_graph(4));> print $I; 2 -1 1 0 -1 2 0 1 1 0 2 1 0 -1 1 2
    •  
      line_graph (G) → Graph

      Creates the line graph of a graph.

      Parameters
      GraphG
      Returns
      Graph
    •  
      maximal_chains (F) → IncidenceMatrix

      Computes the set of maximal chains of a FaceLattice object. Note that all such chains begin at the bottom node and end in nodes of dimension F->dim()

      Parameters
      FaceLatticeF
      Returns
      IncidenceMatrix
      Each row is a maximal chain, indices refer to nodes of the FaceLattice
    •  
      signed_incidence_matrix (G) → SparseMatrix<Int>

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

    Comparing

    These clients are concerned with automorphisms of graphs and determining whether graphs are isomorphic.

    •  
      automorphisms (graph) → Array<Array<Int>>

      Find the automorphism group of the graph.

      Parameters
      props::Graphgraph
      Returns
      Array<Array<Int>>
      each element encodes a node permutation.

      Example:
      • We first create the vertex-edge graph of the square and then print its automorphism group:> $g=new props::Graph(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.
      Depends on: bliss or nauty
    •  
      automorphisms (m) → Array<Pair<Array<Int>,Array<Int>>>

      Find the automorphism group of the non-symmetric incidence matrix.

      Parameters
      IncidenceMatrix<NonSymmetric>m
      Returns
      Array<Pair<Array<Int>,Array<Int>>>
      each element encodes a permutation of its rows (first) and columns (second).

      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.
      Depends on: bliss or nauty
    •  
      automorphisms (m) → Array<Array<Int>>

      Find the automorphism group of the symmetric incidence matrix.

      Parameters
      IncidenceMatrix<Symmetric>m
      Returns
      Array<Array<Int>>
      each element encodes a permutation of its rows (=columns).
      Depends on: bliss or nauty
    •  
      canonical_form (g) → props::Graph

      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
      props::Graphg
      Returns
      props::Graph
      Depends on: bliss or nauty
    •  
      canonical_hash (g, k) → Int

      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
      props::Graphg
      Intk
      a key for the hash computation, default value 2922320
      Returns
      Int
      Depends on: bliss or nauty
    •  
      find_node_permutation (graph1, graph2) → Array<Int>

      Find the node permutation mapping graph1 to graph2. If the given graphs are not isomorphic, throw an expection.

      Parameters
      props::Graphgraph1
      props::Graphgraph2
      Returns
      Array<Int>
      Depends on: bliss or nauty
    •  
      find_row_col_permutation (m1, m2) → Pair<Array<Int>,Array<Int>>

      Find the permutations mapping the non-symmetric incidence matrix m1 to m2. If the given matrices are not isomorphic, throw an expection.

      Parameters
      IncidenceMatrix<NonSymmetric>m1
      IncidenceMatrix<NonSymmetric>m2
      Returns
      Pair<Array<Int>,Array<Int>>
      first permutation applies to the rows, second applies to the columns

      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>
      Depends on: bliss or nauty
    •  
      isomorphic (IncidenceMatrix1, IncidenceMatrix2) → Bool

      true if IncidenceMatrix1 and IncidenceMatrix2 are isomorphic.

      Parameters
      IncidenceMatrixIncidenceMatrix1
      IncidenceMatrixIncidenceMatrix2
      Returns
      Bool

      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); 1
      Depends on: bliss or nauty
    •  
      isomorphic (graph1, graph2) → Bool

      true if graph1 and graph2 are isomorphic.

      Parameters
      props::Graphgraph1
      props::Graphgraph2
      Returns
      Bool

      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); 1
      Depends on: bliss or nauty
    •  
      n_automorphisms (graph) → Int

      Find the order of the automorphism group of the graph.

      Parameters
      props::Graphgraph
      Returns
      Int
      the order of the automorphism group

      Example:
      • > print n_automorphisms(cycle_graph(5)->ADJACENCY); 2
      Depends on: bliss or nauty
  •  

    Other

    Special purpose functions.

    •  
      all_spanningtrees (G) → Array<Set<int>>

      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.
      Parameters
      GraphG
      beeing connected
      Returns
      Array<Set<int>>
    •  
      edge_lengths (G, coords) → EdgeMap

      Compute the lengths of all edges of a given graph G from the coordinates coords of its nodes.

      Parameters
      props::Graph<Directed>G
      the input graph
      Matrixcoords
      the coordinates of the nodes
      Returns
      EdgeMap
    •  
      graph_from_edges (edges) → Graph

      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}
    •  
      hungarian_perfect_matching (weights) → Array

      Vector representation of the permutation corresponding to a perfect matching in a weighted bipartite graph.

      Parameters
      Matrixweights
      Returns
      Array

      Example:
      • The following computes a matching in a small bipartite weighted graph:> $M = new Matrix(['inf',2,'inf',1],[2,'inf',1,'inf'],['inf',1,'inf',8],[1,'inf',8,'inf']);> print hungarian_perfect_matching($M); 3 2 1 0
  •  

    Producing a graph

    With these clients you can create special examples of graphs, graphs belonging to parameterized families and random graphs.

    •  
      complete (n) → Graph

      Constructs a complete graph on n nodes.

      Parameters
      Intn
      Returns
      Graph
    •  
      complete_bipartite (k, l) → Graph

      Constructs a complete bipartite graph on k + l nodes.

      Parameters
      Intk
      Intl
      Returns
      Graph
    •  
      cycle_graph (n) → Graph

      Constructs a cycle graph on n nodes.

      Parameters
      Intn
      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 (n, k, i) → Graph

      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
      Intn
      the size of the ground set
      Intk
      the size of the subsets
      Inti
      the size of the subsets
      Returns
      Graph
    •  
      johnson_graph (n, k) → Graph

      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
      Intn
      the size of the ground set
      Intk
      the size of the subsets
      Returns
      Graph
    •  
      kneser_graph (n, k) → Graph

      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
      Intn
      the size of the ground set
      Intk
      the size of the subsets
      Returns
      Graph
    •  
      neighborhood_graph (D, delta) → Graph

      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)
      Rationaldelta
      the maximal distance of neighbored vertices
      Returns
      Graph
    •  
      path_graph (n) → Graph

      Constructs a path graph on n nodes.

      Parameters
      Intn
      Returns
      Graph
    •  
      petersen () → Graph

      Constructs the Petersen graph.

      Returns
      Graph
    •  
      random_graph (n) → Graph

      Constructs a random graph with n nodes according to the Erdos-Renyi model. Each edge is chosen uniformly with probability p.

      Parameters
      Intn
      Options
      Rationalp
      the probability of an edge occurring; default 1/2
      Booltry_connected
      whether to try to generate a connected graph, default 1
      Intmax_attempts
      If connected is set, specifies how many times to try to make a connected random graph before giving up.
      Intseed
      controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.
      Returns
      Graph
  •  

    Visualization

    These functions are for visualization.

    •  
      clip_graph (G, V, BB) → GeometricGraph

      Clip a graph with respect to a given bounding box. Used for the visualization of Voronoi diagrams.

      Parameters
      GraphG
      MatrixV
      MatrixBB
      Returns
      GeometricGraph
    •  
      hd_embedder (label_width)

      Create an embedding of the Hasse diagram 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
      Arraylabel_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
      Booldual
      the node representing the empty face is put on the topmost level
      Floateps
      calculation accuracy.
      Intseed
      effects the initial placement of the nodes.
    •  
      LEDA_graph (G)

      Write a graph in LEDA input format.

      Parameters
      props::GraphG
    •  
      metapost (vis_obj ...)

      Produce a MetaPost input file with given visual objects.

      Parameters
      Visual::Objectvis_obj ...
      objects to display
      Options
      StringFile
      "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.
    •  
      spring_embedder (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
      props::Graph<Undirected>graph
      to be embedded.
      Options
      affecting the desired picture
      EdgeMapedge_weights
      relative edge lengths. By default the embedding algorithm tries to stretch all edges to the same length.
      Vectorz-ordering
      an objective function provides an additional force along the z-axis, trying to rearrange nodes in the order of the function growth.
      Floatz-factor
      gain coefficient applied to the z-ordering force.
      Intseed
      random seed for initial node placement on a unit sphere.
      calculation fine-tuning
      Floatscale
      enlarges the ideal edge length
      Floatbalance
      changes the balance between the edge contraction and node repulsion forces
      Floatinertion
      affects how the nodes are moved, can be used to restrain oscillations
      Floatviscosity
      idem
      Floateps
      a threshold for point movement between iterations, below that it is considered to stand still
      Intmax-iterations
      hard limit for computational efforts. The algorithm terminates at latest after that many iterations regardless of the convergence achieved so far.

Common Option Lists