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.
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

UNDOCUMENTED

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


An undirected graph with given node coordinates and a bounding box
Properties of GeometricGraph

BOUNDING_BOX: common::Matrix<Scalar, NonSymmetric>
Since a Voronoi polyhedron is unbounded it must be artificially bounded for visualization purposes. Allowed is any set of hyperplanes which makes the projection onto the last d1 coordinates bounded. By default, these are the vertical facets of a suitably scaled cube.



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

CHARACTERISTIC_POLYNOMIAL: common::UniPolynomial<Rational, Int>
Characteristic polynomial of the adjacency matrix; its roots are the eigenvalues









SIGNED_INCIDENCE_MATRIX: common::SparseMatrix<Int, NonSymmetric>
Signed vertexedge incidence matrix; for undirected graphs, the orientation comes from the lexicographic order of the nodes.
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.


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
Graph G


UNDOCUMENTED

incidence_matrix () → SparseMatrix<Int>

line_graph (G) → Graph

signed_incidence_matrix () → SparseMatrix<Int>
Compute the signed vertexedge incidence matrix of the graph. in case of undirected graphs, the orientation of the edges is induced by the order of the nodes.
Returns
SparseMatrix<Int>


UNDOCUMENTED

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 (IncidenceMatrix1, IncidenceMatrix2) → Bool
true if IncidenceMatrix1 and IncidenceMatrix2 are isomorphic.

isomorphic (graph1, graph2) → Bool

n_automorphisms (graph) → Int
Find the order of the automorphism group of the graph.


UNDOCUMENTED

kneser_graph (n, k)


UNDOCUMENTED

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


UNDOCUMENTED

complete_bipartite (k, l) → Graph

cycle_graph (n) → Graph

path_graph (n) → Graph

random_graph (n) → Graph
Constructs a random graph with n nodes according to the ErdosRenyi model. Each edge is chosen uniformly with probability p.
Parameters
Int n Options
Rational p the probability of an edge occurring; default 1/2Bool try_connected whether to try to generate a connected graph, default 1Int max_attempts If connected is set, specifies how many times to try to make a connected random graph before giving up.Int seed 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.


UNDOCUMENTED

clip_graph (G, V, BB) → GeometricGraph
Clip a graph with respect to a given bounding box. Used for the visualization of Voronoi diagrams.

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

UNDOCUMENTED

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.
