Community Structures

Graphs.jl contains many algorithm to detect and analyze community structures in graphs. These include:

Full Docs

Graphs.GraphsModule
Graphs

An optimized graphs package.

Simple graphs (not multi- or hypergraphs) are represented in a memory- and time-efficient manner with adjacency lists and edge sets. Both directed and undirected graphs are supported via separate types, and conversion is available from directed to undirected.

The project goal is to mirror the functionality of robust network and graph analysis libraries such as NetworkX while being simpler to use and more efficient than existing Julian graph libraries such as Graphs.jl. It is an explicit design decision that any data not required for graph manipulation (attributes and other information, for example) is expected to be stored outside of the graph structure itself. Such data lends itself to storage in more traditional and better-optimized mechanisms.

Full documentation is available, and tutorials are available at the JuliaGraphsTutorials repository.

source
Graphs.DefaultDistanceType
DefaultDistance

An array-like structure that provides distance values of 1 for any src, dst combination.

source
Graphs.EdgeType
Edge

A datastruture representing an edge between two vertices in a Graph or DiGraph.

source
Graphs.JohnsonVisitorType
type JohnsonVisitor{T<:Integer} <: Visitor{T}
    stack::Vector{T}
    blocked::BitVector
    blockedmap::Vector{Set{T}}
end

JohnsonVisitor(dg::::IsDirected)

Composite type that regroups the information needed for Johnson's algorithm.

stack is the stack of visited vertices. blocked is a boolean for each vertex that tells whether it is blocked or not. blockedmap tells which vertices to unblock if the key vertex is unblocked.

JohnsonVisitor may also be constructed directly from the directed graph.

source
Graphs.NotImplementedErrorType
NotImplementedError{M}(m)

Exception thrown when a method from the AbstractGraph interface is not implemented by a given graph type.

source
Base.eltypeMethod
eltype(g)

Return the type of the graph's vertices (must be <: Integer)

source
Base.intersectMethod
intersect(g, h)

Return a graph with edges that are only in both graph g and graph h.

Implementation Notes

This function may produce a graph with 0-degree vertices. Preserves the eltype of the input graph.

Examples

julia> g1 = 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> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> foreach(println, edges(intersect(g1, g2)))
Edge 1 => 2
Edge 2 => 3
Edge 3 => 1
source
Base.joinMethod
join(g, h)

Return a graph that combines graphs g and h using blockdiag and then adds all the edges between the vertices in g and those in h.

Implementation Notes

Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.

Examples

julia> using Graphs

julia> g = join(star_graph(3), path_graph(2))
{5, 9} undirected simple Int64 graph

julia> collect(edges(g))
9-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 1 => 5
 Edge 2 => 4
 Edge 2 => 5
 Edge 3 => 4
 Edge 3 => 5
 Edge 4 => 5
source
Base.reverseFunction
reverse(g)

Return a directed graph where all edges are reversed from the original directed graph.

Implementation Notes

Preserves the eltype of the input graph.

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> foreach(println, edges(reverse(g)))
Edge 1 => 3
Edge 2 => 1
Edge 3 => 2
Edge 4 => 3
Edge 4 => 5
Edge 5 => 4
source
Base.reverse!Function
reverse!(g)

In-place reverse of a directed graph (modifies the original graph). See reverse for a non-modifying version.

source
Base.reverseMethod
reverse(e)

Create a new edge from e with source and destination vertices reversed.

Examples

julia> using Graphs

julia> g = SimpleDiGraph(2);

julia> add_edge!(g, 1, 2);

julia> reverse(first(edges(g)))
Edge 2 => 1
source
Base.sizeMethod
size(g, i)

Return the number of vertices in g if i=1 or i=2, or 1 otherwise.

Examples

julia> using Graphs

julia> g = cycle_graph(4);

julia> size(g, 1)
4

julia> size(g, 2)
4

julia> size(g, 3)
1
source
Base.sumMethod
sum(g, i)

Return a vector of indegree (i=1) or outdegree (i=2) values for graph g.

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> sum(g, 2)
5-element Array{Int64,1}:
 1
 1
 2
 1
 1

julia> sum(g, 1)
5-element Array{Int64,1}:
 1
 1
 1
 2
 1
source
Base.sumMethod
sum(g)

Return the number of edges in g.

Examples

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

julia> sum(g)
2
source
Base.unionMethod
union(g, h)

Return a graph that combines graphs g and h by taking the set union of all vertices and edges.

Implementation Notes

Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.

Examples

julia> using Graphs

julia> g = SimpleGraph(3); h = SimpleGraph(5);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 1, 3);

julia> add_edge!(h, 3, 4);

julia> add_edge!(h, 3, 5);

julia> add_edge!(h, 4, 5);

julia> f = union(g, h);

julia> collect(edges(f))
5-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 3 => 4
 Edge 3 => 5
 Edge 4 => 5
source
Base.zeroMethod
zero(G)

Return a zero-vertex, zero-edge version of the graph type G. The fallback is defined for graph values zero(g::G) = zero(G).

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> zero(typeof(g))
{0, 0} directed simple Int64 graph

julia> zero(g)
{0, 0} directed simple Int64 graph
source
Graphs.BoundedMinkowskiCostMethod
BoundedMinkowskiCost(μ₁, μ₂)

Return value similar to MinkowskiCost, but ensure costs smaller than 2τ.

Optional Arguments

p=1: the p value for p-norm calculation. τ=1: value specifying half of the upper limit of the Minkowski cost.

source
Graphs.MinkowskiCostMethod
MinkowskiCost(μ₁, μ₂; p::Real=1)

For labels μ₁ on the vertices of graph G₁ and labels μ₂ on the vertices of graph G₂, compute the p-norm cost of substituting vertex u ∈ G₁ by vertex v ∈ G₂.

Optional Arguments

p=1: the p value for p-norm calculation.

source
Graphs.a_starMethod
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.add_vertices!Method
add_vertices!(g, n)

Add n new vertices to the graph g. Return the number of vertices that were added successfully.

Examples

julia> using Graphs

julia> g = SimpleGraph()
{0, 0} undirected simple Int64 graph

julia> add_vertices!(g, 2)
2
source
Graphs.all_neighborsFunction
all_neighbors(g, v)

Return a list of all inbound and outbound neighbors of v in g. For undirected graphs, this is equivalent to both outneighbors and inneighbors.

Implementation Notes

Returns a reference to the current graph's internal structures, not a copy. Do not modify result. If the graph is modified, the behavior is undefined: the array behind this reference may be modified too, but this is not guaranteed.

Examples

