# Graphs

`Catlab.Graphs.BasicGraphs`

— ModuleData structures for graphs, based on C-sets.

This module provides the category theorist's four basic kinds of graphs: graphs (aka directed multigraphs), symmetric graphs, reflexive graphs, and symmetric reflexive graphs. It also defines half-edge graphs, which are isomorphic to symmetric graphs, and a few standard kinds of attributed graphs, such as weighted graphs.

The graphs 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.BipartiteGraphs`

— ModuleBipartite graphs, directed and undirected, as C-sets.

A graph theorist might call these "bipartitioned graphs," as in a graph *equipped with* a bipartition, as opposed to "bipartite graphs," as in a graph that *can be* bipartitioned. Here we use the former notion, which is more natural from the structuralist perspective, but the latter terminology, which is shorter and more familiar.

`Catlab.Graphs.BipartiteGraphs.AbstractBipartiteGraph`

— TypeAbstract type for bipartite graphs.

`Catlab.Graphs.BipartiteGraphs.AbstractUndirectedBipartiteGraph`

— TypeAbstract type for undirected bipartite graphs.

`Catlab.Graphs.BipartiteGraphs.BipartiteGraph`

— TypeA bipartite graph, better known as a bipartite directed multigraph.

Directed bipartite graphs are isomorphic to port hypergraphs and to whole grain Petri nets.

`Catlab.Graphs.BipartiteGraphs.HasBipartiteGraph`

— TypeAbstract type for C-sets that contain a (directed) bipartite graph.

`Catlab.Graphs.BipartiteGraphs.HasBipartiteVertices`

— TypeAbstract type for C-sets that contain a bipartition of vertices.

`Catlab.Graphs.BipartiteGraphs.UndirectedBipartiteGraph`

— TypeAn undirected bipartite graph.

It is a matter of perspective whether to consider such graphs "undirected," in the sense that the edges have no orientation, or "unidirected," in the sense that all edges go from vertices of type 1 to vertices of type 2.

`Catlab.Graphs.BipartiteGraphs.add_edges₁₂!`

— MethodAdd edges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_edges₂₁!`

— MethodAdd edges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_edge₁₂!`

— MethodAdd edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_edge₂₁!`

— MethodAdd edge from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertex₁!`

— MethodAdd a vertex of type 1 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertex₂!`

— MethodAdd a vertex of type 2 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertices₁!`

— MethodAdd vertices of type 1 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.add_vertices₂!`

— MethodAdd vertices of type 2 to a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.edges₁₂`

— MethodEdges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.edges₂₁`

— MethodEdges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.ne₁₂`

— MethodNumber of edges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.ne₂₁`

— MethodNumber of edges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.nv₁`

— MethodNumber of vertices of type 1 in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.nv₂`

— MethodNumber of vertices of type 2 in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edges₁₂!`

— MethodRemove edges from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edges₂₁!`

— MethodRemove edges from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edge₁₂!`

— MethodRemove edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_edge₂₁!`

— MethodRemove edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertex₁!`

— MethodRemove vertex of type 1 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertex₂!`

— MethodRemove vertex of type 2 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertices₁!`

— MethodRemove vertices of type 1 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.rem_vertices₂!`

— MethodRemove vertices of type 2 from a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.src₁`

— MethodSource vertex of edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.src₂`

— MethodSource vertex of edge from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.tgt₁`

— MethodTarget vertex of edge from V₂ to V₁ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.tgt₂`

