Reference

NamedGraphs

An extension of Graphs.jl providing graph types with named vertices. The vertices of a NamedGraph or NamedDiGraph can be strings, tuples, or any other names, rather than the contiguous integers of a Graphs.SimpleGraph. Named graphs aim to implement the functionality of Graphs.jl accounting for named vertices and edges, so see the Graphs.jl documentation for the available functionality. Not all of it is wrapped yet: for performance, functions are usually implemented by translating to the integer vertices and forwarding to the Graphs.jl implementation, which assumes contiguous integer vertices, so they have to be wrapped one at a time. Please raise an issue if functionality you need is missing.

See also NamedGraphs.PartitionedGraphs for partitioned graphs and their quotient graphs.

AbstractNamedGraph{V} <: Graphs.AbstractGraph{V}

Abstract type for graphs whose vertices are names of type V rather than contiguous integers. Subtypes implement the Graphs.jl interface in terms of a graph on integer vertex codes through encoded_graph, encoded_vertex, and decoded_vertex. The developer interface page of the documentation covers what a subtype has to define.

EncodedGraphView(graph::AbstractNamedGraph)

An AbstractGraph{Int} presenting graph on its vertex codes 1:nv(graph), for graph types that compute their topology directly rather than storing an integer graph. Such a type can return EncodedGraphView(graph) from encoded_graph and must then define nv, ne, has_vertex, has_edge, edges, and the neighbor hooks itself, since the view answers every query by asking graph.

NamedDiGraph(vertices)
NamedDiGraph(simple_graph::AbstractSimpleGraph, vertices)

A directed graph whose vertices are the names in vertices, backed by a Graphs.SimpleDiGraph on the integer vertex codes. When constructed from a simple graph, the ith name corresponds to the vertex i of simple_graph, and otherwise the graph starts with no edges.

Examples

julia> using Graphs: add_edge!, has_edge

julia> using NamedGraphs: NamedDiGraph

julia> g = NamedDiGraph(["a", "b"]);

julia> add_edge!(g, "a" => "b")
true

julia> has_edge(g, "a", "b")
true

julia> has_edge(g, "b", "a")
false

NamedEdge(src, dst)
NamedEdge(src => dst)

An edge between two named vertices, the edge type of NamedGraph and NamedDiGraph.

NamedGraph(vertices)
NamedGraph(simple_graph::AbstractSimpleGraph, vertices)

An undirected graph whose vertices are the names in vertices, backed by a Graphs.SimpleGraph on the integer vertex codes. When constructed from a simple graph, the ith name corresponds to the vertex i of simple_graph, and otherwise the graph starts with no edges.

Examples

julia> using Graphs: add_edge!, has_edge, ne, nv, path_graph

julia> using NamedGraphs: NamedGraph

julia> g = NamedGraph(["a", "b", "c", "d"]);

julia> add_edge!(g, "a" => "b")
true

julia> has_edge(g, "b", "a")
true

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> (nv(g), ne(g))
(4, 3)

rem_vertices!(graph::AbstractNamedGraph, vs)

Remove the vertices vs from graph in place, along with their incident edges, returning how many were removed. A vertex not in graph does not count.

This is a method of Graphs.rem_vertices!, and it deliberately differs from the Graphs.SimpleGraph and SimpleDiGraph methods, the only ones Graphs.jl provides, which throw for a vertex outside 1:nv(graph) and return a vector mapping new vertex labels back to old ones. Named vertices are stable under removal, so there is nothing to map, and a name that is not present is simply not removed.

Examples

julia> using Graphs: ne, rem_vertices!, vertices

julia> using NamedGraphs: named_path_graph

julia> g = named_path_graph(3);

julia> rem_vertices!(g, [2, 4])
1

julia> (collect(vertices(g)), ne(g))
([1, 3], 0)

add_vertices!(graph::AbstractNamedGraph, vs)

Add the vertices vs to graph in place, returning how many were added. A vertex already in graph is not added and does not count.

This is a method of Graphs.add_vertices!, whose other form takes a count of vertices to append. A named graph cannot invent names, so an integer here is a vertex name rather than a count.

Examples

julia> using Graphs: add_vertices!, vertices

julia> using NamedGraphs: NamedGraph

julia> g = NamedGraph([1, 2, 3]);

julia> add_vertices!(g, [3, 4])
1

julia> collect(vertices(g))
4-element Vector{Int64}:
 1
 2
 3
 4

julia> add_vertices!(g, 5) # Integers are iterable, so equivalent to add_vertices!(g, [5])
1

dijkstra_shortest_paths(graph::AbstractNamedGraph, vs, distmx = weights(graph))

Compute shortest paths in graph from the source vertices vs, returning a path state whose parents, dists, and pathcounts are keyed by vertex name.

vs is a collection of sources, so a single source is passed as a one-element collection. A bare vertex is a different thing: [(1, 1)] is the one source (1, 1), while (1, 1) is read as the two sources 1 and 1, and "ab" as the two sources 'a' and 'b'.

This is a method of Graphs.dijkstra_shortest_paths, whose other form takes a single integer source. An integer here is a vertex name rather than a vertex code, and a bare integer means one source.

Examples

julia> using Graphs: dijkstra_shortest_paths

julia> using NamedGraphs: named_grid

julia> g = named_grid((2, 2));

julia> state = dijkstra_shortest_paths(g, [(1, 1)]); # One source

julia> state.dists[(2, 2)]
2

julia> state = dijkstra_shortest_paths(g, [(1, 1), (2, 2)]); # Two sources

julia> state.dists[(2, 2)]
0