```jldoctest julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

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

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

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

source
Graphs.articulationFunction
articulation(g)

Compute the articulation points of a connected graph g and return an array containing all cut vertices.

Examples

julia> using Graphs

julia> articulation(star_graph(5))
1-element Array{Int64,1}:
 1

julia> articulation(path_graph(5))
3-element Array{Int64,1}:
 2
 3
 4
source
Graphs.assortativityMethod
assortativity(g)

Return the assortativity coefficient of graph g, defined as the Pearson correlation of excess degree between the end vertices of all the edges of the graph.

The excess degree is equal to the degree of linked vertices minus one, i.e. discounting the edge that links the pair. In directed graphs, the paired values are the out-degree of source vertices and the in-degree of destination vertices.

Examples

julia> using Graphs

julia> assortativity(star_graph(4))
-1.0
source
Graphs.attracting_componentsFunction
attracting_components(g)

Return a vector of vectors of integers representing lists of attracting components in the directed graph g.

The attracting components are a subset of the strongly connected components in which the components do not have any leaving edges.

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])
{5, 6} directed simple Int64 graph

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

julia> attracting_components(g)
1-element Array{Array{Int64,1},1}:
 [4, 5]
source
Graphs.bfs_parentsMethod
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.bfs_treeMethod
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
Graphs.biconnected_componentsFunction
biconnected_components(g) -> Vector{Vector{Edge{eltype(g)}}}

Compute the biconnected components of an undirected graph gand return a vector of vectors containing each biconnected component.

Performance: Time complexity is $\mathcal{O}(|V|)$.

Examples

julia> using Graphs

julia> biconnected_components(star_graph(5))
4-element Array{Array{Graphs.SimpleGraphs.SimpleEdge,1},1}:
 [Edge 1 => 3]
 [Edge 1 => 4]
 [Edge 1 => 5]
 [Edge 1 => 2]

julia> biconnected_components(cycle_graph(5))
1-element Array{Array{Graphs.SimpleGraphs.SimpleEdge,1},1}:
 [Edge 1 => 5, Edge 4 => 5, Edge 3 => 4, Edge 2 => 3, Edge 1 => 2]
source
Graphs.bipartite_mapMethod
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
Graphs.boruvka_mstFunction
boruvka_mst(g, distmx = weights(g); minimize = true)

Return a tuple (mst, weights) where mst is a vector of edges representing the optimum (minimum, by default) spanning tree of a connected, undirected graph g with optional matrix distmx that provides distinct edge weights, and weights is the sum of all the edges in the solution by using Boruvka's algorithm. The algorithm requires that all edges have different weights to correctly generate a minimun/maximum spanning tree

Optional Arguments

  • minimize=true: if set to false, calculate the maximum spanning tree.
source
Graphs.bridgesFunction
bridges(g)

Compute the bridges of a connected graph g and return an array containing all bridges, i.e edges whose deletion increases the number of connected components of the graph.

Examples

julia> using Graphs

julia> bridges(star_graph(5))
8-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 1 => 5

julia> bridges(path_graph(5))
8-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 4 => 5
 Edge 3 => 4
 Edge 2 => 3
 Edge 1 => 2
source
Graphs.cartesian_productMethod
cartesian_product(g, h)

Return the cartesian product of g and h.

Implementation Notes

Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.

Examples

julia> using Graphs

julia> g = cartesian_product(star_graph(3), path_graph(3))
{9, 12} undirected simple Int64 graph

julia> collect(edges(g))
12-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 4
 Edge 1 => 7
 Edge 2 => 3
 Edge 2 => 5
 Edge 2 => 8
 Edge 3 => 6
 Edge 3 => 9
 Edge 4 => 5
 Edge 5 => 6
 Edge 7 => 8
 Edge 8 => 9
source
Graphs.centerMethod
center(eccentricities)
center(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the set of all vertices whose eccentricity is equal to the graph's radius (that is, the set of vertices with the smallest eccentricity).

Examples

julia> using Graphs

julia> center(star_graph(5))
1-element Array{Int64,1}:
 1

julia> center(path_graph(5))
1-element Array{Int64,1}:
 3
source
Graphs.circuitFunction
circuit{T<:Integer}(v::T, dg::::IsDirected, vis::JohnsonVisitor{T},
allcycles::Vector{Vector{T}}, vmap::Vector{T}, startnode::T = v)

Return one step of the recursive version of simple cycle detection, using a DFS algorithm.

  • v: the vertex considered in this iteration of the DFS
  • dg: the digraph from which cycles are computed
  • visitor: Informations needed for the cycle computation, contains:
    • stack: the stack of parent vertices
    • blocked: tells whether a vertex has already been explored or not
    • blockedmap: mapping of the blocking / unblocking consequences
  • allcycles: output containing the cycles already detected
  • vmap: vector map containing the link from the old to the new nodes of the directed graph
  • startnode = v: optional argument giving the starting node. In the first iteration,

the same as v, otherwise it should be passed.

Implementation Notes

Implements Johnson's CIRCUIT function. This is a recursive version. Modifies the vector of cycles, when needed.

References

source
Graphs.circuit_iterFunction
circuit_iter{T<:Integer}(v::T, dg::::IsDirected, vis::JohnsonVisitor{T},
vmap::Vector{T}, cycle::Channel, startnode::T = v)

Execute one step of the recursive version of simple cycle detection, using a DFS algorithm. Return true if a circuit has been found in the current exploration.

Arguments

  • v: the vertex considered in this iteration of the DFS
  • dg: the digraph from which cycles are computed
  • visitor: Informations needed for the cycle computation, contains:
    • stack: the stack of parent vertices
    • blocked: tells whether a vertex has already been explored or not
    • blockedmap: mapping of the blocking / unblocking consequences
  • vmap: vector map containing the link from the old to the new nodes of the directed graph
  • cycle: storage of the channel
  • startnode = v: optional argument giving the starting node. In the first iteration,

the same as v, otherwise it should be passed.

Implementation Notes

Implements the CIRCUIT function from Johnson's algorithm, recursive and iterative version. Produces a cycle when needed. Can be used only inside a Channel.

References

source
Graphs.clique_percolationFunction
clique_percolation(g, k=3)

Community detection using the clique percolation algorithm. Communities are potentionally overlapping. Return a vector of vectors c such that c[i] is the set of vertices in community i. The parameter k defines the size of the clique to use in percolation.

References

Examples

julia> using Graphs

julia> clique_percolation(clique_graph(3, 2))
2-element Array{BitSet,1}:
 BitSet([4, 5, 6])
 BitSet([1, 2, 3])

julia> clique_percolation(clique_graph(3, 2), k=2)
1-element Array{BitSet,1}:
 BitSet([1, 2, 3, 4, 5, 6])

julia> clique_percolation(clique_graph(3, 2), k=4)
0-element Array{BitSet,1}
source
Graphs.common_neighborsMethod
common_neighbors(g, u, v)

Return the neighbors common to vertices u and v in g.

Implementation Notes

Returns a reference to the current graph's internal structures, not a copy. Do not modify result. If the graph is modified, the behavior is undefined: the array behind this reference may be modified too, but this is not guaranteed.

Examples

julia> using Graphs

julia> g = SimpleGraph(4);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 4);

julia> add_edge!(g, 4, 1);

julia> add_edge!(g, 1, 3);

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

julia> common_neighbors(g, 1, 4)
1-element Array{Int64,1}:
 3
source
Graphs.complementMethod
complement(g)

Return the graph complement of a graph

Implementation Notes

Preserves the eltype of the input graph.

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> foreach(println, edges(complement(g)))
Edge 1 => 3
Edge 1 => 4
Edge 1 => 5
Edge 2 => 1
Edge 2 => 4
Edge 2 => 5
Edge 3 => 2
Edge 3 => 5
Edge 4 => 1
Edge 4 => 2
Edge 4 => 3
Edge 5 => 1
Edge 5 => 2
Edge 5 => 3
source
Graphs.componentsMethod
components(labels)

Given a vector of component labels, return a vector of vectors representing the vertices associated with a given component id.

source
Graphs.components_dictMethod
components_dict(labels)

Convert an array of labels to a map of component id to vertices, and return a map with each key corresponding to a given component id and each value containing the vertices associated with that component.

source
Graphs.compute_shiftsMethod
compute_shifts(n::Int, x::AbstractArray)

Determine how many elements of x are less than i for all i in 1:n.

source
Graphs.condensationFunction
condensation(g[, scc])

Return the condensation graph of the strongly connected components scc in the directed graph g. If scc is missing, generate the strongly connected components first.

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])
{5, 6} directed simple Int64 graph

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

julia> foreach(println, edges(condensation(g)))
Edge 2 => 1
source
Graphs.connected_components!Method
connected_components!(label, g)

Fill label with the id of the connected component in the undirected graph g to which it belongs. Return a vector representing the component assigned to each vertex. The component value is the smallest vertex ID in the component.

Performance

This algorithm is linear in the number of edges of the graph.

source
Graphs.connected_componentsMethod
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
Graphs.core_numberMethod
core_number(g)

Return the core number for each vertex in graph g.

A k-core is a maximal subgraph that contains vertices of degree k or more. The core number of a vertex is the largest value k of a k-core containing that vertex.

Implementation Notes

Not implemented for graphs with self loops.

References

  • An O(m) Algorithm for Cores Decomposition of Networks, Vladimir Batagelj and Matjaz Zaversnik, 2003. http://arxiv.org/abs/cs.DS/0310049

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> add_vertex!(g);

julia> add_edge!(g, 5, 2);

julia> core_number(g)
6-element Array{Int64,1}:
 1
 2
 2
 2
 2
 0
source
Graphs.core_periphery_degFunction
core_periphery_deg(g)

Compute the degree-based core-periphery for graph g. Return the vertex assignments (1 for core and 2 for periphery) for each node in g.

References: Lip)

Examples

julia> using Graphs

julia> core_periphery_deg(star_graph(5))
5-element Array{Int64,1}:
 1
 2
 2
 2
 2

julia> core_periphery_deg(path_graph(3))
3-element Array{Int64,1}:
 2
 1
 2
source
Graphs.crosspathFunction
crosspath(len::Integer, g::Graph)

Return a graph that duplicates g len times and connects each vertex with its copies in a path.

Implementation Notes

Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.

Examples

julia> using Graphs

julia> g = crosspath(3, path_graph(3))
{9, 12} undirected simple Int64 graph

julia> collect(edges(g))
12-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 4
 Edge 2 => 3
 Edge 2 => 5
 Edge 3 => 6
 Edge 4 => 5
 Edge 4 => 7
 Edge 5 => 6
 Edge 5 => 8
 Edge 6 => 9
 Edge 7 => 8
 Edge 8 => 9
source
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
Graphs.deepcopy_adjlistMethod
deepcopy_adjlist(adjlist::Vector{Vector{T}})

Internal utility function for copying adjacency lists. On adjacency lists this function is more efficient than deepcopy for two reasons:

  • As of Julia v1.0.2, deepcopy is not typestable.
  • deepcopy needs to track all references when traversing a recursive data structure in order to ensure that references to the same location do need get assigned to different locations in the copy. Because we can assume that all lists in our adjacency list are different, we don't need to keep track of them.

If T is not a bitstype (e.g. BigInt), we use the standard deepcopy.

source
Graphs.degreeFunction
degree(g[, v])

Return a vector corresponding to the number of edges which start or end at each vertex in graph g. If v is specified, only return degrees for vertices in v. For directed graphs, this value equals the incoming plus outgoing edges. For undirected graphs, it equals the connected edges.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> degree(g)
3-element Array{Int64,1}:
 1
 1
 2
source
Graphs.degree_histogramMethod
degree_histogram(g, degfn=degree)

Return a Dict with values representing the number of vertices that have degree represented by the key.

Degree function (for example, indegree or outdegree) may be specified by overriding degfn.

source
Graphs.densityFunction
density(g)

Return the density of g. Density is defined as the ratio of the number of actual edges to the number of possible edges ($|V|×(|V|-1)$ for directed graphs and $\frac{|V|×(|V|-1)}{2}$ for undirected graphs).

source
Graphs.desopo_pape_shortest_pathsMethod
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.dfs_parentsMethod
dfs_parents(g, s[; dir=:out])

Perform a depth-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).

Implementation Notes

This version of DFS is iterative.

source
Graphs.dfs_treeMethod
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.diameterMethod
diameter(eccentricities)
diameter(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the maximum eccentricity of the graph.

Examples

julia> using Graphs

julia> diameter(star_graph(5))
2

julia> diameter(path_graph(5))
4
source
Graphs.differenceMethod
difference(g, h)

Return a graph with edges in graph g that are not in graph h.

Implementation Notes

Note that this function may produce a graph with 0-degree vertices. Preserves the eltype of the input graph.

Examples

julia> g1 = 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> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> foreach(println, edges(difference(g1, g2)))
Edge 3 => 4
Edge 4 => 5
Edge 5 => 4
source
Graphs.diffusionMethod
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_rateMethod
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.dijkstra_shortest_pathsMethod
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.dominating_setMethod
dominating_set(g, DegreeDominatingSet())

Obtain a dominating set using a greedy heuristic.

Implementation Notes

A vertex is said to be dominated if it is in the dominating set or adjacent to a vertex in the dominating set. Initialise the dominating set to an empty set and iteratively choose the vertex that would dominate the most undominated vertices.

Performance

Runtime: $\mathcal{O}((|V|+|E|)*log(|V|))$ Memory: $\mathcal{O}(|V|)$ Approximation Factor: ln(maximum(degree(g)))+2

source
Graphs.dominating_setMethod
dominating_set(g, MinimalDominatingSet(); seed=-1)

Find a set of vertices that consitute a dominating set (all vertices in g are either adjacent to a vertex in the set or is a vertex in the set) and it is not possible to delete a vertex from the set without sacrificing the dominating property.

Implementation Notes

Initially, every vertex is in the dominating set. In some random order, we check if the removal of a vertex from the set will destroy the dominating property. If no, the vertex is removed from the dominating set.

Performance

Runtime: $\mathcal{O}(|V|+|E|)$ Memory: $\mathcal{O}(|V|)$

Optional Arguments

  • If seed >= 0, a random generator is seeded with this value.
source
Graphs.dstMethod
dst(e)

Return the destination vertex of edge e.

Examples

julia> using Graphs

julia> g = SimpleGraph(2);

julia> add_edge!(g, 1, 2);

julia> dst(first(edges(g)))
2
source
Graphs.eccentricityMethod
eccentricity(g[, v][, distmx])
eccentricity(g[, vs][, distmx])

Return the eccentricity[ies] of a vertex / vertex list v or a set of vertices vs defaulting to the entire graph. An optional matrix of edge distances may be supplied; if missing, edge distances default to 1.

The eccentricity of a vertex is the maximum shortest-path distance between it and all other vertices in the graph.

The output is either a single float (when a single vertex is provided) or a vector of floats corresponding to the vertex vector. If no vertex vector is provided, the vector returned corresponds to each vertex in the graph.

Performance

Because this function must calculate shortest paths for all vertices supplied in the argument list, it may take a long time.

Implementation Notes

The eccentricity vector returned by eccentricity() may be used as input for the rest of the distance measures below. If an eccentricity vector is provided, it will be used. Otherwise, an eccentricity vector will be calculated for each call to the function. It may therefore be more efficient to calculate, store, and pass the eccentricities if multiple distance measures are desired.

An infinite path length is represented by the typemax of the distance matrix.

Examples

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

julia> eccentricity(g, 1)
2

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

julia> eccentricity(g, [1; 2], [0 2 0; 0.5 0 0.5; 0 2 0])
2-element Array{Float64,1}:
 2.5
 0.5
source
Graphs.edgesMethod
edges(g)

Return (an iterator to or collection of) the edges of a graph. For AbstractSimpleGraphs it returns a SimpleEdgeIter. The expressions e in edges(g) and e ∈ edges(ga) evaluate as calls to has_edge.

Implementation Notes

A returned iterator is valid for one pass over the edges, and is invalidated by changes to g.

Examples

julia> using Graphs

julia> g = path_graph(3);

julia> collect(edges(g))
2-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3
source
Graphs.edit_distanceMethod
edit_distance(G₁::AbstractGraph, G₂::AbstractGraph)

Compute the edit distance between graphs G₁ and G₂. Return the minimum edit cost and edit path to transform graph G₁ into graph G₂. An edit path consists of a sequence of pairs of vertices(u,v) ∈ [0,|G₁|] × [0,|G₂|]` representing vertex operations:

  • $(0,v)$: insertion of vertex $v ∈ G₂$
  • $(u,0)$: deletion of vertex $u ∈ G₁$
  • $(u>0,v>0)$: substitution of vertex $u ∈ G₁$ by vertex $v ∈ G₂$

