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 — TypeDefaultDistanceA 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)
trueMissing 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 — TypeAbstractPathStateAn 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.