Catlab.WiringDiagrams API

Catlab.WiringDiagrams API

Generic data structure for wiring diagrams (aka, string diagrams).

A (directed) wiring diagram consists of a collection of boxes with input and output ports connected by wires. A box can be atomic (possessing no internal structure) or can itself be a wiring diagram. Thus, wiring diagrams can be nested recursively. Wiring diagrams are closely related to what the CS literature calls "directed graphs with ports" or more simply "port graphs". The main difference is that a wiring diagram has an "outer box": a wiring diagram has its own ports that can be connected to the ports of its boxes.

This module offers a generic data structure for wiring diagrams. Arbitrary data can be attached to the boxes, ports, and wires of a wiring diagram. There is a low-level interface for direct manipulation of boxes and wires and a high-level interface based on the theory of symmetric monoidal categories.

The wiring diagrams in this module are "abstract" in the sense that they cannot be directly rendered as raster or vector graphics. However, they form a useful intermediate representation that can be straightforwardly serialized to and from GraphML or translated into Graphviz or other declarative diagram languages.

source

Base type for any box (node) in a wiring diagram.

This type represents an arbitrary black box with inputs and outputs.

source

An atomic box in a wiring diagram.

These boxes have no internal structure.

source

Create box for a morphism generator.

source

A port on a box to which wires can be connected.

source

Kind of port: input or output.

source

Error thrown when the source and target ports of a wire are incompatible.

source

List of ports: object in the category of wiring diagrams.

source

A wire connecting one port to another.

source

Wiring diagram: morphism in the category of wiring diagrams.

The wiring diagram is implemented using the following internal data structures. A LightGraphs DiGraph stores the "skeleton" of the diagram: a simple directed graph with the boxes as vertices and with an edge between two vertices iff there is at least one wire between the corresponding boxes. There are two special vertices, accessible via input_id and output_id, representing the input and output ports, respectively.

The DiGraph is wrapped inside a MetaDiGraph to attach properties to the vertices and edges. For each edge, an edge property stores the list of wires between the source and target boxes.

source

Create empty wiring diagram with given domain and codomain objects.

source

Simultaneous encapsulation of boxes.

source

Encapsulate multiple boxes within a single sub wiring diagram.

This operation is a (one-sided) inverse to subsitution (see substitute!).

source

Retrieve the underlying LightGraphs graph.

Do not mutate it! All mutations should pass through the WiringDiagram methods: add_box!, rem_box!, etc.

source

Get all wires coming into the port.

source

Get all wires coming into the box.

source

Check equality of wiring diagram under permutation of boxes.

When the boxes in the first diagram d1 are permuted according to σ, does it become identical to the second diagram d2?

source

Get all wires coming out of the port.

source

Get all wires coming out of the box.

source

Create wiring diagram with a single box connected to the outer ports.

source

Simultaneous substitution of wiring diagrams for vertices.

source

Substitute a wiring diagram for a vertex.

This operation is the operadic composition of wiring diagrams.

source

Check compatibility of source and target ports.

Throws a PortValueError when the ports are incompatible. The default implementation of this method is a no-op.

source

Get all wires coming into or out of the box.

source

Wiring diagram as monoidal category with diagonals and codiagonals.

source

Internal data structure corresponding to Port. Do not use directly.

source

Internal data structure corresponding to Wire. Do not use directly.

source
Base.:==Method.

Check equality of wiring diagrams.

Warning: This method checks exact equality of the underlying graph representation, not mathematical equality which involves graph isomorphism.

See also: is_permuted_equal

source

The insertion phase of a substitution operation.

source

Create input and output ports for encapsulating box.

Any port of the boxes vs that has an incoming (resp. outgoing) wire from a box outside of vs will become an input (resp. output) port of the encapsulating box.

A set of box ports connected to the same (set of) outside ports will be simplified into a single port of the encapsulating box. This simplification is only relevant when duplication or merging is used, as in a cartesian or cocartesian category.

source

Data structure for connecting one layer to another by wires.

This module defines a generic data structure to represent a wiring between one layer of input ports and another layer of output ports. A wiring layer forms a bipartite graph with independent edge sets the input ports and the output ports.

Wiring layers are an auxillary data structure. They are not very interesting in their own right, but they can be a useful intermediate representation. For example, a morphism expression comprising generators, compositions, products, and wiring layers is intermediate between a pure GAT expression (which has no wiring layers, but may have identities, braidings, copies, etc.) and a wiring diagram, which is purely graphical.

source

Number of input or output ports in a layer.

Object in the category of wiring layers.

source

Connection by wires of one layer to another.

Morphism in the category of wiring layers.

source

Completely connected wiring layer.

The layer's underlying graph is the complete bipartite graph.

source

Convert a wiring layer into a wiring diagram.

