# Graphs

`Catlab.Graphs.BasicGraphs`

— ModuleData 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 Graphs.jl, with some departures due to differences between the data structures.

`Catlab.Graphs.BasicGraphs.AbstractGraph`

— TypeAbstract type for graphs, aka directed multigraphs.

`Catlab.Graphs.BasicGraphs.AbstractHalfEdgeGraph`

— TypeAbstract type for half-edge graphs, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractLabeledGraph`

— TypeAbstract type for labeled graphs.

`Catlab.Graphs.BasicGraphs.AbstractReflexiveGraph`

— TypeAbstract type for reflexive graphs, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractSymmetricGraph`

— TypeAbstract type for symmetric graph, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractSymmetricReflexiveGraph`

— TypeAbstract type for symmetric reflexive graphs, possibly with data attributes.

`Catlab.Graphs.BasicGraphs.AbstractSymmetricWeightedGraph`

— TypeAbstract type for symmetric weighted graphs.

`Catlab.Graphs.BasicGraphs.AbstractWeightedGraph`

— TypeAbstract type for weighted graphs.

`Catlab.Graphs.BasicGraphs.Graph`

— TypeA graph, also known as a directed multigraph.

`Catlab.Graphs.BasicGraphs.HalfEdgeGraph`

— TypeA half-edge graph.

Half-edge graphs are a variant of undirected graphs whose edges are pairs of "half-edges" or "darts". Half-edge graphs are isomorphic to symmetric graphs but have a different data model.

`Catlab.Graphs.BasicGraphs.HasGraph`

— TypeAbstract 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.HasVertices`

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

`Catlab.Graphs.BasicGraphs.LabeledGraph`

— TypeA labeled graph.

By convention, a "labeled graph" without qualification is a vertex-labeled graph. We do not require that the label be unique, and in this data type, the label attribute is not indexed.

`Catlab.Graphs.BasicGraphs.ReflexiveGraph`

— TypeA reflexive graph.

Reflexive graphs are graphs in which every vertex has a distinguished self-loop.

`Catlab.Graphs.BasicGraphs.SymmetricGraph`

— TypeA symmetric graph, or graph with an orientation-reversing edge involution.

Symmetric graphs are closely related, but not identical, to undirected graphs.

`Catlab.Graphs.BasicGraphs.SymmetricReflexiveGraph`

— TypeA symmetric reflexive graph.

Symmetric reflexive graphs are both symmetric graphs (`SymmetricGraph`

) and reflexive graphs (`ReflexiveGraph`

) such that the reflexive loops are fixed by the edge involution.

`Catlab.Graphs.BasicGraphs.SymmetricWeightedGraph`

— TypeA symmetric weighted graph.

A symmetric graph in which every edge has a numerical weight, preserved by the edge involution.

`Catlab.Graphs.BasicGraphs.WeightedGraph`

— TypeA weighted graph.

A graph in which every edge has a numerical weight.

`Base.inv`

— MethodInvolution on half-edge(s) in a half-edge graph.

`Base.inv`

— MethodInvolution on edge(s) in a symmetric graph.

`Catlab.Graphs.BasicGraphs.add_dangling_edge!`

— MethodAdd 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.add_dangling_edges!`

— MethodAdd multiple dangling edges to a half-edge graph.

`Catlab.Graphs.BasicGraphs.add_edge!`

— MethodAdd an edge to a graph.

`Catlab.Graphs.BasicGraphs.add_edges!`

— MethodAdd multiple edges to a graph.

`Catlab.Graphs.BasicGraphs.add_vertex!`

— MethodAdd a vertex to a graph.

`Catlab.Graphs.BasicGraphs.add_vertices!`

— MethodAdd multiple vertices to a graph.

`Catlab.Graphs.BasicGraphs.add_vertices_with_indices!`

— MethodAdd vertices with preallocated src/tgt indexes

`Catlab.Graphs.BasicGraphs.all_neighbors`

— MethodUnion of in-neighbors and out-neighbors in a graph.

`Catlab.Graphs.BasicGraphs.degree`

— MethodTotal degree of a vertex

Equivalent to length(all_neighbors(g,v)) but faster

`Catlab.Graphs.BasicGraphs.edges`

— MethodEdges in a graph, or between two vertices in a graph.

`Catlab.Graphs.BasicGraphs.half_edges`

— MethodHalf-edges in a half-edge graph, or incident to a vertex.

`Catlab.Graphs.BasicGraphs.has_edge`

— MethodWhether the graph has the given edge, or an edge between two vertices.

`Catlab.Graphs.BasicGraphs.has_vertex`

— MethodWhether the graph has the given vertex.

`Catlab.Graphs.BasicGraphs.induced_subgraph`

— MethodSubgraph induced by a set of a vertices.

The induced subgraph consists of the given vertices and all edges between vertices in this set.

`Catlab.Graphs.BasicGraphs.inedges`

— MethodEdges coming into a vertex

`Catlab.Graphs.BasicGraphs.inneighbors`

— MethodIn-neighbors of vertex in a graph.

`Catlab.Graphs.BasicGraphs.ne`

— MethodNumber 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.neighbors`

