Experimental algorithms

IsomorphismAlgorithm

An abstract type used for method dispatch on isomorphism functions.

all_induced_subgraphisomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return all isomorphism from vertex induced subgraphs of g1 to g2. The isomorphisms are returned as an iterator of vectors of tuples, where the i-th vector is the i-th isomorphism and a tuple (u, v) in this vector means that u ∈ g1 is mapped to v ∈ g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> all_induced_subgraphisomorph(path_graph(3), SimpleGraph(2)) |> collect
2-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(1, 1), (3, 2)]
 [(3, 1), (1, 2)]

julia> g1 = path_digraph(3); color1 = [1, 1, 2]
julia> g2 = path_digraph(2); color2 = [1, 2]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> all_induced_subgraphisomorph(g1, g2) |> collect
2-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(1, 1), (2, 2)]
 [(2, 1), (3, 2)]
julia> all_induced_subgraphisomorph(g1, g2, vertex_relation=color_rel) |> collect
1-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(1, 1), (2, 2)]

See also

all_subgraphisomorph, all_isomorph, has_induced_subgraphisomorph, count_induced_subgraphisomorph

all_isomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return all isomorphism from g1 to g2. The isomorphisms are returned as an iterator of vectors of tuples, where the i-th vector is the i-th isomorphism and a tuple (u, v) in this vector means that u ∈ g1 is mapped to v ∈ g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> all_isomorph(star_graph(4), star_graph(4)) |> collect
6-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(1, 1), (2, 2), (3, 3), (4, 4)]
 [(1, 1), (2, 2), (4, 3), (3, 4)]
 [(1, 1), (3, 2), (2, 3), (4, 4)]
 [(1, 1), (3, 2), (4, 3), (2, 4)]
 [(1, 1), (4, 2), (2, 3), (3, 4)]
 [(1, 1), (4, 2), (3, 3), (2, 4)]
 
julia> g1 = cycle_digraph(3); color1 = [1, 1, 2]
julia> g2 = cycle_digraph(3); color2 = [2, 1, 1]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> all_isomorph(g1, g2) |> collect
3-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(1, 1), (2, 2), (3, 3)]
 [(2, 1), (3, 2), (1, 3)]
 [(3, 1), (1, 2), (2, 3)]
julia> all_subgraphisomorph(g1, g2, vertex_relation=color_rel)
1-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(3, 1), (1, 2), (2, 3)]

See also

all_induced_subgraphisomorph, all_subgraphisomorph, has_isomorph, count_isomorph

all_subgraphisomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return all isomorphism from subgraphs of g1 to g2. The isomorphisms are returned as an iterator of vectors of tuples, where the i-th vector is the i-th isomorphism and a tuple (u, v) in this vector means that u ∈ g1 is mapped to v ∈ g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> all_subgraphisomorph(path_graph(3), path_graph(2)) |> collect
4-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(1, 1), (2, 2)]
 [(2, 1), (1, 2)]
 [(2, 1), (3, 2)]
 [(3, 1), (2, 2)]

julia> g1 = path_digraph(3); color1 = [1, 1, 2]
julia> g2 = path_digraph(2); color2 = [1, 2]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> all_subgraphisomorph(g1, g2) |> collect
2-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(1, 1), (2, 2)]
 [(2, 1), (3, 2)]
julia> all_subgraphisomorph(g1, g2, vertex_relation=color_rel)
1-element Array{Array{Tuple{Int64,Int64},1},1}:
 [(2, 1), (3, 2)]

See also

all_induced_subgraphisomorph, all_isomorph, has_subgraphisomorph, count_subgraphisomorph

could_have_isomorph(g1, g2)