edges(graph::AbstractNamedGraph) -> Graphs.AbstractEdgeIter

A Graphs.AbstractEdgeIter over the edges of graph, yielding each edge exactly once.

It can be iterated, so it works in a for loop and with collect. length gives the number of edges and eltype gives the edge type of the graph, generally NamedEdge{V} for a graph with vertex type V. Membership testing with in matches has_edge, so on an undirected graph an edge and its reverse are both members even though iteration yields each edge once.

The iteration order is an implementation detail of how the graph stores its edges and is not part of the interface.

The concrete type is currently NamedGraphs.NamedEdgeIter, which may change.

The output is a live view of the graph: do not rely on it across mutations of the graph.

Examples

julia> using Graphs: edges, path_graph

julia> using NamedGraphs: NamedEdge, NamedGraph

julia> g = NamedGraph(path_graph(3), ["a", "b", "c"]);

julia> for e in edges(g)
           println(e)
       end
"a" => "b"
"b" => "c"

julia> length(edges(g))
2

julia> eltype(edges(g))
NamedEdge{String}

julia> collect(edges(g))
2-element Vector{NamedEdge{String}}:
 "a" => "b"
 "b" => "c"

julia> NamedEdge("b" => "a") in edges(g)
true

neighbors(graph::AbstractNamedGraph, vertex) -> AbstractVector

The neighbors of vertex in graph, as vertex names. On a directed graph these are the out-neighbors, following the Graphs.jl convention. inneighbors, outneighbors, and all_neighbors select the other directions and behave the same way in every other respect.

Examples

julia> using Graphs: all_neighbors, inneighbors, neighbors, path_digraph

julia> using NamedGraphs: NamedDiGraph

julia> g = NamedDiGraph(path_digraph(3), ["a", "b", "c"]);

julia> neighbors(g, "b")
1-element Vector{String}:
 "c"

julia> inneighbors(g, "b")
1-element Vector{String}:
 "a"

julia> all_neighbors(g, "b")
2-element Vector{String}:
 "a"
 "c"

vertices(graph::AbstractNamedGraph) -> Dictionaries.AbstractIndices

The set of vertices of graph: a Dictionaries.AbstractIndices containing each vertex exactly once, with fast membership testing. See Dictionaries.jl for that interface.

The vertices iterate in insertion order: they appear in the order they were added to the graph, removing a vertex does not reorder the rest, and added vertices appear at the end. The iteration order therefore does not in general match the vertex codes after removals, since codes are reassigned. Use decoded_vertex for the vertices in code order, for example map(c -> decoded_vertex(graph, c), 1:nv(graph)).

The output is a live read-only view of the graph: do not mutate it directly, and do not rely on it (or containers sharing its state) across mutations of the graph.

Examples

Removing a vertex does not reorder the rest, but it does reassign codes, so the two orders come apart:

julia> using Graphs: nv, path_graph, rem_vertex!, vertices

julia> using NamedGraphs: NamedGraph, decoded_vertex

julia> g = NamedGraph(path_graph(4), ["v1", "v2", "v3", "v4"]);

julia> rem_vertex!(g, "v2");

julia> collect(vertices(g))
3-element Vector{String}:
 "v1"
 "v3"
 "v4"

julia> [decoded_vertex(g, c) for c in 1:nv(g)]
3-element Vector{String}:
 "v1"
 "v4"
 "v3"

add_edge(graph::AbstractNamedGraph, edge)

A copy of graph with edge added, leaving graph itself alone. An edge naming a vertex that graph does not have is not added.

See also add_edges and Graphs.add_edge! for the in-place form.

Examples

julia> using Graphs: ne

julia> using NamedGraphs: NamedGraph, add_edge

julia> g = NamedGraph(["a", "b"]);

julia> h = add_edge(g, "a" => "b");

julia> (ne(g), ne(h))
(0, 1)

add_edges!(graph::AbstractNamedGraph, edges)

Add edges to graph in place, returning how many were added. An edge already in graph, or one naming a vertex graph does not have, is not added and does not count, following Graphs.add_edge!.

See also add_edges for the non-mutating form.

Examples

julia> using Graphs: ne

julia> using NamedGraphs: NamedGraph, add_edges!

julia> g = NamedGraph(["a", "b", "c"]);

julia> add_edges!(g, ["a" => "b", "b" => "c"])
2

julia> add_edges!(g, ["a" => "b", "a" => "z"])
0

julia> ne(g)
2

add_edges(graph::AbstractNamedGraph, edges)

A copy of graph with edges added. See also add_edges!.

Examples

julia> using Graphs: ne

julia> using NamedGraphs: NamedGraph, add_edges

julia> g = NamedGraph(["a", "b", "c"]);

julia> h = add_edges(g, ["a" => "b", "b" => "c"]);

julia> (ne(g), ne(h))
(0, 2)

add_vertex(graph::AbstractNamedGraph, vertex)

A copy of graph with vertex added, leaving graph itself alone. A vertex already in graph is not added again.

See also add_vertices and Graphs.add_vertex! for the in-place form.

Examples

julia> using Graphs: nv

julia> using NamedGraphs: NamedGraph, add_vertex

julia> g = NamedGraph(["a", "b"]);

julia> h = add_vertex(g, "c");

julia> (nv(g), nv(h))
(2, 3)

add_vertices(graph::AbstractNamedGraph, vs)

A copy of graph with the vertices vs added.

Examples

julia> using Graphs: nv

julia> using NamedGraphs: NamedGraph, add_vertices

julia> g = NamedGraph(["a", "b"]);

julia> h = add_vertices(g, ["c", "d"]);