— MethodTarget vertex of edge from V₁ to V₂ in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.vertices₁`

— MethodVertices of type 1 in a bipartite graph.

`Catlab.Graphs.BipartiteGraphs.vertices₂`

— MethodVertices of type 2 in a bipartite graph.

`Catlab.Graphs.NamedGraphs`

— ModuleExtends the basic graph types with vertex and/or edge names.

Naming vertices and edges and looking them up by name is a common requirement. This module provides a simple interface and default graph types for named graphs. Names are understood to be unique within the graph but are *not* assumed to be strings or symbols.

`Catlab.Graphs.NamedGraphs.AbstractNamedGraph`

— TypeAbstract type for graph with named vertices and edges.

`Catlab.Graphs.NamedGraphs.NamedGraph`

— TypeGraph with named vertices and edges.

`Catlab.Graphs.NamedGraphs.edge_name`

— MethodName of an edge in a graph.

By default, the name of an edge is its ID.

`Catlab.Graphs.NamedGraphs.edge_named`

— MethodGet edge in graph with given name.

`Catlab.Graphs.NamedGraphs.has_edge_names`

— MethodWhether a graph has edge names distinct from its edge IDs.

`Catlab.Graphs.NamedGraphs.has_vertex_names`

— MethodWhether a graph has vertex names distinct from its vertex IDs.

`Catlab.Graphs.NamedGraphs.vertex_name`

— MethodName of a vertex in a graph.

By default, the name of a vertex is its ID.

`Catlab.Graphs.NamedGraphs.vertex_named`

— MethodGet vertex in graph with given name.

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

`Catlab.Graphs.GraphGenerators.complete_graph`

— MethodComplete graph on $n$ vertices.

`Catlab.Graphs.GraphGenerators.cycle_graph`

— MethodCycle graph on $n$ vertices.

When $n = 1$, this is a loop graph.

`Catlab.Graphs.GraphGenerators.erdos_renyi`

— Method`erdos_renyi(GraphType, n, ne)`

Create an Erdős–Rényi random graph with `n`

vertices and `ne`

edges.

**References**

- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl

`Catlab.Graphs.GraphGenerators.erdos_renyi`

— Method`erdos_renyi(GraphType, n, p)`

Create an Erdős–Rényi random graph with `n`

vertices. Edges are added between pairs of vertices with probability `p`

.

**Optional Arguments**

`seed=-1`

: set the RNG seed.`rng`

: set the RNG directly

**References**

- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl

`Catlab.Graphs.GraphGenerators.expected_degree_graph`

— Method`expected_degree_graph(GraphType, ω)`

Given a vector of expected degrees `ω`

indexed by vertex, create a random undirected graph in which vertices `i`

and `j`

are connected with probability `ω[i]*ω[j]/sum(ω)`

.

**Optional Arguments**

`seed=-1`

: set the RNG seed.`rng`

: set the RNG directly

**Implementation Notes**

The algorithm should work well for `maximum(ω) << sum(ω)`

. As `maximum(ω)`

approaches `sum(ω)`

, some deviations from the expected values are likely.

**References**

- Connected Components in Random Graphs with Given Expected Degree Sequences, Linyuan Lu and Fan Chung. https://link.springer.com/article/10.1007%2FPL00012580
- Efficient Generation of Networks with Given Expected Degrees, Joel C. Miller and Aric Hagberg. https://doi.org/10.1007/978-3-642-21286-4_10
- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl#L187

`Catlab.Graphs.GraphGenerators.parallel_arrows`

— MethodGraph with two vertices and $n$ parallel edges.

`Catlab.Graphs.GraphGenerators.path_graph`

— MethodPath graph on $n$ vertices.

`Catlab.Graphs.GraphGenerators.star_graph`

— MethodStar graph on $n$ vertices.

In the directed case, the edges point outward.

`Catlab.Graphs.GraphGenerators.watts_strogatz`

— Method`watts_strogatz(n, k, β)`

Return a Watts-Strogatz small world random graph with `n`

vertices, each with expected degree `k`

(or `k

- 1
`if`

k`is odd). Edges are randomized per the model based on probability`

β`.

The algorithm proceeds as follows. First, a perfect 1-lattice is constructed, where each vertex has exacly `div(k, 2)`

neighbors on each side (i.e., `k`

or `k - 1`

in total). Then the following steps are repeated for a hop length `i`

of `1`

through `div(k, 2)`

.

Consider each vertex

`s`

in turn, along with the edge to its`i`

th nearest neighbor`t`

, in a clockwise sense.Generate a uniformly random number

`r`

. If`r ≥ β`

, then the edge`(s, t)`

is left unaltered. Otherwise, the edge is deleted and*rewired*so that`s`

is connected to some vertex`d`

, chosen uniformly at random from the entire graph, excluding`s`

and its neighbors. (Note that`t`

is a valid candidate.)

For `β = 0`

, the graph will remain a 1-lattice, and for `β = 1`

, all edges will be rewired randomly.

**Optional Arguments**

`is_directed=false`

: if true, return a directed graph.`seed=-1`

: set the RNG seed.

**References**

- Collective dynamics of ‘small-world’ networks, Duncan J. Watts, Steven H. Strogatz. https://doi.org/10.1038/30918
- Small Worlds, Duncan J. watts. https://en.wikipedia.org/wiki/Special:BookSources?isbn=978-0691005416
- https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/SimpleGraphs/generators/randgraphs.jl#L187

`Catlab.Graphs.GraphGenerators.wheel_graph`

— MethodWheel graph on $n$ vertices.

In the directed case, the outer cycle is directed and the spokes point outward.