Named 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 the minimal interface encoded_graph, encoded_vertex, and decoded_vertex.

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)

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.

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"

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

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

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, including the caveat below.

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"

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

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)

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)

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)

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

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)

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)

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)

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

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)

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

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)

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)

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)

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)

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)

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.

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_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_cycle_graph(dim::Integer)

A named cycle graph on the vertices 1:dim.

named_path_digraph(dim::Integer)

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

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