julia> (nv(g), nv(h))
(2, 4)

all_edges(graph::AbstractNamedGraph)

Both directions of each edge of an undirected graph, each edge immediately followed by its reverse, or just the edges of a directed one. Useful where a value belongs to a direction rather than to an edge, such as a message on each directed edge.

Examples

julia> using NamedGraphs: all_edges, named_path_digraph, named_path_graph

julia> collect(all_edges(named_path_graph(3)))
4-element Vector{NamedEdge{Int64}}:
 1 => 2
 2 => 1
 2 => 3
 3 => 2

julia> collect(all_edges(named_path_digraph(3)))
2-element Vector{NamedEdge{Int64}}:
 1 => 2
 2 => 3

boundary_edges(graph::AbstractGraph, subgraph_vertices; dir=:out)

The edges of graph with one endpoint in subgraph_vertices and the other outside of it. dir orients the returned edges as in incident_edges, so by default each one points from the vertex inside to the vertex outside.

Examples

julia> using NamedGraphs: NamedEdge, boundary_edges, named_grid

julia> g = named_grid((2, 2));

julia> es = boundary_edges(g, [(1, 1), (1, 2)]);

julia> issetequal(es, [NamedEdge((1, 1) => (2, 1)), NamedEdge((1, 2) => (2, 2))])
true

convert_vertextype(V::Type, graph::AbstractGraph)
convert_vertextype(V::Type, G::Type{<:AbstractGraph})

graph with its vertices converted to type V, or the graph type G with its vertex type set to V. A graph or type that already has vertex type V is returned unchanged; any other case needs a method from the graph type.

See also vertextype.

decoded_edge(graph::AbstractNamedGraph, encoded_edge)

The edge of graph corresponding to the edge encoded_edge of encoded_graph(graph). Inverse of encoded_edge.

decoded_vertex(graph::AbstractNamedGraph, code::Integer)

The vertex of graph whose code is code, i.e. the vertex corresponding to the vertex code of encoded_graph(graph). Inverse of encoded_vertex.

Examples

julia> using Graphs: nv, path_graph

julia> using NamedGraphs: NamedGraph, decoded_vertex

julia> g = NamedGraph(path_graph(3), ["a", "b", "c"]);

julia> [decoded_vertex(g, c) for c in 1:nv(g)]
3-element Vector{String}:
 "a"
 "b"
 "c"

default_root_vertex(graph::AbstractGraph)

A vertex of graph of maximum eccentricity, used as the default root for spanning tree constructions and tree traversals.

directed_graph(graph::AbstractNamedGraph)

A directed version of graph, with each undirected edge replaced by a pair of edges pointing in both directions. An already directed graph is returned as-is.

See also undirected_graph.

Examples

julia> using Graphs: ne

julia> using NamedGraphs: directed_graph, named_path_graph, undirected_graph

julia> g = named_path_graph(3);

julia> ne(directed_graph(g))
4

julia> ne(undirected_graph(directed_graph(g)))
2

disjoint_union(graphs...)
disjoint_union(graphs::Vector)
disjoint_union(pairs::Pair...)
graph1 ⊔ graph2

The disjoint union of the graphs: their union after renaming each vertex v of the ith graph to (v, i), so that vertices shared between the inputs stay distinct in the output. Passing pairs i => graph names the graphs explicitly instead of by position.

Unicode ⊔ can be typed by writing \sqcup then pressing tab in the Julia REPL, and in many editors. This is an infix operator, allowing graph1 ⊔ graph2.

Only defined for graphs with named vertices, since it renames them (see rename_vertices).

Examples

julia> using Graphs: edges, path_graph, vertices

julia> using NamedGraphs: NamedEdge, NamedGraph, ⊔

julia> g = NamedGraph(path_graph(2), ["a", "b"]);

julia> h = g ⊔ g;

julia> collect(vertices(h))
4-element Vector{Tuple{String, Int64}}:
 ("a", 1)
 ("b", 1)
 ("a", 2)
 ("b", 2)

julia> collect(edges(h))
2-element Vector{NamedEdge{Tuple{String, Int64}}}:
 ("a", 1) => ("b", 1)
 ("a", 2) => ("b", 2)

eccentricities(graph::AbstractGraph, vs = vertices(graph), distmx = weights(graph))

The eccentricity of each vertex in vs, that is, the length of the longest shortest path from it to any other vertex, as eccentricity(graph, v, distmx) gives for one vertex. The output has one entry per element of vs, keyed the same way, so for the default vertices(graph) it is a Dictionary from vertex to eccentricity.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedGraph, eccentricities

julia> g = NamedGraph(path_graph(3), ["a", "b", "c"]);

julia> eccentricities(g)
3-element Dictionaries.Dictionary{String, Int64}:
 "a" │ 2
 "b" │ 1
 "c" │ 2

julia> eccentricities(g, ["a", "c"])
2-element Vector{Int64}:
 2
 2

edge_subgraph(graph::AbstractNamedGraph, edges)

The subgraph of graph spanned by edges, holding the vertices those edges touch and no edges besides edges themselves. See also subgraph, which is induced by a set of vertices and keeps every edge of graph between them.

Examples

julia> using Graphs: edges, vertices

julia> using NamedGraphs: edge_subgraph, named_grid

julia> g = edge_subgraph(named_grid((2, 2)), [(1, 1) => (2, 1), (1, 2) => (2, 2)]);

julia> collect(vertices(g))
4-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (1, 2)
 (2, 1)
 (2, 2)

julia> collect(edges(g))
2-element Vector{NamedEdge{Tuple{Int64, Int64}}}:
 (1, 1) => (2, 1)
 (1, 2) => (2, 2)

