# Community Structures

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

`Graphs.AbstractEdge`

`Graphs.AbstractEdgeIter`

`Graphs.AbstractGraph`

`Graphs.AbstractPathState`

`Graphs.BellmanFordState`

`Graphs.Biconnections`

`Graphs.DEsopoPapeState`

`Graphs.DefaultDistance`

`Graphs.DiGraph`

`Graphs.DijkstraState`

`Graphs.Edge`

`Graphs.FloydWarshallState`

`Graphs.Graph`

`Graphs.JohnsonState`

`Graphs.JohnsonVisitor`

`Graphs.NeighComm`

`Graphs.NotImplementedError`

`Graphs.YenState`

`Base.eltype`

`Base.getindex`

`Base.intersect`

`Base.join`

`Base.reverse`

`Base.reverse`

`Base.reverse!`

`Base.size`

`Base.sum`

`Base.sum`

`Base.union`

`Base.zero`

`Graphs.BoundedMinkowskiCost`

`Graphs.MinkowskiCost`

`Graphs.a_star`

`Graphs.add_vertices!`

`Graphs.all_neighbors`

`Graphs.articulation`

`Graphs.assortativity`

`Graphs.attracting_components`

`Graphs.bellman_ford_shortest_paths`

`Graphs.bfs_parents`

`Graphs.bfs_tree`

`Graphs.biconnected_components`

`Graphs.bipartite_map`

`Graphs.boruvka_mst`

`Graphs.bridges`

`Graphs.cartesian_product`

`Graphs.center`

`Graphs.circuit`

`Graphs.circuit_iter`

`Graphs.circuit_recursive!`

`Graphs.clique_percolation`

`Graphs.common_neighbors`

`Graphs.complement`

`Graphs.components`

`Graphs.components_dict`

`Graphs.compute_shifts`

`Graphs.condensation`

`Graphs.connected_components`

`Graphs.connected_components!`

`Graphs.core_number`

`Graphs.core_periphery_deg`

`Graphs.crosspath`

`Graphs.cycle_basis`

`Graphs.deepcopy_adjlist`

`Graphs.degree`

`Graphs.degree_histogram`

`Graphs.density`

`Graphs.desopo_pape_shortest_paths`

`Graphs.dfs_parents`

`Graphs.dfs_tree`

`Graphs.diameter`

`Graphs.difference`

`Graphs.diffusion`

`Graphs.diffusion_rate`

`Graphs.dijkstra_shortest_paths`

`Graphs.dominating_set`

`Graphs.dominating_set`

`Graphs.dst`

`Graphs.eccentricity`

`Graphs.edges`

`Graphs.edgetype`

`Graphs.edit_distance`

`Graphs.egonet`

`Graphs.enumerate_paths`

`Graphs.filter_non_term_leaves!`

`Graphs.findall!`

`Graphs.floyd_warshall_shortest_paths`

`Graphs.gdistances`

`Graphs.gdistances!`

`Graphs.global_clustering_coefficient`

`Graphs.greedy_contiguous_partition`

`Graphs.has_edge`

`Graphs.has_negative_edge_cycle_spfa`

`Graphs.has_path`

`Graphs.has_self_loops`

`Graphs.has_vertex`

`Graphs.indegree`

`Graphs.independent_set`

`Graphs.independent_set`

`Graphs.induced_subgraph`

`Graphs.inneighbors`

`Graphs.insorted`

`Graphs.is_bipartite`

`Graphs.is_connected`

`Graphs.is_cyclic`

`Graphs.is_directed`

`Graphs.is_ordered`

`Graphs.is_strongly_connected`

`Graphs.is_weakly_connected`

`Graphs.isbounded`

`Graphs.isbounded`

`Graphs.isgraphical`

`Graphs.itercycles`

`Graphs.johnson_shortest_paths`

`Graphs.k_core`

`Graphs.k_corona`

`Graphs.k_crust`

`Graphs.k_shell`

`Graphs.karger_cut_cost`

`Graphs.karger_cut_edges`

`Graphs.karger_min_cut`

`Graphs.karp_minimum_cycle_mean`

`Graphs.kruskal_mst`

