application: graph

The application graph deals with directed and undirected graphs. They can be defined abstractly as a set of nodes and EDGES or for instance as the vertex-edge graph of a polytope.

imports from: common

Objects

User Functions

  •  
    UNDOCUMENTED
    •  
      degree_sequence (G)

      Calculate the degree sequence and the average degree. The degree sequence is encoded as a map with entries (degree, multiplicity)

      Parameters
      GraphG
  •  
    UNDOCUMENTED
    •  
      incidence_matrix () → SparseMatrix<Int>

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

    •  
      laplacian (G) → Matrix

      creates the Laplacian matrix of a graph

      Parameters
      GraphG
      Returns
      Matrix
    •  
      line_graph (G) → Graph

      creates the line graph of a graph

      Parameters
      GraphG
      Returns
      Graph
    •  
      signed_incidence_matrix () → 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.

  •  
    UNDOCUMENTED
  •  
    UNDOCUMENTED
    •  
      kneser_graph (n, k)

      Create the Kneser graph on parameters (n,k) It has one node for each set in binomial{[n]}{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
  •  
    UNDOCUMENTED
    •  
      connectivity (graph) → Int

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

      Parameters
      props::Graph<Undirected>graph
      Returns
      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
      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
  •  
    UNDOCUMENTED
    •  
      complete (n) → Graph

      Constructs a complete graph with n nodes.

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

      Constructs a complete bipartite graph with k + l nodes.

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

      Constructs a cycle graph with n nodes.

      Parameters
      Intn
      Returns
      Graph
    •  
      path_graph (n) → Graph

      Constructs a path graph with 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
  •  
    UNDOCUMENTED
    •  
      hungarian_perfect_matching (weights) → Array

      vector representation of permutation corresponding to perfect matching in bipartite weighted graph.

      Parameters
      Matrixweights
      Returns
      Array
  •  
    UNDOCUMENTED
    •  
      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
    •  
      graphviz (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::Objectvis_obj ...
      objects to display
      Options
      StringFile
      "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.
    •  
      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 ()

      Write a graph in LEDA input format.

    •  
      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

  •  
    UNDOCUMENTED
    •  
      Visual::Graph::decorations

      Attributes modifying the appearance of graphs

      imports from: Visual::Wire::decorations, Visual::PointSet::decorations

      Options
      Matrix<Float>Coord
      2-d or 3-d coordinates of the nodes. If not specified, a random embedding is generated using a pseudo-physical spring model
      Flexible<RGB>NodeColor
      alias for PointColor
      Flexible<Float>NodeThickness
      alias for PointThickness
      Flexible<RGB>NodeBorderColor
      alias for PointBorderColor
      Flexible<Float>NodeBorderThickness
      alias for PointBorderThickness
      Flexible<String>NodeStyle
      alias for PointStyle
      StringNodeLabels
      alias for PointLabels
    •  
      Visual::Lattice::decorations

      Attributes modifying the appearance of face lattices

      imports from: Visual::Graph::decorations, Visual::Wire::decorations, Visual::PointSet::decorations

      Options
      Flexible<Int>ArrowStyle
      How to draw directed edges: 0 (like undirected), 1 (with an arrow pointing towards the edge), or -1 (with an arrow pointing against the edge). Default is 1.
      Array<String>AtomLabels
      Labels of atoms, to use as building blocks for node labels. By default the ordinal numbers are taken.