edgeless_graph(graph::AbstractNamedGraph)

A copy of graph with all of its edges removed, keeping its vertices. See also empty_graph, which removes the vertices as well.

Examples

julia> using Graphs: ne, nv

julia> using NamedGraphs: edgeless_graph, named_path_graph

julia> g = edgeless_graph(named_path_graph(3));

julia> (nv(g), ne(g))
(3, 0)

empty_graph(graph::AbstractNamedGraph)

A copy of graph with all of its vertices and edges removed. See also edgeless_graph, which keeps the vertices.

Examples

julia> using Graphs: ne, nv

julia> using NamedGraphs: empty_graph, named_path_graph

julia> g = empty_graph(named_path_graph(3));

julia> (nv(g), ne(g))
(0, 0)

encoded_edge(graph::AbstractNamedGraph, edge) -> AbstractEdge{Int}

The edge of encoded_graph(graph) corresponding to edge, i.e. the edge between the codes of the vertices of edge. Inverse of decoded_edge.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedEdge, NamedGraph, decoded_edge, encoded_edge

julia> g = NamedGraph(path_graph(3), ["a", "b", "c"]);

julia> ce = encoded_edge(g, NamedEdge("a" => "b"))
Edge 1 => 2

julia> decoded_edge(g, ce)
"a" => "b"

encoded_graph(graph::AbstractNamedGraph) -> AbstractGraph{Int}

The graph in coded form: a graph with the same topology as graph whose vertices are the codes 1:nv(graph) of the vertices of graph, i.e. it has the edge encoded_vertex(graph, u) => encoded_vertex(graph, v) if and only if graph has the edge u => v.

May be a stored field or a view of graph; mutate the graph only through graph.

A type that computes its topology directly rather than storing an integer graph can return EncodedGraphView(graph), and must then define nv, ne, has_vertex, has_edge, edges, and the neighbor hooks itself, since the view answers those by asking graph.

Examples

julia> using Graphs: edges, has_edge, path_graph, vertices

julia> using NamedGraphs: NamedGraph, encoded_graph, encoded_vertex

julia> g = NamedGraph(path_graph(3), ["a", "b", "c"]);

julia> cg = encoded_graph(g)
{3, 2} undirected simple Int64 graph

julia> vertices(cg)
Base.OneTo(3)

julia> collect(edges(cg))
2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 3

julia> encoded_vertex(g, "a"), encoded_vertex(g, "b")
(1, 2)

julia> has_edge(cg, 1, 2)
true

encoded_vertex(graph::AbstractNamedGraph, vertex) -> Int

The vertex of encoded_graph(graph) corresponding to vertex, i.e. its code in graph. encoded_vertex(graph, ·) and decoded_vertex(graph, ·) are inverse bijections between vertices(graph) and Base.OneTo(nv(graph)).

Codes are not stable across mutation: adding or removing vertices may reassign the codes of other vertices.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedGraph, decoded_vertex, encoded_vertex

julia> g = NamedGraph(path_graph(3), ["a", "b", "c"]);

julia> encoded_vertex(g, "b")
2

julia> decoded_vertex(g, 2)
"b"

forest_cover(graph::AbstractNamedGraph; spanning_tree=spanning_tree)

A vector of graphs, each a spanning forest over all the vertices of graph, whose edge sets partition the edges of graph. The forests are collected greedily, so their number is an upper bound on the arboricity rather than the minimum.

forest_cover_edge_sequence(graph::AbstractNamedGraph; root_vertex=default_root_vertex)

An ordering of the edges of graph that visits every edge in both directions, built by sweeping each tree of each forest of forest_cover inwards to its root in post_order_dfs_edges order and then back outwards. root_vertex is a function picking the root of each tree, such as default_root_vertex.

in_incident_edges(graph::AbstractGraph, vertex)

Edges of graph pointing into vertex, one for each in-neighbor. Equivalent to incident_edges with dir = :in.

incident_edges(graph::AbstractGraph, vertex; dir=:out)

Edges incident to the vertex vertex.

dir ∈ (:in, :out, :both), defaults to :out. The interface is similar to Graphs.adjacency_matrix.

For undirected graphs, returns all incident edges.

Examples

julia> using NamedGraphs: NamedEdge, incident_edges, named_grid

julia> g = named_grid((2, 2));

julia> incident_edges(g, (1, 1))
2-element Vector{NamedEdge{Tuple{Int64, Int64}}}:
 (1, 1) => (2, 1)
 (1, 1) => (1, 2)

is_leaf_vertex(graph::AbstractGraph, vertex)

Whether vertex is a leaf of graph: for an undirected graph, that it has exactly one neighbor; for a directed graph, that it has no children.

See also leaf_vertices.

leaf_vertices(graph::AbstractGraph)

The vertices of graph that are leaves in the sense of is_leaf_vertex.

Examples

julia> using NamedGraphs: leaf_vertices, named_comb_tree

julia> g = named_comb_tree((3, 2));

julia> issetequal(leaf_vertices(g), [(1, 2), (2, 2), (3, 2)])
true

named_binary_tree(k::Integer)

A named binary tree of depth k, with each vertex named by the path from the root as a vector of child indices: the root is [1], its children are [1, 1] and [1, 2], and so on.

named_comb_tree(dims::Tuple)
named_comb_tree(tooth_lengths::AbstractVector{<:Integer})

A named comb tree with dims[1] teeth of length dims[2], or teeth of the given lengths, with each vertex named by its coordinate tuple: (jx, jy) is the jyth vertex of tooth jx, and the (jx, 1) vertices form the backbone.