— MethodNeighbors 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.nv`

— MethodNumber of vertices in a graph.

`Catlab.Graphs.BasicGraphs.outedges`

— MethodEdges coming out of a vertex

`Catlab.Graphs.BasicGraphs.outneighbors`

— MethodOut-neighbors of vertex in a graph.

`Catlab.Graphs.BasicGraphs.refl`

— MethodReflexive loop(s) of vertex (vertices) in a reflexive graph.

`Catlab.Graphs.BasicGraphs.rem_edge!`

— MethodRemove an edge from a graph.

`Catlab.Graphs.BasicGraphs.rem_edges!`

— MethodRemove multiple edges from a graph.

`Catlab.Graphs.BasicGraphs.rem_vertex!`

— MethodRemove 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.BasicGraphs.rem_vertices!`

— MethodRemove multiple vertices from a graph.

Edges incident to any of the vertices are treated as in `rem_vertex!`

.

`Catlab.Graphs.BasicGraphs.vertex`

— MethodIncident vertex (vertices) of half-edge(s) in a half-edge graph.

`Catlab.Graphs.BasicGraphs.vertices`

— MethodVertices in a graph.

`Catlab.Graphs.BasicGraphs.weight`

— MethodWeight(s) of edge(s) in a weighted graph.

`Catlab.Theories.src`

— MethodSource vertex (vertices) of edges(s) in a graph.

`Catlab.Theories.tgt`

— MethodTarget vertex (vertices) of edges(s) in a graph.

`Catlab.Graphs.PropertyGraphs.AbstractPropertyGraph`

— TypeAbstract type for graph with properties.

Concrete types are `PropertyGraph`

and `SymmetricPropertyGraph`

.

`Catlab.Graphs.PropertyGraphs.PropertyGraph`

— TypeGraph 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.PropertyGraphs.SymmetricPropertyGraph`

— TypeSymmetric graphs with properties.

The edge properties are preserved under the edge involution, so these can be interpreted as "undirected" property (multi)graphs.

See also: `PropertyGraph`

.

`Catlab.Graphs.PropertyGraphs.eprops`

— MethodProperties of edge in a property graph.

`Catlab.Graphs.PropertyGraphs.get_eprop`

— MethodGet property of edge or edges in a property graph.

`Catlab.Graphs.PropertyGraphs.get_gprop`

— MethodGet graph-level property of a property graph.

`Catlab.Graphs.PropertyGraphs.get_vprop`

— MethodGet property of vertex or vertices in a property graph.

`Catlab.Graphs.PropertyGraphs.gprops`

— MethodGraph-level properties of a property graph.

`Catlab.Graphs.PropertyGraphs.set_eprop!`

— MethodSet property of edge or edges in a property graph.

`Catlab.Graphs.PropertyGraphs.set_eprops!`

— MethodSet multiple properties of an edge in a property graph.

`Catlab.Graphs.PropertyGraphs.set_gprop!`

— MethodSet graph-level property in a property graph.

`Catlab.Graphs.PropertyGraphs.set_gprops!`

— MethodSet multiple graph-level properties in a property graph.

`Catlab.Graphs.PropertyGraphs.set_vprop!`

— MethodSet property of vertex or vertices in a property graph.

`Catlab.Graphs.PropertyGraphs.set_vprops!`

— MethodSet multiple properties of a vertex in a property graph.

`Catlab.Graphs.PropertyGraphs.vprops`

— MethodProperties of vertex in a property graph.

`Catlab.Graphs.GraphAlgorithms`

— ModuleAlgorithms on graphs based on C-sets.

`Catlab.Graphs.GraphAlgorithms.connected_component_projection`

— FunctionProjection onto (weakly) connected components of a graph.

Returns a function in FinSet{Int} from the vertex set to the set of components.

`Catlab.Graphs.GraphAlgorithms.connected_components`

— Method(Weakly) connected components of a graph.

Returns a vector of vectors, which are the components of the graph.

`Catlab.Graphs.GraphAlgorithms.enumerate_paths`

— MethodEnumerate all paths of an acyclic graph, indexed by src+tgt

`Catlab.Graphs.GraphAlgorithms.topological_sort`

— MethodTopological sort of a directed acyclic graph.

The depth-first search algorithm is adapted from the function `topological_sort_by_dfs`

in Graphs.jl.

`Catlab.Graphs.GraphAlgorithms.transitive_reduction!`

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