# Path and Traversal

*LightGraphs.jl* provides several traversal and shortest-path algorithms, along with various utility functions. Where appropriate, edge distances may be passed in as a matrix of real number values.

Edge distances for most traversals may be passed in as a sparse or dense matrix of values, indexed by `[src,dst]`

vertices. That is, `distmx[2,4] = 2.5`

assigns the distance `2.5`

to the (directed) edge connecting vertex 2 and vertex 4. Note that also for undirected graphs `distmx[4,2]`

has to be set.

Default edge distances may be passed in via the

`LightGraphs.DefaultDistance`

— Type`DefaultDistance`

A matrix-like structure that provides distance values of `1`

for any `src, dst`

combination.

structure.

Any graph traversal will traverse an edge only if it is present in the graph. When a distance matrix is passed in,

- distance values for undefined edges will be ignored, and
- any unassigned values (in sparse distance matrices), for edges that are present in the graph, will be assumed to take the default value of 1.0.
- any zero values (in sparse/dense distance matrices), for edges that are present in the graph, will instead have an implicit edge cost of 1.0.

## Graph Traversal

*Graph traversal* refers to a process that traverses vertices of a graph following certain order (starting from user-input sources). This package implements three traversal schemes:

`BreadthFirst`

,`DepthFirst`

, and`MaximumAdjacency`

.

Missing docstring for `bfs_tree`

. Check Documenter's build log for details.

Missing docstring for `dfs_tree`

. Check Documenter's build log for details.

Missing docstring for `maximum_adjacency_visit`

. Check Documenter's build log for details.

Missing docstring for `bfs_parents`

. Check Documenter's build log for details.

Missing docstring for `has_path`

. Check Documenter's build log for details.

Missing docstring for `diffusion`

. Check Documenter's build log for details.

Missing docstring for `diffusion_rate`

. Check Documenter's build log for details.

Missing docstring for `mincut`

. Check Documenter's build log for details.

## Random walks

*LightGraphs* includes uniform random walks and self avoiding walks:

Missing docstring for `randomwalk`

. Check Documenter's build log for details.

Missing docstring for `non_backtracking_randomwalk`

. Check Documenter's build log for details.

Missing docstring for `self_avoiding_walk`

. Check Documenter's build log for details.

## Connectivity / Bipartiteness

`Graph connectivity`

functions are defined on both undirected and directed graphs:

Missing docstring for `is_connected`

. Check Documenter's build log for details.

Missing docstring for `is_strongly_connected`

. Check Documenter's build log for details.

Missing docstring for `is_weakly_connected`

. Check Documenter's build log for details.

Missing docstring for `connected_components`

. Check Documenter's build log for details.

Missing docstring for `strongly_connected_components`

. Check Documenter's build log for details.

Missing docstring for `strongly_connected_components_kosaraju`

. Check Documenter's build log for details.

Missing docstring for `weakly_connected_components`

. Check Documenter's build log for details.

`LightGraphs.has_self_loops`

— Function`has_self_loops(g)`

Return true if `g`

has any self loops.

**Examples**

```
julia> using LightGraphs
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
```

Missing docstring for `attracting_components`

. Check Documenter's build log for details.

Missing docstring for `is_bipartite`

. Check Documenter's build log for details.

Missing docstring for `bipartite_map`

. Check Documenter's build log for details.

Missing docstring for `biconnected_components`

. Check Documenter's build log for details.

Missing docstring for `condensation`

. Check Documenter's build log for details.

Missing docstring for `neighborhood`

. Check Documenter's build log for details.

Missing docstring for `neighborhood_dists`

. Check Documenter's build log for details.

Missing docstring for `articulation`

. Check Documenter's build log for details.

Missing docstring for `bridges`

. Check Documenter's build log for details.

Missing docstring for `period`

. Check Documenter's build log for details.

Missing docstring for `isgraphical`

. Check Documenter's build log for details.

## Cycle Detection

In graph theory, a cycle is defined to be a path that starts from some vertex `v`

and ends up at `v`

.

Missing docstring for `is_cyclic`