Examples

julia> using Graphs: edges, vertices

julia> using NamedGraphs: named_comb_tree

julia> g = named_comb_tree([2, 1]);

julia> collect(vertices(g))
3-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 1)
 (1, 2)

julia> collect(edges(g))
2-element Vector{NamedEdge{Tuple{Int64, Int64}}}:
 (1, 1) => (2, 1)
 (1, 1) => (1, 2)

named_cycle_graph(dim::Integer)

A named cycle graph on the vertices 1:dim.

named_grid(dims; periodic = false)
named_grid(dim::Integer; periodic = false)

A named grid graph of size dims, with each vertex named by its coordinate tuple, so the grid named_grid((2, 2)) has vertices (1, 1), (2, 1), (1, 2), and (2, 2). A single integer dim gives a one-dimensional grid on the vertices 1:dim. periodic = true connects the boundaries.

Examples

julia> using Graphs: edges, vertices

julia> using NamedGraphs: named_grid

julia> g = named_grid((2, 2));

julia> collect(vertices(g))
4-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 1)
 (1, 2)
 (2, 2)

julia> collect(edges(g))
4-element Vector{NamedEdge{Tuple{Int64, Int64}}}:
 (1, 1) => (2, 1)
 (1, 1) => (1, 2)
 (2, 1) => (2, 2)
 (1, 2) => (2, 2)

named_hexagonal_lattice_graph(m::Integer, n::Integer; periodic = false)

A named graph of a hexagonal tiling of the plane, with m rows and n columns of hexagons and each vertex named by its coordinate tuple. periodic = true tiles the torus instead. Based on the NetworkX generator hexagonal_lattice_graph.

named_path_digraph(dim::Integer)

A named directed path graph on the vertices 1:dim.

named_path_graph(dim::Integer)

A named path graph on the vertices 1:dim.

Examples

julia> using Graphs: edges, vertices

julia> using NamedGraphs: named_path_graph

julia> g = named_path_graph(4);

julia> collect(vertices(g))
4-element Vector{Int64}:
 1
 2
 3
 4

julia> collect(edges(g))
3-element Vector{NamedEdge{Int64}}:
 1 => 2
 2 => 3
 3 => 4

named_triangular_lattice_graph(m::Integer, n::Integer; periodic = false)

A named graph of an equilateral triangle tiling of the plane, with m rows and n columns of triangles and each vertex named by its coordinate tuple. periodic = true tiles the torus instead. Based on the NetworkX generator triangular_lattice_graph.

post_order_dfs_edges(graph::AbstractGraph, root_vertex)

One edge of the tree graph for each vertex besides root_vertex, ordered by post_order_dfs_vertices and directed from that vertex towards its parent, so the sequence sweeps inwards to root_vertex.

Examples

julia> using NamedGraphs: NamedEdge, named_path_graph, post_order_dfs_edges

julia> post_order_dfs_edges(named_path_graph(3), 3)
2-element Vector{NamedEdge{Int64}}:
 1 => 2
 2 => 3

post_order_dfs_vertices(graph::AbstractGraph, root_vertex)

The vertices of the tree graph in post-order depth-first order, so each vertex comes after its children and root_vertex comes last. An undirected graph is first oriented away from root_vertex with Graphs.dfs_tree.

See also post_order_dfs_edges.

rem_edge(graph::AbstractNamedGraph, edge)

A copy of graph with edge removed, leaving the vertices and graph itself alone.

See also rem_edges and Graphs.rem_edge! for the in-place form.

Examples

julia> using Graphs: ne

julia> using NamedGraphs: named_path_graph, rem_edge

julia> g = named_path_graph(3);

julia> h = rem_edge(g, 1 => 2);

julia> (ne(g), ne(h))
(2, 1)

rem_edges!(graph::AbstractNamedGraph, edges)

Remove edges from graph in place, leaving its vertices alone and returning how many were removed. An edge not in graph does not count, following Graphs.rem_edge!.

See also rem_edges for the non-mutating form.

Examples

julia> using Graphs: ne

julia> using NamedGraphs: named_path_graph, rem_edges!

julia> g = named_path_graph(3);

julia> rem_edges!(g, [1 => 2, 1 => 3])
1

julia> ne(g)
1

rem_edges(graph::AbstractNamedGraph, edges)

A copy of graph with edges removed. See also rem_edges!.

Examples

julia> using Graphs: ne

julia> using NamedGraphs: named_path_graph, rem_edges

julia> g = named_path_graph(3);

julia> h = rem_edges(g, [1 => 2]);

julia> (ne(g), ne(h))
(2, 1)

rem_vertex(graph::AbstractNamedGraph, vertex)

A copy of graph with vertex removed along with its incident edges, leaving graph itself alone.

See also rem_vertices and Graphs.rem_vertex! for the in-place form.

Examples

julia> using Graphs: nv

julia> using NamedGraphs: named_path_graph, rem_vertex

julia> g = named_path_graph(3);

julia> h = rem_vertex(g, 2);

julia> (nv(g), nv(h))
(3, 2)

rem_vertices(graph::AbstractNamedGraph, vs)

A copy of graph with the vertices vs removed, along with their incident edges.

Examples

julia> using Graphs: nv

julia> using NamedGraphs: named_path_graph, rem_vertices

julia> g = named_path_graph(3);

julia> h = rem_vertices(g, [2]);

julia> (nv(g), nv(h))
(3, 2)

rename_vertices(f, graph::AbstractGraph)

A graph with the same edges as graph but with each vertex v renamed to f(v). Only defined for graphs with named vertices: renaming the vertices of a Graphs.AbstractSimpleGraph is an error, since its vertices are the fixed integers 1:nv(graph).

