Path and Traversal

bfs_tree(g, s[; dir=:out])

Provide a breadth-first traversal of the graph g starting with source vertex s, and return a directed acyclic graph of vertices in the order they were discovered. If dir is specified, use the corresponding edge direction (:in and :out are acceptable values).

gdistances!(g, source, dists; sort_alg=QuickSort)

Fill dists with the geodesic distances of vertices in g from source vertex (or collection of vertices) source. dists should be a vector of length nv(g) filled with typemax(T). Return dists.

For vertices in disconnected components the default distance is typemax(T).

An optional sorting algorithm may be specified (see Performance section).

Performance

gdistances uses QuickSort internally for its default sorting algorithm, since it performs the best of the algorithms built into Julia Base. However, passing a RadixSort (available via SortingAlgorithms.jl) will provide significant performance improvements on larger graphs.

gdistances(g, source; sort_alg=QuickSort)

Return a vector filled with the geodesic distances of vertices in g from source. If source is a collection of vertices each element should be unique. For vertices in disconnected components the default distance is typemax(T).

An optional sorting algorithm may be specified (see Performance section).

Performance

gdistances uses QuickSort internally for its default sorting algorithm, since it performs the best of the algorithms built into Julia Base. However, passing a RadixSort (available via SortingAlgorithms.jl) will provide significant performance improvements on larger graphs.

has_path(g::AbstractGraph, u, v; exclude_vertices=Vector())

Return true if there is a path from u to v in g (while avoiding vertices in exclude_vertices) or u == v. Return false if there is no such path or if u or v is in excluded_vertices.

dfs_tree(g, s)

Return an ordered vector of vertices representing a directed acylic graph based on depth-first traversal of the graph g starting with source vertex s.

has_cycles(g)

Return true if graph g contains a cycle.

Implementation Notes

Uses DFS.

topological_sort_by_dfs(g)

Return a toplogical sort of a directed graph g as a vector of vertices in topological order.

maximum_adjacency_visit(g[, distmx][, log][, io])

Return the vertices in g traversed by maximum adjacency search. An optional distmx matrix may be specified; if omitted, edge distances are assumed to be 1. If log (default false) is true, visitor events will be printed to io, which defaults to STDOUT; otherwise, no event information will be displayed.

minimum_cut(g, distmx=weights(g))

Return a tuple (parity, bestcut), where parity is a vector of integer values that determines the partition in g (1 or 2) and bestcut is the weight of the cut that makes this partition. An optional distmx matrix may be specified; if omitted, edge distances are assumed to be 1.

nonbacktracking_randomwalk(g, s, niter)

Perform a non-backtracking random walk on directed graph g starting at vertex s and continuing for a maximum of niter steps. Return a vector of vertices visited in order.

randomwalk(g, s, niter)

Perform a random walk on graph g starting at vertex s and continuing for a maximum of niter steps. Return a vector of vertices visited in order.

self_avoiding_randomwalk(g, s, niter)

Perform a self-avoiding walk on graph g starting at vertex s and continuing for a maximum of niter steps. Return a vector of vertices visited in order.

attracting_components(g)

Return a vector of vectors of integers representing lists of attracting components in the directed graph g.

The attracting components are a subset of the strongly connected components in which the components do not have any leaving edges.

Examples

julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
{5, 6} directed simple Int64 graph

julia> strongly_connected_components(g)
2-element Array{Array{Int64,1},1}:
 [4, 5]
 [1, 2, 3]

julia> attracting_components(g)
1-element Array{Array{Int64,1},1}:
 [4, 5]

condensation(g[, scc])

Return the condensation graph of the strongly connected components scc in the directed graph g. If scc is missing, generate the strongly connected components first.

Examples

julia> g = DiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
{5, 6} directed simple Int64 graph

julia> strongly_connected_components(g)
2-element Array{Array{Int64,1},1}:
 [4, 5]
 [1, 2, 3]

julia> foreach(println, edges(condensation(g)))
Edge 2 => 1

connected_components(g)

Return the connected components of an undirected graph g as a vector of components, with each element a vector of vertices belonging to the component.

For directed graphs, see strongly_connected_components and weakly_connected_components.

Examples

julia> g = Graph([0 1 0; 1 0 1; 0 1 0]);

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

julia> g = Graph([0 1 0 0 0; 1 0 1 0 0; 0 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> connected_components(g)
2-element Array{Array{Int64,1},1}:
 [1, 2, 3]
 [4, 5]

is_connected(g)

Return true if graph g is connected. For directed graphs, return true if graph g is weakly connected.

Examples

julia> g = Graph([0 1 0; 1 0 1; 0 1 0]);

julia> is_connected(g)
true

julia> g = Graph([0 1 0 0 0; 1 0 1 0 0; 0 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> is_connected(g)
false

julia> g = DiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> is_connected(g)
true

is_strongly_connected(g)

Return true if directed graph g is strongly connected.

Examples

julia> g = DiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> is_strongly_connected(g)
true

is_weakly_connected(g)

Return true if the graph g is weakly connected. If g is undirected, this function is equivalent to is_connected(g).

Examples

julia> g = DiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> is_weakly_connected(g)
true

julia> g = DiGraph([0 1 0; 1 0 1; 0 0 0]);

julia> is_connected(g)
true

julia> is_strongly_connected(g)
false

julia> is_weakly_connected(g)
true

neighborhood(g, v, d, distmx=weights(g); dir=:out)

Return a vector of each vertex in g at a geodesic distance less than or equal to d, where distances may be specified by distmx.

Optional Arguments

• dir=:out: If g is directed, this argument specifies the edge direction

with respect to v of the edges to be considered. Possible values: :in or :out.

Examples

julia> g = DiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> neighborhood(g, 1, 2)
3-element Array{Int64,1}:
 1
 2
 3

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

julia> neighborhood(g, 1, 3, [0 1 0 0 0; 0 0 1 0 0; 1 0 0 0.25 0; 0 0 0 0 0.25; 0 0 0 0.25 0])
5-element Array{Int64,1}:
 1
 2
 3
 4
 5

period(g)

Return the (common) period for all vertices in a strongly connected directed graph. Will throw an error if the graph is not strongly connected.

Examples

julia> g = DiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> period(g)
3

strongly_connected_components(g)

Compute the strongly connected components of a directed graph g.

Return an array of arrays, each of which is the entire connected component.

Implementation Notes

The order of the components is not part of the API contract.

Examples

julia> g = DiGraph([0 1 0; 1 0 1; 0 0 0]);

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

weakly_connected_components(g)

Return the weakly connected components of the graph g. This is equivalent to the connected components of the undirected equivalent of g. For undirected graphs this is equivalent to the connected_components of g.

Examples

julia> g = DiGraph([0 1 0; 1 0 1; 0 0 0]);

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