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
-
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.
-
-
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 non-symmetric 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 non-symmetric 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 Ford-Fulkerson 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
-
-
-
-
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 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 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 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 pictureEdgeMap 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-tuningFloat 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 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
-
-
Visual::Graph::decorationsimports from: Visual::Wire::decorations, Visual::PointSet::decorations
Attributes modifying the appearance of graphs
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 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.
-