ImplicitGraphs
An ImplicitGraph
is a graph in which the vertices and edges are implicitly defined by two functions: one that tests for vertex membership and one that returns a list of the (out) neighbors of a vertex.
The vertex set of an ImplicitGraph
may be finite or (implicitly) infinite. The (out) degrees, however, must be finite.
Creating Graphs
An ImplicitGraph
is defined as follows:
ImplicitGraph{T}(has_vertex, out_neighbors)
where
T
is the data type of the vertices.has_vertex(v::T)::Bool
is a function that takes objects of typeT
as input and returnstrue
ifv
is a vertex of the graph.out_neighbors(v::T)::Vector{T}
is a function that takes objects of typeT
as input and returns a list of the (out) neighbors ofv
.
For example, the following creates an (essentially) infinite path whose vertices are integers (see the iPath
function):
yes(v::Int)::Bool = true
N(v::Int)::Vector{Int} = [v-1, v+1]
G = ImplicitGraph{Int}(yes, N)
The yes
function always returns true
for any Int
. The N
function returns the two neighbors of a vertex v
. (For a truly infinite path, use BigInt
in place of Int
.)
Note that if v
is an element of its own neighbor set, that represents a loop at vertex v
.
Undirected and directed graphs
The user-supplied out_neighbors
function can be used to create both undirected and directed graphs. If an undirected graph is intended, be sure that if {v,w}
is an edge of the graph, then w
will be in the list returned by out_neighbors(v)
and v
will be in the list returned by out_neighbors(w)
.
To create an infinite directed path, the earlier example can be modified like this:
yes(v::Int)::Bool = true
N(v::Int)::Vector{Int} = [v+1]
G = ImplicitGraph{Int}(yes, N)
Predefined Graphs
We provide a few basic graphs that can be created using the following methods:
-
iCycle(n::Int)
creates an undirected cycle with vertex set{1,2,...,n}
;iCycle(n,false)
creates a directedn
-cycle. -
iPath()
creates an (essentially) infinite undirected path whose vertex set contains all integers (objects of typeInt
);iPath(false)
creates a one-way infinite path⋯ → -2 → -1 → 0 → 1 → 2 → ⋯
. -
iGrid()
creates an (essentially) infinite grid whose vertices are ordered pairs of integers (objects of typeInt
). -
iCube(d::Int)
creates ad
-dimensional cube graph. The vertices are alld
-long strings of0
s and1
s. Two vertices are adjacent iff they differ in exactly one bit. -
iKnight()
creates the Knight's move graph on an (essentially) infinite chessboard. The vertices are pairs of integers (objects of typeInt
). -
iShift(alphabet, n::Int)
creates the shift digraph whose vertices aren
-tuples of elements ofalphabet
.
Inspection
-
To test if
v
is a vertex of anImplicitGraph
G
, usehas(G)
. Note that the data type ofv
must match the element type ofG
. (The functioneltype
returns the data type of the vertices of theImplicitGraph
.) -
To test if
{v,w}
is an edge ofG
useG[v,w]
orhas(G,v,w)
. Note thatv
andw
must both be vertices ofG
or an error is thrown. -
To get a list of the (out) neighbors of a vertex
v
, useG[v]
. -
To get the degree of a vertex in a graph, use
deg(G,v)
.
julia> G = iGrid()
ImplicitGraph{Tuple{Int64,Int64}}
julia> has_vertex(G,(1,2))
true
julia> G[(1,2)]
4-element Array{Tuple{Int64,Int64},1}:
(1, 1)
(1, 3)
(0, 2)
(2, 2)
julia> G[(1,2),(1,3)]
true
julia> deg(G,(5,0))
4
Path Finding
Shortest path
The function find_path
finds a shortest path between vertices of a graph. This function may run without returning if the graph is infinite and disconnected.
julia> G = iGrid()
ImplicitGraph{Tuple{Int64,Int64}}
julia> find_path(G,(0,0), (3,5))
9-element Array{Tuple{Int64,Int64},1}:
(0, 0)
(0, 1)
(0, 2)
(0, 3)
(0, 4)
(0, 5)
(1, 5)
(2, 5)
(3, 5)
The function dist
returns the length of a shortest path between vertices in the graph.
julia> dist(G,(0,0),(3,5))
8
Guided path finding
The function guided_path_finder
employs a score function to try to find a
path between vertices. It may be faster than find_path
, but might not give a shortest path.
This function is called as follows: guided_path_finder(G,s,t,score=sc, depth=d, verbose=0)
where
G
is anImplicitGraph
,s
is the starting vertex of the desired path,t
is the ending vertex of the desired path,sc
is a score function that mapping vertices to integers and should get smaller as vertices get closer tot
(and should minimize att
),d
controls amount of look ahead (default is1
), andverbose
sets how often to print progess information (or0
for no diagnostics).
julia> G = iKnight();
julia> s = (9,9); t = (0,0);
julia> sc(v) = sum(abs.(v)); # score of (a,b) is |a| + |b|
julia> guided_path_finder(G,s,t,score=sc,depth=1)
9-element Vector{Tuple{Int64, Int64}}:
(9, 9)
(8, 7)
(7, 5)
(6, 3)
(5, 1)
(3, 0)
(1, -1)
(-1, -2)
(0, 0)
# With better look-ahead we find a shorter path
julia> guided_path_finder(G,s,t,score=sc,depth=3)
7-element Vector{Tuple{Int64, Int64}}:
(9, 9)
(8, 7)
(7, 5)
(6, 3)
(4, 2)
(2, 1)
(0, 0)
Greater depth can find a shorter path, but that comes at a cost:
julia> using BenchmarkTools
julia> @btime guided_path_finder(G,s,t,score=sc,depth=1);
52.361 μs (1308 allocations: 81.05 KiB)
julia> @btime guided_path_finder(G,s,t,score=sc,depth=3);
407.546 μs (8691 allocations: 696.47 KiB)
Extras
The extras
directory contains additional code and examples that may be
useful in conjunction with the ImplicitGraph
type. See the README
in that directory.