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 vertexedge graph of a polytope.
imports from: common
Objects

Lattice represented as a directed acyclic graph.
Properties of FaceLattice

DIMS: common::Array<Int>
Indices of the first nodes in each level. Intended for internal use only; please use nodes_of_dim instead

FACES: common::NodeMap<Directed, Set<Int>>
Each node of the FaceLattice corresponds to a face. The node attribute is a set of vertices comprising the face. Incident edges lead to the containing faces of the next (higher) dimension.
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>

top_node ()
Index of the node representing the whole thing


VISUAL_DUAL () → Visual::Lattice
Visualize the dual FaceLattice.
Options
Int seed random seed value for the node placementoption list: Visual::Lattice::decorations Returns
Visual::Lattice


A graph with optional node and edge attributes.
Properties of Graph

ADJACENCY: common::Graph<Dir>
combinatorial description of the Graph in the form of adjacency matrix








User Methods of Graph

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

Permutations of Graph

NodePerm
UNDOCUMENTED
Properties of NodePerm




derived from: Graph
Properties of Graph<Undirected>


CONNECTIVITY: common::Int
Node connectivity of the graph, that is, the minimal number of nodes to be removed from the graph such that the result is disconnected.


SIGNATURE: common::Int
Difference of the black and white nodes if the graph is BIPARTITE. Otherwise 1.



A Graph with lengths on the edges and a subset of the nodes that is labeled.
Properties of WeightedLabeledGraph

COORDINATES: common::NodeMap<Undirected, Vector<Scalar>>
Coordinates to (exactly) realise the graph in Euclidean space.



LABELED_NODES_MAP: common::Array<Int>
ith entry is 1 if the ith node is not labeled and equal to the index of the labeled node otherwise.


METRIC: common::Matrix<Scalar, NonSymmetric>
The metric defined by the shortest paths between labeled nodes.


User Methods of WeightedLabeledGraph


smallest_subgraph (G) → WeightedLabeledGraph
Produces the subgraph of G with shortest TOTAL_LENGTH that still realises the same metric between the LABELED_NODES.



VISUAL () → Visual::Graph
Visualizes the graph putting on the right labels and using the explicit edge lengths as starting weights for the spring embedder in order to achieve them as good as possible.
Options
Int seed random seed value for the string embedderoption list: Visual::Graph::decorations Returns
Visual::Graph 
VISUAL () → Visual::Graph
Visualizes the graph putting on the right labels and using the explicitely available coordinates.
Options
option list: Visual::Graph::decorations Returns
Visual::Graph


User Functions


automorphisms (graph) → Array<Array<Int>>
Find the automorphism group of the graph.

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). 
automorphisms (m) → Array<Pair<Array<Int>,Array<Int>>>
Find the automorphism group of the nonsymmetric 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
). 
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.

find_row_col_permutation (m1, m2) → Pair<Array<Int>,Array<Int>>
Find the permutations mapping the nonsymmetric 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. 
isomorphic (graph1, graph2) → Bool



connectivity (graph) → Int
Compute the connectivity of a given graph using the FordFulkerson flow algorithm.

edge_lengths (G, coords) → EdgeMap
Compute the lengths of all edges of a given graph G from the coordinates coords of its nodes.

graph_from_edges (edges) → Graph

metric_from_graph (g, labeled) → Matrix
Computes the distances defined by the shortest path distance between the labeled nodes in g.



complete_bipartite (k, l) → Graph

rand_tree_split_system (n) → Array<Set<Int>>
Constructs a split system defining random binary tree with n (labeled) leaves.
Parameters
Int n Options
Int seed controls the outcome of the random number generator; fixing a seed number guarantees the same outcome.Returns
Array<Set<Int>>


graphviz (vis_obj ...)
Draw the given graph or face lattice object using graphviz program
neato
ordot
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 theneato
ordot
program manually.Parameters
Visual::Object vis_obj ... objects to displayOptions
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 theopen
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 yspace 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 levelFloat 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 displayOptions
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 theopen
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 3d embedding for the graph using the spring embedding algorithm along the lines of
Thomas Fruchtermann and Edward Reingold:Graph Drawing by Forcedirected Placement.Software Practice and Experience Vol. 21, 11291164 (1992), no. 11.Parameters
props::Graph<Undirected> graph to be embedded.Options
affecting the desired pictureEdgeMap edge_weights relative edge lengths. By default the embedding algorithm tries to stretch all edges to the same length.Vector zordering an objective function provides an additional force along the zaxis, trying to rearrange nodes in the order of the function growth.Float zfactor gain coefficient applied to the zordering force.Int seed random seed for initial node placement on a unit sphere.calculation finetuningFloat scale enlarges the ideal edge lengthFloat balance changes the balance between the edge contraction and node repulsion forcesFloat inertion affects how the nodes are moved, can be used to restrain oscillationsFloat viscosity idemFloat eps a threshold for point movement between iterations, below that it is considered to stand stillInt maxiterations hard limit for computational efforts. The algorithm terminates at latest after that many iterations regardless of the convergence achieved so far.

Common Option Lists


Visual::Graph::decorationsimports from: Visual::Wire::decorations, Visual::PointSet::decorations
Attributes modifying the appearance of graphs
Options
Matrix<Float> Coord 2d or 3d coordinates of the nodes. If not specified, a random embedding is generated using a pseudophysical spring modelFlexible<RGB> NodeColor alias for PointColorFlexible<Float> NodeThickness alias for PointThicknessFlexible<RGB> NodeBorderColor alias for PointBorderColorFlexible<Float> NodeBorderThickness alias for PointBorderThicknessFlexible<String> NodeStyle alias for PointStyleString NodeLabels alias for PointLabels 
Visual::Lattice::decorationsimports from: Visual::Graph::decorations, Visual::Wire::decorations, Visual::PointSet::decorations
Attributes modifying the appearance of face lattices
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.