Optional Arguments

  • insert_cost::Function=v->1.0
  • delete_cost::Function=u->1.0
  • subst_cost::Function=(u,v)->0.5

By default, the algorithm uses constant operation costs. The user can provide classical Minkowski costs computed from vertex labels μ₁ (for G₁) and μ₂ (for G₂) in order to further guide the search, for example:

edit_distance(G₁, G₂, subst_cost=MinkowskiCost(μ₁, μ₂))
  • heuristic::Function=DefaultEditHeuristic: a custom heuristic provided to the A*

search in case the default heuristic is not satisfactory.

Performance

  • Given two graphs $|G₁| < |G₂|$, edit_distance(G₁, G₂) is faster to

compute than edit_distance(G₂, G₁). Consider swapping the arguments if involved costs are equivalent.

  • The use of simple Minkowski costs can improve performance considerably.
  • Exploit vertex attributes when designing operation costs.

References

  • RIESEN, K., 2015. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. (Chapter 2)

Author

  • Júlio Hoffimann Mendes (juliohm@stanford.edu)

Examples

julia> g1 = 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> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> edit_distance(g1, g2)
(3.5, Tuple[(1, 2), (2, 1), (3, 0), (4, 3), (5, 0)])
source
Graphs.egonetMethod
egonet(g, v, d, distmx=weights(g))

