Traversals and coloring

Graphs.jl includes various routines for exploring graphs.

Index

Full docs

Graphs.bfs_parentsMethod
bfs_parents(g, s[; dir=:out])

Perform a breadth-first search of graph g starting from vertex s. Return a vector of parent vertices indexed by vertex. If dir is specified, use the corresponding edge direction (:in and :out are acceptable values).

Performance

This implementation is designed to perform well on large graphs. There are implementations which are marginally faster in practice for smaller graphs, but the performance improvements using this implementation on large graphs can be significant.

source
Graphs.bfs_treeMethod
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).

source
Graphs.gdistances!Method
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.

source
Graphs.gdistancesMethod
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.

source
Graphs.has_pathMethod
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.

source
Graphs.treeMethod
tree(parents)

Convert a parents array into a directed graph.

source
Graphs.bipartite_mapMethod
bipartite_map(g) -> Vector{UInt8}

For a bipartite graph g, return a vector c of size $|V|$ containing the assignment of each vertex to one of the two sets ($c_i == 1$ or $c_i == 2$). If g is not bipartite, return an empty vector.

Implementation Notes

Note that an empty vector does not necessarily indicate non-bipartiteness. An empty graph will return an empty vector but is bipartite.

Examples

julia> using Graphs

julia> g = SimpleGraph(3);

julia> bipartite_map(g)
3-element Vector{UInt8}:
 0x01
 0x01
 0x01

julia> add_vertices!(g, 3);

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

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

julia> bipartite_map(g)
6-element Vector{UInt8}:
 0x01
 0x02
 0x01
 0x01
 0x01
 0x01
source
Graphs.is_bipartiteMethod
is_bipartite(g)

Return true if graph g is bipartite.

Examples

julia> using Graphs

julia> g = SimpleGraph(3);

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

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

julia> is_bipartite(g)
true

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

julia> is_bipartite(g)
false
source
Graphs.dfs_parentsMethod
dfs_parents(g, s[; dir=:out])

Perform a depth-first search of graph g starting from vertex s. Return a vector of parent vertices indexed by vertex. If dir is specified, use the corresponding edge direction (:in and :out are acceptable values).

Implementation Notes

This version of DFS is iterative.

source
Graphs.dfs_treeMethod
dfs_tree(g, s[;dir=:out])

Provide a depth-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).

source
Graphs.is_cyclicFunction
is_cyclic(g)

Return true if graph g contains a cycle.

Implementation Notes

The algorithm uses a DFS. Self-loops are counted as cycles.

source
Graphs.topological_sortFunction
topological_sort(g)

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

Implementation Notes

This is currently just an alias for topological_sort_by_dfs

source
Graphs.diffusionMethod
diffusion(g, p, n)

Run diffusion simulation on g for n steps with spread probabilities based on p. Return a vector with the set of new vertices reached at each step of the simulation.

Optional Arguments

  • initial_infections=sample(vertices(g), 1): A list of vertices that

are infected at the start of the simulation.

  • watch=Vector(): While simulation is always run on the full graph,

specifying watch limits reporting to a specific set of vertices reached during the simulation. If left empty, all vertices will be watched.

  • normalize=false: if false, set the probability of spread from a vertex $i$ to

each of the outneighbors of $i$ to $p$. If true, set the probability of spread from a vertex $i$ to each of the outneighbors of $i$ to $\frac{p}{outdegreee(g, i)}$.

  • rng=nothing: A random generator to sample from.
source
Graphs.diffusion_rateMethod
diffusion_rate(results)
diffusion_rate(g, p, n; ...)

Given the results of a diffusion output or the parameters to the diffusion simulation itself, (run and) return the rate of diffusion as a vector representing the cumulative number of vertices infected at each simulation step, restricted to vertices included in watch, if specified.

source
Graphs.ColoringType
struct Coloring{T}

Store the number of colors used and mapping from vertex to color

source
Graphs.greedy_colorMethod
greedy_color(g; sort_degree=false, reps = 1)

Color graph g based on Greedy Coloring Heuristics

The heuristics can be described as choosing a permutation of the vertices and assigning the lowest color index available iteratively in that order.

If sort_degree is true then the permutation is chosen in reverse sorted order of the degree of the vertices. parallel and reps are irrelevant in this case.

If sort_degree is false then reps colorings are obtained based on random permutations and the one using least colors is chosen.

source
Graphs.perm_greedy_colorMethod
perm_greedy_color(g, seq)

Color graph g according to an order specified by seq using a greedy heuristic. seq[i] = v implies that vertex v is the $i^{th}$ vertex to be colored.

source
Graphs.random_greedy_colorMethod
random_greedy_color(g, reps)

Color the graph g iteratively in a random order using a greedy heuristic and choose the best coloring out of reps such random colorings.

source
Graphs.maximum_adjacency_visitMethod
maximum_adjacency_visit(g[, distmx][, log][, io][, s])
maximum_adjacency_visit(g[, s])

Return the vertices in g traversed by maximum adjacency search, optionally starting from vertex s (default 1). 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.

source
Graphs.mincutMethod
mincut(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 of non-negative weights may be specified; if omitted, edge distances are assumed to be 1.

source
Graphs.non_backtracking_randomwalkFunction
non_backtracking_randomwalk(g, s, niter; rng=nothing, seed=nothing)

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.

source
Graphs.randomwalkMethod
randomwalk(g, s, niter; rng=nothing, seed=nothing)

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.

source
Graphs.self_avoiding_walkMethod
self_avoiding_walk(g, s, niter; rng=nothing, seed=nothing)

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.

source
Graphs.eulerianMethod
eulerian(g::AbstractSimpleGraph{T}[, u::T]) --> T[]

Returns a Eulerian trail or cycle through an undirected graph g, starting at vertex u, returning a vector listing the vertices of g in the order that they are traversed. If no such trail or cycle exists, throws an error.

A Eulerian trail or cycle is a path that visits every edge of g exactly once; for a cycle, the path starts and ends at vertex u.

Optional arguments

  • If u is omitted, a Eulerian trail or cycle is computed with u = first(vertices(g)).
source
Graphs.all_simple_pathsMethod
all_simple_paths(g, u, v; cutoff)  --> Graphs.SimplePathIterator
all_simple_paths(g, u, vs; cutoff) --> Graphs.SimplePathIterator

Returns an iterator that generates all simple paths in the graph g from a source vertex u to a target vertex v or iterable of target vertices vs. A simple path has no repeated vertices.

The iterator's elements (i.e., the paths) can be materialized via collect or iterate. Paths are iterated in the order of a depth-first search.

If the requested path has identical source and target vertices, i.e., if u = v, a zero-length path [u] is included among the iterates.

Keyword arguments

The maximum path length (i.e., number of edges) is limited by the keyword argument cutoff (default, nv(g)-1). If a path's path length is greater than cutoff, it is omitted.

Examples

julia> g = complete_graph(4);

julia> spi = all_simple_paths(g, 1, 4)
SimplePathIterator{SimpleGraph{Int64}}(1 → 4)

julia> collect(spi)
5-element Vector{Vector{Int64}}:
 [1, 2, 3, 4]
 [1, 2, 4]
 [1, 3, 2, 4]
 [1, 3, 4]
 [1, 4]

We can restrict the search to path lengths less than or equal to a specified cut-off (here, 2 edges):

julia> collect(all_simple_paths(g, 1, 4; cutoff=2))
3-element Vector{Vector{Int64}}:
 [1, 2, 4]
 [1, 3, 4]
 [1, 4]
source