`Graphs.label_propagation`

`Graphs.loadgraph`

`Graphs.loadgraphs`

`Graphs.loadlg_mult`

`Graphs.local_clustering`

`Graphs.local_clustering_coefficient`

`Graphs.maximal_cliques`

`Graphs.maximum_adjacency_visit`

`Graphs.maxsimplecycles`

`Graphs.maxsimplecycles`

`Graphs.merge_vertices`

`Graphs.merge_vertices!`

`Graphs.mincut`

`Graphs.modularity`

`Graphs.ncycles_n_i`

`Graphs.ne`

`Graphs.neighborhood`

`Graphs.neighborhood_dists`

`Graphs.neighbors`

`Graphs.noallocextreme`

`Graphs.non_backtracking_randomwalk`

`Graphs.normalized_cut`

`Graphs.num_self_loops`

`Graphs.nv`

`Graphs.optimal_contiguous_partition`

`Graphs.outdegree`

`Graphs.outneighbors`

`Graphs.period`

`Graphs.periphery`

`Graphs.prim_mst`

`Graphs.radius`

`Graphs.randomwalk`

`Graphs.range_shuffle!`

`Graphs.resetB!`

`Graphs.resetblocked!`

`Graphs.rich_club`

`Graphs.sample`

`Graphs.sample!`

`Graphs.savegraph`

`Graphs.savegraph`

`Graphs.savelg`

`Graphs.savelg_mult`

`Graphs.self_avoiding_walk`

`Graphs.simplecycles`

`Graphs.simplecycles_hawick_james`

`Graphs.simplecycles_iter`

`Graphs.simplecycles_limited_length`

`Graphs.simplecyclescount`

`Graphs.simplecycleslength`

`Graphs.spfa_shortest_paths`

`Graphs.squash`

`Graphs.src`

`Graphs.steiner_tree`

`Graphs.strongly_connected_components`

`Graphs.strongly_connected_components_kosaraju`

`Graphs.symmetric_difference`

`Graphs.tensor_product`

`Graphs.topological_sort_by_dfs`

`Graphs.transitiveclosure`

`Graphs.transitiveclosure!`

`Graphs.transitivereducion`

`Graphs.tree`

`Graphs.triangles`

`Graphs.unblock!`

`Graphs.unblock!`

`Graphs.unweighted_contiguous_partition`

`Graphs.update_dominated!`

`Graphs.vertex_cover`

`Graphs.vertex_cover`

`Graphs.vertices`

`Graphs.visit!`

`Graphs.vote!`

`Graphs.weakly_connected_components`

`Graphs.weights`

`Graphs.yen_k_shortest_paths`

`Graphs.Δ`

`Graphs.Δin`

`Graphs.Δout`

`Graphs.δ`

`Graphs.δin`

`Graphs.δout`

`SparseArrays.blockdiag`

`SparseArrays.sparse`

## Full Docs

`Graphs.Graphs`

— Module`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.

`Graphs.AbstractEdge`

— Type`AbstractEdge`

An abstract type representing a single edge between two vertices of a graph.

`Graphs.AbstractEdgeIter`

— Type`AbstractEdgeIter`

An abstract type representing an edge iterator.

`Graphs.AbstractGraph`

— Type`AbstractGraph`

An abstract type representing a graph.

`Graphs.AbstractPathState`

— Type`AbstractPathState`

An abstract type that provides information from shortest paths calculations.

`Graphs.BellmanFordState`

— Type`BellmanFordState{T, U}`

An `AbstractPathState`

designed for Bellman-Ford shortest-paths calculations.

`Graphs.Biconnections`

— Type`Biconnections`

A state type for depth-first search that finds the biconnected components.

`Graphs.DEsopoPapeState`

— Type`struct DEposoPapeState{T, U}`

An `AbstractPathState`

designed for D`Esopo-Pape shortest-path calculations.

`Graphs.DefaultDistance`

— Type`DefaultDistance`

An array-like structure that provides distance values of `1`

for any `src, dst`

combination.

`Graphs.DiGraph`

— Type`DiGraph`

A datastruture representing a directed graph.