Return the subgraph of g induced by the neighbors of v up to distance d, using weights (optionally) provided by distmx. This is equivalent to induced_subgraph(g, neighborhood(g, v, d, dir=dir))[1].

Optional Arguments

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

with respect to v (i.e. :in or :out).

source
Graphs.enumerate_pathsMethod
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
Graphs.findall!Method
findall!(A, B)

Set the B[1:|I|] to I where I is the set of indices A[I] returns true.

Assumes length(B) >= |I|.

source
Graphs.gdistances!Method
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.gdistancesMethod
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.greedy_contiguous_partitionMethod
greedy_contiguous_partition(weight, required_partitions, num_items=length(weight))

Partition 1:num_items into atmost required_partitions number of contiguous partitions with the objective of minimising the largest partition. The size of a partition is equal to the num of the weight of its elements. weight[i] > 0.

Performance

Time: O(numitems+requiredpartitions) Requires only one iteration over weight but may not output the optimal partition.

Implementation Notes

Balance(wt, left, right, n_items, n_part) = max(sum(wt[left:right])*(n_part-1), sum(wt[right+1:n_items])). Find right that minimises Balance(weight, 1, right, num_items, required_partitions). Set the first partition as 1:right. Repeat on indices right+1:num_items and one less partition.

source
Graphs.has_edgeMethod
has_edge(g, s, d)

Return true if the graph g has an edge from node s to node d.

An optional has_edge(g, e) can be implemented to check if an edge belongs to a graph, including any data other than source and destination node.

e ∈ edges(g) or e ∈ edges(g) evaluate as calls to has_edge, c.f. edges.

Examples

julia> using Graphs

julia> g = SimpleDiGraph(2);

julia> add_edge!(g, 1, 2);

julia> has_edge(g, 1, 2)
true

julia> has_edge(g, 2, 1)
false
source
Graphs.has_negative_edge_cycle_spfaMethod

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

Examples

julia> g = complete_graph(3);

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

