Graphs

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.

Abstract type for graphs, possibly with data attributes.

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

Abstract type for reflexive graphs, possibly with data attributes.

Abstract type for symmetric graph, possibly with data attributes.

Abstract type for symmetric reflexive graphs, possibly with data attributes.

Abstract type for symmetric weights graphs.

Abstract type for weighted graphs.

A graph, also known as a directed multigraph.

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

A reflexive graph.

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

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

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

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

A symmetric weighted graph.

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

A weighted graph.

A graph in which every edge has a numerical weight.

Involution on edge(s) in a symmetric graph.

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.

Add multiple dangling edges to a half-edge graph.

Add an edge to a graph.

Add multiple edges to a graph.

Add a vertex to a graph.

Add multiple vertices to a graph.

Union of in-neighbors and out-neighbors in a graph.

Edges in a graph, or between two vertices in a graph.

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

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

Whether the graph has the given vertex.

Subgraph induced by a set of a vertices.

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

In-neighbors of vertex in a graph.

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

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

Number of vertices in a graph.

Out-neighbors of vertex in a graph.

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

Remove an edge from a graph.

Remove multiple edges from a graph.

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.

Remove multiple vertices from a graph.

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

Source vertex (vertices) of edges(s) in a graph.

Target vertex (vertices) of edges(s) in a graph.

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

Vertices in a graph.

Weight(s) of edge(s) in a weighted graph.

Embedded graphs, represented as C-sets.

The term embedded graph is used as in topological graph theory, graph drawing, and related fields to mean a combinatorial structure representing a graph embedded in an (oriented) surface, up to equivalence under (orientation-preserving) homeomorphism.

Add corolla to rotation graph, rotation system, or similar structure.

A corolla is a vertex together with its incident half-edges, the number of which is its valence. The rotation on the half-edges is the consecutive one induced by the half-edge part numbers.

Pair together half-edges into edges.

Trace edges of rotation system or similar, return a listing of cycles.

Usually the cycles will be pairs of half edges but in a hypermap the cycles can be arbitrary.

Trace faces of rotation system or similar, returning list of cycles.

Trace vertices of rotation system or similar, returning a list of cycles.

Edge permutation of rotation system or similar structure.

Vertex permutation of rotation system or similar structure.

Face permutation of rotation system or similar structure.

Abstract type for graph with properties.

Concrete types are PropertyGraph and SymmetricPropertyGraph.

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

See also: SymmetricPropertyGraph.

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

Properties of edge in a property graph.

Get property of edge or edges in a property graph.

Get graph-level property of a property graph.

Get property of vertex or vertices in a property graph.

Graph-level properties of a property graph.

Set property of edge or edges in a property graph.

Set multiple properties of an edge in a property graph.

Set graph-level property in a property graph.

Set multiple graph-level properties in a property graph.

Set property of vertex or vertices in a property graph.

Set multiple properties of a vertex in a property graph.

Properties of vertex in a property graph.

Algorithms on graphs based on C-sets.

Projection onto (weakly) connected components of a graph.

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

(Weakly) connected components of a graph.

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

Topological sort of a directed acyclic graph.

The depth-first search algorithm is adapted from the function topological_sort_by_dfs in LightGraphs.jl.

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.