`Graphs.DijkstraState`

— Type`struct DijkstraState{T, U}`

An `AbstractPathState`

designed for Dijkstra shortest-paths calculations.

`Graphs.Edge`

— Type`Edge`

A datastruture representing an edge between two vertices in a `Graph`

or `DiGraph`

.

`Graphs.FloydWarshallState`

— Type`struct FloydWarshallState{T, U}`

An `AbstractPathState`

designed for Floyd-Warshall shortest-paths calculations.

`Graphs.Graph`

— Type`Graph`

A datastruture representing an undirected graph.

`Graphs.JohnsonState`

— Type`struct JohnsonState{T, U}`

An `AbstractPathState`

designed for Johnson shortest-paths calculations.

`Graphs.JohnsonVisitor`

— Type```
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.

`Graphs.NeighComm`

— Type`NeighComm{T}`

Type to record neighbor labels and their counts.

`Graphs.NotImplementedError`

— Type`NotImplementedError{M}(m)`

`Exception`

thrown when a method from the `AbstractGraph`

interface is not implemented by a given graph type.

`Graphs.YenState`

— Type`struct YenState{T, U}`

Designed for yen k-shortest-paths calculations.

`Base.eltype`

— Method`eltype(g)`

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

`Base.getindex`

— Method`g[iter]`

Return the subgraph induced by `iter`

. Equivalent to `induced_subgraph`

`(g, iter)[1]`

.

`Base.intersect`

— Method`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
```

`Base.join`

— Method`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
```

`Base.reverse`

— Function`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
```

`Base.reverse!`

— Function`reverse!(g)`

In-place reverse of a directed graph (modifies the original graph). See `reverse`

for a non-modifying version.

`Base.reverse`

— Method`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
```

`Base.size`

— Method`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
```

`Base.sum`

— Method`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
```

`Base.sum`

— Method`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
```

`Base.union`

— Method`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
```

`Base.zero`

— Method`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
```

`Graphs.BoundedMinkowskiCost`

— Method`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.

`Graphs.MinkowskiCost`

— Method`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.

`Graphs.a_star`

— Method`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`

.

`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
```

`Graphs.all_neighbors`

— Function`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 ```

`Graphs.articulation`

— Function`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
```

`Graphs.assortativity`

— Method`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
```

`Graphs.attracting_components`

— Function`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]
```

`Graphs.bellman_ford_shortest_paths`

— Method```
bellman_ford_shortest_paths(g, s, distmx=weights(g))
bellman_ford_shortest_paths(g, ss, distmx=weights(g))
```

Compute shortest paths between a source `s`

(or list of sources `ss`

) and all other nodes in graph `g`

using the Bellman-Ford algorithm. Return a `Graphs.BellmanFordState`

with relevant traversal information.

`Graphs.bfs_parents`

— Method`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.

`Graphs.bfs_tree`

— Method`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).

`Graphs.biconnected_components`

— Function`biconnected_components(g) -> Vector{Vector{Edge{eltype(g)}}}`

Compute the biconnected components of an undirected graph `g`

and 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]
```

`Graphs.bipartite_map`

— Method`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
```

`Graphs.boruvka_mst`

— Function`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.

`Graphs.bridges`

— Function`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
```

`Graphs.cartesian_product`

— Method`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
```

`Graphs.center`

— Method```
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
```

`Graphs.circuit`

— Function```
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**

`Graphs.circuit_iter`

— Function```
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**

`Graphs.circuit_recursive!`

— Function`circuit_recursive!(g, v1, v2, blocked, B, stack, cycles)`

Find circuits in `g`

recursively starting from v1.

`Graphs.clique_percolation`

— Function`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}
```

`Graphs.common_neighbors`

— Method`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
```

`Graphs.complement`

— Method`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
```

`Graphs.components`

— Method`components(labels)`

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

`Graphs.components_dict`

— Method`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.

`Graphs.compute_shifts`

— Method`compute_shifts(n::Int, x::AbstractArray)`

Determine how many elements of `x`

are less than `i`

for all `i`

in `1:n`

.

`Graphs.condensation`

— Function`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
```

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

`Graphs.connected_components`

