# Traversals and coloring

*Graphs.jl* includes various routines for exploring graphs.

## Index

`Graphs.Coloring`

`Graphs.bfs_parents`

`Graphs.bfs_tree`

`Graphs.bipartite_map`

`Graphs.degree_greedy_color`

`Graphs.dfs_parents`

`Graphs.dfs_tree`

`Graphs.diffusion`

`Graphs.diffusion_rate`

`Graphs.gdistances`

`Graphs.gdistances!`

`Graphs.greedy_color`

`Graphs.has_path`

`Graphs.is_bipartite`

`Graphs.is_cyclic`

`Graphs.maximum_adjacency_visit`

`Graphs.mincut`

`Graphs.non_backtracking_randomwalk`

`Graphs.perm_greedy_color`

`Graphs.random_greedy_color`

`Graphs.randomwalk`

`Graphs.self_avoiding_walk`

`Graphs.topological_sort_by_dfs`

`Graphs.tree`

## Full docs

`Graphs.bfs_parents`

— Method`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.

`Graphs.bfs_tree`

— Method`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).

`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.

`Graphs.gdistances`

— Method`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.

`Graphs.has_path`

— Method`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`

.

`Graphs.tree`

— Method`tree(parents)`

Convert a parents array into a directed graph.

`Graphs.bipartite_map`

— Method`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 Array{UInt8,1}:
0x01
0x01
0x01
julia> add_vertices!(g, 3);
julia> add_edge!(g, 1, 2);
julia> add_edge!(g, 2, 3);
julia> bipartite_map(g)
3-element Array{UInt8,1}:
0x01
0x02
0x01
```

`Graphs.is_bipartite`

— Method`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
```

`Graphs.dfs_parents`

— Method`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.

`Graphs.dfs_tree`

— Method`dfs_tree(g, s)`

Return an ordered vector of vertices representing a directed acyclic graph based on depth-first traversal of the graph `g`

starting with source vertex `s`

.

`Graphs.is_cyclic`

— Function`is_cyclic(g)`

Return `true`

if graph `g`

contains a cycle.

**Implementation Notes**

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

`Graphs.topological_sort_by_dfs`

— Function`topological_sort_by_dfs(g)`

Return a topological sort of a directed graph `g`

as a vector of vertices in topological order.

`Graphs.diffusion`

— Method`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.

`Graphs.diffusion_rate`

— Method```
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.

`Graphs.Coloring`

— Type`struct Coloring{T}`

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

`Graphs.degree_greedy_color`

— Method`degree_greedy_color(g)`

Color graph `g`

iteratively in the descending order of the degree of the vertices.

`Graphs.greedy_color`

— Method`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.

`Graphs.perm_greedy_color`

— Method`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.

`Graphs.random_greedy_color`

— Method`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.

`Graphs.maximum_adjacency_visit`

— Method```
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.

`Graphs.mincut`

— Method`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 may be specified; if omitted, edge distances are assumed to be 1.

`Graphs.non_backtracking_randomwalk`

— Function`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.

`Graphs.randomwalk`

— Method`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.

`Graphs.self_avoiding_walk`

— Method`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.