. Check Documenter's build log for details.

Missing docstring for `maxsimplecycles`

. Check Documenter's build log for details.

Missing docstring for `simplecycles`

. Check Documenter's build log for details.

Missing docstring for `simplecycles_iter`

. Check Documenter's build log for details.

Missing docstring for `simplecycles_hawick_james`

. Check Documenter's build log for details.

Missing docstring for `simplecyclescount`

. Check Documenter's build log for details.

Missing docstring for `simplecycleslength`

. Check Documenter's build log for details.

Missing docstring for `simplecycles_limited_length`

. Check Documenter's build log for details.

Missing docstring for `karp_minimum_cycle_mean`

. Check Documenter's build log for details.

## Minimum Spanning Trees (MST) Algorithms

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

`LightGraphs.kruskal_mst`

— Function`kruskal_mst(g, distmx=weights(g); minimize=true)`

Return a vector of edges representing the minimum (by default) spanning tree of a connected, undirected graph `g`

with optional distance matrix `distmx`

using Kruskal's algorithm.

**Optional Arguments**

`minimize=true`

: if set to`false`

, calculate the maximum spanning tree.

`LightGraphs.prim_mst`

— Function`prim_mst(g, distmx=weights(g))`

Return a vector of edges representing the minimum spanning tree of a connected, undirected graph `g`

with optional distance matrix `distmx`

using Prim's algorithm. Return a vector of edges.

## Shortest-Path Algorithms

### General properties of shortest path algorithms

- The distance from a vertex to itself is always
`0`

. - The distance between two vertices with no connecting edge is always
`Inf`

.

Missing docstring for `a_star`

. Check Documenter's build log for details.

Missing docstring for `dijkstra_shortest_paths`

. Check Documenter's build log for details.

Missing docstring for `desopo_pape_shortest_paths`

. Check Documenter's build log for details.

Missing docstring for `bellman_ford_shortest_paths`

. Check Documenter's build log for details.

Missing docstring for `floyd_warshall_shortest_paths`

. Check Documenter's build log for details.

Missing docstring for `yen_k_shortest_paths`

. Check Documenter's build log for details.

Missing docstring for `spfa_shortest_paths`

. Check Documenter's build log for details.

## Path discovery / enumeration

Missing docstring for `gdistances`

. Check Documenter's build log for details.

Missing docstring for `gdistances!`

. Check Documenter's build log for details.

Missing docstring for `enumerate_paths`

. Check Documenter's build log for details.

### Path States

All path states derive from

`LightGraphs.AbstractPathState`

— Type`AbstractPathState`

An abstract type that provides information from shortest paths calculations.

The `dijkstra_shortest_paths`

, `floyd_warshall_shortest_paths`

, `bellman_ford_shortest_paths`

, and `yen_shortest_paths`

functions return states that contain various information about the graph learned during traversal.

Missing docstring for `LightGraphs.DijkstraState`

. Check Documenter's build log for details.

Missing docstring for `LightGraphs.DEsopoPapeState`

. Check Documenter's build log for details.

Missing docstring for `LightGraphs.BellmanFordState`

. Check Documenter's build log for details.

Missing docstring for `LightGraphs.FloydWarshallState`

. Check Documenter's build log for details.

Missing docstring for `LightGraphs.YenState`

. Check Documenter's build log for details.

The above state types (with the exception of `YenState`

) have the following common information, accessible via the type:

`.dists`

Holds a vector of distances computed, indexed by source vertex.

`.parents`

Holds a vector of parents of each vertex on the paths. The parent of a source vertex is always `0`

.

(`YenState`

substitutes `.paths`

for `.parents`

.)

In addition, the following information may be populated with the appropriate arguments to `dijkstra_shortest_paths`

:

`.predecessors`

Holds a vector, indexed by vertex, of all the predecessors discovered during shortest-path calculations. This keeps track of all parents when there are multiple shortest paths available from the source.

`.pathcounts`

Holds a vector, indexed by vertex, of the path counts discovered during traversal. This equals the length of each subvector in the `.predecessors`

output above.