julia> has_negative_edge_cycle_spfa(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_edge_cycle_spfa(g, d);
false
source
Graphs.has_pathMethod
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.has_self_loopsMethod
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
Graphs.has_vertexMethod
has_vertex(g, v)

Return true if v is a vertex of g.

Examples

julia> using Graphs

julia> has_vertex(SimpleGraph(2), 1)
true

julia> has_vertex(SimpleGraph(2), 3)
false
source
Graphs.indegreeMethod
indegree(g[, v])

Return a vector corresponding to the number of edges which end at each vertex in graph g. If v is specified, only return degrees for vertices in v.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> indegree(g)
3-element Array{Int64,1}:
 1
 0
 1
source
Graphs.independent_setMethod
independent_set(g, DegreeIndependentSet())

Obtain an independent set of g using a greedy heuristic based on the degree of the vertices.

Implementation Notes

A vertex is said to be valid if it is not in the independent set or adjacent to any vertex in the independent set. Initilalise the independent set to an empty set and iteratively choose the vertex that is adjacent to the fewest valid vertices in the independent set until all vertices are invalid.

Performance

Runtime: O((|V|+|E|)*log(|V|)) Memory: O(|V|)

source
Graphs.independent_setMethod
independent_set(g, MaximalIndependentSet(); seed=-1)

Find a random set of vertices that are independent (no two vertices are adjacent to each other) and it is not possible to insert a vertex into the set without sacrificing the independence property.

Implementation Notes

Performs Approximate Maximum Independent Set once. Returns a vector of vertices representing the vertices in the independent set.

Performance

Runtime: O(|V|+|E|) Memory: O(|V|) Approximation Factor: maximum(degree(g))+1

Optional Arguments

  • If seed >= 0, a random generator is seeded with this value.
source
Graphs.induced_subgraphMethod
induced_subgraph(g, vlist)
induced_subgraph(g, elist)

Return the subgraph of g induced by the vertices in vlist or edges in elist along with a vector mapping the new vertices to the old ones (the vertex i in the subgraph corresponds to the vertex vmap[i] in g.)

The returned graph has length(vlist) vertices, with the new vertex i corresponding to the vertex of the original graph in the i-th position of vlist.

Usage Examples

julia> g = complete_graph(10)

julia> sg, vmap = induced_subgraph(g, 5:8)

julia> @assert g[5:8] == sg

julia> @assert nv(sg) == 4

julia> @assert ne(sg) == 6

julia> @assert vm[4] == 8

julia> sg, vmap = induced_subgraph(g, [2,8,3,4])

julia> @assert sg == g[[2,8,3,4]]

julia> elist = [Edge(1,2), Edge(3,4), Edge(4,8)]

julia> sg, vmap = induced_subgraph(g, elist)

julia> @assert sg == g[elist]
source
Graphs.inneighborsMethod
inneighbors(g, v)

Return a list of all neighbors connected to vertex v by an incoming edge.

Implementation Notes

Returns a reference to the current graph's internal structures, not a copy. Do not modify result. If the graph is modified, the behavior is undefined: the array behind this reference may be modified too, but this is not guaranteed.

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> inneighbors(g, 4)
2-element Array{Int64,1}:
 3
 5
source
Graphs.insortedMethod
insorted(item, collection)

Return true if item is in sorted collection collection.

Implementation Notes

Does not verify that collection is sorted.

source
Graphs.is_bipartiteMethod
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.is_connectedMethod
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
Graphs.is_cyclicFunction
is_cyclic(g)

Return true if graph g contains a cycle.

Implementation Notes

Uses DFS.

source
Graphs.is_directedMethod
is_directed(G)

Return true if the graph type G is a directed graph; false otherwise. New graph types must implement is_directed(::Type{<:G}). The method can also be called with is_directed(g::G)

Examples

julia> using Graphs

julia> is_directed(SimpleGraph(2))
false

julia> is_directed(SimpleGraph)
false

julia> is_directed(SimpleDiGraph(2))
true
source
Graphs.is_orderedMethod
is_ordered(e)

Return true if the source vertex of edge e is less than or equal to the destination vertex.

Examples

julia> using Graphs

julia> g = DiGraph(2);

julia> add_edge!(g, 2, 1);

julia> is_ordered(first(edges(g)))
false
source
Graphs.is_strongly_connectedFunction
is_strongly_connected(g)

Return true if directed graph g is strongly connected.

Examples

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

julia> is_strongly_connected(g)
true
source
Graphs.is_weakly_connectedMethod
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.isgraphicalMethod
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
Graphs.itercyclesFunction
itercycles(dg::::IsDirected, cycle::Channel)

Compute all cycles of the given directed graph, using Johnson's algorithm.

Implementation Notes

Iterative version of the algorithm, using Channels to stop the exploration after a given number of cycles.

References

source
Graphs.k_coreFunction
k_core(g[, k]; corenum=core_number(g))

Return a vector of vertices in the k-core of graph g. If k is not specified, return the core with the largest degree.

A k-core is a maximal subgraph that contains vertices of degree k or more.

Implementation Notes

Not implemented for graphs with self loops.

References

  • An O(m) Algorithm for Cores Decomposition of Networks, Vladimir Batagelj and Matjaz Zaversnik, 2003. http://arxiv.org/abs/cs.DS/0310049

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> add_vertex!(g);

julia> add_edge!(g, 5, 2);

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

julia> k_core(g, 2)
4-element Array{Int64,1}:
 2
 3
 4
 5
source
Graphs.k_coronaMethod
k_corona(g, k; corenum=core_number(g))

Return a vector of vertices in the k-corona of g.

The k-corona is the subgraph of vertices in the k-core which have exactly k neighbors in the k-core.

Implementation Notes

Not implemented for graphs with parallel edges or self loops.

References

  • k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects, A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, Phys. Rev. E 73, 056101 (2006) http://link.aps.org/doi/10.1103/PhysRevE.73.056101

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> add_vertex!(g);

julia> add_edge!(g, 5, 2);

julia> k_corona(g, 0)
1-element Array{Int64,1}:
 6

julia> k_corona(g, 1)
1-element Array{Int64,1}:
 1

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

julia> k_corona(g, 3)
0-element Array{Int64,1}
source
Graphs.k_crustFunction
k_crust(g[, k]; corenum=core_number(g))

Return a vector of vertices in the k-crust of g. If k is not specified, return the crust of the core with the largest degree.

The k-crust is the graph g with the k-core removed.

Implementation Notes

This definition of k-crust is different than the definition in References. The k-crust in References is equivalent to the k+1 crust of this algorithm.

Not implemented for graphs with self loops.

References

  • A model of Internet topology using k-shell decomposition Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 http://www.pnas.org/content/104/27/11150.full

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> add_vertex!(g);

julia> add_edge!(g, 5, 2);

julia> k_crust(g, 0)
1-element Array{Int64,1}:
 6

julia> k_crust(g, 1)
2-element Array{Int64,1}:
 1
 6

julia> k_crust(g, 2)
6-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6
source
Graphs.k_shellFunction
k_shell(g[, k]; corenum=core_number(g))

Return a vector of vertices in the k-shell of g. If k is not specified, return the shell of the core with the largest degree.

The k-shell is the subgraph of vertices in the k-core but not in the (k+1)-core. This is similar to k_corona but in that case only neighbors in the k-core are considered.

Implementation Notes

Not implemented for graphs with parallel edges or self loops.

References

  • A model of Internet topology using k-shell decomposition Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir, PNAS July 3, 2007 vol. 104 no. 27 11150-11154 http://www.pnas.org/content/104/27/11150.full

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> add_vertex!(g);

julia> add_edge!(g, 5, 2);

julia> k_shell(g, 0)
1-element Array{Int64,1}:
 6

julia> k_shell(g, 1)
1-element Array{Int64,1}:
 1

julia> k_shell(g, 2)
4-element Array{Int64,1}:
 2
 3
 4
 5
source
Graphs.karger_cut_costMethod
karger_cut_cost(g, cut)

Find the number of crossing edges in a cut of graph g where the cut is represented by the integer array, cut.

source
Graphs.karger_cut_edgesMethod
karger_cut_edges(g, cut)

Find the crossing edges in a cut of graph g where the cut is represented by the integer array, cut.

source
Graphs.karger_min_cutMethod
karger_min_cut(g)

Perform Karger Minimum Cut to find the minimum cut of graph g with some probability of success. A cut is a partition of vertices(g) into two non-empty sets. The size of a cut is the number of edges crossing the two non-empty sets.

Implementation Notes

The cut is represented by an integer array. If cut[v] == 1 then v is in the first non-empty set. If cut[v] == 2 then v is in the second non-empty set. cut[1] = 1.

If |V| < 2 then cut[v] = 0 for all v.

Performance

Runtime: O(|E|) Memory: O(|E|)

source
Graphs.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
Graphs.label_propagationMethod
label_propagation(g, maxiter=1000)

Community detection using the label propagation algorithm. Return two vectors: the first is the label number assigned to each node, and the second is the convergence history for each node. Will return after maxiter iterations if convergence has not completed.

References

source
Graphs.loadgraphMethod
loadgraph(file, gname="graph", format=LGFormat())

Read a graph named gname from file in the format format.

Implementation Notes

gname is graph-format dependent and is only used if the file contains multiple graphs; if the file format does not support multiple graphs, this value is ignored. The default value may change in the future.

source
Graphs.loadgraphsMethod
loadgraphs(file, format=LGFormat())

Load multiple graphs from file in the format format. Return a dictionary mapping graph name to graph.

Implementation Notes

For unnamed graphs the default name "graph" will be used. This default may change in the future.

source
Graphs.local_clusteringMethod
local_clustering(g, v)
local_clustering(g, vs)

Return a tuple (a, b), where a is the number of triangles in the neighborhood of v and b is the maximum number of possible triangles. If a list of vertices vs is specified, return two vectors representing the number of triangles and the maximum number of possible triangles, respectively, for each node in the list.

This function is related to the local clustering coefficient r by $r=\frac{a}{b}$.

source
Graphs.local_clustering_coefficientMethod
local_clustering_coefficient(g, v)
local_clustering_coefficient(g, vs)

Return the local clustering coefficient for node v in graph g. If a list of vertices vs is specified, return a vector of coefficients for each node in the list.

Examples

julia> using Graphs

julia> g = SimpleGraph(4);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 4);

julia> add_edge!(g, 4, 1);

julia> local_clustering_coefficient(g, [1, 2, 3])
3-element Array{Float64,1}:
 1.0
 1.0
 0.0
source
Graphs.maximal_cliquesFunction
maximal_cliques(g)

Return a vector of vectors representing the node indices in each of the maximal cliques found in the undirected graph g.

julia> using Graphs
julia> g = SimpleGraph(3)
julia> add_edge!(g, 1, 2)
julia> add_edge!(g, 2, 3)
julia> maximal_cliques(g)
2-element Array{Array{Int64,N},1}:
 [2,3]
 [2,1]
source
Graphs.maximum_adjacency_visitMethod
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.maxsimplecyclesFunction
maxsimplecycles(dg::::IsDirected, byscc::Bool = true)

Compute the theoretical maximum number of cycles in the directed graph dg.

The computation can be performed assuming the graph is complete or taking into account the decomposition in strongly connected components (byscc parameter).

Performance

A more efficient version is possible.

References

source
Graphs.maxsimplecyclesMethod
maxsimplecycles(n::Integer)

Compute the theoretical maximum number of cycles in a directed graph of n vertices, assuming there are no self-loops.

References

source
Graphs.merge_vertices!Method
merge_vertices!(g, vs)

Combine vertices specified in vs into single vertex whose index will be the lowest value in vs. All edges connected to vertices in vs connect to the new merged vertex.

Return a vector with new vertex values are indexed by the original vertex indices.

Implementation Notes

Supports SimpleGraph only.

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> collect(edges(g))
4-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3
 Edge 3 => 4
 Edge 4 => 5

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

julia> collect(edges(g))
3-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3
 Edge 3 => 4
source
Graphs.merge_verticesMethod
merge_vertices(g::AbstractGraph, vs)

Create a new graph where all vertices in vs have been aliased to the same vertex minimum(vs).

Examples

julia> using Graphs

julia> g = path_graph(5);

julia> collect(edges(g))
4-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3
 Edge 3 => 4
 Edge 4 => 5

julia> h = merge_vertices(g, [2, 3]);

julia> collect(edges(h))
3-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3
 Edge 3 => 4