Examples

julia> using Graphs: edges, path_graph, vertices

julia> using NamedGraphs: NamedEdge, NamedGraph, rename_vertices

julia> g = NamedGraph(path_graph(3), ["a", "b", "c"]);

julia> h = rename_vertices(uppercase, g);

julia> collect(vertices(h))
3-element Vector{String}:
 "A"
 "B"
 "C"

julia> collect(edges(h))
2-element Vector{NamedEdge{String}}:
 "A" => "B"
 "B" => "C"

similar_graph(graph::AbstractNamedGraph)
similar_graph(graph::AbstractGraph, vertices)
similar_graph(G::Type{<:AbstractGraph})
similar_graph(G::Type{<:AbstractGraph}, vertices)

A new graph like graph, or of type G, with vertices vertices and no edges. Given a graph and no vertices, the result has the same vertices and edges as graph; given a type and no vertices, it is empty.

spanning_forest(graph::AbstractNamedGraph; spanning_tree=spanning_tree)

A spanning forest of the undirected graph: the union of a spanning_tree over each of its connected components. Pass spanning_tree to control how each tree is built.

Examples

julia> using Graphs: ne, nv

julia> using NamedGraphs: named_grid, rem_edges, spanning_forest

julia> g = rem_edges(named_grid((2, 2)), [(1, 1) => (2, 1), (1, 2) => (2, 2)]);

julia> f = spanning_forest(g);

julia> (nv(f), ne(f))
(4, 2)

spanning_tree(graph::AbstractNamedGraph; alg=default_spanning_tree_alg(), root_vertex=default_root_vertex(graph))
spanning_tree(alg, graph::AbstractNamedGraph; root_vertex=default_root_vertex(graph))

An undirected spanning tree of the undirected graph, grown outwards from root_vertex by the traversal algorithm alg. graph must be connected. Use spanning_forest if it may not be.

Examples

julia> using Graphs: ne, nv

julia> using NamedGraphs: named_grid, spanning_tree

julia> t = spanning_tree(named_grid((2, 2)));

julia> (nv(t), ne(t))
(4, 3)

subgraph(graph::AbstractGraph, vertices)
subgraph(f::Function, graph::AbstractGraph)

The subgraph of graph induced by the given vertices, or by the vertices selected by the filter function f. Vertex names are preserved.

Examples

julia> using Graphs: edges, vertices

julia> using NamedGraphs: NamedEdge, named_grid, subgraph

julia> g = named_grid((2, 2));

julia> collect(edges(subgraph(g, [(1, 1), (2, 1), (2, 2)])))
2-element Vector{NamedEdge{Tuple{Int64, Int64}}}:
 (1, 1) => (2, 1)
 (2, 1) => (2, 2)

julia> collect(vertices(subgraph(v -> first(v) == 1, g)))
2-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (1, 2)

to_graph_index(graph, index)

Canonicalize index into the index type that graph is indexed by, for example turning a Pair of vertices into an edge of edgetype(graph). Indices that are already canonical are returned unchanged.

The indexing entry points call this on the index they are given, so overload it to teach a graph type or an index type a new spelling of a vertex or an edge. That covers writes as well as reads: downstream routes setindex! and isassigned through it too, not only getindex. The first argument is deliberately untyped, so anything indexed by vertices and edges can use it rather than graphs alone.

undirected_graph(graph::AbstractNamedGraph)

An undirected version of graph, with each directed edge replaced by an undirected one and a pair of opposite edges collapsing into a single edge. An already undirected graph is returned as-is.

See also directed_graph.

vertextype(graph::AbstractGraph)
vertextype(G::Type{<:AbstractGraph})
vertextype(edge::AbstractEdge)
vertextype(E::Type{<:AbstractEdge})

The type of the vertices of a graph, or of the source and destination of an edge. Works in the type domain as well as on instances.

Examples

julia> using Graphs: SimpleGraph

julia> using NamedGraphs: named_grid, vertextype

julia> vertextype(named_grid((2, 2)))
Tuple{Int64, Int64}

julia> vertextype(SimpleGraph{Int})
Int64

module PartitionedGraphs

A library for partitioned graphs and their quotients.

This module provides data structures and functionalities to work with partitioned graphs, including quotient vertices and edges, as well as views of partitioned graphs. It defines an abstract supertype AbstractPartitionedGraph for graphs that have some notion of a non-trivial partitioning of their vertices. It also provides an interface of functions that can be overloaded on any subtype of Graphs.AbstractGraph to make this subtype behave like a partitioned graph, without itself subtyping AbstractPartitionedGraph.

It defines the following concrete types:

• QuotientVertex: Represents a vertex in the quotient graph.
• QuotientEdge: Represents an edge in the quotient graph.
• PartitionedView: A lightweight view of a partitioned graph.
• PartitionedGraph: An implementation of a partitioned graph with extra caching not provided by PartitionedView.
• QuotientView: A view of the quotient graph derived from a partitioned graph.

It provides the following functions:

• partitionedgraph: Partitions an AbstractGraph.
• departition: Removes a single layer of partitioning from a partitioned graph.
• unpartition: Recursively removes all layers of partitioning from a partitioned graph.

Interfaces

For a type MyGraphType{V} <: Graphs.AbstractGraph{V}, to have a non-trivial partitioning then the interface can be summarized as follows:

# 1. If you want a non-trivial partitioning, then overload the method:
partitioned_vertices(g::MyGraphType)

