search

ITensor / NamedGraphs.jl

Extension of `Graphs.jl` to graphs with named vertices.
MIT License
6 stars 3 forks source link

readme

NamedGraphs

Stable Dev Build Status Coverage Code Style: Blue

Installation

You can install the package using Julia's package manager:

julia> ] add NamedGraphs

Introduction

This 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

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)

Generating this README

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