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 for instance as the vertex-edge graph of a polytope.


imports from: common

Objects

  •  

    FaceLattice

    Lattice represented as a directed acyclic graph.

    derived from: Graph<Directed>

    Properties of FaceLattice

    User Methods of FaceLattice

    •  
      bottom_node ()

      Index of the node representing the empty face

    •  
      dim ()

      Dimension of the lattice = number of levels - 1

    •  
      nodes_of_dim () → Set<Int>

      Indices of nodes representing faces of the given dimension

      Returns
      Set<Int>
    •  
      top_node ()

      Index of the node representing the whole thing

    •  

      Visualization
    •  
      VISUAL () → Visual::Lattice

      Visualize the FaceLattice.

      Options
      Intseed
      random seed value for the node placement
      option list:Visual::Lattice::decorations
      Returns
      Visual::Lattice
    •  
      VISUAL_DUAL () → Visual::Lattice

      Visualize the dual FaceLattice.

      Options
      Intseed
      random seed value for the node placement
      option list:Visual::Lattice::decorations
      Returns
      Visual::Lattice
  •  

    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
      GraphG
      Returns
      Array<Set<Int>>
    •  

      Visualization
    •  
      VISUAL () → Visual::Graph

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

      Options
      Intseed
      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

  •  

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

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