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

  •  

    Graph

    A graph with optional node and edge attributes.

    Properties of Graph

    User Methods of Graph

    •  
      EDGES (G) → Array<Set<Int>>

      Explore the graph as a sequence of its edges.

      Parameters
      Graph G
      Returns
      Array<Set<Int>>
    •  
      VISUAL () → Visual::Graph

      Visualizes the graph. Decorations may include Coord, disabling the default spring embedder.

      Options
      Int seed
      random seed value for the spring embedder
      option list: Visual::Graph::decorations
      Returns
      Visual::Graph
  • Permutations of Graph

  •  

    Graph<Directed>

    derived from: Graph

    Properties of Graph<Directed>

  •  

    Graph<Undirected>

    derived from: Graph

    Properties of Graph<Undirected>

  • User Functions

  •  
  •  
    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
    Matrix coords
    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
  •  
  •  
    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::Object vis_obj ...
    objects to display
    Options
    String File
    "filename" or "AUTO" Store the graph description in a DOT source file without starting the interactive GUI. The .dot suffix is automatically added to the file name.
    Specify AUTO if you want the filename be automatically derived from the drawing title.
    You can also use any expression allowed for the open function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe.
  •  
    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
    Array label_width
    estimates (better upper bounds) of the label width of each node. The computed layout guarantees that the distances between the nodes in a layer are at least equal to the widest label in this layer.
    Options
    Bool dual
    the node representing the empty face is put on the topmost level
    Float eps
    calculation accuracy.
    Int seed
    effects the initial placement of the nodes.
  •  
    LEDA_graph ()

    Write a graph in LEDA input format.

  •  
    metapost (vis_obj ...)

    Produce a MetaPost input file with given visual objects.

    Parameters
    Visual::Object vis_obj ...
    objects to display
    Options
    String File
    "filename" or "AUTO" The MetaPost description always has to be stored in a file, there is no interactive viewer for this kind of visualization.
    For the file name you can use any expression allowed for the open function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe. Real file names are automatically completed with the .mp suffix if needed.
    The default setting "AUTO" lets the file name be derived from the drawing title. The automatically generated file name is displayed in the verbose mode.
  •  
    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
    EdgeMap edge_weights
    relative edge lengths. By default the embedding algorithm tries to stretch all edges to the same length.
    Vector z-ordering
    an objective function provides an additional force along the z-axis, trying to rearrange nodes in the order of the function growth.
    Float z-factor
    gain coefficient applied to the z-ordering force.
    Int seed
    random seed for initial node placement on a unit sphere.
    calculation fine-tuning
    Float scale
    enlarges the ideal edge length
    Float balance
    changes the balance between the edge contraction and node repulsion forces
    Float inertion
    affects how the nodes are moved, can be used to restrain oscillations
    Float viscosity
    idem
    Float eps
    a threshold for point movement between iterations, below that it is considered to stand still
    Int max-iterations
    hard limit for computational efforts. The algorithm terminates at latest after that many iterations regardless of the convergence achieved so far.
  • Common Option Lists