Created
October 15, 2021 15:32
-
-
Save Tokazama/4b309a05540ede4091953b2bb1553ce7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module GraphTraits | |
abstract type GraphStyle end | |
GraphStyle(x) = GraphStyle(typeof(x)) | |
GraphStyle(::Type{T}) where {T} = throw(MethodError(GraphStyle, T)) | |
vertex_type(x) = vertex_type(typeof(x)) | |
vertex_type(::Type{T}) where {T} = throw(MethodError(vertex_type, T)) | |
edge_type(x) = edge_type(typeof(x)) | |
edge_type(::Type{T}) where {T} = throw(MethodError(edge_type, T)) | |
""" | |
nvertices(g) -> Int | |
Return the number of vertices in `g`. | |
""" | |
nvertices(g) = nvertices(GraphStyle(g), g) | |
nvertices(s::GraphStyle, g) = throw(MethodError(nvertices, (s, g))) | |
""" | |
nedges(g) -> Int | |
Return the number of edges in `g`. | |
""" | |
nedges(g) = nedges(GraphStyle(g), g) | |
nedges(s::GraphStyle, g) = throw(MethodError(nedges, (s, g))) | |
""" | |
inneighbors(g, v) | |
Return a list of all neighbors connected to vertex `v` by an incoming edge. | |
""" | |
inneighbors(g, v) = inneighbors(GraphStyle(g), g, v) | |
inneighbors(s::GraphStyle, g, v) = throw(MethodError(inneighbors, (s, g, v))) | |
""" | |
outneighbors(g, v) | |
Return a list of all neighbors connected to vertex `v` by an outgoing edge. | |
""" | |
outneighbors(g, v) = outneighbors(GraphStyle(g), g, v) | |
outneighbors(s::GraphStyle, g, v) = throw(MethodError(outneighbors, (s, g, v))) | |
""" | |
neighbors(g, v) | |
Return a list of all neighbors reachable from vertex `v` in `g`. | |
For directed graphs, the default is equivalent to [`outneighbors`](@ref); | |
use [`all_neighbors`](@ref) to list inbound and outbound neighbors. | |
""" | |
neighbors(g, v) = neighbors(GraphStyle(g), g, v) | |
neighbors(s::GraphStyle, g, v) = throw(MethodError(neighbors, (s, g, v))) | |
""" | |
indegree(g, v) -> Int | |
indegree(g, v::AbstractVector) -> Vector{Int} | |
Return a vector corresponding to the number of edges which end at each vertex in graph `g`. | |
If `v` is specified, only return degrees for vertices in `v`. | |
""" | |
indegree(g, v=vertex_indicess(g)) = indegree(GraphStyle(g), g, v) | |
indegree(s::GraphStyle, g, v) = throw(MethodError(indegree, (s, g, v))) | |
function indegree(s::GraphStyle, g::AbstractGraph, v::AbstractVector) | |
out = Vector{Int}(undef, length(v)) | |
@inbounds for (i, v_i) in enumerate(v) | |
out[i] = indegree(s, g, v_i) | |
end | |
return out | |
end | |
""" | |
outdegree(g, v) -> Int | |
outdegree(g, v::AbstractVector) -> Vector{Int} | |
Return a vector corresponding to the number of edges which start at each vertex in | |
graph `g`. If `v` is specified, only return degrees for vertices in `v`. | |
""" | |
outdegree(g, v=vertex_indices(g)) = outdegree(GraphStyle(g), g, v) | |
outdegree(s::GraphStyle, g, v::Integer) = throw(MethodError(outdegree, (s, g, v))) | |
function outdegree(s::GraphStyle, g, v::AbstractVector) | |
out = Vector{Int}(undef, length(v)) | |
@inbounds for (i, v_i) in enumerate(v) | |
out[i] = outdegree(s, g, v_i) | |
end | |
return out | |
end | |
""" | |
degree(g, v) -> Int | |
degree(g, v::AbstractVector) -> Vector{Int} | |
Return a vector corresponding to the number of edges which start or end at each | |
vertex in graph `g`. If `v` is specified, only return degrees for vertices in `v`. | |
For directed graphs, this value equals the incoming plus outgoing edges. | |
For undirected graphs, it equals the connected edges. | |
""" | |
degree(g, v = vertex_indices(g)) = degree(GraphStyle(g), g, v) | |
degree(s::GraphStyle, g, v::Integer) = throw(MethodError(degree, (s, g, v))) | |
function degree(s::GraphStyle, g, v::AbstractVector) | |
out = Vector{Int}(undef, length(v)) | |
@inbounds for (i, v_i) in enumerate(v) | |
out[i] = degree(s, g, v_i) | |
end | |
return out | |
end | |
""" | |
vertex_indices(g) | |
Return the indices to the vertices of graph `g`. | |
""" | |
vertex_indices(g) = vertex_indices(GraphStyle(g), g) | |
vertex_indices(s::GraphStyle, g) = throw(MethodError(vertex_indices, (s, g)) | |
""" | |
vertices(g) | |
Return an iterable of to vertices of graph `g`. | |
""" | |
vertices(g) = vertices(GraphStyle(g), g) | |
vertices(s::GraphStyle, g) = throw(MethodError(vertices, (s, g)) | |
""" | |
edges(g) | |
Return (an iterator to or collection of) the edges of a graph. | |
For `AbstractSimpleGraph`s it returns a `SimpleEdgeIter`. | |
The expressions `e in edges(g)` and `e ∈ edges(ga)` evaluate as | |
calls to [`has_edge`](@ref). | |
""" | |
edges(g) = edges(GraphStyle(g), g) | |
edges(s::GraphStyle, g) = throw(MethodError(edges, (s, g))) | |
""" | |
add_vertex!(g) | |
Add a new vertex to the graph `g`. Return true if addition was successful. | |
""" | |
add_vertex!(g) = add_vertex!(GraphStyle(g), g) | |
add_vertex!(g::GraphStyle, g) = throw(MethodError(add_vertex!, (s, g))) | |
""" | |
add_vertices!(g, n) | |
Add `n` new vertices to the graph `g`. | |
Return the number of vertices that were added successfully. | |
""" | |
add_vertices!(g, n::Integer) = sum([add_vertex!(g) for i = 1:n]) | |
""" | |
insert_vertex!(g, index) | |
Insert a new vertex at `index` into the graph `g`. | |
""" | |
insert_vertex!(g, i) = insert_vertex!(GraphStyle(g), g, i) | |
insert_vertex!(g::GraphStyle, g, i) = throw(MethodError(insert_vertex!, (s, g, i))) | |
""" | |
insert_vertex!(g, index, v) | |
Insert a vertex `v` into the graph `g` at `index`. | |
""" | |
insert_vertex!(g, i, v) = insert_vertex!(GraphStyle(g), g, i, v) | |
insert_vertex!(g::GraphStyle, g, i, v) = throw(MethodError(insert_vertex!, (s, g, i, v))) | |
""" | |
children(g) | |
Get the immediate children of vertex `g`. | |
""" | |
function children(g) | |
if has_children(g) | |
return g | |
else | |
return () | |
end | |
end | |
has_children(x) = has_children(typeof(x)) | |
has_children(::Typee{T}) where {T} = Base.isiterable(T) | |
""" | |
is_directed(g) = is_directed(GraphStyle(g)) | |
is_directed(s::GraphStyle) | |
Return `true` if the graph type `G` is a directed graph; `false` otherwise. | |
New graph types must implement `is_directed(::Type{<:G})`. | |
The method can also be called with `is_directed(g::G)` | |
""" | |
is_directed(g) = is_directed(GraphStyle(g)) | |
is_directed(s::GraphStyle) = throw(MethodError(is_directed, s)) | |
""" | |
has_vertex(g, v) | |
Return true if `v` is a vertex of `g`. | |
""" | |
has_vertex(g, v) = has_vertex(GraphStyle(g), g, v) | |
has_vertex(s::GraphStyle, g, v) = throw(MethodError(has_vertex, (s, g, v))) | |
""" | |
has_edge(g, s, d) | |
Return true if the graph `g` has an edge from node `s` to node `d`. | |
An optional `has_edge(g, e)` can be implemented to check if an edge belongs | |
to a graph, including any data other than source and destination node. | |
`e ∈ edges(g)` or `e ∈ edges(g)` evaluate as | |
calls to `has_edge`, c.f. [`edges`](@ref). | |
""" | |
has_edge(g, v) = has_edge(GraphStyle(g), g, v) | |
has_edge(s::GraphStyle, g, v) = throw(MethodError(has_edge, (s, g, v))) | |
""" | |
all_neighbors(g, v) | |
Return a list of all inbound and outbound neighbors of `v` in `g`. | |
For undirected graphs, this is equivalent to both [`outneighbors`](@ref) | |
and [`inneighbors`](@ref). | |
### Implementation Notes | |
Returns a reference to the current graph's internal structures, not a copy. | |
Do not modify result. If the graph is modified, the behavior is undefined: | |
the array behind this reference may be modified too, but this is not guaranteed. | |
""" | |
all_neighbors(g, v) = all_neighbors(GraphStyle(g), g, v) | |
all_neighbors(s::GraphStyle, g, v) = throw(MethodError(all_neighbors, (s, g, v))) | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment