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

structure.

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

  1. distance values for undefined edges will be ignored, and
  2. 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.
  3. 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.

Missing docstring for bfs_tree. Check Documenter's build log for details.

Missing docstring.

Missing docstring for dfs_tree. Check Documenter's build log for details.

Missing docstring.

Missing docstring for maximum_adjacency_visit. Check Documenter's build log for details.

Missing docstring.

Missing docstring for bfs_parents. Check Documenter's build log for details.

Missing docstring.

Missing docstring for has_path. Check Documenter's build log for details.

Missing docstring.

Missing docstring for diffusion. Check Documenter's build log for details.

Missing docstring.

Missing docstring for diffusion_rate. Check Documenter's build log for details.

Missing docstring.

Missing docstring for mincut. Check Documenter's build log for details.

Random walks

LightGraphs includes uniform random walks and self avoiding walks:

Missing docstring.

Missing docstring for randomwalk. Check Documenter's build log for details.

Missing docstring.

Missing docstring for non_backtracking_randomwalk. Check Documenter's build log for details.

Missing docstring.

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.

Missing docstring for is_connected. Check Documenter's build log for details.

Missing docstring.

Missing docstring for is_strongly_connected. Check Documenter's build log for details.

Missing docstring.

Missing docstring for is_weakly_connected. Check Documenter's build log for details.

Missing docstring.

Missing docstring for connected_components. Check Documenter's build log for details.

Missing docstring.

Missing docstring for strongly_connected_components. Check Documenter's build log for details.

Missing docstring.

Missing docstring for strongly_connected_components_kosaraju. Check Documenter's build log for details.

Missing docstring.

Missing docstring for weakly_connected_components. Check Documenter's build log for details.

LightGraphs.has_self_loopsFunction
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
source
Missing docstring.

Missing docstring for attracting_components. Check Documenter's build log for details.

Missing docstring.

Missing docstring for is_bipartite. Check Documenter's build log for details.

Missing docstring.

Missing docstring for bipartite_map. Check Documenter's build log for details.

Missing docstring.

Missing docstring for biconnected_components. Check Documenter's build log for details.

Missing docstring.

Missing docstring for condensation. Check Documenter's build log for details.

Missing docstring.

Missing docstring for neighborhood. Check Documenter's build log for details.

Missing docstring.

Missing docstring for neighborhood_dists. Check Documenter's build log for details.

Missing docstring.

Missing docstring for articulation. Check Documenter's build log for details.

Missing docstring.

Missing docstring for bridges. Check Documenter's build log for details.

Missing docstring.

Missing docstring for period. Check Documenter's build log for details.

Missing docstring.

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.

Missing docstring for is_cyclic. Check Documenter's build log for details.

Missing docstring.

Missing docstring for maxsimplecycles. Check Documenter's build log for details.

Missing docstring.

Missing docstring for simplecycles. Check Documenter's build log for details.

Missing docstring.

Missing docstring for simplecycles_iter. Check Documenter's build log for details.

Missing docstring.

Missing docstring for simplecycles_hawick_james. Check Documenter's build log for details.

Missing docstring.

Missing docstring for simplecyclescount. Check Documenter's build log for details.

Missing docstring.

Missing docstring for simplecycleslength. Check Documenter's build log for details.

Missing docstring.

Missing docstring for simplecycles_limited_length. Check Documenter's build log for details.

Missing docstring.

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_mstFunction
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.
source
LightGraphs.prim_mstFunction
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.

source

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.

Missing docstring for a_star. Check Documenter's build log for details.

Missing docstring.

Missing docstring for dijkstra_shortest_paths. Check Documenter's build log for details.

Missing docstring.

Missing docstring for desopo_pape_shortest_paths. Check Documenter's build log for details.

Missing docstring.

Missing docstring for bellman_ford_shortest_paths. Check Documenter's build log for details.

Missing docstring.

Missing docstring for floyd_warshall_shortest_paths. Check Documenter's build log for details.

Missing docstring.

Missing docstring for yen_k_shortest_paths. Check Documenter's build log for details.

Missing docstring.

Missing docstring for spfa_shortest_paths. Check Documenter's build log for details.

Path discovery / enumeration

Missing docstring.

Missing docstring for gdistances. Check Documenter's build log for details.

Missing docstring.

Missing docstring for gdistances!. Check Documenter's build log for details.

Missing docstring.

Missing docstring for enumerate_paths. Check Documenter's build log for details.

Path States

All path states derive from

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.

Missing docstring for LightGraphs.DijkstraState. Check Documenter's build log for details.

Missing docstring.

Missing docstring for LightGraphs.DEsopoPapeState. Check Documenter's build log for details.

Missing docstring.

Missing docstring for LightGraphs.BellmanFordState. Check Documenter's build log for details.

Missing docstring.

Missing docstring for LightGraphs.FloydWarshallState. Check Documenter's build log for details.

Missing docstring.

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.