You can install the package using Julia's package manager:
julia> ] add NamedGraphsThis packages introduces graph types with named vertices, which are built on top of the Graph/SimpleGraph type in the Graphs.jl package that only have contiguous integer vertices (i.e. linear indexing). The vertex names can be strings, tuples of integers, or other unique identifiers (anything that is hashable).
There is a supertype AbstractNamedGraph that defines an interface and fallback implementations of standard
Graphs.jl operations, and two implementations: NamedGraph and NamedDiGraph.
NamedGraph simply takes a set of names for the vertices of the graph. For example:
julia> using Graphs: grid, has_edge, has_vertex, neighbors
julia> using NamedGraphs: NamedGraph
julia> using NamedGraphs.GraphsExtensions: ⊔, disjoint_union, subgraph, rename_vertices
julia> g = NamedGraph(grid((4,)), ["A", "B", "C", "D"])
NamedGraphs.NamedGraph{String} with 4 vertices:
4-element NamedGraphs.OrderedDictionaries.OrderedIndices{String}
"A"
"B"
"C"
"D"
and 3 edge(s):
"A" => "B"
"B" => "C"
"C" => "D"
Common operations are defined as you would expect:
julia> has_vertex(g, "A")
true
julia> has_edge(g, "A" => "B")
true
julia> has_edge(g, "A" => "C")
false
julia> neighbors(g, "B")
2-element Vector{String}:
"A"
"C"
julia> subgraph(g, ["A", "B"])
NamedGraphs.NamedGraph{String} with 2 vertices:
2-element NamedGraphs.OrderedDictionaries.OrderedIndices{String}
"A"
"B"
and 1 edge(s):
"A" => "B"
Internally, this type wraps a SimpleGraph, and stores a Dictionary from the Dictionaries.jl package that maps the vertex names to the linear indices of the underlying SimpleGraph.
Graph operations are implemented by mapping back and forth between the generalized named vertices and the linear index vertices of the SimpleGraph.
It is natural to use tuples of integers as the names for the vertices of graphs with grid connectivities. For example:
julia> dims = (2, 2)
(2, 2)
julia> g = NamedGraph(grid(dims), Tuple.(CartesianIndices(dims)))
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 4 vertices:
4-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 1)
(2, 1)
(1, 2)
(2, 2)
and 4 edge(s):
(1, 1) => (2, 1)
(1, 1) => (1, 2)
(2, 1) => (2, 2)
(1, 2) => (2, 2)
In the future we will provide a shorthand notation for this, such as cartesian_graph(grid((2, 2)), (2, 2)).
Internally the vertices are all stored as tuples with a label in each dimension.
Vertices can be referred to by their tuples:
julia> has_vertex(g, (1, 1))
true
julia> has_edge(g, (1, 1) => (2, 1))
true
julia> has_edge(g, (1, 1) => (2, 2))
false
julia> neighbors(g, (2, 2))
2-element Vector{Tuple{Int64, Int64}}:
(2, 1)
(1, 2)You can use vertex names to get induced subgraphs:
julia> subgraph(v -> v[1] == 1, g)
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 2 vertices:
2-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 1)
(1, 2)
and 1 edge(s):
(1, 1) => (1, 2)
julia> subgraph(v -> v[2] == 2, g)
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 2 vertices:
2-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 2)
(2, 2)
and 1 edge(s):
(1, 2) => (2, 2)
julia> subgraph(g, [(1, 1), (2, 2)])
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 2 vertices:
2-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 1)
(2, 2)
and 0 edge(s):
You can also take disjoint unions or concatenations of graphs:
julia> g₁ = g
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 4 vertices:
4-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 1)
(2, 1)
(1, 2)
(2, 2)
and 4 edge(s):
(1, 1) => (2, 1)
(1, 1) => (1, 2)
(2, 1) => (2, 2)
(1, 2) => (2, 2)
julia> g₂ = g
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 4 vertices:
4-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 1)
(2, 1)
(1, 2)
(2, 2)
and 4 edge(s):
(1, 1) => (2, 1)
(1, 1) => (1, 2)
(2, 1) => (2, 2)
(1, 2) => (2, 2)
julia> disjoint_union(g₁, g₂)
NamedGraphs.NamedGraph{Tuple{Tuple{Int64, Int64}, Int64}} with 8 vertices:
8-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Tuple{Int64, Int64}, Int64}}
((1, 1), 1)
((2, 1), 1)
((1, 2), 1)
((2, 2), 1)
((1, 1), 2)
((2, 1), 2)
((1, 2), 2)
((2, 2), 2)
and 8 edge(s):
((1, 1), 1) => ((2, 1), 1)
((1, 1), 1) => ((1, 2), 1)
((2, 1), 1) => ((2, 2), 1)
((1, 2), 1) => ((2, 2), 1)
((1, 1), 2) => ((2, 1), 2)
((1, 1), 2) => ((1, 2), 2)
((2, 1), 2) => ((2, 2), 2)
((1, 2), 2) => ((2, 2), 2)
julia> g₁ ⊔ g₂ # Same as above
NamedGraphs.NamedGraph{Tuple{Tuple{Int64, Int64}, Int64}} with 8 vertices:
8-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Tuple{Int64, Int64}, Int64}}
((1, 1), 1)
((2, 1), 1)
((1, 2), 1)
((2, 2), 1)
((1, 1), 2)
((2, 1), 2)
((1, 2), 2)
((2, 2), 2)
and 8 edge(s):
((1, 1), 1) => ((2, 1), 1)
((1, 1), 1) => ((1, 2), 1)
((2, 1), 1) => ((2, 2), 1)
((1, 2), 1) => ((2, 2), 1)
((1, 1), 2) => ((2, 1), 2)
((1, 1), 2) => ((1, 2), 2)
((2, 1), 2) => ((2, 2), 2)
((1, 2), 2) => ((2, 2), 2)
The symbol ⊔ is just an alias for disjoint_union and can be written in the terminal
or in your favorite IDE with the appropriate Julia extension with \sqcup<tab>
By default, this maps the vertices v₁ ∈ vertices(g₁) to (v₁, 1) and the vertices v₂ ∈ vertices(g₂)
to (v₂, 2), so the resulting vertices of the unioned graph will always be unique.
The resulting graph will have no edges between vertices (v₁, 1) and (v₂, 2), these would have to
be added manually.
The original graphs can be obtained from subgraphs:
julia> rename_vertices(first, subgraph(v -> v[2] == 1, g₁ ⊔ g₂))
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 4 vertices:
4-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 1)
(2, 1)
(1, 2)
(2, 2)
and 4 edge(s):
(1, 1) => (2, 1)
(1, 1) => (1, 2)
(2, 1) => (2, 2)
(1, 2) => (2, 2)
julia> rename_vertices(first, subgraph(v -> v[2] == 2, g₁ ⊔ g₂))
NamedGraphs.NamedGraph{Tuple{Int64, Int64}} with 4 vertices:
4-element NamedGraphs.OrderedDictionaries.OrderedIndices{Tuple{Int64, Int64}}
(1, 1)
(2, 1)
(1, 2)
(2, 2)
and 4 edge(s):
(1, 1) => (2, 1)
(1, 1) => (1, 2)
(2, 1) => (2, 2)
(1, 2) => (2, 2)
This file was generated with Weave.jl with the following commands:
using NamedGraphs: NamedGraphs
using Weave: Weave
Weave.weave(
joinpath(pkgdir(NamedGraphs), "examples", "README.jl");
doctype="github",
out_path=pkgdir(NamedGraphs),
)