GitHub

Graphs

Catlab.Graphs.BasicGraphs — Module

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

source
Catlab.Graphs.BasicGraphs.HasGraph — Type

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.

source
Catlab.Graphs.BasicGraphs.HasVertices — Type

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.

source
Catlab.Graphs.BasicGraphs.LabeledGraph — Type

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

source
Base.inv — Method

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

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

source
Catlab.Graphs.BasicGraphs.add_loops! — Method

Adds loops to a graph

Setting the keyword idempotent::Bool=true will skip adding loops on vertices which already have them. These loops may canonically become reflexive edges by converting the Graph to an AbstractReflexiveGraph 

convert(AbstractReflexiveGraph, g)

however this will throw an error if any vertex has more than one loop.

source
Catlab.Graphs.BasicGraphs.ne — Method

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

source
Catlab.Graphs.BasicGraphs.neighbors — Method

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

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

source
Catlab.Graphs.BipartiteGraphs — Module

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

source
Catlab.Graphs.BipartiteGraphs.UndirectedBipartiteGraph — Type

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

source
Catlab.Graphs.NamedGraphs — Module

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

source
Catlab.Graphs.PropertyGraphs.PropertyGraph — Type

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.

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

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

source
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

  • 1ifkis 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).

  1. Consider each vertex s in turn, along with the edge to its ith nearest neighbor t, in a clockwise sense.

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

source