# 2a. For fast quotient graph construction and fast `has_edge` at the quotient_graph level:
quotient_graph(g::MyGraphType)
# 2b. If Julia is unable to infer the returned type of `quotient_graph` then you should
# also define the `quotient_graph_type` function:
quotient_graph_type(g::MyGraphType)

# 3. For a fast vertex to quotient-vertex map then:
quotientvertex(g::MyGraphType, vertex)
# ...which automatically gives a fast edge to quotient-edge map via:
quotientedge(g, edge) # no need to overload this.

# 4. For fast finding of edge partitions: 
partitioned_edges(g::MyGraphType)

If any of the above properties are desirable for MyGraphType, then store the data in a field and overload the associated function to get that field, e.g.

quotientvertex(g::MyGraphType, vertex) = g.inverse_vertex_map[vertex]

where we have chosen to store the map in the field inverse_vertex_map of the MyGraphType type. Doing this is not essential as everything can and will be derived from partitioned_vertices as a fallback.

Interface for adding and removing vertices

For a given partitioned graph, all vertices must live in a quotient vertex and there should be no empty quotient vertices. The methods:

Graphs.rem_vertex!(g::MyGraphType, vertex)
Graphs.add_edge!(g::MyGraphType, edge)
Graphs.rem_edge!(g::MyGraphType, edge)

should be overloaded to ensure that these properties are maintained for the particular implementation of MyGraphType. Note, that the method:

Graphs.add_vertex!(g::MyGraphType, vertex)

is not supported for partitioned graphs as it is ambiguous which quotient vertex the new vertex should belong to. To add a vertex to a partitioned graph, one should define the method:

PartitionedGraphs.add_subquotientvertex!(
    g::MyGraphType,
    quotientvertex::QuotientVertex,
    vertex
)

Doing so enables the syntax:

Graphs.add_vertex!(graph, QuotientVertex(quotientvertex)[vertex])

for adding vertex to the quotient vertex quotientvertex in the partitioned graph.

abstract type AbstractPartitionedGraph{V, PV} <: AbstractNamedGraph{V}

Supertype for named graphs that carry a partitioning of their vertices, with vertex type V and quotient vertex type PV.

A subtype must define unpartitioned_graph, returning the underlying graph without any partitioning, on top of the partitioned-graph interface documented in PartitionedGraphs. Note that interface can also be implemented by a graph type that does not subtype AbstractPartitionedGraph.

PartitionedGraph(graph::AbstractGraph, partitioned_vertices)
PartitionedGraph(partitioned_vertices)
PartitionedGraph(graph::AbstractGraph; kwargs...)

A graph together with a partitioning of its vertices into quotient vertices. It caches the quotient graph and the vertex to quotient vertex map, so quotient level queries do not search the partitioning. PartitionedView is the alternative that stores neither.

The vertices of graph are partitioned according to partitioned_vertices, whose keys are the quotient vertices and whose values are the sets of vertices in each partition. It can be a Dictionaries.Dictionary, a Dict, or a vector of vertex collections keyed by 1:length(partitioned_vertices). Every vertex must land in exactly one quotient vertex.

Passing partitioned_vertices alone gives the discrete partitioning of an edgeless graph. Passing graph alone partitions with partition_vertices, which the keyword arguments go to: it needs either npartitions or nvertices_per_partition, and a backend such as Metis.jl loaded.

Examples

julia> using Graphs: ne, nv, path_graph, vertices

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedGraph, QuotientVertex, QuotientView

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = PartitionedGraph(g, [["a", "b"], ["c", "d"]]);

julia> (nv(pg), ne(pg))
(4, 3)

julia> vertices(pg, QuotientVertex(1))
2-element Vector{String}:
 "a"
 "b"

julia> (nv(QuotientView(pg)), ne(QuotientView(pg)))
(2, 1)

PartitionedView(graph::AbstractGraph, partitioned_vertices)

A lightweight view of graph as a partitioned graph. See PartitionedGraph for the accepted forms of partitioned_vertices.

Unlike PartitionedGraph, it stores nothing beyond graph and partitioned_vertices, recomputing the quotient graph and the vertex to quotient vertex map on each use, so it is cheaper to construct but slower to query at the quotient level.

Examples

julia> using Graphs: ne, nv, path_graph

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedView, QuotientView

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pv = PartitionedView(g, [["a", "b"], ["c", "d"]]);

julia> (nv(pv), ne(pv))
(4, 3)

julia> (nv(QuotientView(pv)), ne(QuotientView(pv)))
(2, 1)

QuotientEdge(e)

Represents a super-edge in a partitioned graph corresponding to the set of edges in between partitions src(e) and dst(e).

QuotientEdges(edges)
QuotientEdges(graph::AbstractGraph)

A collection of quotient edges, which iterates QuotientEdges. QuotientEdges(graph) holds every quotient edge of graph, and quotientedges returns one of these.

QuotientVertex(v)

Represents a super-vertex in a partitioned graph corresponding to the set of vertices in partition v.

QuotientView(graph::AbstractGraph)

A view of graph as its quotient graph: the graph whose vertices are the quotient vertices of graph and which has an edge between two quotient vertices whenever graph has an edge between them. Its vertices are the quotient vertices themselves rather than QuotientVertex wrappers, so it can be used with the Graphs.jl interface like any other named graph.

The view is backed by graph, so mutating it mutates graph: removing a vertex of the view removes all of the vertices of graph in that quotient vertex, and removing an edge of the view removes all of the edges of graph between those two quotient vertices.

Any Graphs.AbstractGraph can be viewed this way. A graph with no partitioning defined has the trivial partitioning with all of its vertices in a single quotient vertex, so its quotient graph is a single vertex with no edges.