Run quick test to check if g1 andg2` could be isomorphic.

If the result is false, then g1 and g2 are definitely not isomorphic, but if the result is true this is not guaranteed.

Examples

julia> using Graphs

julia> Graphs.Experimental.could_have_isomorph(path_graph(3), star_graph(4))
false

julia> Graphs.Experimental.could_have_isomorph(path_graph(3), star_graph(3))
true

count_induced_subgraphisomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return the number of vertex induced subgraphs of the graph g1 that are isomorphic to g2.

Optional Arguments

• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> count_induced_subgraphisomorph(complete_graph(5), complete_graph(4))
120
julia> count_induced_subgraphisomorph(complete_graph(5), cycle_graph(4))
0

julia> g1 = path_graph(3); color1 = [1, 1, 2]
julia> g2 = path_graph(2); color2 = [1, 2]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> count_induced_subgraphisomorph(g1, g2)
2
julia> count_induced_subgraphisomorph(g1, g2, vertex_relation=color_rel)
1

See also

count_subgraphisomorph, count_isomorph, has_induced_subgraphisomorph, all_induced_subgraphisomorph

count_isomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return the number of isomorphism from graph g1 to g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> count_isomorph(cycle_graph(5), cycle_graph(5))
10
julia> count_isomorph(complete_graph(5), cycle_graph(5))
0

julia> g1 = cycle_digraph(3); color1 = [1, 1, 2]
julia> g2 = cycle_digraph(3); color2 = [1, 1, 1]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> count_isomorph(g1, g2)
3
julia> count_isomorph(g1, g2, vertex_relation=color_rel)
0

See also

count_induced_subgraphisomorph, count_subgraphisomorph, has_isomorph, all_isomorph

count_subgraphisomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return the number of subgraphs of the graph g1 that are isomorphic to g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> count_subgraphisomorph(complete_graph(5), complete_graph(4))
120
julia> count_subgraphisomorph(complete_graph(5), cycle_graph(4))
120

julia> g1 = cycle_digraph(3); color1 = [1, 1, 2]
julia> g2 = SimpleDiGraph(2); color2 = [1, 2]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> count_subgraphisomorph(g1, g2)
6
julia> count_subgraphisomorph(g1, g2, vertex_relation=color_rel)
2

See also

count_induced_subgraphisomorph, count_isomorph, has_subgraphisomorph, all_subgraphisomorph

has_induced_subgraphisomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return true if the graph g1 contains a vertex induced subgraph that is isomorphic to g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> has_induced_subgraphisomorph(complete_graph(5), complete_graph(4))
true
julia> has_induced_subgraphisomorph(complete_graph(5), cycle_graph(4))
false

julia> g1 = path_digraph(3); color1 = [1, 1, 1]
julia> g2 = path_digraph(2); color2 = [1, 2]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> has_induced_subgraphisomorph(g1, g2)
true
julia> has_induced_subgraphisomorph(g1, g2, vertex_relation=color_rel)
false

See also

has_subgraphisomorph, has_isomorph, count_induced_subgraphisomorph, all_induced_subgraphisomorph

has_isomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return true if the graph g1 is isomorphic to g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> has_isomorph(complete_graph(3), cycle_graph(3))
true
julia> has_isomorph(complete_graph(4), cycle_graph(4))
false

julia> g1 = path_digraph(4); color1 = [1, 2, 1, 1]
julia> g2 = path_digraph(4); color2 = [1, 2, 2, 1]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> has_isomorph(g1, g2)
true
julia> has_isomorph(g1, g2, vertex_relation=color_rel)
false

See also

has_induced_subgraphisomorph, has_subgraphisomorph, count_subgraphisomorph, all_subgraphisomorph

has_subgraphisomorph(g1, g2, alg::IsomorphismAlgorithm=VF2(); vertex_relation=nothing, edge_relation=nothing)

Return true if the graph g1 contains a subgraph that is isomorphic to g2.

Optional Arguments

• alg: The algorithm that is used to find the induced subgraph isomorphism. Can be only VF2() at the moment.
• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

Examples

julia> has_subgraphisomorph(complete_graph(5), complete_graph(4))
true
julia> has_subgraphisomorph(complete_graph(5), cycle_graph(4))
true

julia> g1 = path_digraph(3); color1 = [1, 1, 1]
julia> g2 = path_digraph(2); color2 = [1, 2]
julia> color_rel(u, v) = (color1[u] == color2[v])
julia> has_subgraphisomorph(g1, g2)
true
julia> has_subgraphisomorph(g1, g2, vertex_relation=color_rel)
false

See also

has_induced_subgraphisomorph, has_isomorph, count_subgraphisomorph, all_subgraphisomorph

VF2

An empty concrete type used to dispatch to vf2 isomorphism functions.

VF2State{G, T}

Structure that is internally used by vf2

vf2(callback, g1, g2, problemtype; vertex_relation=nothing, edge_relation=nothing)

Iterate over all isomorphism between the graphs g1 (or subgraphs thereof) and g2. The problem that is solved depends on the value of problemtype:

• IsomorphismProblem(): Only isomorphisms between the whole graph g1 and g2 are considered.
• SubGraphIsomorphismProblem(): All isomorphism between subgraphs of g1 and g2 are considered.
• InducedSubGraphIsomorphismProblem(): All isomorphism between vertex induced subgraphs of g1 and g2 are considered.

Upon finding an isomorphism, the function callback is called with a vector vmap as an argument. vmap is a vector where vmap[v] == u means that vertex v in g2 is mapped to vertex u in g1. If the algorithm should look for another isomorphism, then this function should return true.

Optional Arguments

• vertex_relation: A binary function that takes a vertex from g1 and one from g2. An isomorphism only exists if this function returns true for all matched vertices.
• edge_relation: A binary function that takes an edge from g1 and one from g2. An isomorphism only exists if this function returns true for all matched edges.

References

Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs”

vf2check_feasibility(u, v, state, problemtype, vertex_relation, edge_relation)

Check whether two vertices of G₁ and G₂ can be matched. Used by vf2match!.

vf2match!(state, depth, callback, problemtype, vertex_relation, edge_relation)

Perform isomorphic subgraph matching. Called by vf2.

vf2reset_state!(state, u, v, depth)

Reset state after returning from recursion. Helper function for vf2match!.

vf2update_state!(state, u, v, depth)

Update state before recursing. Helper function for vf2match!.

distances(g, s, alg=BFS())
distances(g, ss, alg=BFS())

Return a vector filled with the geodesic distances of vertices in g from vertex s / unique vertices ss using BFS traversal algorithm alg. For vertices in disconnected components the default distance is typemax(T).

traverse_graph!(g, s, alg, state, neighborfn=outneighbors)
traverse_graph!(g, ss, alg, state, neighborfn=outneighbors)

Traverse a graph `g` starting at vertex `s` / vertices `ss` using algorithm `alg`, maintaining state in [`AbstractTraversalState`](@ref) `state`. Next vertices to be visited are determined by `neighborfn` (default `outneighbors`). Return `true` if traversal finished; `false` if one of the visit functions caused an early termination.

abstract type AbstractTraversalState

AbstractTraversalState is the abstract type used to hold mutable states for various traversal algorithms (see traverse_graph!).

When creating concrete types, you should override the following functions where relevant. These functions are listed in order of occurrence in the traversal:

• initfn!(<:AbstractTraversalState, u::Integer): runs prior to traversal, used to set initial state.
• previsitfn!(<:AbstractTraversalState, u::Integer): runs prior to neighborhood discovery for vertex u.
• visitfn!(<:AbstractTraversalState, u::Integer, v::Integer): runs for each neighbor v (newly-discovered or not) of vertex u.
• newvisitfn!(<:AbstractTraversalState, u::Integer, v::Integer): runs when a new neighbor v of vertex u is discovered.
• postvisitfn!(<:AbstractTraversalState, u::Integer): runs after neighborhood discovery for vertex u.
• postlevelfn!(<:AbstractTraversalState): runs after each traversal level.

Each of these functions should return a boolean. If the return value of the function is false, the traversal will return the state immediately. Otherwise, the traversal will continue.

For better performance, use the @inline directive and make your functions branch-free.

abstract type TraversalAlgorithm

TraversalAlgorithm is the abstract type used to specify breadth-first traversal (BFS) or depth-first traversal (DFS) for the various traversal functions.

initfn!(state, u)

Modify AbstractTraversalState state on initialization of traversal with source vertices, and return true if successful; false otherwise. initfn! will be called once for each vertex passed to traverse_graph!.

newvisitfn!(state, u, v)

Modify AbstractTraversalState state when the first edge between u and v is encountered, and return true if successful; false otherwise.

parents(g, s, alg, neighborfn=outneighbors)

Return a vector of parent vertices indexed by vertex using TraversalAlgorithm alg starting with vertex s. If neighborfn is specified, use the corresponding neighbor-generation function (inneighborsr and outneighbors are valid 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.

postlevelfn!(state)

Modify AbstractTraversalState state before moving to the next vertex in the traversal algorithm, and return true if successful; false otherwise.

postvisitfn!(state, u)

Modify AbstractTraversalState state after having examined all neighbors of vertex u, and return true if successful; false otherwise.

previsitfn!(state, u)

Modify AbstractTraversalState state before examining neighbors of vertex u, and return true if successful; false otherwise.

traverse_graph!(g, s, alg, state, neighborfn=outneighbors)
traverse_graph!(g, ss, alg, state, neighborfn=outneighbors)

Traverse a graph g from source vertex s / vertices ss keeping track of state. Return true if traversal finished normally; false if one of the visit functions returned false (see )

tree(g, s, alg, neighborfn=outneighbors)

Return a directed acyclic graph based on traversal of the graph g starting with source vertex s using algorithm alg with neighbor function neighborfn.

tree(p)

Return a directed acyclic graph based on a parents vector p.

visited_vertices(g, s, alg)
visited_vertices(g, ss, alg)

Return a vector representing the vertices of g visited in order by TraversalAlgorithm alg starting at vertex s (vertices ss).

visitfn!(state, u, v)

Modify AbstractTraversalState state when the edge between u and v is encountered, and return true if successful; false otherwise. Note: visitfn! may be called multiple times per edge, depending on the traversal algorithm, for a function that operates on the first occurrence only, use newvisitfn!.

struct AStar <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use the A* search algorithm. An optional heuristic function may be supplied. If missing, the heuristic is set to n -> 0.

Implementation Notes

AStar supports the following shortest-path functionality:

• non-negative distance matrices / weights
• single destination

struct BellmanFord <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use the Bellman-Ford algorithm. No fields are specified or required.

Implementation Notes

BellmanFord supports the following shortest-path functionality:

• negative distance matrices / weights
• (optional) multiple sources
• all destinations

struct BFS <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use the Breadth-First Search algorithm.

An optional sorting algorithm may be specified (default = no sorting). Sorting helps maintain cache locality and will improve performance on very large graphs; for normal use, sorting will incur a performance penalty.

BFS is the default algorithm used when a source is specified but no distance matrix is specified.

Implementation Notes

BFS supports the following shortest-path functionality:

• (optional) multiple sources
• all destinations

struct DEsopoPape <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use the D'Esopo-Pape algorithm. No fields are specified or required.

Implementation Notes

DEsopoPape supports the following shortest-path functionality:

• non-negative distance matrices / weights
• all destinations

struct Dijkstra <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use Dijkstra's algorithm to compute shortest paths. Optional fields for this structure include

• all_paths::Bool - set to true to calculate all (redundant, equivalent) paths to a given destination
• track_vertices::Bool - set to true to keep a running list of visited vertices (used for specific centrality calculations; generally not needed).

Dijkstra is the default algorithm used when a distance matrix is specified.

Implementation Notes

Dijkstra supports the following shortest-path functionality:

• non-negative distance matrices / weights
• (optional) multiple sources
• all destinations
• redundant equivalent path tracking
• vertex tracking

Performance

If using a sparse matrix for distmx in shortest_paths, 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 shortest_paths with the distance matrix are planned.

struct FloydWarshall <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use the Floyd-Warshall algorithm. No additional configuration parameters are specified or required.

FloydWarshall is the default all-pairs algorithm used when no source is specified.

Implementation Notes

FloydWarshall supports the following shortest-path functionality:

• non-negative distance matrices / weights
• all-pairs shortest paths

Performance

Space complexity is on the order of $\mathcal{O}(|V|^2)$.

struct Johnson <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use the Johnson algorithm. No additional configuration parameters are specified or required.

Implementation Notes

Johnson supports the following shortest-path functionality:

• non-negative distance matrices / weights
• all-pairs shortest paths

Performance

Complexity: O(|V|*|E|)

ShortestPathAlgorithm <: AbstractGraphAlgorithm

Concrete subtypes of ShortestPathAlgorithm are used to specify the type of shortest path calculation used by shortest_paths. Some concrete subtypes (most notably Dijkstra have fields that specify algorithm parameters.

See AStar, BellmanFord, BFS, DEsopoPape, Dijkstra, FloydWarshall, Johnson, and SPFA for specific requirements and usage details.

ShortestPathResult <: AbstractGraphResult

Concrete subtypes of ShortestPathResult contain the results of a shortest-path calculation using a specific ShortestPathAlgorithm.

In general, the fields in these structs should not be accessed directly; use the dists and paths functions to obtain the results of the calculation.

dists(state[, v])

Given the output of a shortest_paths calculation of type ShortestPathResult, return a vector (indexed by vertex) of the distances between the source vertex used to compute the shortest path and a single destination vertex v or the entire graph.

For ShortestPathAlgorithms that compute all-pairs shortest paths, dists(state) will return a matrix (indexed by source and destination vertices) of distances.

has_negative_weight_cycle(g[, distmx=weights(g), alg=BellmanFord()])

Given a graph g, an optional distance matrix distmx, and an optional algorithm alg (one of BellmanFord or SPFA), return true if any cycle detected in the graph has a negative weight.

Examples

julia> using Graphs, Graphs.Experimental.ShortestPaths

julia> g = complete_graph(3);

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

julia> has_negative_weight_cycle(g, d)
true

julia> g = complete_graph(4);

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

julia> has_negative_weight_cycle(g, d, SPFA())
false

paths(state[, v])
paths(state[, vs])
paths(state[, v, d]))

Given the output of a shortest_paths calculation of type ShortestPathResult, return a vector (indexed by vertex) of the paths between the source vertex used to compute the shortest path and a single destination vertex v, a vector of destination vertices vs, 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.

For ShortestPathAlgorithms that compute all shortest paths for all pairs of vertices, paths(state) will return a vector (indexed by source vertex) of vectors (indexed by destination vertex) of paths. paths(state, v) will return a vector (indexed by destination vertex) of paths from source v to all other vertices. In addition, paths(state, v, d) will return a vector representing the path from vertex v to vertex d.

shortest_paths(g, s, distmx, alg)
shortest_paths(g, s, t, alg)
shortest_paths(g, s, alg)
shortest_paths(g, s)
shortest_paths(g)

Return a ShortestPathResult that allows construction of the shortest path between sets of vertices in graph g. Depending on the algorithm specified, other information may be required: (e.g., a distance matrix distmx, and/or a target vertex t). Some algorithms will accept multiple source vertices s; algorithms that do not accept any source vertex s produce all-pairs shortest paths.

See ShortestPathAlgorithm for more details on the algorithm specifications.

Implementation Notes

The elements of distmx may be of any type that has a Total Ordering and valid comparator, zero and typemax functions. Concretely, this means that distance matrices containing complex numbers are invalid.

Examples

g = path_graph(4)
w = zeros(4, 4)
for i in 1:3
    w[i, i+1] = 1.0
    w[i+1, i] = 1.0
end

s1 = shortest_paths(g)                   # `alg` defaults to `FloydWarshall`
s2 = shortest_paths(g, 1)                # `alg` defaults to `BFS`
s3 = shortest_paths(g, 1, w)             # `alg` defaults to `Dijkstra`
s4 = shortest_paths(g, 1, BellmanFord())
s5 = shortest_paths(g, 1, w, DEsopoPape())

struct SPFA <: ShortestPathAlgorithm

The structure used to configure and specify that shortest_paths should use the Shortest Path Faster Algorithm. No additional configuration parameters are specified or required.

Implementation Notes

SPFA supports the following shortest-path functionality:

• non-negative distance matrices / weights
• all destinations

Function which returns true if there is any negative weight cycle in the graph.

Examples

julia> using Graphs

julia> g = complete_graph(3);

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

julia> has_negative_weight_cycle(g, d, SPFA())
true

julia> g = complete_graph(4);

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

julia> has_negative_weight_cycle(g, d, SPFA());
false

gdistances!(g, sources, vert_level; queue_segment_size=20)
gdistances!(g, source, vert_level; queue_segment_size=20)

Parallel implementation of Graphs.gdistances! with dynamic load balancing.

Optional Arguments

• queue_segment_size = 20: It is the number of vertices a thread can claim from a queue

at a time. For graphs with uniform degree, a larger value of queue_segment_size could improve performance.

References

• [Avoiding Locks and Atomic Instructions in Shared-Memory Parallel BFS Using Optimistic

Parallelization](https://www.computer.org/csdl/proceedings/ipdpsw/2013/4979/00/4979b628-abs.html).

gdistances(g, sources; queue_segment_size=20)
gdistances(g, source; queue_segment_size=20)

Parallel implementation of Graphs.gdistances! with dynamic load balancing.

Optional Arguments

• queue_segment_size = 20: It is the number of vertices a thread can claim from a queue at a time.

For denser graphs, a smaller value of queue_segment_size could improve performance.

References

• [Avoiding Locks and Atomic Instructions in Shared-Memory Parallel BFS Using Optimistic

Parallelization](https://www.computer.org/csdl/proceedings/ipdpsw/2013/4979/00/4979b628-abs.html).

partition_sources!(queue_list, sources)

Partition sources using Graphs.unweighted_contiguous_partition and place the i^{th} partition into queue_list[i] and set to empty_list[i] to true if the i^{th} partition is empty.