[[application: graph]]

# 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

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

    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

    Int | seed | random seed value for the node placement
    option list: | Visual::Lattice::decorations

    ##### Returns

    Visual::Lattice |

  - VISUAL_DUAL () → Visual::Lattice

    Visualize the dual FaceLattice.

    ##### Options

    Int | seed | 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

  - ADJACENCY: common::Graph<Dir>

    combinatorial description of the Graph in the form of adjacency matrix

  - CONNECTED: common::Bool

    True if the graph is a connected graph.

  - CONNECTED_COMPONENTS: common::PowerSet<Int>

    The connected components, encoded as node sets.

  - DIAMETER: common::Int

    The diameter of the graph.

  - NODE_DEGREES: common::Array<Int>

    Degrees of nodes in the graph.

  - NODE_LABELS: common::Array<String>

    Labels of the nodes of the graph.

  - N_CONNECTED_COMPONENTS: common::Int

    Number of CONNECTED_COMPONENTS of the graph.

  - N_EDGES: common::Int

    Number of EDGES of the graph.

  - N_NODES: common::Int

    Number of nodes of the 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>> |

  - ###
    Visualization

  - 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

- NodePerm
  UNDOCUMENTED

  #### Properties of NodePerm

  - PERMUTATION: common::Array<Int>

    Transforming this ADJACENCY into the basic object

- ###
  Graph<Directed>

  derived from: Graph

  #### Properties of Graph<Directed>

  - NODE_IN_DEGREES: common::Array<Int>

    The number of incoming edges of the graph nodes.

  - NODE_OUT_DEGREES: common::Array<Int>

    The number of outgoing edges of the graph nodes.

- ###
  Graph<Undirected>

  derived from: Graph

  #### Properties of Graph<Undirected>

  - BIPARTITE: common::Bool

    True if the graph is a bipartite.

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

  - MAX_CLIQUES: common::PowerSet<Int>

    The maximal cliques of the graph, encoded as node sets.

  - SIGNATURE: common::Int

    Difference of the black and white nodes if the graph is BIPARTITE. Otherwise -1.

  - TRIANGLE_FREE: common::Bool

    Determine whether the graph has triangles or not.

## User Functions

- ###
  Comparing

- automorphisms (graph) → Array<Array<Int>>

  Find the automorphism group of the graph.

  ##### Parameters

  props::Graph | graph |

  ##### Returns

  Array<Array<Int>> | each element encodes a node permutation.

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

  ##### Parameters

  props::Graph | graph1 |
  props::Graph | graph2 |

  ##### Returns

  Array<Int> |

- 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

  true if graph1 and graph2 are isomorphic.

  ##### Parameters

  props::Graph | graph1 |
  props::Graph | graph2 |

  ##### Returns

  Bool |

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

- ###
  Visualization

- 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

- ###
  Visualization

- Visual::Graph::decorations

  Attributes modifying the appearance of graphs

  imports from: Visual::Wire::decorations, Visual::PointSet::decorations

  ##### 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 model
  Flexible<RGB> | NodeColor | alias for PointColor
  Flexible<Float> | NodeThickness | alias for PointThickness
  Flexible<RGB> | NodeBorderColor | alias for PointBorderColor
  Flexible<Float> | NodeBorderThickness | alias for PointBorderThickness
  Flexible<String> | NodeStyle | alias for PointStyle
  String | NodeLabels | alias for PointLabels

- Visual::Lattice::decorations

  Attributes modifying the appearance of face lattices

  imports from: Visual::Graph::decorations, Visual::Wire::decorations, Visual::PointSet::decorations

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