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
— TypeDefaultDistance
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
, andMaximumAdjacency
.
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
— Functionhas_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
— Functionkruskal_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 tofalse
, calculate the maximum spanning tree.
LightGraphs.prim_mst
— Functionprim_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
— TypeAbstractPathState
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.