Path and Traversal

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

Missing docstring.

Missing docstring for Graphs.DefaultDistance. Check Documenter's build log for details.

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.
Graphs.bfs_treeFunction
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).

source
Missing docstring.

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

Graphs.dfs_treeFunction
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.

source
Graphs.maximum_adjacency_visitFunction
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.

source
Graphs.bfs_parentsFunction
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.

source
Graphs.has_pathFunction
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.

source
Graphs.diffusionFunction
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)}$.

source
Graphs.diffusion_rateFunction
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.

source
Graphs.mincutFunction
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.

source

Random walks

Graphs includes uniform random walks and self avoiding walks:

Graphs.randomwalkFunction
randomwalk(g, s, niter; seed=-1)

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.

source
Missing docstring.

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

Connectivity / Bipartiteness

Graph connectivity functions are defined on both undirected and directed graphs:

Graphs.is_connectedFunction
is_connected(g)

Return true if graph g is connected. For directed graphs, return true if graph g is weakly connected.

Examples

julia> g = SimpleGraph([0 1 0; 1 0 1; 0 1 0]);

julia> is_connected(g)
true

julia> g = SimpleGraph([0 1 0 0 0; 1 0 1 0 0; 0 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> is_connected(g)
false

julia> g = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> is_connected(g)
true
source
Missing docstring.

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

Graphs.is_weakly_connectedFunction
is_weakly_connected(g)

Return true if the graph g is weakly connected. If g is undirected, this function is equivalent to is_connected(g).

Examples

julia> g = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> is_weakly_connected(g)
true

julia> g = SimpleDiGraph([0 1 0; 1 0 1; 0 0 0]);

julia> is_connected(g)
true

julia> is_strongly_connected(g)
false

julia> is_weakly_connected(g)
true
source
Graphs.connected_componentsFunction
connected_components(g)

Return the connected components of an undirected graph g as a vector of components, with each element a vector of vertices belonging to the component.

For directed graphs, see strongly_connected_components and weakly_connected_components.

Examples

julia> g = SimpleGraph([0 1 0; 1 0 1; 0 1 0]);

julia> connected_components(g)
1-element Array{Array{Int64,1},1}:
 [1, 2, 3]

julia> g = SimpleGraph([0 1 0 0 0; 1 0 1 0 0; 0 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> connected_components(g)
2-element Array{Array{Int64,1},1}:
 [1, 2, 3]
 [4, 5]
source
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.

Graphs.weakly_connected_componentsFunction
weakly_connected_components(g)

Return the weakly connected components of the graph g. This is equivalent to the connected components of the undirected equivalent of g. For undirected graphs this is equivalent to the connected_components of g.

Examples

julia> g = SimpleDiGraph([0 1 0; 1 0 1; 0 0 0]);

julia> weakly_connected_components(g)
1-element Array{Array{Int64,1},1}:
 [1, 2, 3]
source
Graphs.has_self_loopsFunction
has_self_loops(g)

Return true if g has any self loops.

Examples

julia> using Graphs

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.

Graphs.is_bipartiteFunction
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
source
Graphs.bipartite_mapFunction
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
source
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.

Graphs.neighborhoodFunction
neighborhood(g, v, d, distmx=weights(g))

Return a vector of each vertex in g at a geodesic distance less than or equal to d, where distances may be specified by distmx.

Optional Arguments

  • dir=:out: If g is directed, this argument specifies the edge direction

with respect to v of the edges to be considered. Possible values: :in or :out.

Examples

julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> neighborhood(g, 1, 2)
3-element Array{Int64,1}:
 1
 2
 3

julia> neighborhood(g, 1, 3)
4-element Array{Int64,1}:
 1
 2
 3
 4

julia> neighborhood(g, 1, 3, [0 1 0 0 0; 0 0 1 0 0; 1 0 0 0.25 0; 0 0 0 0 0.25; 0 0 0 0.25 0])
5-element Array{Int64,1}:
 1
 2
 3
 4
 5
source
Graphs.neighborhood_distsFunction
neighborhood_dists(g, v, d, distmx=weights(g))

Return a a vector of tuples representing each vertex which is at a geodesic distance less than or equal to d, along with its distance from v. Non-negative distances may be specified by distmx.

Optional Arguments

  • dir=:out: If g is directed, this argument specifies the edge direction

with respect to v of the edges to be considered. Possible values: :in or :out.

Examples

julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> neighborhood_dists(g, 1, 3)
4-element Array{Tuple{Int64,Int64},1}:
 (1, 0)
 (2, 1)
 (3, 2)
 (4, 3)

julia> neighborhood_dists(g, 1, 3, [0 1 0 0 0; 0 0 1 0 0; 1 0 0 0.25 0; 0 0 0 0 0.25; 0 0 0 0.25 0])
5-element Array{Tuple{Int64,Float64},1}:
 (1, 0.0)
 (2, 1.0)
 (3, 2.0)
 (4, 2.25)
 (5, 2.5)

julia> neighborhood_dists(g, 4, 3)
2-element Array{Tuple{Int64,Int64},1}:
 (4, 0)
 (5, 1)

julia> neighborhood_dists(g, 4, 3, dir=:in)
5-element Array{Tuple{Int64,Int64},1}:
 (4, 0)
 (3, 1)
 (5, 1)
 (2, 2)
 (1, 3)
source
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.

Graphs.isgraphicalFunction
isgraphical(degs)

Return true if the degree sequence degs is graphical. A sequence of integers is called graphical, if there exists a graph where the degrees of its vertices form that same sequence.

Performance

Time complexity: $\mathcal{O}(|degs|*\log(|degs|))$.

Implementation Notes

According to Erdös-Gallai theorem, a degree sequence $\{d_1, ...,d_n\}$ (sorted in descending order) is graphic iff the sum of vertex degrees is even and the sequence obeys the property -

\[\sum_{i=1}^{r} d_i \leq r(r-1) + \sum_{i=r+1}^n min(r,d_i)\]

for each integer r <= n-1

source

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.

Graphs.cycle_basisFunction
cycle_basis(g, root=nothing)

Return a list of cycles which form a basis for cycles of the undirected graph g, optionally starting at node root.

A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis. Here summation of cycles is defined as "exclusive or" of the edges. Cycle bases are useful, e.g. when deriving equations for electric circuits using Kirchhoff's Laws.

Examples

julia> elist = [(1,2),(2,3),(2,4),(3,4),(4,1),(1,5)];

julia> g = SimpleGraph(SimpleEdge.(elist));

julia> cycle_basis(g)
2-element Array{Array{Int64,1},1}:
 [2, 3, 4]
 [2, 1, 3]

References

  • Paton, K. An algorithm for finding a fundamental set of cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518. [https://dl.acm.org/citation.cfm?id=363232]
source
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.

Graphs.simplecycles_limited_lengthFunction
simplecycles_limited_length(g, n, ceiling=10^6)

Compute and return at most ceiling cycles of length at most n of the given graph. Both directed and undirected graphs are supported.

Performance

The number of cycles grows very fast with the number of vertices and the allowed length of the cycles. This function is intended for finding short cycles. If you want to find cycles of any length in a directed graph, simplecycles or simplecycles_iter may be more efficient.

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

Missing docstring.

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

Missing docstring.

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

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.
Graphs.a_starFunction
a_star(g, s, t[, distmx][, heuristic])

Return a vector of edges comprising the shortest path between vertices s and t using the A* search algorithm. An optional heuristic function and edge distance matrix may be supplied. If missing, the distance matrix is set to Graphs.DefaultDistance and the heuristic is set to n -> 0.

source
Graphs.dijkstra_shortest_pathsFunction
dijkstra_shortest_paths(g, srcs, distmx=weights(g));

Perform Dijkstra's algorithm on a graph, computing shortest distances between srcs and all other vertices. Return a Graphs.DijkstraState that contains various traversal information.

Optional Arguments

predecessors of a given vertex.

Performance

If using a sparse matrix for distmx, you may achieve better performance by passing in a transpose of its sparse transpose. That is, assuming D is the sparse distance matrix:

D = transpose(sparse(transpose(D)))

Be aware that realizing the sparse transpose of D incurs a heavy one-time penalty, so this strategy should only be used when multiple calls to dijkstra_shortest_paths with the distance matrix are planned.

Examples

julia> using Graphs

julia> ds = dijkstra_shortest_paths(cycle_graph(5), 2);

julia> ds.dists
5-element Array{Int64,1}:
 1
 0
 1
 2
 2

julia> ds = dijkstra_shortest_paths(path_graph(5), 2);

julia> ds.dists
5-element Array{Int64,1}:
 1
 0
 1
 2
 3
source
Graphs.desopo_pape_shortest_pathsFunction
desopo_pape_shortest_paths(g, src, distmx=weights(g))

Compute shortest paths between a source src and all other nodes in graph g using the D'Esopo-Pape algorithm. Return a Graphs.DEsopoPapeState with relevant traversal information.

Examples

julia> using Graphs

julia> ds = desopo_pape_shortest_paths(cycle_graph(5), 2);

julia> ds.dists
5-element Array{Int64,1}:
 1
 0
 1
 2
 2

julia> ds = desopo_pape_shortest_paths(path_graph(5), 2);

julia> ds.dists
5-element Array{Int64,1}:
 1
 0
 1
 2
 3
source
Graphs.yen_k_shortest_pathsFunction
yen_k_shortest_paths(g, source, target, distmx=weights(g), K=1; maxdist=Inf);

Perform Yen's algorithm on a graph, computing k-shortest distances between source and target other vertices. Return a YenState that contains distances and paths.

source
Graphs.spfa_shortest_pathsFunction
spfa_shortest_paths(g, s, distmx=weights(g))

Compute shortest paths between a source s and all other nodes in graph g using the Shortest Path Faster Algorithm.

Examples

julia> g = complete_graph(3);

julia> d = [1 -3 1; -3 1 1; 1 1 1];

julia> spfa_shortest_paths(g, 1, d)

ERROR: Graphs.NegativeCycleError()

julia> g = complete_graph(4);

julia> d = [1 1 -1 1; 1 1 -1 1; 1 1 1 1; 1 1 1 1];

julia> spfa_shortest_paths(gx, 1, d)

4-element Array{Int64,1}:
  0
  0
 -1
  0
source

Path discovery / enumeration

Graphs.gdistancesFunction
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.

source
Graphs.gdistances!Function
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.

source
Graphs.enumerate_pathsFunction
enumerate_paths(state[, vs])

Given a path state state of type AbstractPathState, return a vector (indexed by vertex) of the paths between the source vertex used to compute the path state and a single destination vertex, a list of destination vertices, or the entire graph. For multiple destination vertices, each path is represented by a vector of vertices on the path between the source and the destination. Nonexistent paths will be indicated by an empty vector. For single destinations, the path is represented by a single vector of vertices, and will be length 0 if the path does not exist.

Implementation Notes

For Floyd-Warshall path states, please note that the output is a bit different, since this algorithm calculates all shortest paths for all pairs of vertices: enumerate_paths(state) will return a vector (indexed by source vertex) of vectors (indexed by destination vertex) of paths. enumerate_paths(state, v) will return a vector (indexed by destination vertex) of paths from source v to all other vertices. In addition, enumerate_paths(state, v, d) will return a vector representing the path from vertex v to vertex d.

source

Path States

All path states derive from

Missing docstring.

Missing docstring for Graphs.AbstractPathState. Check Documenter's build log for details.

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 Graphs.DijkstraState. Check Documenter's build log for details.

Missing docstring.

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

Missing docstring.

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

Missing docstring.

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

Missing docstring.

Missing docstring for Graphs.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.