source
Graphs.mincutMethod
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
Graphs.modularityMethod
modularity(g, c, distmx=weights(g), γ=1.0)

Return a value representing Newman's modularity Q for the undirected and directed graph g given the partitioning vector c. This method also supports weighted graphs if the distance matrix is provided.

Modularity $Q$ for undirected graph:

\[Q = \frac{1}{2m} \sum_{c} \left( e_{c} - \gamma \frac{K_c^2}{2m} \right)\]

Modularity $Q$ for directed graph:

\[Q = \frac{1}{m} \sum_{c} \left( e_{c} - \gamma \frac{K_c^{in} K_c^{out}}{m} \right)\]

where:

  • $m$: total number of edges in the network
  • $e_c$: number of edges in community $c$
  • $K_c$: sum of the degrees of the nodes in community $c$ or the sum of the weighted degree of the nodes in community $c$ when the graph is weighted. $K_c^{in}$ sum of the in-degrees of the nodes in community $c$.

Optional Arguments

  • distmx=weights(g): distance matrix for weighted graphs
  • γ=1.0: where γ > 0 is a resolution parameter. When the modularity is used to find communities structure in networks (i.e with Louvain's method for community detection), higher resolutions lead to more communities, while lower resolutions lead to fewer communities. Where γ=1.0 it lead to the traditional definition of the modularity.

References

  • M. E. J. Newman and M. Girvan. "Finding and evaluating community structure in networks". Phys. Rev. E 69, 026113 (2004). (arXiv)
  • J. Reichardt and S. Bornholdt. "Statistical mechanics of community detection". Phys. Rev. E 74, 016110 (2006). (arXiv)
  • E. A. Leicht and M. E. J. Newman. "Community structure in directed networks". Physical Review Letter, 100:118703, (2008). (arXiv)

Examples

julia> using Graphs

julia> barbell = blockdiag(complete_graph(3), complete_graph(3));

julia> add_edge!(barbell, 1, 4);

julia> modularity(barbell, [1, 1, 1, 2, 2, 2])
0.35714285714285715

julia> modularity(barbell, [1, 1, 1, 2, 2, 2], γ=0.5)
0.6071428571428571  

julia> using SimpleWeightedGraphs

julia> triangle = SimpleWeightedGraph(3);

julia> add_edge!(triangle, 1, 2, 1);

julia> add_edge!(triangle, 2, 3, 1);

julia> add_edge!(triangle, 3, 1, 1);

julia> barbell = blockdiag(triangle, triangle);

julia> add_edge!(barbell, 1, 4, 5); # this edge has a weight of 5

julia> modularity(barbell, [1, 1, 1, 2, 2, 2])
0.045454545454545456
source
Graphs.ncycles_n_iMethod
ncycles_n_i(n::Integer, i::Integer)

Compute the theoretical maximum number of cycles of size i in a directed graph of n vertices.

source
Graphs.neMethod
ne(g)

Return the number of edges in g.

Examples

julia> using Graphs

julia> g = path_graph(3);

julia> ne(g)
2
source
Graphs.neighborhoodMethod
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_distsMethod
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
Graphs.neighborsMethod
neighbors(g, v)

Return a list of all neighbors reachable from vertex v in g. For directed graphs, the default is equivalent to outneighbors; use all_neighbors to list inbound and outbound neighbors.

Implementation Notes

Returns a reference to the current graph's internal structures, not a copy. Do not modify result. If the graph is modified, the behavior is undefined: the array behind this reference may be modified too, but this is not guaranteed.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> neighbors(g, 1)
0-element Array{Int64,1}

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

julia> neighbors(g, 3)
1-element Array{Int64,1}:
 1
source
Graphs.noallocextremeMethod
noallocextreme(f, comparison, initial, g)

Compute the extreme value of [f(g,i) for i=i:nv(g)] without gathering them all

source
Graphs.non_backtracking_randomwalkFunction
non_backtracking_randomwalk(g, s, niter; seed=-1)

Perform a non-backtracking random walk on directed graph g starting at vertex s and continuing for a maximum of niter steps. Return a vector of vertices visited in order.

source
Graphs.normalized_cutMethod
normalized_cut(g, thres, distmx=weights(g), [num_cuts=10]);

Perform recursive two-way normalized graph-cut on a graph, partitioning the vertices into disjoint sets. Return a vector that contains the set index for each vertex.

It is important to identify a good threshold for your application. A bisection search over the range (0,1) will help determine a good value of thres.

Keyword Arguments

  • thres: Subgraphs aren't split if best normalized cut is above this threshold
  • num_cuts: Number of cuts performed to determine optimal cut

References

"Normalized Cuts and Image Segmentation" - Jianbo Shi and Jitendra Malik

source
Graphs.num_self_loopsMethod
num_self_loops(g)

Return the number of self loops in g.

Examples

julia> using Graphs

julia> g = SimpleGraph(2);

julia> add_edge!(g, 1, 2);

julia> num_self_loops(g)
0

julia> add_edge!(g, 1, 1);

julia> num_self_loops(g)
1
source
Graphs.nvMethod
nv(g)

Return the number of vertices in g.

Examples

julia> using Graphs

julia> nv(SimpleGraph(3))
3
source
Graphs.optimal_contiguous_partitionMethod
optimal_contiguous_partition(weight, required_partitions, num_items=length(weight))

Partition 1:num_items into atmost required_partitions number of contiguous partitions such that the largest partition is minimised. The size of a partition is equal to the sum of the weight of its elements. weight[i] > 0.

Performance

Time: O(num_items*log(sum(weight)))

Implementation Notes

Binary Search for the partitioning over [fld(sum(weight)-1, required_partitions), sum(weight)].

source
Graphs.outdegreeMethod
outdegree(g[, v])

Return a vector corresponding to the number of edges which start at each vertex in graph g. If v is specified, only return degrees for vertices in v.

Examples

julia> using Graphs

julia> g = DiGraph(3);

julia> add_edge!(g, 2, 3);

julia> add_edge!(g, 3, 1);

julia> outdegree(g)
3-element Array{Int64,1}:
 0
 1
 1
source
Graphs.outneighborsMethod
outneighbors(g, v)

Return a list of all neighbors connected to vertex v by an outgoing edge.

Implementation Notes

Returns a reference to the current graph's internal structures, not a copy. Do not modify result. If the graph is modified, the behavior is undefined: the array behind this reference may be modified too, but this is not guaranteed.

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> outneighbors(g, 4)
1-element Array{Int64,1}:
 5
source
Graphs.periodFunction
period(g)

Return the (common) period for all vertices in a strongly connected directed graph. Will throw an error if the graph is not strongly connected.

Examples

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

julia> period(g)
3
source
Graphs.peripheryMethod
periphery(eccentricities)
periphery(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the set of all vertices whose eccentricity is equal to the graph's diameter (that is, the set of vertices with the largest eccentricity).

Examples

julia> using Graphs

julia> periphery(star_graph(5))
4-element Array{Int64,1}:
 2
 3
 4
 5

julia> periphery(path_graph(5))
2-element Array{Int64,1}:
 1
 5
source
Graphs.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
Graphs.radiusMethod
radius(eccentricities)
radius(g, distmx=weights(g))

Given a graph and optional distance matrix, or a vector of precomputed eccentricities, return the minimum eccentricity of the graph.

Examples

julia> using Graphs

julia> radius(star_graph(5))
1

julia> radius(path_graph(5))
2
source
Graphs.randomwalkMethod
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
Graphs.range_shuffle!Method
range_shuffle!(r, a; seed=-1)

Fast shuffle Array a in UnitRange r. Uses seed to initialize the random number generator, defaulting to Random.GLOBAL_RNG for seed=-1.

source
Graphs.sample!Method
sample!([rng, ]a, k)

Sample k element from array a without repetition and eventually excluding elements in exclude.

Optional Arguments

  • exclude=(): elements in a to exclude from sampling.

Implementation Notes

Changes the order of the elements in a. For a non-mutating version, see sample.

source
Graphs.sampleMethod
sample([rng,] r, k)

Sample k element from unit range r without repetition and eventually excluding elements in exclude.

Optional Arguments

  • exclude=(): elements in a to exclude from sampling.

Implementation Notes

Unlike sample!, does not produce side effects.

source
Graphs.savegraphMethod
savegraph(file, g, gname="graph", format=LGFormat)

Saves a graph g with name gname to file in the format format. Return the number of graphs written.

Implementation Notes

The default graph name assigned to gname may change in the future.

source
Graphs.savegraphMethod
savegraph(file, g, d, format=LGFormat)

Save a dictionary of graphname => graph to file in the format format. Return the number of graphs written.

Implementation Notes

Will only work if the file format supports multiple graph types.

source
Graphs.savelgMethod
savelg(io, g, gname)

Write a graph g with name gname in a proprietary format to the IO stream designated by io. Return 1 (number of graphs written).

source
Graphs.savelg_multMethod
savelg_mult(io, graphs)

Write a dictionary of (name=>graph) to an IO stream io, with default GZip compression. Return number of graphs written.

source
Graphs.simplecyclesFunction
simplecycles(dg::::IsDirected)

Compute and return all cycles of the given directed graph using Johnson's algorithm.

Performance

The number of cycles grows more than exponentially with the number of vertices, you might want to use the algorithm with a ceiling – simplecycles_iter – on large directed graphs (slightly slower). If you want to have an idea of the possible number of cycles, look at function maxsimplecycles(dg::DiGraph, byscc::Bool = true). If you only need short cycles of a limited length, simplecycles_limited_length can be more efficient.

References

Examples

julia> simplecycles(complete_digraph(3))
5-element Array{Array{Int64,1},1}:
 [1, 2]
 [1, 2, 3]
 [1, 3]
 [1, 3, 2]
 [2, 3]
source
Graphs.simplecycles_hawick_jamesFunction
simplecycles_hawick_james(g)

Find circuits (including self-loops) in g using the algorithm of Hawick & James.

References

  • Hawick & James, "Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs", 2008
source
Graphs.simplecycles_iterFunction
simplecycles_iter(dg::DiGraph, ceiling = 10^6)

Search all cycles of the given directed graph, using Johnson's algorithm, up to the ceiling (to avoid memory overload).

Implementation Notes

If the graph is small, the ceiling will not be reached and simplecycles(dg::DiGraph) is more efficient. It avoids the overhead of the counting and testing if the ceiling is reached. It returns all the cycles of the directed graph if the ceiling is not reached, a subset of them otherwise.

To get an idea of the possible number of cycles, use function `maxsimplecycles(dg::DiGraph, byscc::Bool = true) on the directed graph.

References

source
Graphs.simplecycles_limited_lengthMethod
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
Graphs.simplecyclescountFunction
simplecyclescount(dg::DiGraph, ceiling = 10^6)

Count the number of cycles in a directed graph, using Johnson's algorithm. Return the minimum of the ceiling and the number of cycles.

Implementation Notes

The ceiling is here to avoid memory overload if there are a lot of cycles in the graph. Default value is 10^6, but it can be higher or lower. You can use the function maxsimplecycles(dg::DiGraph, byscc::Bool = true) to get an idea of the theoretical maximum number or cycles.

References

Examples

julia> simplecyclescount(complete_digraph(6))
409
source
Graphs.simplecycleslengthFunction
simplecycleslength(dg::DiGraph, ceiling = 10^6)

Search all cycles of the given directed graph, using Johnson's algorithm, and return a tuple representing the cycle length and the number of cycles.

Implementation Notes

To get an idea of the possible number of cycles, using function maxsimplecycles(dg::DiGraph, byscc::Bool = true) on the directed graph.

If the ceiling is reached (ncycles = ceiling), the output is only a subset of the cycles lengths.

References

Examples

julia> simplecycleslength(complete_digraph(16))
([0, 1, 1, 1, 1, 1, 2, 10, 73, 511, 3066, 15329, 61313, 183939, 367876, 367876], 1000000)

julia> simplecycleslength(wheel_digraph(16))
([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 1)
source
Graphs.spfa_shortest_pathsMethod
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
Graphs.squashMethod
squash(g)

Return a copy of a graph with the smallest practical eltype that can accommodate all vertices.

May also return the original graph if the eltype does not change.

source
Graphs.srcMethod
src(e)

Return the source vertex of edge e.

Examples

julia> using Graphs

julia> g = SimpleGraph(2);

julia> add_edge!(g, 1, 2);

julia> src(first(edges(g)))
1
source
Graphs.steiner_treeFunction
steiner_tree(g, term_vert, distmx=weights(g))

Return an approximately minimum steiner tree of connected, undirected graph g with positive edge weights represented by distmx using Approximate Steiner Tree. The minimum steiner tree problem involves finding a subset of edges in g of minimum weight such that all the vertices in term_vert are connected.

t = length(term_vert).

Performance

Runtime: O(t(tlog(t)+|E|log(|V| )) Memory: O(t|V|) Approximation Factor: 2-2/t

source
Graphs.strongly_connected_componentsFunction
strongly_connected_components(g)

Compute the strongly connected components of a directed graph g.

Return an array of arrays, each of which is the entire connected component.

Implementation Notes

The order of the components is not part of the API contract.

Examples

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

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


julia> g=SimpleDiGraph(11)
{11, 0} directed simple Int64 graph

julia> edge_list=[(1,2),(2,3),(3,4),(4,1),(3,5),(5,6),(6,7),(7,5),(5,8),(8,9),(9,8),(10,11),(11,10)];

julia> g = SimpleDiGraph(Edge.(edge_list))
{11, 13} directed simple Int64 graph

julia> strongly_connected_components(g)
4-element Array{Array{Int64,1},1}:
 [8, 9]
 [5, 6, 7]
 [1, 2, 3, 4]
 [10, 11]
source
Graphs.strongly_connected_components_kosarajuFunction
strongly_connected_components_kosaraju(g)

Compute the strongly connected components of a directed graph g using Kosaraju's Algorithm. (https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm).

Return an array of arrays, each of which is the entire connected component.

Performance

Time Complexity : O(|E|+|V|) Space Complexity : O(|V|) {Excluding the memory required for storing graph}

|V| = Number of vertices |E| = Number of edges

Examples


julia> g=SimpleDiGraph(3)
{3, 0} directed simple Int64 graph

julia> g = SimpleDiGraph([0 1 0 ; 0 0 1; 0 0 0])
{3, 2} directed simple Int64 graph

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


julia> g=SimpleDiGraph(11)
{11, 0} directed simple Int64 graph

julia> edge_list=[(1,2),(2,3),(3,4),(4,1),(3,5),(5,6),(6,7),(7,5),(5,8),(8,9),(9,8),(10,11),(11,10)]
13-element Array{Tuple{Int64,Int64},1}:
 (1, 2)
 (2, 3)
 (3, 4)
 (4, 1)
 (3, 5)
 (5, 6)
 (6, 7)
 (7, 5)
 (5, 8)
 (8, 9)
 (9, 8)
 (10, 11)
 (11, 10)

julia> g = SimpleDiGraph(Edge.(edge_list))
{11, 13} directed simple Int64 graph

julia> strongly_connected_components_kosaraju(g)
4-element Array{Array{Int64,1},1}:
 [11, 10]
 [2, 3, 4, 1]
 [6, 7, 5]
 [9, 8]
source
Graphs.symmetric_differenceMethod
symmetric_difference(g, h)

Return a graph with edges from graph g that do not exist in graph h, and vice versa.

Implementation Notes

Note that this function may produce a graph with 0-degree vertices. Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.

Examples

julia> using Graphs

julia> g = SimpleGraph(3); h = SimpleGraph(3);

julia> add_edge!(g, 1, 2);

julia> add_edge!(h, 1, 3);

julia> add_edge!(h, 2, 3);

julia> f = symmetric_difference(g, h);

julia> collect(edges(f))
3-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 2 => 3
source
Graphs.tensor_productMethod
tensor_product(g, h)

Return the tensor product of g and h.

Implementation Notes

Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.

Examples

julia> using Graphs

julia> g = tensor_product(star_graph(3), path_graph(3))
{9, 8} undirected simple Int64 graph

julia> collect(edges(g))
8-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 5
 Edge 1 => 8
 Edge 2 => 4
 Edge 2 => 6
 Edge 2 => 7
 Edge 2 => 9
 Edge 3 => 5
 Edge 3 => 8
source
Graphs.transitiveclosureFunction
transitiveclosure(g, selflooped=false)

Compute the transitive closure of a directed graph, using DFS. Return a graph representing the transitive closure. If selflooped is true, add self loops to the graph.

Performance

Time complexity is $\mathcal{O}(|E||V|)$.

Examples

julia> using Graphs

julia> barbell = blockdiag(complete_digraph(3), complete_digraph(3));

julia> add_edge!(barbell, 1, 4);

julia> collect(edges(barbell))
13-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 2 => 1
 Edge 2 => 3
 Edge 3 => 1
 Edge 3 => 2
 Edge 4 => 5
 Edge 4 => 6
 Edge 5 => 4
 Edge 5 => 6
 Edge 6 => 4
 Edge 6 => 5

julia> collect(edges(transitiveclosure(barbell)))
21-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 1 => 5
 Edge 1 => 6
 Edge 2 => 1
 Edge 2 => 3
 Edge 2 => 4
 Edge 2 => 5
 Edge 2 => 6
 Edge 3 => 1
 Edge 3 => 2
 Edge 3 => 4
 Edge 3 => 5
 Edge 3 => 6
 Edge 4 => 5
 Edge 4 => 6
 Edge 5 => 4
 Edge 5 => 6
 Edge 6 => 4
 Edge 6 => 5
source
Graphs.transitiveclosure!Function
transitiveclosure!(g, selflooped=false)

Compute the transitive closure of a directed graph, using DFS. If selflooped is true, add self loops to the graph.

Performance

Time complexity is $\mathcal{O}(|E||V|)$.

Implementation Notes

This version of the function modifies the original graph.

source
Graphs.transitivereducionFunction
transitivereduction(g; selflooped=false)

Compute the transitive reduction of a directed graph. If the graph contains cycles, each strongly connected component is replaced by a directed cycle and the transitive reduction is calculated on the condensation graph connecting the components. If selflooped is true, self loops on strongly connected components of size one will be preserved.

Performance

Time complexity is $\mathcal{O}(|V||E|)$.

Examples

julia> using Graphs

julia> barbell = blockdiag(complete_digraph(3), complete_digraph(3));

julia> add_edge!(barbell, 1, 4);

julia> collect(edges(barbell))
13-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 2 => 1
 Edge 2 => 3
 Edge 3 => 1
 Edge 3 => 2
 Edge 4 => 5
 Edge 4 => 6
 Edge 5 => 4
 Edge 5 => 6
 Edge 6 => 4
 Edge 6 => 5

julia> collect(edges(transitivereduction(barbell)))
7-element Array{Graphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 1 => 4
 Edge 2 => 3
 Edge 3 => 1
 Edge 4 => 5
 Edge 5 => 6
 Edge 6 => 4
source
Graphs.treeMethod
tree(parents)

Convert a parents array into a directed graph.

source
Graphs.trianglesMethod
triangles(g[, v])
triangles(g, vs)

Return the number of triangles in the neighborhood of node v in graph g. If a list of vertices vs is specified, return a vector of number of triangles for each node in the list. If no vertices are specified, return the number of triangles for each node in the graph.

Examples

julia> using Graphs

julia> g = SimpleGraph(4);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 4);

julia> add_edge!(g, 4, 1);

julia> triangles(g)
4-element Array{Int64,1}:
 1
 1
 0
 1
source
Graphs.unblock!Method
unblock!(v, blocked, B)

Unblock the value v from the blocked list and remove from B.

source
Graphs.unblock!Method
unblock!{T<:Integer}(v::T, blocked::BitVector, B::Vector{Set{T}})

Unblock the vertices recursively.

v is the vertex to unblock, blocked tells whether a vertex is blocked or not and B is the map that tells if the unblocking of one vertex should unblock other vertices.

source
Graphs.unweighted_contiguous_partitionMethod
unweighted_contiguous_partition(num_items, required_partitions)

Partition 1:num_items into required_partitions number of partitions such that the difference in length of the largest and smallest partition is atmost 1.

Performance

Time: O(required_partitions)

source
Graphs.update_dominated!Method
update_dominated!(degree_queue, v, dominated, in_dom_set)

Check if a vertex is already dominated. If not, make it dominated and update degree_queue by decreasing the priority of the vertices adjacent to v by 1.

source
Graphs.vertex_coverMethod
vertex_cover(g, DegreeVertexCover())

Obtain a vertex cover using a greedy heuristic.

Implementation Notes

An edge is said to be covered if it has at least one end-point in the vertex cover. Initialise the vertex cover to an empty set and iteratively choose the vertex with the most uncovered edges.

Performance

Runtime: O((|V|+|E|)*log(|V|)) Memory: O(|V|)

Examples

julia> using Graphs

julia> vertex_cover(path_graph(3), DegreeVertexCover())
1-element Array{Int64,1}:
 2

julia> vertex_cover(cycle_graph(3), DegreeVertexCover())
2-element Array{Int64,1}:
 1
 3
source
Graphs.vertex_coverMethod
vertex_cover(g, RandomVertexCover(); seed=-1)

Find a set of vertices such that every edge in g has some vertex in the set as atleast one of its end point.

Implementation Notes

Performs Approximate Minimum Vertex Cover once. Returns a vector of vertices representing the vertices in the Vertex Cover.

Performance

Runtime: O(|V|+|E|) Memory: O(|E|) Approximation Factor: 2

Optional Arguments

  • If seed >= 0, a random generator is seeded with this value.
source
Graphs.verticesMethod
vertices(g)

Return (an iterator to or collection of) the vertices of a graph.

Implementation Notes

A returned iterator is valid for one pass over the edges, and is invalidated by changes to g.

Examples

julia> using Graphs

julia> collect(vertices(SimpleGraph(4)))
4-element Array{Int64,1}:
 1
 2
 3
 4
source
Graphs.visit!Method
visit!(g, state, u, v)

Perform a DFS visit storing the depth and low-points of each vertex.

source
Graphs.weakly_connected_componentsMethod
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.weightsMethod
weights(g)

Return the weights of the edges of a graph g as a matrix. Defaults to Graphs.DefaultDistance.

Implementation Notes

In general, referencing the weight of a nonexistent edge is undefined behavior. Do not rely on the weights matrix as a substitute for the graph's adjacency_matrix.

source
Graphs.yen_k_shortest_pathsMethod
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
SparseArrays.blockdiagMethod
blockdiag(g, h)

Return a graph with $|V(g)| + |V(h)|$ vertices and $|E(g)| + |E(h)|$ edges where the vertices and edges from graph h are appended to graph g.

Implementation Notes

Preserves the eltype of the input graph. Will error if the number of vertices in the generated graph exceeds the eltype.

Examples

julia> g1 = 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> g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0]);

julia> blockdiag(g1, g2)
{8, 9} directed simple Int64 graph

julia> foreach(println, edges(blockdiag(g1, g2)))
Edge 1 => 2
Edge 2 => 3
Edge 3 => 1
Edge 3 => 4
Edge 4 => 5
Edge 5 => 4
Edge 6 => 7
Edge 7 => 8
Edge 8 => 6
source