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 containing the degrees of every vertex of the graph g, where the degree of a vertex is defined as the number of edges which start or end at that vertex. For directed graphs, the degree of a vertex is equal to the sum of its indegree and outdegree. If v is specified and is a single vertex, only return the degree of v. If v is specified and is a vector of vertices, only return the degrees of the vertices in v.

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

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

julia> degree(g,3)
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 containing the indegrees of every vertex of the graph g, where the indegree of a vertex is defined as the number of edges which end at that vertex. If v is specified and is a single vertex, only return the indegree of v. If v is specified and is a vector of vertices, only return the indegrees of the 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

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

julia> indegree(g,2)
0

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 containing the outdegrees of every vertex of the graph g, where the outdegree of a vertex is defined as the number of edges which start at that vertex. If v is specified and is a single vertex, only return the outdegree of v. If v is specified and is a vector of vertices, only return the outdegrees of the 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

julia> outdegree(g,[1,2])
2-element Vector{Int64}:
 0
 1

julia> outdegree(g,2)
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.