source

Wiring layer representing the wires between two boxes in a wiring diagram.

source

Wiring layers as monoidal category with diagonals and codiagonals.

source

Algorithms operating on wiring diagrams.

source

Junction node in a wiring diagram.

Used to explicitly represent copies, merges, deletions, and creations.

source

Add junction nodes to wiring diagram.

Transforms from implicit to explicit representation of (co)diagonals.

source

Crossing minimization by sorting a univariate statistic.

The boxes in sources and/or targets are fixed and the boxes in vs are permuted. A permutation σ of the latter is returned, such that vs[σ] are the sorted box IDs. Both one-sided and two-sided crossing minimization are supported, depending on whether just one, or both, of sources and targets are given.

In this simple but popular heuristic algorithm, the boxes are permuted by sorting a univariate statistic of the positions of incoming and/or outgoing wires. Typical choices are:

  • mean: the sample mean, yielding the "barycenter method"
  • median: the sample median

In both cases, this algorithm has the property that if there is a permutation with no crossings, it will find it.

source

Put a wiring diagram for a cartesian category into normal form.

This function puts a wiring diagram representing a morphism in a free cartesian category into normal form. Copies and deletions are simplified as much as possible.

source

Normalize copies in a wiring diagram.

This function maximizes sharing of intermediate computations in a wiring diagram where copies are natural.

This algorithm is basically the same as the congruence closure algorithm on term graphs, in the special case of the empty relation R = ∅ (Baader & Nipkow, 1998, Term Rewriting and All That, Sec. 4.4). The main difference is the possibility of zero or many function outputs.

source

Normalize deletions in a wiring diagram.

This function removes all unused intermediate computations in a wiring diagram where deletion is natural.

source

Remove junction nodes from wiring diagram.

Transforms from explicit to implicit representation of (co)diagonals.

source

Topological sort of boxes in wiring diagram.

Returns a list of box IDs, excluding the outer box's input and output IDs.

source

Make function mapping ports to logical coordinates.

source

Serialize abstract wiring diagrams as GraphML.

Serialization of box, port, and wire values can be overloaded by data type (see convert_to_graphml_data and convert_from_graphml_data).

GraphML is the closest thing to a de jure and de facto standard in the space of graph data formats, supported by a variety of graph applications and libraries. We depart mildly from the GraphML spec by allowing JSON data attributes for GraphML nodes, ports, and edges.

References:

  • GraphML Primer: http://graphml.graphdrawing.org/primer/graphml-primer.html
  • GraphML DTD: http://graphml.graphdrawing.org/specification/dtd.html
source

Generate GraphML representing a wiring diagram.

source

Parse a wiring diagram from a GraphML string or XML document.

source

Read a wiring diagram from a GraphML file.

source

Write a wiring diagram to a file as GraphML.

source

Parse an attributed graph from a GraphML string or XML document.

The equivalent of NetworkX's parse_graphml function.

source

Read an attributed graph (MetaGraph) from a GraphML file.

The equivalent of NetworkX's read_graphml function.

source

Conventions for serialization of wiring diagrams.

Defines a consistent set of names for boxes, ports, and wires to be used when serializing wiring diagrams, as well as conventions for serializing box, port, and wire attributes.

source

Serialize abstract wiring diagrams as JSON.

JSON data formats are convenient when programming for the web. Unfortunately, no standard for JSON graph formats has gained any kind of widespread adoption. We adopt a format compatible with that used by the KEILER project and its successor ELK (Eclipse Layout Kernel). This format is roughly feature compatible with GraphML, supporting nested graphs and ports. It also supports layout information like node position and size.

References:

  • KEILER's JSON graph format: https://rtsys.informatik.uni-kiel.de/confluence/display/KIELER/JSON+Graph+Format
  • ELK's JSON graph format: https://www.eclipse.org/elk/documentation/tooldevelopers/graphdatastructure/jsonformat.html
source

Generate a JSON dict representing a wiring diagram.

source

Parse a wiring diagram from a JSON string or dict.

source

Read a wiring diagram from a JSON file.

source

Write a wiring diagram to a file as JSON.

source

Deserialize abstract wiring diagram from yFiles.

Reads a wiring diagram from the GraphML dialect used by yEd and yFiles. Unlike the GraphML spec, the yEd data model does not explicitly include ports:

  • https://yed.yworks.com/support/qa/102/
  • https://yed.yworks.com/support/qa/2531/

We infer the ports of boxes and their order from the geometry of the diagram. Thus, this module has the nature of a hack. While it may be useful for interactive and exploratory work, it should not be used in a production system.

source

Parse a wiring diagram from a GraphML string or XML doc created by yFiles.

source

Read a wiring diagram from a GraphML file created by yEd and yFiles.

source