— Method`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]
```

`Graphs.core_number`

— Method`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
```

`Graphs.core_periphery_deg`

— Function`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
```

`Graphs.crosspath`

— Function`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**

**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
```

`Graphs.cycle_basis`

— Function`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]

`Graphs.deepcopy_adjlist`

— Method`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`

.

`Graphs.degree`

— Function`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
```

`Graphs.degree_histogram`

— Method`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`

.

`Graphs.density`

— Function`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).

`Graphs.desopo_pape_shortest_paths`

— Method`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
```

`Graphs.dfs_parents`

— Method`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.

`Graphs.dfs_tree`

— Method`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`

.

`Graphs.diameter`

— Method```
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
```

`Graphs.difference`

— Method`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
```

`Graphs.diffusion`

— Method`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)}$.

`Graphs.diffusion_rate`

— Method```
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.

`Graphs.dijkstra_shortest_paths`

— Method`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**

`allpaths=false`

: If true, returns a`Graphs.DijkstraState`

that keeps track of all

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
```

`Graphs.dominating_set`

— Method`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`

`Graphs.dominating_set`

— Method`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.

`Graphs.dst`

— Method`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
```

`Graphs.eccentricity`

— Method```
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
```

`Graphs.edges`

— Method`edges(g)`

Return (an iterator to or collection of) the edges of a graph. For `AbstractSimpleGraph`

s 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
```

`Graphs.edgetype`

— Method`edgetype(g)`

Return the type of graph `g`

's edge

`Graphs.edit_distance`

— Method`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)])
```

`Graphs.egonet`

— Method`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`

).

`Graphs.enumerate_paths`

— Method`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`

.

`Graphs.filter_non_term_leaves!`

— Method`filter_non_term_leaves!(g, term_vert)`

Remove edges of `g`

so that all non-isolated leaves of `g`

are in the set `term_vert`

`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|`

.

`Graphs.floyd_warshall_shortest_paths`

— Method`floyd_warshall_shortest_paths(g, distmx=weights(g))`

Use the Floyd-Warshall algorithm to compute the shortest paths between all pairs of vertices in graph `g`

using an optional distance matrix `distmx`

. Return a `Graphs.FloydWarshallState`

with relevant traversal information.

**Performance**

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

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

`Graphs.gdistances`

— Method`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.

`Graphs.global_clustering_coefficient`

— Method`global_clustering_coefficient(g)`

Return the global clustering coefficient of graph `g`

.

**Examples**

```
julia> using Graphs
julia> global_clustering_coefficient(star_graph(4))
0.0
julia> global_clustering_coefficient(smallgraph(:housex))
0.7894736842105263
```

`Graphs.greedy_contiguous_partition`

— Method`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(num*items+required*partitions) 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.

`Graphs.has_edge`

— Method`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
```

`Graphs.has_negative_edge_cycle_spfa`

— MethodFunction 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
```

`Graphs.has_path`

— Method`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`

.

`Graphs.has_self_loops`

— Method`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
```

`Graphs.has_vertex`

— Method`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
```

`Graphs.indegree`

— Method`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
```

`Graphs.independent_set`

— Method`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|)

`Graphs.independent_set`

— Method`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.

`Graphs.induced_subgraph`

— Method```
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]
```

`Graphs.inneighbors`

— Method`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
```

`Graphs.insorted`

— Method`insorted(item, collection)`

Return true if `item`

is in sorted collection `collection`

.

**Implementation Notes**

Does not verify that `collection`

is sorted.

`Graphs.is_bipartite`

— Method`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
```

`Graphs.is_connected`

— Method`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
```

`Graphs.is_cyclic`

— Function`is_cyclic(g)`

Return `true`

if graph `g`

contains a cycle.

**Implementation Notes**

Uses DFS.

`Graphs.is_directed`

— Method`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
```

`Graphs.is_ordered`

— Method`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
```

`Graphs.is_strongly_connected`

— Function`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
```

`Graphs.is_weakly_connected`

— Method`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
```

`Graphs.isbounded`

— Method`isbounded(n)`

Returns true if `typemax(n)`

of an integer `n`

