Graphs

Catlab.Graphs.BasicGraphsModule

Data structures for graphs, based on C-sets.

Provides the category theorist's four basic kinds of graphs: graphs (aka directed multigraphs), symmetric graphs, reflexive graphs, and symmetric reflexive graphs. Also defines half-edge graphs. The API generally follows that of LightGraphs.jl, with some departures due to differences between the data structures.

Catlab.Graphs.BasicGraphs.HasGraphType

Abstract type for C-sets that contain a graph.

This type encompasses C-sets where the schema for graphs is a subcategory of C. This includes, for example, graphs, symmetric graphs, and reflexive graphs, but not half-edge graphs.

Catlab.Graphs.BasicGraphs.HasVerticesType

Abstract type for C-sets that contain vertices.

This type encompasses C-sets where the schema C contains an object V interpreted as vertices. This includes, for example, graphs and half-edge graphs, but not bipartite graphs or wiring diagrams.

Base.invMethod

Involution on half-edge(s) in a half-edge graph.

Base.invMethod

Involution on edge(s) in a symmetric graph.

Catlab.Graphs.BasicGraphs.add_dangling_edge!Method

Add a dangling edge to a half-edge graph.

A "dangling edge" is a half-edge that is paired with itself under the half-edge involution. They are usually interpreted differently than "self-loops", i.e., a pair of distinct half-edges incident to the same vertex.

Catlab.Graphs.BasicGraphs.neMethod

Number of edges in a graph, or between two vertices in a graph.

In a symmetric graph, this function counts both edges in each edge pair, so that the number of edges in a symmetric graph is twice the number of edges in the corresponding undirected graph (at least when the edge involution has no fixed points).

Catlab.Graphs.BasicGraphs.neighborsMethod

Neighbors of vertex in a graph.

In a graph, this function is an alias for outneighbors; in a symmetric graph, a vertex has the same out-neighbors and as in-neighbors, so the distinction is moot.

In the presence of multiple edges, neighboring vertices are given with multiplicity. To get the unique neighbors, call unique(neighbors(g)).

Catlab.Graphs.BasicGraphs.rem_vertex!Method

Remove a vertex from a graph.

When keep_edges is false (the default), all edges incident to the vertex are also deleted. When keep_edges is true, incident edges are preserved but their source/target vertices become undefined.

Catlab.Graphs.PropertyGraphs.PropertyGraphType

Graph with properties.

"Property graphs" are graphs with arbitrary named properties on the graph, vertices, and edges. They are intended for applications with a large number of ad-hoc properties. If you have a small number of known properties, it is better and more efficient to create a specialized C-set type using @acset_type.

See also: SymmetricPropertyGraph.

Catlab.Graphs.GraphAlgorithms.transitive_reduction!Method

Transitive reduction of a DAG.

The algorithm computes the longest paths in the DAGs and keeps only the edges corresponding to longest paths of length 1. Requires a topological sort, which is computed if it is not supplied.