Core functions

AbstractPathState

An abstract type that provides information from shortest paths calculations.

add_vertices!(g, n)

Add n new vertices to the graph g. Return the number of vertices that were added successfully.

Examples

julia> using Graphs

julia> g = SimpleGraph()
{0, 0} undirected simple Int64 graph

julia> add_vertices!(g, 2)
2

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 and inneighbors.

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.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> all_neighbors(g, 1)
1-element Vector{Int64}:
 3

julia> all_neighbors(g, 2)
1-element Vector{Int64}:
 3

julia> all_neighbors(g, 3)
2-element Vector{Int64}:
 1
 2

common_neighbors(g, u, v)

Return the neighbors common to vertices u and v in g.

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.

Examples

julia> using Graphs

julia> g = SimpleGraph(4);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 4);

julia> add_edge!(g, 4, 1);

julia> add_edge!(g, 1, 3);

julia> common_neighbors(g, 1, 3)
2-element Vector{Int64}:
 2
 4

julia> common_neighbors(g, 1, 4)
1-element Vector{Int64}:
 3

degree(g[, v])

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.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> degree(g)
3-element Vector{Int64}:
 1
 1
 2

degree_histogram(g, degfn=degree)

Return a Dict with values representing the number of vertices that have degree represented by the key.

Degree function (for example, indegree or outdegree) may be specified by overriding degfn.

density(g)

Return the density of g. Density is defined as the ratio of the number of actual edges to the number of possible edges ($|V|×(|V|-1)$ for directed graphs and $\frac{|V|×(|V|-1)}{2}$ for undirected graphs).

has_self_loops(g)

Return true if g has any self loops.

Examples

julia> using Graphs

julia> g = SimpleGraph(2);

julia> add_edge!(g, 1, 2);

julia> has_self_loops(g)
false

julia> add_edge!(g, 1, 1);

julia> has_self_loops(g)
true

indegree(g[, v])

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.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> indegree(g)
3-element Vector{Int64}:
 1
 0
 1

is_ordered(e)

Return true if the source vertex of edge e is less than or equal to the destination vertex.

Examples

julia> using Graphs

julia> g = DiGraph(2);

julia> add_edge!(g, 2, 1);

julia> is_ordered(first(edges(g)))
false

neighbors(g, v)

Return a list of all neighbors reachable from vertex v in g. For directed graphs, the default is equivalent to outneighbors; use all_neighbors to list inbound and outbound neighbors.

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.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> neighbors(g, 1)
Int64[]

julia> neighbors(g, 2)
1-element Vector{Int64}:
 3

julia> neighbors(g, 3)
1-element Vector{Int64}:
 1

noallocextreme(f, comparison, initial, g)

Compute the extreme value of [f(g,i) for i=i:nv(g)] without gathering them all

num_self_loops(g)

Return the number of self loops in g.

Examples

julia> using Graphs

julia> g = SimpleGraph(2);

julia> add_edge!(g, 1, 2);

julia> num_self_loops(g)
0

julia> add_edge!(g, 1, 1);

julia> num_self_loops(g)
1

outdegree(g[, v])

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.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> outdegree(g)
3-element Vector{Int64}:
 0
 1
 1

squash(g)

Return a copy of a graph with the smallest practical eltype that can accommodate all vertices.

May also return the original graph if the eltype does not change.

weights(g)

Return the weights of the edges of a graph g as a matrix. Defaults to Graphs.DefaultDistance.

Implementation Notes

In general, referencing the weight of a nonexistent edge is undefined behavior. Do not rely on the weights matrix as a substitute for the graph's adjacency_matrix.

Δ(g)

Return the maximum degree of vertices in g.

Δin(g)

Return the maximum indegree of vertices in g.

Δout(g)

Return the maximum outdegree of vertices in g.

δ(g)

Return the minimum degree of vertices in g.

δin(g)

Return the minimum indegree of vertices in g.

δout(g)

Return the minimum outdegree of vertices in g.