exists.

`Graphs.isbounded`

— Method`isbounded(T)`

Returns true if `typemax(T)`

of a type `T <: Integer`

exists.

`Graphs.isgraphical`

— Method`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

`Graphs.itercycles`

— Function`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 `Channel`

s to stop the exploration after a given number of cycles.

**References**

`Graphs.johnson_shortest_paths`

— Method`johnson_shortest_paths(g, distmx=weights(g))`

Use the Johnson algorithm to compute the shortest paths between all pairs of vertices in graph `g`

using an optional distance matrix `distmx`

.

Return a `Graphs.JohnsonState`

with relevant traversal information.

**Performance**

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

`Graphs.k_core`

— Function`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
```

`Graphs.k_corona`

— Method`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}
```

`Graphs.k_crust`

— Function`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
```

`Graphs.k_shell`

— Function`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
```

`Graphs.karger_cut_cost`

— Method`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`

.

`Graphs.karger_cut_edges`

— Method`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`

.

`Graphs.karger_min_cut`

— Method`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|)

`Graphs.karp_minimum_cycle_mean`

— Function`karp_minimum_cycle_mean(g[, distmx])`

Return minimum cycle mean of the directed graph `g`

with optional edge weights contained in `distmx`

.

**References**

- Karp.

`Graphs.kruskal_mst`

— Function`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.

`Graphs.label_propagation`

— Method`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**

`Graphs.loadgraph`

— Method`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.

`Graphs.loadgraphs`

— Method`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.

`Graphs.loadlg_mult`

— Method`loadlg_mult(io)`

Return a dictionary of (name=>graph) loaded from IO stream `io`

.

`Graphs.local_clustering`

— Method```
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}$.

`Graphs.local_clustering_coefficient`

— Method```
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
```

`Graphs.maximal_cliques`

— Function`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]
```

`Graphs.maximum_adjacency_visit`

— Method```
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.

`Graphs.maxsimplecycles`

— Function`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**

`Graphs.maxsimplecycles`

— Method`maxsimplecycles(n::Integer)`

Compute the theoretical maximum number of cycles in a directed graph of `n`

vertices, assuming there are no self-loops.

**References**

`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
```

`Graphs.merge_vertices`

— Method`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
```

`Graphs.mincut`

— Method`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.

`Graphs.modularity`

— Method`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
```

`Graphs.ncycles_n_i`

— Method`ncycles_n_i(n::Integer, i::Integer)`

Compute the theoretical maximum number of cycles of size `i`

in a directed graph of `n`

vertices.

`Graphs.ne`

— Method`ne(g)`

Return the number of edges in `g`

.

**Examples**

```
julia> using Graphs
julia> g = path_graph(3);
julia> ne(g)
2
```

`Graphs.neighborhood`

— Method`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
```

`Graphs.neighborhood_dists`

— Method`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)
```

`Graphs.neighbors`

— Method`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**

**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
```

`Graphs.noallocextreme`

— Method`noallocextreme(f, comparison, initial, g)`

Compute the extreme value of `[f(g,i) for i=i:nv(g)]`

without gathering them all

`Graphs.non_backtracking_randomwalk`

— Function`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.

`Graphs.normalized_cut`

— Method`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

`Graphs.num_self_loops`

— Method`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
```

`Graphs.nv`

— Method`nv(g)`

Return the number of vertices in `g`

.

**Examples**

```
julia> using Graphs
julia> nv(SimpleGraph(3))
3
```

`Graphs.optimal_contiguous_partition`

— Method`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)]`

.

`Graphs.outdegree`

— Method`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
```

`Graphs.outneighbors`

— Method`outneighbors(g, v)`

Return a list of all neighbors connected to vertex `v`

by an outgoing edge.

**Implementation Notes**

**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
```

`Graphs.period`

— Function`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
```

`Graphs.periphery`

— Method```
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
```

`Graphs.prim_mst`

— Function`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.

`Graphs.radius`

— Method```
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
```

`Graphs.randomwalk`

— Method`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.

`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`

.

`Graphs.resetB!`

— Method`resetB!(B)`

Reset B work structure.

