In Graphs.jl, the graph concepts are abstracted into a set of generic interfaces. Below is a detailed specification. We strongly recommend reading through this specification before you write a graph type to ensure that your graph type conforms to the interface system.
All graph types should be declared as a sub-type of AbstractGraph{V,E}, where V is the vertex type, and E is the edge type.
The following two functions are provided for graphs of all types.
returns the vertex type of a graph, i.e., V.
returns the edge type of a graph, i.e., E.
Note: The two basic functions above have been implemented over AbstractGraph and one need not implement them for specific graph types.
In addition, the following method needs to be implemented for each graph type:
returns whether g is a directed graph.
returns the number of vertices contained in g.
returns an iterable view/container of all vertices.
returns the number of edges contained in g.
returns an iterable view/container of all edges.
returns the source vertex of an edge e in graph g.
returns the target vertex of an edge e in graph g.
returns the number of outgoing neighbors from vertex v in graph g.
returns an iterable view/container of all outgoing neighbors of vertex v in graph g.
The following example prints all vertices of a graph as well as its neighbors
for u in vertices(g)
print("$u: ")
for v in out_neighbors(u, g)
println("$v ")
end
println()
end
returns the number of outgoing edges from vertex v in graph g.
returns the number of outgoing edges from vertex v in graph g.
returns the source vertex of an edge e in graph g.
returns the target vertex of an edge e in graph g.
The following example prints all vertices of a graph as well as its incidence edges
for u in vertices(g)
print("$u: ")
for e in out_edges(u, g)
v = target(e, g)
println("($u -- $v) ")
end
println()
end
This interface refines the Incidence List and requires the implementation of two additional methods:
returns the number of incoming edges from vertex v in graph g.
returns the number of incoming edges from vertex v in graph g.
It is important to note that a specific graph type can implement multiple interfaces. If a method is required to be implemented for two interfaces (e.g., out_degree in both adjacency list an incidence list), this method need only be implemented once.
Julia does not provide a builtin mechanism for interface declaration. To declare that a specific graph type implements certain interfaces, one can use the macro @graph_implements. For example, to declare that a graph type G implements vertex list and adjacency list, one can write:
@graph_implements G vertex_list adjacency_list
This statement instantiates the following methods:
implements_vertex_list(::G) = true
implements_adjacency_list(::G) = true
The following is a list of supported interface names
In a function that implements a generic graph algorithm, one can use the macro @graph_requires to verify whether the input graph implements the required interfaces. A typical graph algorithm function may look like follows
function myfunc(g::AbstractGraph, params)
@graph_requires g vertex_list adjacency_list
...
end
Here, the @graph_requires statement checks whether the graph g implements the interfaces for vertex_list and adjacency_list, and throws exceptions if g does not satisfy the requirements.