Examples

julia> using Graphs: edges, ne, nv, path_graph, vertices

julia> using NamedGraphs: NamedEdge, NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedGraph, QuotientView

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = PartitionedGraph(g, [["a", "b"], ["c", "d"]]);

julia> qg = QuotientView(pg);

julia> collect(vertices(qg))
2-element Vector{Int64}:
 1
 2

julia> collect(edges(qg))
1-element Vector{NamedEdge{Int64}}:
 1 => 2

julia> (nv(QuotientView(g)), ne(QuotientView(g)))
(1, 0)

edges(g::AbstractGraph, quotientedge::QuotientEdge)
edges(g::AbstractGraph, quotientedges::QuotientEdges)

Return the set of edges in the graph g that correspond to a single quotient edge or a list of quotient edges.

ne(g::AbstractGraph, qe::QuotientEdge) -> Int

Returns the number of edges in g that correspond to the quotient edge qe.

See also: nv.

vertices(g::AbstractGraph, quotientvertex::QuotientVertex)
vertices(g::AbstractGraph, quotientvertices::QuotientVertices)

Return the set of vertices in the graph g associated with the quotient vertex quotientvertex or set of quotient vertices quotientvertices.

The result can alias the partitioning stored in g, so do not modify it.

boundary_quotientedges(graph::AbstractGraph, quotientvertices; dir = :out)
boundary_quotientedges(graph::AbstractGraph, quotientvertex::QuotientVertex; dir = :out)

The QuotientEdges of graph that connect the given quotient vertices to the quotient vertices outside of them, i.e. the boundary edges of quotientvertices in the quotient graph of graph.

Keyword arguments are forwarded to boundary_edges, in particular dir, which selects the edge direction to consider in a directed graph.

departition(graph::AbstractGraph)

The graph underlying graph with a single layer of partitioning removed: the graph that was partitioned to make graph, without the partitioning. Graphs that are not an AbstractPartitionedGraph are returned as-is, so departition is the identity on them.

Note that a partitioned graph can itself be partitioned, so removing one layer may leave a graph that is still partitioned. Use unpartition to remove every layer at once.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: departition, partitionedgraph

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = partitionedgraph(g, [["a", "b"], ["c", "d"]]);

julia> departition(pg) === g
true

julia> departition(g) === g
true

julia> departition(partitionedgraph(pg, [["a", "c"], ["b", "d"]])) === pg
true

partitioned_vertices(graph::AbstractGraph)

The partitioning of the vertices of graph: a mapping from each quotient vertex to the collection of vertices of graph it contains. Overload this on your own graph type to give it a non-trivial partitioning; the fallback puts every vertex into a single quotient vertex.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedGraph, partitioned_vertices

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pvs = partitioned_vertices(PartitionedGraph(g, [["a", "b"], ["c", "d"]]));

julia> pvs[1]
2-element Vector{String}:
 "a"
 "b"

julia> pvs[2]
2-element Vector{String}:
 "c"
 "d"

partitionedgraph(graph::AbstractGraph, partitioned_vertices) -> PartitionedGraph

The function form of the PartitionedGraph constructor, which documents the accepted forms of partitioned_vertices.

graph may itself be a partitioned graph, giving two layers of partitioning, which departition and unpartition remove.

quotient_graph(graph::AbstractGraph)

The graph on the quotient vertices of graph, with an edge between two quotient vertices whenever graph has an edge between them. Its vertices are the quotient vertices themselves rather than QuotientVertex wrappers, and QuotientView is the corresponding lazy view that mutates graph when it is mutated.

Overload this on your own graph type for fast quotient graph construction and fast quotient level has_edge; the fallback builds it from partitioned_vertices and the edges of graph.

Examples

julia> using Graphs: ne, nv, path_graph, vertices

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedGraph, quotient_graph

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> qg = quotient_graph(PartitionedGraph(g, [["a", "b"], ["c", "d"]]));

julia> (nv(qg), ne(qg))
(2, 1)

julia> issetequal(vertices(qg), [1, 2])
true

quotientedge(g::AbstractGraph{V}, edge) -> QuotientEdge{V}

Return the quotient edge corresponding to edge of the graph g. Note, the returned quotient edge may be a self-loop.

See also: quotientedges, quotientvertex.

quotientedges(g::AbstractGraph, es = edges(g)) -> QuotientEdges

Return an iterator over all unique quotient edges corresponding to the set of edges es of the graph g.

quotientvertices(g::AbstractGraph, vs = vertices(g))

Return an iterator over unique quotient vertices corresponding to the vertices vs of the graph g.

unpartition(graph::AbstractGraph)

The graph underlying graph with every layer of partitioning removed, i.e. departition applied repeatedly until the result is no longer partitioned. Graphs that are not an AbstractPartitionedGraph are returned as-is.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: partitionedgraph, unpartition

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = partitionedgraph(g, [["a", "b"], ["c", "d"]]);

julia> pg2 = partitionedgraph(pg, [["a", "c"], ["b", "d"]]);

julia> unpartition(pg2) === g
true

julia> unpartition(g) === g
true

unpartitioned_graph(graph::AbstractPartitionedGraph)

The graph that was partitioned to make graph, without the partitioning. Every AbstractPartitionedGraph subtype must overload this, on top of the partitioned graph interface documented in PartitionedGraphs.

departition is the equivalent that also accepts graphs that are not partitioned, returning them as-is.

rem_edges!(g::AbstractNamedGraph, qe::QuotientEdge)

Remove, in place, all the edges of g that correspond to the quotient edge qe. Returns the number of edges removed.