`Graphs.resetblocked!`

— Method`resetblocked!(blocked)`

Reset vector of `blocked`

vertices.

`Graphs.rich_club`

— Method`rich_club(g, k)`

Return the non-normalised rich-club coefficient of graph `g`

, with degree cut-off `k`

.

```
julia> using LightGraphs
julia> g = star_graph(5)
julia> rich_club(g, 1)
0.4
```

`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`

.

`Graphs.sample`

— Method`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.

`Graphs.savegraph`

— Method`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.

`Graphs.savegraph`

— Method`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.

`Graphs.savelg`

— Method`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).

`Graphs.savelg_mult`

— Method`savelg_mult(io, graphs)`

Write a dictionary of (name=>graph) to an IO stream `io`

, with default `GZip`

compression. Return number of graphs written.

`Graphs.self_avoiding_walk`

— Method`self_avoiding_walk(g, s, niter; seed=-1)`

Perform a self-avoiding walk on graph `g`

starting at vertex `s`

and continuing for a maximum of `niter`

steps. Return a vector of vertices visited in order.

`Graphs.simplecycles`

— Function`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]
```

`Graphs.simplecycles_hawick_james`

— Function`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

`Graphs.simplecycles_iter`

— Function`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**

`Graphs.simplecycles_limited_length`

— Method`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.

`Graphs.simplecyclescount`

— Function`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
```

`Graphs.simplecycleslength`

— Function`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)
```

`Graphs.spfa_shortest_paths`

— Method`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
```

`Graphs.squash`

— Method`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.

`Graphs.src`

— Method`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
```

`Graphs.steiner_tree`

— Function`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*(t*log(t)+|E|*log(|V| )) Memory: O(t*|V|) Approximation Factor: 2-2/t

`Graphs.strongly_connected_components`

— Function`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]
```

`Graphs.strongly_connected_components_kosaraju`

— Function`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]
```

`Graphs.symmetric_difference`

— Method`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
```

`Graphs.tensor_product`

— Method`tensor_product(g, h)`

Return the tensor product of `g`

and `h`

.

**Implementation Notes**

**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
```

`Graphs.topological_sort_by_dfs`

— Function`topological_sort_by_dfs(g)`

Return a topological sort of a directed graph `g`

as a vector of vertices in topological order.

`Graphs.transitiveclosure`

— Function`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
```

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

`Graphs.transitivereducion`

— Function`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
```

`Graphs.tree`

— Method`tree(parents)`

Convert a parents array into a directed graph.

`Graphs.triangles`

— Method```
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
```

`Graphs.unblock!`

— Method`unblock!(v, blocked, B)`

Unblock the value `v`

from the `blocked`

list and remove from `B`

.

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

`Graphs.unweighted_contiguous_partition`

— Method`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)

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

`Graphs.vertex_cover`

— Method`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
```

`Graphs.vertex_cover`

— Method`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.

`Graphs.vertices`

— Method`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
```

`Graphs.visit!`

— Method`visit!(g, state, u, v)`

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

`Graphs.vote!`

— Method`vote!(g, m, c, u)`

Return the label with greatest frequency.

`Graphs.weakly_connected_components`

— Method`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]
```

`Graphs.weights`

— Method`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`

.

`Graphs.yen_k_shortest_paths`

— Method`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.

`Graphs.Δ`

— Method`Δ(g)`

Return the maximum `degree`

of vertices in `g`

.

`Graphs.Δin`

— Method`Δin(g)`

Return the maximum `indegree`

of vertices in `g`

.

`Graphs.Δout`

— Method`Δout(g)`

Return the maximum `outdegree`

of vertices in `g`

.

`Graphs.δ`

— Method`δ(g)`

Return the minimum `degree`

of vertices in `g`

.

`Graphs.δin`

— Method`δin(g)`

Return the minimum `indegree`

of vertices in `g`

.

`Graphs.δout`

— Method`δout(g)`

Return the minimum `outdegree`

of vertices in `g`

.

`SparseArrays.blockdiag`

— Method`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
```

`SparseArrays.sparse`

— Method`sparse(g)`

Return the default adjacency matrix of `g`

.