`Erdos.Erdos`

— ModuleA graph and network analysis package for julia.

`Erdos.AGraphOrDiGraph`

— Type`Erdos.ADiGraph`

— Type`abstract ADiGraph`

Abstract directed graph type

`Erdos.ADiNetwork`

— Type`abstract type ADiNetwork <: ADiGraph end`

An abstract directed graph with the additional possibility to attach properties to vertices and edges.

`Erdos.AEdge`

— Type`abstract type AEdge end`

An abstract edge type.

`Erdos.AEdgeMap`

— Type`abstract type AEdgeMap{T} end`

Type representing an abstract edge map with value type `T`

.

`Erdos.AGraph`

— Type`abstract type AGraph end`

Abstract undirected graph type

`Erdos.AIndexedEdge`

— Type`abstract type AIndexedEdge <: AEdge end`

Edge types with unique indexes, accessed by `idx`

`Erdos.ANetwork`

— Type`abstract type ANetwork <: AGraph end`

An abstract graph with the additional possibility to attach properties to vertices and edges.

`Erdos.AVertexMap`

— Type`abstract type AVertexMap{T} end`

Type representing an abstract vertex map with value type `T`

.

`Erdos.AbstractFlowAlgorithm`

— Typeabstract type that allows users to pass in their preferred Algorithm

`Erdos.AbstractMultirouteFlowAlgorithm`

— Typeabstract type that allows users to pass in their preferred Algorithm

`Erdos.BoykovKolmogorovAlgorithm`

— TypeForces the maximum_flow function to use the Boykov-Kolmogorov algorithm.

`Erdos.ConstEdgeMap`

— Type```
struct ConstEdgeMap{T} <: SimpleEdgeMap{T}
val::T
end
```

A type representing a constant vector map. Any attempt to change the internal value, e.g. `emap[u,v] = 4`

, will fail silently.

`Erdos.ConstVertexMap`

— Type```
struct ConstVertexMap{T} <: AVertexMap{T}
val::T
end
```

A type representing a constant vector map. Any attempt to change the internal value, e.g. `vm[1] = 4`

, will fail silently.

`Erdos.DefaultCapacity`

— TypeType that returns 1 if a forward edge exists, and 0 otherwise

`Erdos.DiGraph`

— Type```
mutable struct DiGraph{T<:Integer} <: ADiGraph
ne::Int
fadjlist::Vector{Vector{T}}
badjlist::Vector{Vector{T}}
end
```

A simple digraph type based on two adjacency lists (forward and backward).

```
DiGraph{T}(n=0)
DiGraph(n=0) = DiGraph{Int}(n)
```

Construct a `DiGraph`

with `n`

vertices and no edges.

`DiGraph{T}(adjmx::AbstractMatrix; selfedges=true)`

Construct a `DiGraph{T}`

from the adjacency matrix `adjmx`

, placing an edge in correspondence to each nonzero element of `adjmx`

. If `selfedges=false`

the diagonal elements of `adjmx`

are ignored.

`Erdos.DiNetwork`

— Type`DiNetwork`

A type representing a directed graph with indexed edges and the possibility to store graph/vertex/edge properties.

`DiNetwork(n=0)`

Construct a `DiNetwork`

with `n`

vertices and no edges.

`DiNetwork(adjmx::AbstractMatrix; selfedges=true)`

Construct a `DiNetwork`

from the adjacency matrix `adjmx`

. If `selfedges=false`

the diagonal elements of `adjmx`

are ignored.

`Erdos.DinicAlgorithm`

— TypeForces the maximum_flow function to use Dinic's algorithm.

`Erdos.Edge`

— Type```
struct Edge
src::Int
dst::Int
end
```

A type representing an edge between two vertices of a graph.

`Erdos.EdgeMap`

— Type```
mutable struct EdgeMap{G <: AGraphOrDiGraph, T, D} <: AEdgeMap{T}
g::G
vtype::Type{T}
data::D
end
```

Type implementing an edge map. The underlying container `data`

can be a dictionary, a matrix or a vector (for graphs with indexed edges).

`EdgeMap{T}(g, ::Type{T})`

Returns a map that associates values of type `T`

to the vertices of graph `g`

. The underlying storage structures is chosen accordingly.

`EdgeMap(g, data)`

Construct a EdgeMap with `data`

as underlying storage. The storage type can be a matrix or an associative `edg => val`

type or a vector for graph with indexed edges.

`EdgeMap(g, f)`

Construct an edge map with value `f(e)`

for each `e`

in `edges(g)`

.

`Erdos.EdmondsKarpAlgorithm`

— TypeForces the maximum_flow function to use the Edmonds–Karp algorithm.

`Erdos.ExtendedMultirouteFlowAlgorithm`

— TypeForces the multiroute_flow function to use the Extended Multiroute Flow algorithm.

`Erdos.Graph`

— Type```
mutable struct Graph{T<:Integer} <: AGraph
ne::Int
fadjlist::Vector{Vector{T}}
end
```

A simple graph type based on an adjacency list.

The constructors

```
Graph{T}(n=0)
Graph(n=0) = Graph{Int}(n)
```

return a `Graph`

with `n`

vertices and no edges.

`Graph{T}(adjmx::AbstractMatrix; upper=false, selfedges=true)`

Construct a `Graph{T}`

from the adjacency matrix `adjmx`

, placing an edge in correspondence to each nonzero element of `adjmx`

. If `selfedges=false`

the diagonal elements of `adjmx`

are ignored. If `upper=true`

only the upper triangular part of `adjmx`

is considered.

`Erdos.IndexedEdge`

— Type```
struct IndexedEdge <: AIndexedEdge
src::Int
dst::Int
idx::Int
end
```

An indexed edge type

`IndexedEdge(u, v) = IndexedEdge(u,v,-1)`

Creates an edge with invalid index.

`Erdos.KishimotoAlgorithm`

— TypeForces the multiroute_flow function to use the Kishimoto algorithm.

`Erdos.NeighComm`

— TypeType to record neighbor labels and their counts.

`Erdos.Network`

— Type`Network`

A type representing a graph with indexed edges and the possibility to store graph/vertex/edge properties.

`Network(n=0)`

Construct a `Network`

with `n`

vertices and no edges.

`Network(adjmx::AbstractMatrix; selfedges=true, upper=false)`

Construct a `Network`

from the adjacency matrix `adjmx`

, placing an edge in correspondence to each nonzero element of `adjmx`

. If `selfedges=false`

the diagonal elements of `adjmx`

are ignored. If `upper=true`

only the upper triangular part of `adjmx`

is considered.

`Erdos.PropertyStore`

— Type```
mutable struct PropertyStore
gmaps::Dict{String, Any}
emaps::Dict{String,AEdgeMap}
vmaps::Dict{String,AVertexMap}
end
```

A type storing properties associated to networks.

`Erdos.PushRelabelAlgorithm`

— TypeForces the maximum_flow function to use the Push-Relabel algorithm.

`Erdos.VertexMap`

— Type```
mutable struct VertexMap{G <: AGraphOrDiGraph, T, D} <: AVertexMap{T}
g::G
vtype::Type{T}
data::D
end
```

Type implementing a vertex map. The underlying container `data`

can be a dictionary or a vector.

`VertexMap{T}(g, ::Type{T})`

Returns a map that associates values of type `T`

to the vertices of graph `g`

. The underlying storage structures is chosen accordingly.

`VertexMap(g, data)`

Construct a VertexMap with `data`

as underlying storage.

`VertexMap(g, f)`

Construct a vertex map with value `f(u)`

for `u in 1:nv(g)`

.

`Base.:≈`

— MethodRedefinition of ≈ (isapprox) for a pair of points Requires argument: a::Tuple{T, T}, # Point A with floating coordinates b::Tuple{T, T} # Point B with floating coordinates

`Base.getindex`

— Method`g[iter]`

Returns the subgraph induced by the vertex or edge iterable `iter`

. Equivalent to `subgraph`

`(g, iter)[1]`

or `subnetwork`

`(g, iter)[1]`

for networks.

`Base.intersect`

— Method`intersect(g, h)`

Produces a graph with edges that are only in both graph `g`

and graph `h`

.

Note that this function may produce a graph with 0-degree vertices.

`Base.join`

— Method`join(g, h)`

Merges graphs `g`

and `h`

using `blockdiag`

and then adds all the edges between the vertices in `g`

and those in `h`

.

`Base.reverse!`

— Method`reverse!(g::DiGraph)`

In-place reverse (modifies the original graph).

`Base.reverse`

— Method`reverse(e)`

Returns an edge with swapped `src(e)`

and `dst(e)`

.

`Base.reverse`

— Method`reverse(g::ADiGraph)`

Produces a graph where all edges are reversed from the original.

`Base.size`

— Method`size(g,i)`

provides 1:nv or 2:nv else 1

`Base.sum`

— Methodsum(g,i) provides 1:in*degree or 2:out*degree vectors

`Base.sum`

— Method`sum(g)`

` provides the number of edges in the graph

`Base.union`

— Method`union(g, h)`

Merges graphs `g`

and `h`

by taking the set union of all vertices and edges.

`Erdos.BinaryTree`

— Method`BinaryTree(levels, G=Graph)`

Creates a binary tree with k-levels vertices are numbered 1:2^levels-1

`Erdos.BoundedMinkowskiCost`

— MethodSimilar to MinkowskiCost, but ensures costs smaller than 2τ.

`Erdos.CliqueGraph`

— Method`CliqueGraph(k, n, G=Graph)`

This function generates a graph with `n`

`k`

-cliques connected circularly by `n`

edges.

`Erdos.CompleteBipartiteGraph`

— Method`CompleteBipartiteGraph(n1, n2, G = Graph)`

Creates a complete bipartite graph with `n1+n2`

vertices. It has edges connecting each pair of vertices in the two sets.

`Erdos.CompleteDiGraph`

— Method`CompleteDiGraph(n, G = DiGraph)`

Creates a complete digraph with `n`

vertices. A complete digraph has edges connecting each pair of vertices (both an ingoing and outgoing edge).

`Erdos.CompleteGraph`

— Method`CompleteGraph(n, G = Graph)`

Creates a complete graph of type `G`

with `n`

vertices. A complete graph has edges connecting each pair of vertices.

`Erdos.CycleDiGraph`

— MethodCreates a cycle digraph with `n`

vertices. A cycle digraph is a closed path digraph.

`Erdos.CycleGraph`

— Method`CycleGraph(n, G=Graph)`

Creates a cycle graph with `n`

vertices. A cycle graph is a closed path graph.

`Erdos.DoubleBinaryTree`

— Method`DoubleBinaryTree(levels, G=Graph)`

Create a double complete binary tree with k-levels used as an example for spectral clustering by Guattery and Miller 1998.

`Erdos.Grid`

— Method`Grid(dims::AbstractVector, G=Graph; periodic=false)`

Creates a `d`

-dimensional cubic lattice, with `d=length(dims)`

and length `dims[i]`

in dimension `i`

. If `periodic=true`

the resulting lattice will have periodic boundary condition in each dimension.

`Erdos.MinkowskiCost`

— MethodFor 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₂.

`Erdos.PathDiGraph`

— Method`PathDiGraph(n, G = DiGraph)`

Creates a path digraph with `n`

vertices. A path graph connects each successive vertex by a single directed edge.

`Erdos.PathGraph`

— Method`PathGraph(n, G = Graph)`

Creates a path graph with `n`

vertices. A path graph connects each successive vertex by a single edge.

`Erdos.RoachGraph`

— MethodThe Roach Graph from Guattery and Miller 1998

`Erdos.StarDiGraph`

— MethodCreates a star digraph with `n`

vertices. A star digraph has a central vertex with directed edges to every other vertex.

`Erdos.StarGraph`

— Method`StarGraph(n, G = Graph)`

Creates a star graph with `n`

vertices. A star graph has a central vertex with edges to each other vertex.

`Erdos.WheelDiGraph`

— MethodCreates a wheel digraph with `n`

vertices. A wheel graph is a star digraph with the outer vertices connected via a closed path graph.

`Erdos.WheelGraph`

— Method`WheelGraph(n, G=Graph)`

Creates a wheel graph with `n`

vertices. A wheel graph is a star graph with the outer vertices connected via a closed path graph.

`Erdos.a_star`

— Function`a_star(g, s, t, distmx=weights(g), heuristic = n->0)`

Computes the shortest path between vertices `s`

and `t`

using the A* search algorithm. An optional heuristic function and edge distance matrix may be supplied. Returns an empty path if there are no such paths.

`Erdos.add_edge!`

— Method`add_edge!(g, e) -> (ok, new_edge)`

Add to `g`

the edge `e`

.

`add_edge!(g, u, v) -> (ok, new_edge)`

Add to `g`

an edge from `u`

to `v`

.

`ok=false`

if add fails (e.g. if vertices are not in the graph or the edge is already present) and `true`

otherwise. `new_edge`

is the descriptor of the new edge.

`Erdos.add_edge_property!`

— Method```
add_edge_property!(g, name, T)
add_edge_property!(g, name, emap)
```

Add the edge property `name`

to `g`

.

If a type `T`

is given as an input, an edge map with valtype `T`

is created and stored into `g`

.

As an alternative, an existing edge map `emap`

can be stored into `g`

.

`eprop!`

is the short form of this function.

**Example**

```
g = random_regular_graph(10, 3, Network)
add_edge_property!(g, "weight", Float64)
# or equivalently
eprop!(g, "weight", Float64)
```

`Erdos.add_vertex!`

— Method`add_vertex!(g)`

Add a new vertex to the graph `g`

.

`Erdos.add_vertex_property!`

— Method```
add_vertex_property!(g, name, T)
add_vertex_property!(g, name, vmap)
```

Add the vertex property `name`

to `g`

.

If a type `T`

is given as an input, a vertex map with valtype `T`

is created and stored into `g`

.

As an alternative, an existing vertex map `vmap`

can be stored into `g`

.

`vprop!`

is the short form of this function.

`Erdos.add_vertices!`

— Method`add_vertices!(g, n)`

Add `n`

new vertices to the graph `g`

. Returns the final number of vertices.

`Erdos.adjacency_list`

— Method```
adjacency_list(g::AGraph)
adjacency_list(g::ADiGraph, dir=:out)
```

Returns the adjacency list `a`

of a graph (a vector of vector of ints). The `i`

-th element of the adjacency list is a vector containing the neighbors of `i`

in `g`

.

For directed graphs a second optional argument can be specified (`:out`

or `:in`

). The neighbors in the returned adjacency list are considered accordingly as those related through outgoing or incoming edges.

The elements of `a[i]`

have the same order as in the iterator `(out_/in_)neighbors(g,i)`

.

*Attention*: For some graph types it returns a reference, not a copy, therefore the returned object should not be modified.

`Erdos.adjacency_matrix`

— Function`adjacency_matrix(g, dir=:out, T::DataType=Int)`

Returns a sparse boolean adjacency matrix for a graph, indexed by `[u, v]`

vertices. `true`

values indicate an edge between `u`

and `v`

. Users may specify a direction (`:in`

, `:out`

, or `:all`

are currently supported; `:out`

is default for both directed and undirected graphs) and a data type for the matrix (defaults to `Int`

).

`Erdos.all_edges`

— Method`all_edges(g, v)`

Iterates over all in and out edges of vertex `v`

in `g`

.

`Erdos.all_neighbors`

— Method`all_neighbors(g, v)`

Iterates over all distinct in/out neighbors of vertex `v`

in `g`

.

`Erdos.attracting_components`

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

`Erdos.augment_path!`

— MethodCalculates the amount by which flow can be augmented in the given path. Augments the flow and returns the augment value. Requires arguments:

- path::Vector{Int} # input path
- flow_matrix::AbstractMatrix{T} # the current flow matrix
- capacity_matrix::AbstractMatrix{T} # edge flow capacities

`Erdos.auxiliaryPoints`

— MethodOutput a set of (point,slope) that compose the restricted max-flow function. One point by possible slope is enough (hence O(λ×max_flow) complexity). Requires arguments:

- flow_graph::ADiGraph # the input graph
- source::Int # the source vertex
- target::Int # the target vertex
- capacity_matrix::AbstractMatrix{T} # edge flow capacities

`Erdos.barabasi_albert!`

— Method`barabasi_albert!(g, n::Int, k::Int; seed::Int = -1)`

Grows the graph `g`

according to Barabási–Albert process into a graph with `n`

vertices. At each step a new vertex is attached by preferential attachment to `k`

different vertices already present in the graph.

See also `barabasi_albert`

.

`Erdos.barabasi_albert`

— Method```
barabasi_albert(n, k, G=Graph; seed=-1)
barabasi_albert(n, n0, k, G=Graph; seed=-1)
```

Creates a random graph of type `G`

with `n`

vertices according to Barabási–Albert model. It is grown by adding new vertices to an initial graph with `n0`

vertices (`n0=k`

if not specified). Each new vertex is attached with `k`

edges to `k`

different vertices already present in the system by preferential attachment. The initial graph is empty by default.

Undirected graphs are created by default. Directed graphs can be created passing a directed graph type as last argument (e.g. `DiGraph`

).

See also `barabasi_albert!`

for growing a given graph.

`Erdos.bellman_ford_shortest_paths`

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

Uses the Bellman-Ford algorithm to compute shortest paths of all vertices of a `g`

from a source vertex `s`

(or a set of source vertices `sources`

). Returns a `BellmanFordState`

with relevant traversal information.

`Erdos.betweenness_centrality`

— Method`betweenness_centrality(g; normalize=true, endpoints=false, approx=-1)`

Calculates the betweenness centrality of the vertices of graph `g`

.

Betweenness centrality for vertex `v`

is defined as:

\[bc(v) = \frac{1}{\mathcal{N}} \sum_{s \neq t \neq v} \frac{\sigma_{st}(v)}{\sigma_{st}},\]

where $\sigma _{st}} \sigma_{st}$ is the total number of shortest paths from node `s`

to node `t`

and $\sigma_{st}(v)$ is the number of those paths that pass through `v`

.

If `endpoints=true`

, endpoints are included in the shortest path count.

If `normalize=true`

, the betweenness values are normalized by the total number of possible distinct paths between all pairs in the graph. For an undirected graph, this number if `((n-1)*(n-2))/2`

and for a directed graph, `(n-1)*(n-2)`

where `n`

is the number of vertices in the graph.

If an integer argument `approx > 0`

is given, returns an approximation of the betweenness centrality of each vertex of the graph involving `approx`

randomly chosen vertices.

**References**

[1] Brandes 2001 & Brandes 2008

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

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

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

`Erdos.blocking_flow!`

— Methodblocking*flow! Preallocated version of blocking*flow.Uses BFS to identify a blocking flow in the input graph and then backtracks from the target to the source, aumenting flow along all possible paths.

Requires arguments: residual*graph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacity*matrix::AbstractMatrix{T} # edge flow capacities flow_matrix::AbstractMatrix{T} # the current flow matrix P::AbstractVector{Int} # Parent vector to store Level Graph

`Erdos.blocking_flow!`

— MethodUses BFS to identify a blocking flow in the input graph and then backtracks from the targetto the source, aumenting flow along all possible paths.

Requires arguments: residual*graph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacity*matrix::AbstractMatrix{T} # edge flow capacities flow_matrix::AbstractMatrix{T} # the current flow matrix

`Erdos.boykov_kolmogorov_impl`

— MethodComputes the max-flow/min-cut between source and target using Boykov-Kolmogorov algorithm.

Returns the maximum flow in the network, the flow matrix and the partition {S,T} in the form of a vector of 1's and 2's. The partition vector may also contain 0's. These can be assigned any label (1 or 2), it is a user choice.

For further details, please refer to the paper:

BOYKOV, Y.; KOLMOGOROV, V., 2004. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision.

Uses a default capacity of 1 when the capacity matrix isn't specified.

Requires arguments: residual*graph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacity*matrix::AbstractMatrix{T} # edge flow capacities

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

`Erdos.breakingPoints`

— MethodCalculates the breaking of the restricted max-flow from a set of auxiliary points. Requires arguments:

- flow_graph::ADiGraph # the input graph
- source::Int # the source vertex
- target::Int # the target vertex
- capacity_matrix::AbstractMatrix{T} # edge flow capacities

`Erdos.cartesian_product`

— Method`cartesian_product(g, h)`

Returns the (cartesian product)[https://en.wikipedia.org/wiki/Cartesian*product*of_graphs] of `g`

and `h`

`Erdos.center`

— Method```
center(g, distmx=weights(g))
center(all_ecc)
```

Returns the set of all vertices whose eccentricity is equal to the graph's radius (that is, the set of vertices with the smallest eccentricity).

Eventually a vector `all_ecc`

contain the eccentricity of each node can be passed as argument.

See `eccentricities`

.

`Erdos.circular_layout`

— Method`circular_layout(g) -> x, y`

Return two vectors representing the positions of the nodes of graph `g`

when placed on the unit circonference of radius one centered at the origin.

`Erdos.clean_vertex!`

— Method`clean_vertex!(g, v)`

Remove all incident edges on vertex `v`

in `g`

.

`Erdos.closeness_centrality`

— MethodCalculates the closeness centrality of the graph `g`

.

`Erdos.community_detection_bethe`

— Function`community_detection_bethe(g::AGraph, k=-1; kmax=15)`

Community detection using the spectral properties of the Bethe Hessian matrix associated to `g`

(see Saade et al.). `k`

is the number of communities to detect. If omitted or if `k < 1`

the optimal number of communities will be automatically selected. In this case the maximum number of detectable communities is given by `kmax`

. Returns a vector containing the vertex assignments.

`Erdos.community_detection_nback`

— Method`community_detection_nback(g, k)`

Community detection using the spectral properties of the non-backtracking matrix of graph `g`

(see Krzakala et al.). `k`

is the number of communities to detect.

See also `community_detection_bethe`

for a related community ddetection algorithm.

Returns a vector with the vertex assignments in the communities.

`Erdos.complement`

— Method`complement(g)`

Produces the graph complement of a graph.

`Erdos.complete!`

— Method`complete!(g::ADiGraph)`

For each edge `(u, v)`

in `g`

, adds to `g`

its reverse, i.e. `(v, u)`

.

`Erdos.complete`

— Method`complete(g::ADiGraph)`

Returns a digraph containing both the edges `(u, v)`

of `g`

and their reverse `(v, u)`

. See also `complete!`

.

`Erdos.components`

— Method`components(labels)`

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

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

`Erdos.condensation`

— Method`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 = DiGraph([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
```

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

`Erdos.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 = Graph([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 = Graph([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]
```

`Erdos.contract!`

— Method```
contract!(g, vs)
contract!(g, v1, v2, ....)
```

Merge the vertices in `vs`

into a unique vertex.

`Erdos.core_periphery_deg`

— Method`core_periphery_deg(g)`

A simple degree-based core-periphery detection algorithm (see Lip). Returns the vertex assignments (1 for core and 2 for periphery).

`Erdos.cores`

— Method`cores(g)`

Returns a vector `deg`

such that if `deg[v]=k`

then the vertex `v`

belongs to the `k`

-core of `g`

and not to the `k+1`

-core.

See also `kcore`

.

`Erdos.count_spanning_trees`

— Method`count_spanning_trees(g::AGraph)`

Returns the number of spanning trees of `g`

, computed through Kirchhoff's theorem. The return type is a float, since the number can be very large.

`Erdos.crosspath`

— Method`crosspath(g::AGraph, n::Integer)`

Replicate `n`

times `g`

and connect each vertex with its copies in a path.

`Erdos.degree`

— Method`degree(g, v)`

Return the number of edges from the vertex `v`

.

`Erdos.degree_centrality`

— MethodCalculates the degree centrality of the graph `g`

, with optional (default) normalization.

`Erdos.density`

— Method`density(g)`

Density is defined as the ratio of the number of actual edges to the number of possible edges. This is $|v| |v-1|$ for directed graphs and $(|v| |v-1|) / 2$ for undirected graphs.

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

`Erdos.dfs_tree`

— Method`dfs_tree(g, s)`

Return an ordered vector of vertices representing a directed acylic graph based on depth-first traversal of the graph `g`

starting with source vertex `s`

.

`Erdos.diameter`

— Function`diameter(g, distmx=weights(g))`

Returns the maximum distance between any two vertices in `g`

. Distances between two adjacent nodes are given by `distmx`

.

See also `eccentricities`

, `radius`

.

`Erdos.difference`

— Method`difference(g, h)`

Produces a graph with all the edges in graph `g`

that are not in graph `h`

.

Note that this function may produce a graph with 0-degree vertices.

`Erdos.digraph`

— Method```
digraph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
G = Graph)
```

Build a digraph with `n`

vertices, type `G`

, and given `edgelist`

.

`Erdos.digraph`

— Method`digraph(s::Symbol, G = DiGraph)`

Creates a notorious digraph `s`

of type `G`

. Admissible values for `s`

are:

`s` | graph type |
---|---|

:truncatedtetrahedron | A skeleton of the truncated tetrahedron digraph. |

`Erdos.digraphtype`

— Method`digraphtype{G<:AGraphOrDiGraph}(::Type{G})`

The digraph type corresponding to `G`

. If `G<:ADiGraph`

returns `G`

, if `G<:AGraph`

returns a type `H<:ADiGraph`

.

`Erdos.dijkstra_shortest_paths`

— Function```
dijkstra_shortest_paths(g, s, distmx=weights(g); allpaths=false)
dijkstra_shortest_paths(g, sources, distmx=weights(g); allpaths=false)
```

Performs Dijkstra's algorithm on a graph, computing shortest distances between a source vertex `s`

(or a vector `sources`

) and all other veritces. Returns a `DijkstraState`

that contains various traversal information.

With `allpaths=true`

, returns a `DijkstraState`

that keeps track of all predecessors of a given vertex.

`Erdos.dinic_impl`

— MethodComputes the maximum flow between the source and target vertexes in a flow graph using Dinic's Algorithm Returns the value of the maximum flow as well as the final flow matrix.

Use a default capacity of 1 when the capacity matrix isn't specified.

Requires arguments: residual

`Erdos.discharge!`

— MethodDrains the excess flow out of a vertex. Runs the gap heuristic or relabels the vertex if the excess remains non-zero.

Requires arguments:

- g::ADiGraph # the input graph
- v # vertex to be discharged
- capacity_matrix::AbstractMatrix{T}
- flow_matrix::AbstractMatrix{T}
- excess::AbstractVector{T}
- height::AbstractVector{Int}
- active::AbstractVector{Bool}
- count::AbstractVector{Int}
- Q::PushRelabelHeap

`Erdos.dismantle_ci`

— Method`dismantle_ci(g::AGraph, l::Integer, nrem; verbose=false)`

Applies the Collective Influence (CI) heuristic of Ref. [1] with distance parameter `l`

(tipically `l=3,4`

). Removes a maximum of `nrem`

vertices from `g`

, trying to minimize the size of the maximum connected component of the resulting graph. It stops earlier if the maximum CI goes to zero.

Set `verbose`

to `true`

for info printing in each iteration.

Returns `(gnew, vmap, remlist)`

, where `gnew`

is the reduced graph, `vmap`

is a vertex map of the vertices of `gnew`

to the old ones (see also `rem_vertices!`

) and `remlist`

contains the removed vertices by removal order.

For more fine grained control see `dismantle_ci_init`

and `dismantle_ci_oneiter!`

.

**Usage**

```
g = Graph(100, 1000)
l=3
nrem=10
gnew, vmap, remlist = dismantle_ci(g, l, nrem)
# or equivalently
gnew, heap, lneigs = dismantle_ci_init(g, l)
for it=1:nrem
irem = dismantle_ci_oneiter!(gnew, heap, lneigs, l)
irem <= 0 && break
push!(remlist, irem)
println("Size Max Component: ", maximum(length, connected_components(g)))
end
vmap = rem_vertices!(gnew, remlist)
```

[1] Morone F., Makse H. Influence maximization in complex networks through optimal percolation. Nature (2015)

`Erdos.dismantle_ci_init`

— Method`dismantle_ci_init(g, l)`

Initialization part of `dismantle_ci`

algorithm. Returns `(gnew, heap, lneigs)`

.

`Erdos.dismantle_ci_oneiter!`

— Method`dismantle_ci_oneiter!(g, heap, lneigs, l)`

One step of `dismantle_ci`

algorithm. To be called after `dismantle_ci_init`

Returns the cleaned vertex if any (see `clean_vertex!`

), -1 otherwise.

`Erdos.dst`

— Method`dst(e)`

Returns the destination of an edge.

`Erdos.eccentricities`

— Function```
eccentricities(g, distmx=weights(g))
eccentricities(g, vs, distmx=weights(g))
```

Returns `[eccentricity(g,v,distmx) for v in vs]`

. When `vs`

it is not supplied, considers all node in the graph.

See also `eccentricity`

.

Note: the eccentricity vector returned by `eccentricity`

may be eventually used as input in some eccentricity related measures (`periphery`

, `center`

).

`Erdos.eccentricity`

— Function`eccentricity(g, v, distmx=weights(g))`

Calculates the eccentricity[ies] of a vertex `v`

, An optional matrix of edge distances may be supplied.

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

`Erdos.edge`

— Method`edge(g, u, v)`

Returns an edge from 'u' to 'v'. The edge doesn't necessarily exists in `g`

.

`Erdos.edge_property`

— Method`edge_property(g, name)`

Return an edge map corresponding to property `name`

of edges in `g`

.

`edge_property(g)`

Returns a dictionary with elements `property_name => edge_map`

.

```
edge_property(g, e)
edge_property(g, u, v)
```

Returns a dictionary of the form `name => val`

containing all the properties associated to edge `e`

.

```
edge_property(g, e, name)
edge_property(g, u, v, name)
```

Equivalent to `edge_property(g, e)[name]`

`eprop`

is the short form of this function.

`Erdos.edgemap2adjlist`

— Method`edgemap2adjlist(emap)`

Returns a vector of vectors containing the values of the edge map `emap`

on graph `g`

following the same ordering of `adjacency_list`

`(g)`

.

`Erdos.edges`

— Method`Erdos.edgetype`

— Method```
edgetype(g)
edgetype(G)
```

Returns the type of edges of graph `g`

(or graph type `G`

), i. e. the element type returned of the iterator `edges(g)`

.

`Erdos.edit_distance`

— Method```
edit_distance(G₁, G₂;
insert_cost::Function=v->1.0,
delete_cost::Function=u->1.0,
subst_cost::Function=(u,v)->0.5,
heuristic::Function=DefaultEditHeuristic)
```

Computes the edit distance between graphs G₁ and G₂.

Returns 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₂

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(μ₁, μ₂))`

A custom heuristic can be provided to the A* search in case the default heuristic is not satisfactory. Performance tips: ––––––––-

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

.

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

For further details, please refer to:

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

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

`Erdos.edmonds_karp_impl`

— MethodComputes the maximum flow between the source and target vertexes in a flow graph using the Edmonds-Karp algorithm. Returns the value of the maximum flow as well as the final flow matrix. Use a default capacity of 1 when the capacity matrix isn't specified. Requires arguments:

- residual_graph::ADiGraph # the input graph
- source # the source vertex
- target # the target vertex
- capacity_matrix::AbstractMatrix{T} # edge flow capacities

`Erdos.egonet`

— Method`egonet(g, v::Int, d::Int; dir=:out)`

Returns the subgraph of `g`

induced by the neighbors of `v`

up to distance `d`

. If `g`

is a `DiGraph`

the `dir`

optional argument specifies the edge direction the edge direction with respect to `v`

(i.e. `:in`

or `:out`

) to be considered. This is equivalent to `subgraph`

`(g, neighborhood(g, v, d, dir=dir))[1].`

`Erdos.emrf`

— MethodComputes the maximum multiroute flow (for any real number of routes) between the source and target vertexes in a flow graph using the Extended Multiroute Flow algorithm. If a number of routes is given, returns the value of the multiroute flow as well as the final flow matrix, along with a multiroute cut if Boykov-Kolmogorov max-flow algorithm is used as a subroutine. Otherwise, it returns the vector of breaking points of the parametric multiroute flow function. Use a default capacity of 1 when the capacity matrix isn't specified. Requires arguments:

- flow_graph::ADiGraph # the input graph
- source::Int # the source vertex
- target::Int # the target vertex
- capacity_matrix::AbstractMatrix{T} # edge flow capacities
- flow_algorithm::AbstractFlowAlgorithm # keyword argument for algorithm
- routes::Int # keyword argument for routes

`Erdos.enqueue_vertex!`

— MethodPushes inactive nodes into the queue and activates them.

Requires arguments:

- Q::PushRelabelHeap
- v
- active::AbstractVector{Bool}
- excess::AbstractVector{T}

`Erdos.enumerate_paths`

— Method```
enumerate_paths(state::AbstractPathState)
enumerate_paths(state::AbstractPathState, dest)
```

Given a path state `state`

of type `AbstractPathState`

(see below), returns a vector (indexed by vertex) of the paths between the source vertex used to compute the path state and a destination vertex `v`

, a set of destination vertices `vs`

, or the entire graph. For multiple destination vertices, each path is represented by a vector of vertices on the path between the source and the destination. Nonexistent paths will be indicated by an empty vector. For single destinations, the path is represented by a single vector of vertices, and will be length 0 if the path does not exist.

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

.

`Erdos.eprop`

— FunctionSee `edge_property`

`Erdos.eprop!`

— Function`Erdos.erdos_renyi`

— Method```
erdos_renyi(n::Int, p::Real, G=Graph; seed=-1)
erdos_renyi(n::Int, m::Int, G=Graph; seed=-1)
```

Creates an Erdős–Rényi random graph of type `G`

with `n`

vertices. Edges are added between pairs of vertices with probability `p`

in the first method. In the second method `m`

edges are randomly chosen insted.

Undirected graphs are created by default. Directed graphs can be created passing a directed graph type as last argument (e.g. `DiGraph`

)

Note also that Erdős–Rényi graphs may be generated quickly using `erdos_renyi(n, ne)`

or the `Graph(nv, ne)`

constructor, which randomly select `ne`

edges among all the potential edges.

`Erdos.euclidean_graph`

— Method`euclidean_graph(points::Matrix, G; L=1., p=2., cutoff=Inf, bc=:periodic)`

Given the `d×N`

matrix `points`

builds an Euclidean graph of `N`

vertices according to the following procedure.

Defining the `d`

-dimensional vectors `x[i] = points[:,i]`

, an edge between vertices `i`

and `j`

is inserted if `norm(x[i]-x[j], p) < cutoff`

. In case of negative `cutoff`

instead every edge is inserted. For `p=2`

we have the standard Euclidean distance. Set `bc=:periodic`

to impose periodic boundary conditions in the box $[0,L]^d$. Set `bc=:open`

for open boundary condition. In this case the keyword argument `L`

will be ignored.

Returns a graph and Dict containing the distance on each edge.

`Erdos.fetch_path!`

— MethodA preallocated version of fetch*paths. The parent and successor tables are pre-allocated. Uses Bidirectional BFS to look for augmentable-paths. Returns the vertex where the two BFS searches intersect, the Parent table of the path, the Successor table of the path found, and a flag indicating success Flag Values: 0 => success 1 => No Path to target 2 => No Path to source Requires arguments: residual*graph::ADiGraph # the input graph source # the source vertex target # the target vertex flow*matrix::AbstractMatrix{T} # the current flow matrix capacity*matrix::AbstractMatrix{T} # edge flow capacities P::Vector{Int} # parent table of path init to -1s S::Vector{Int} # successor table of path init to -1s

`Erdos.fetch_path`

— MethodUses Bidirectional BFS to look for augmentable-paths. Returns the vertex where the two BFS searches intersect, the Parent table of the path, the Successor table of the path found, and a flag indicating success Flag Values: 0 => success 1 => No Path to target 2 => No Path to source

`Erdos.floyd_warshall_shortest_paths`

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

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

. Returns a `FloydWarshallState`

with relevant traversal information, each is a vertex-indexed vector of vectors containing the metric for each vertex in the graph.

Note that this algorithm may return a large amount of data (it will allocate on the order of $O(nv^2)$).

`Erdos.gap!`

— MethodImplements the gap heuristic. Relabels all vertices above a cutoff height. Reduces the number of relabels required.

Requires arguments:

- g::ADiGraph # the input graph
- h # cutoff height
- excess::AbstractVector{T}
- height::AbstractVector{Int}
- active::AbstractVector{Bool}
- count::AbstractVector{Int}
- Q::PushRelabelHeap

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

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

`Erdos.getchild!`

— Methodadds a child `s`

to `el`

if it doesn't exist

`Erdos.global_clustering_coefficient`

— Method`global_clustering_coefficient(g)`

Computes the global clustering coefficient.

`Erdos.gprop`

— FunctionSee `graph_property`

`Erdos.gprop!`

— Function`Erdos.graph`

— Method```
graph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
G = Graph)
```

Build a graph with `n`

vertices, of type `G`

, and given `edgelist`

.

`Erdos.graph`

— Method`graph(s::Symbol, G = Graph)`

Creates a notorious graph `s`

of type `G`

. Admissible values for `s`

are:

`s` | graph type |
---|---|

:bull | A bull graph. |

:chvatal | A Chvátal graph. |

:cubical | A Platonic cubical graph. |

:desargues | A Desarguesgraph. |

:diamond | A diamond graph. |

:dodecahedral | A Platonic dodecahedral graph. |

:frucht | A Frucht graph. |

:heawood | A Heawood graph. |

:house | A graph mimicing the classic outline of a house. |

:housex | A house graph, with two edges crossing the bottom square. |

:icosahedral | A Platonic icosahedral graph. |

:krackhardtkite | A Krackhardt-Kite social network graph. |

:moebiuskantor | A Möbius-Kantor graph. |

:octahedral | A Platonic octahedral graph. |

:pappus | A Pappus graph. |

:petersen | A Petersen graph. |

:sedgewickmaze | A simple maze graph used in Sedgewick's Algorithms in C++: Graph Algorithms (3rd ed.) |

:tetrahedral | A Platonic tetrahedral graph. |

:truncatedcube | A skeleton of the truncated cube graph. |

:truncatedtetrahedron | A skeleton of the truncated tetrahedron graph. |

:tutte | A Tutte graph. |

A collection of real world graphs is available through the `readgraph`

function.

`Erdos.graph_property`

— Method`graph_property(g, name)`

Return the property `name`

of `g`

.

`graph_property(g)`

Returns a dictionary with elements `property_name => property_value`

`gprop`

is the short form of this function.

`Erdos.graphtype`

— Method`graphtype{G<:AGraphOrDiGraph}(::Type{G})`

The graph type corresponding to `G`

. If `G<:AGraph`

returns `G`

, if `G<:ADiGraph`

returns a type `H<:AGraph`

.

`Erdos.has_cycles`

— Method`has_cycles(g)`

Return `true`

if graph `g`

contains a cycle.

**Implementation Notes**

Uses DFS.

`Erdos.has_edge`

— Method```
has_edge(g, e)
has_edge(g, u, v)
```

Returns true if the graph `g`

has an edge `e`

(from `u`

to `v`

).

`Erdos.has_edge_property`

— Method```
has_edge_property(g, name)
has_edge_property(g, name, e)
```

Check if network `g`

has an edge property named `name`

. The second method checks also if edge `e`

has an assigned value for that property.

`has_eprop`

is the short form of this function.

`Erdos.has_eprop`

— Function`Erdos.has_gprop`

— Function`Erdos.has_graph_property`

— Method`has_graph_property(g, name)`

Check if network `g`

has a graph property named `name`

.

`has_gprop`

is the short form of this function.

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

.

`Erdos.has_self_loops`

— Method`has_self_loops(g)`

Returns true if `g`

has any self loops.

`Erdos.has_vertex`

— Method`has_vertex(g, v)`

Return true if `v`

is a vertex of `g`

.

`Erdos.has_vertex_property`

— Method`has_vertex_property(g, name, v)`

Check if network `g`

has a vertex property named `name`

. The second method checks also if vertex `v`

has an assigned value for that property.

`has_vprop`

is the short form of this function.

`Erdos.has_vprop`

— Function`Erdos.idx`

— Method`idx(e::AIndexedEdge)`

Returns the index of edge `e`

.

`Erdos.in_adjlist`

— Method`in_adjlist(g)`

Returns the backward adjacency list of a graph. For each vertex the vector of neighbors though incoming edges.

`in_adjlist(g) == [collect(in_neighbors(i)) for i=1:nv(g)]`

It is the same as `adjlist`

and `out_adjlist`

for undirected graphs.

NOTE: returns a reference, not a copy. Do not modify result.

`Erdos.in_degree`

— Method`in_degree(g, v)`

Returns the number of edges which start at vertex `v`

.

`Erdos.in_degree_centrality`

— MethodCalculates the degree centrality of the graph `g`

, with optional (default) normalization.

`Erdos.in_edges`

— Method`in_edges(g, v)`

Returns an iterator to the edges in `g`

going to vertex `v`

. `v == dst(e)`

for each returned edge `e`

.

`Erdos.in_neighbors`

— Method`in_neighbors(g, v)`

Returns an iterable to all neighbors connected to vertex `v`

by an incoming edge.

NOTE: it may return a reference, not a copy. Do not modify result.

`Erdos.incidence_matrix`

— Function`incidence_matrix(g::AGraphOrDiGraph, T::DataType=Int; oriented=false)`

Returns a sparse node-arc incidence matrix for a graph, indexed by `[v, i]`

, where `i`

is in `1:ne(g)`

, indexing an edge `e`

. For directed graphs, a value of `-1`

indicates that `src(e) == v`

, while a value of `1`

indicates that `dst(e) == v`

. Otherwise, the value is `0`

.

For undirected graphs, both entries are `1`

if `oriented=false`

, otherwise `[v, i] -> -1`

and `[u, i] -> 1`

if `v < u`

.

`Erdos.intersection`

— MethodComputes the intersection between:

- Two lines
- A set of segments and a linear function of slope k passing by the origin.

Requires argument:

- x1, y1, a1, x2, y2, a2::T<:AbstractFloat # Coordinates/slopes

- points::Vector{Tuple{T, T, Int}} # vector of points with T<:AbstractFloat
- k::R<:Real # number of routes (slope of the line)

`Erdos.is_bipartite`

— Method`is_bipartite(g)`

Return `true`

if graph `g`

is bipartite.

**Examples**

```
julia> using LightGraphs
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
```

`Erdos.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 = Graph([0 1 0; 1 0 1; 0 1 0]);
julia> is_connected(g)
true
julia> g = Graph([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 = DiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> is_connected(g)
true
```

`Erdos.is_directed`

— Method`is_directed(g)`

Check if `g`

a graph with directed edges.

`Erdos.is_graphical`

— Method`is_graphical(degs::Vector{Int})`

Check whether the degree sequence `degs`

is graphical, according to Erdös-Gallai condition.

Time complexity: O(length(degs)^2)

`Erdos.is_strongly_connected`

— Method`is_strongly_connected(g)`

Return `true`

if directed graph `g`

is strongly connected.

**Examples**

```
julia> g = DiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> is_strongly_connected(g)
true
```

`Erdos.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 = DiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> is_weakly_connected(g)
true
julia> g = DiGraph([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
```

`Erdos.isgraphical`

— Method`isgraphical(degs)`

Return true if the degree sequence `degs`

is graphical, according to Erdös-Gallai condition.

**Performance**

`Time complexity: ``\mathcal{O}(|degs|^2)```

`Erdos.katz_centrality`

— FunctionCalculates the Katz centrality of the graph `g`

.

`Erdos.kcore`

— Method`kcore(g, k) -> (gnew, vmap)`

Returns the `k`

-core of `g`

along with a vertex map associating the mutated vertex indexes to the old ones (as in `rem_vertices!`

).

See also `cores`

`Erdos.kishimoto`

— MethodComputes the maximum multiroute flow (for an integer number of routes) between the source and target vertexes in a flow graph using the Kishimoto algorithm. Returns the value of the multiroute flow as well as the final flow matrix, along with a multiroute cut if Boykov-Kolmogorov is used as a subroutine. Use a default capacity of 1 when the capacity matrix isn't specified. Requires arguments:

- flow_graph::ADiGraph # the input graph
- source::Int # the source vertex
- target::Int # the target vertex
- capacity_matrix::AbstractMatrix{T} # edge flow capacities
- flow_algorithm::AbstractFlowAlgorithm, # keyword argument for algorithm
- routes::Int # keyword argument for routes

`Erdos.label_propagation`

— Method`label_propagation(g; maxiter=1000)`

Community detection using the label propagation algorithm (see Raghavan et al.). `g`

is the input Graph, `maxiter`

is the maximum number of iterations. Returns a vertex assignments and the convergence history

`Erdos.laplacian_matrix`

— Function`laplacian_matrix(g, dir::Symbol=:out, T::DataType=Int)`

Returns a sparse Laplacian matrix for a graph `g`

, indexed by `[u, v]`

vertices. `dir`

has to be `:in, :out`

or `:all`

.

`Erdos.local_clustering`

— Function`local_clustering(g, vlist = vertices(g))`

Returns two vectors, respectively containing the first and second result of `local_clustering_coefficients(g, v)`

for each `v`

in `vlist`

.

`Erdos.local_clustering`

— Method`local_clustering(g, v)`

Returns 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. It is related to the local clustering coefficient by `r=a/b`

.

`Erdos.local_clustering_coefficient`

— Function`local_clustering_coefficient(g, vlist = vertices(g))`

Returns a vector containing the local clustering coefficients for vertices `vlist`

.

`Erdos.local_clustering_coefficient`

— Method`local_clustering_coefficient(g, v)`

Computes the local clustering coefficient for node `v`

.

`Erdos.maximal_cliques`

— MethodFinds all maximal cliques of an undirected graph.

```
julia> using Erdos
julia> g = Graph(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]
```

`Erdos.maximum_adjacency_visit`

— Method`maximum_adjacency_visit(g[, distmx][, log][, io])`

Return the vertices in `g`

traversed by maximum adjacency search. 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.

`Erdos.maximum_flow`

— Method```
maximum_flow{T<:Number}(
g::ADiGraph,
source::Int,
target::Int,
capacity_matrix::AbstractMatrix{T} =
DefaultCapacity(g);
algorithm::AbstractFlowAlgorithm =
PushRelabelAlgorithm(),
restriction::T = zero(T)
)
```

Generic maximum*flow function. The function defaults to the Push-Relabel (also called Preflow) algorithm. Alternatively, the algorithm to be used can also be specified through a keyword argument. A default capacity of 1 is assumed for each link if no capacity matrix is provided. If the restriction is bigger than 0, it is applied to capacity*matrix.

All algorithms return a tuple with

- the maximum flow
- the flow matrix
- the labelling associated to the minimum cut

Available algorithms are `DinicAlgorithm`

, `EdmondsKarpAlgorithm`

, `BoykovKolmogorovAlgorithm`

and `PushRelabelAlgorithm`

.

Time complexity is O(V²√E) for the push relabel algorithm.

**Usage Example:**

```
# Create a flow-graph and a capacity matrix
g = DiGraph(8)
flow_edges = [
(1,2,10),(1,3,5),(1,4,15),(2,3,4),(2,5,9),
(2,6,15),(3,4,4),(3,6,8),(4,7,16),(5,6,15),
(5,8,10),(6,7,15),(6,8,10),(7,3,6),(7,8,10)
]
capacity_matrix = zeros(Int, 8, 8)
for e in flow_edges
u, v, f = e
add_edge!(g, u, v)
capacity_matrix[u,v] = f
end
# Run default maximum_flow without the capacity_matrix (assumes capacity 1. on each edge).
f, F, labels = maximum_flow(g, 1, 8)
# Run Endmonds-Karp algorithm
f, F, labels = maximum_flow(g,1,8,capacity_matrix,algorithm=EdmondsKarpAlgorithm())
```

`Erdos.minimum_cut`

— Method`minimum_cut(g, s, t, capacity_matrix=DefaultCapacity(); kws...)`

Finds the `s-t cut`

of minimal weight according to the `capacities`

matrix on the directed graph `g`

. The solution is found through a maximal flow algorithm. See `maximum_flow`

for the optional arguments.

Returns a triple `(f, cut, labels)`

, where `f`

is the weight of the cut, `cut`

is a vector of the edges in the cut, and `labels`

gives a partitioning of the vertices in two sets, according to the cut.

`Erdos.minimum_cut`

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

`Erdos.minimum_spanning_tree`

— Method```
minimum_spanning_tree{T<:Real}(
g, distmx::AbstractMatrix{T} = weights(g)
)
```

Performs Kruskal's algorithm on a connected, undirected graph `g`

, having adjacency matrix `distmx`

, and computes minimum spanning tree. Returns a `Vector{KruskalHeapEntry}`

, that contains the containing edges and its weights.

`Erdos.minmaxCapacity`

— MethodFunction to get the nonzero min and max function of a Matrix.

Note: this is more efficient than maximum() / minimum() / extrema() since we have to ignore zero values.since we have to ignore zero values.

Requires argument:

- capacity_matrix::AbstractMatrix{T} # edge flow capacities

`Erdos.modularity`

— Method`modularity(g, c)`

Computes Newman's modularity `Q`

for graph `g`

given the partitioning `c`

.

`Erdos.multiroute_flow`

— MethodThe generic multiroute_flow function will output three kinds of results:

- When the number of routes is 0 or non-specified, the set of breaking points of

the multiroute flow is returned.

- When the input is limited to a set of breaking points and a route value k,

only the value of the k-route flow is returned

- Otherwise, a tuple with 1) the maximum flow and 2) the flow matrix. When the

max-flow subroutine is the Boykov-Kolmogorov algorithm, the associated mincut is returned as a third output.

When the input is a network, it requires the following arguments:

- flow_graph::ADiGraph # the input graph
- source::Int # the source vertex
- target::Int # the target vertex
- capacity_matrix::AbstractMatrix{T} # edge flow capacities with T<:Real
- flow_algorithm::AbstractFlowAlgorithm # keyword argument for flow algorithm
- mrf_algorithm::AbstractFlowAlgorithm # keyword argument for multiroute flow algorithm
- routes::R<:Real # keyword argument for the number of routes

When the input is only the set of (breaking) points and the number of route, it requires the following arguments:

- breakingpoints::Vector{Tuple{T, T, Int}}, # vector of breaking points
- routes::R<:Real, # number of routes

When the input is the set of (breaking) points, the number of routes, and the network descriptors, it requires the following arguments:

- breakingpoints::Vector{Tuple{T1, T1, Int}} # vector of breaking points (T1<:Real)
- routes::R<:Real # number of routes
- flow_graph::ADiGraph # the input graph
- source::Int # the source vertex
- target::Int # the target vertex
- capacity_matrix::AbstractMatrix{T2} # optional edge flow capacities (T2<:Real)
- flow_algorithm::AbstractFlowAlgorithm # keyword argument for algorithm

The function defaults to the Push-relabel (classical flow) and Kishimoto (multiroute) algorithms. Alternatively, the algorithms to be used can also be specified through keyword arguments. A default capacity of 1 is assumed for each link if no capacity matrix is provided.

The mrf_algorithm keyword is inforced to Extended Multiroute Flow in the following cases:

- The number of routes is non-integer
- The number of routes is 0 or non-specified

**Usage Example :**

(please consult the max*flow section for options about flow*algorithm and capacity_matrix)

```
# Create a flow-graph and a capacity matrix
flow_graph = DiGraph(8)
flow_edges = [
(1, 2, 10), (1, 3, 5), (1, 4, 15), (2, 3, 4), (2, 5, 9),
(2, 6, 15), (3, 4, 4), (3, 6, 8), (4, 7, 16), (5, 6, 15),
(5, 8, 10), (6, 7, 15), (6, 8, 10), (7, 3, 6), (7, 8, 10)
]
capacity_matrix = zeros(Int, 8, 8)
for e in flow_edges
u, v, f = e
add_edge!(flow_graph, u, v)
capacity_matrix[u, v] = f
end
# Run default multiroute_flow with an integer number of routes = 2
f, F = multiroute_flow(flow_graph, 1, 8, capacity_matrix, routes = 2)
# Run default multiroute_flow with a noninteger number of routes = 1.5
f, F = multiroute_flow(flow_graph, 1, 8, capacity_matrix, routes = 1.5)
# Run default multiroute_flow for all the breaking points values
points = multiroute_flow(flow_graph, 1, 8, capacity_matrix)
# Then run multiroute flow algorithm for any positive number of routes
f, F = multiroute_flow(points, 1.5)
f = multiroute_flow(points, 1.5, valueonly = true)
# Run multiroute flow algorithm using Boykov-Kolmogorov algorithm as max_flow routine
f, F, labels = multiroute_flow(flow_graph, 1, 8, capacity_matrix,
algorithm = BoykovKolmogorovAlgorithm(), routes = 2)
```

`Erdos.ne`

— Method`ne(g)`

The number of edges in `g`

.

Time Complexity: O(1)

`Erdos.neighborhood`

— Function`neighborhood(g, v, d, distmx=weights(g); dir=:out)`

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 = DiGraph([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
```

`Erdos.neighborhood_dists`

— Method`neighborhood_dists(g, v, d, distmx=weights(g))`

Return a tuple of each vertex at a geodesic distance less than or equal to `d`

, where distances may be specified by `distmx`

, along with its distance from `v`

.

**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 = DiGraph([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)
```

`Erdos.neighbors`

— Method`neighbors(g, v)`

Returns a list of all neighbors from vertex `v`

in `g`

.

For directed graph, this is equivalent to `out_neighbors`

(g, v).

NOTE: it may return a reference, not a copy. Do not modify result.

`Erdos.nonbacktrack_embedding`

— Method`nonbacktrack_embedding(g::AGraph, k::Int)`

Spectral embedding of the non-backtracking matrix of `g`

(see Krzakala et al.).

```
`g`: imput Graph
`k`: number of dimensions in which to embed
```

Returns a matrix `ϕ`

where `ϕ[:,i]`

are the coordinates for vertex `i`

.

Note: does not explicitly construct the `nonbacktracking_matrix`

. See `nonbacktracking_matrix`

for details.

`Erdos.nonbacktracking_matrix`

— Method`nonbacktracking_matrix(g)`

Return a non-backtracking matrix `B`

and an edgemap storing the oriented edges' positions in `B`

. Given two arcs $A_{i j}` and `A_{k l}` in `g`, the non-backtraking matrix$B$is defined as$B*{A*{i j}, A*{k l}} = δ*{j k} * (1 - δ_{i l})``

`Erdos.nonbacktracking_randomwalk`

— Method`nonbacktracking_randomwalk(g, s, niter)`

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.

`Erdos.num_self_loops`

— Method`num_self_loops(g)`

Returns the number of self loops in `g`

.

`Erdos.nv`

— Method`nv(g)`

The number of vertices in `g`

.

`Erdos.out_adjlist`

— Method`out_adjlist(g)`

Returns the forward adjacency list of a graph, i.e. a vector of vectors containing for each vertex the neighbors trhough outgoing edges.

`out_adjlist(g) == [collect(out_neighbors(i)) for i=1:nv(g)]`

The adjacency list is be pre-calculated for most graph types. It is the same as `adjlist`

and `in_adjlist`

for undirected graphs and the same as `adjlist`

for directed ones.

NOTE: It may return a reference, not a copy. Do not modify result.

`Erdos.out_degree`

— Method`out_degree(g, v)`

Returns the number of edges which end at vertex `v`

.

`Erdos.out_degree_centrality`

— MethodCalculates the degree centrality of the graph `g`

, with optional (default) normalization.

`Erdos.out_edges`

— Method`out_edges(g, v)`

Returns an iterator to the edges in `g`

coming from vertex `v`

. `v == src(e)`

for each returned edge `e`

.

`Erdos.out_neighbors`

— Method`out_neighbors(g::AGraphOrDiGraph, v)`

Returns an iterable to all neighbors connected to vertex `v`

by an outgoing edge.

NOTE: it may return a reference, not a copy. Do not modify result.

`Erdos.pagerank`

— Function`pagerank(g::ADiGraph, α=0.85, n=100, ϵ = 1.0e-6)`

Calculates the PageRank of the graph `g`

. Can optionally specify a different damping factor (`α`

), number of iterations (`n`

), and convergence threshold (`ϵ`

). If convergence is not reached within `n`

iterations, an error will be returned.

`Erdos.period`

— Method`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 = DiGraph([0 1 0; 0 0 1; 1 0 0]);
julia> period(g)
3
```

`Erdos.periphery`

— Method```
periphery(g, distmx=weights(g))
periphery(all_ecc)
```

Returns the set of all vertices whose eccentricity is equal to the graph's diameter (that is, the set of vertices with the largest eccentricity).

Eventually a vector `all_ecc`

contain the eccentricity of each node can be passed as argument.

See `eccentricities`

.

`Erdos.pop_vertex!`

— Method`pop_vertex!(g)`

Remove the last vertex of `g`

. Equivalent to rem_vertex!(g, nv(g)).

`Erdos.poslist`

— Method`pl[i][k]`

is the position of vertex `i`

in the adjlist of its neighbour `j=fadj[i][k]`

, i.e. `i == adj[j][pl[i][k]]`

.

`Erdos.push_flow!`

— MethodPushes as much flow as possible through the given edge.

Requires arguements:

- g::ADiGraph # the input graph
- u # input from-vertex
- v # input to-vetex
- capacity_matrix::AbstractMatrix{T}
- flow_matrix::AbstractMatrix{T}
- excess::AbstractVector{T}
- height::AbstractVector{Int}
- active::AbstractVector{Bool}
- Q::PushRelabelHeap

`Erdos.push_relabel_impl`

— MethodImplementation of the push relabel algorithm with gap and highest excess heuristics. Takes O(V²√E) time.

Maintains the following auxillary arrays:

- height -> Stores the labels of all vertices
- count -> Stores the number of vertices at each height
- excess -> Stores the difference between incoming and outgoing flow for all vertices
- active -> Stores the status of all vertices. (e(v)>0 => active[v] = true)
- Q -> The heap that stores active vertices waiting to be discharged.

Requires arguments:

- g::ADiGraph # the input graph
- source # the source vertex
- target # the target vertex
- capacity_matrix::AbstractMatrix{T} # edge flow capacities

`Erdos.quick_find!`

— MethodPerforms Quick-Find algorithm on a given pair of nodes `p`

and `q`

, and makes a connection between them in the vector `nodes`

.

`Erdos.radius`

— Function`radius(g, distmx=weights(g))`

Returns the minimum distance between any two vertices in `g`

. Distances between two adjacent nodes are given by `distmx`

.

See `eccentricities`

, `diameter`

.

`Erdos.random_bipartite_configuration_model`

— Method```
random_bipartite_configuration_model(
n1::Int, n2::Int,
k1::Vector{Int}, k2::Vector{Int},
G=Graph; seed=-1)
```

Create a random bipartie undirected graph according to the configuration model. It contains `n1+n2`

vertices. The vertex `i`

in the first set will have degree `k1[i]`

, while the vertex `i`

in the second set will have degree `k2[i]`

.

`G`

is the resulting graph type.

`Erdos.random_bipartite_regular_graph`

— Method`random_bipartite_regular_graph(n1, n2, k1, k2, G=Graph; seed=-1)`

Creates a random undirected nipartite regular graph with `n1+n2`

vertices, the first `n1`

with degree `k1`

, the others with degree `k2`

See also `random_regular_graph`

and `random_bipartite_configuration_model`

.

`Erdos.random_configuration_model`

— Method`random_configuration_model(n::Int, k::Vector{Int}, G=Graph; seed=-1, check_graphical=false)`

Creates a random undirected graph according to the configuration model. It contains `n`

vertices, the vertex `i`

having degree `k[i]`

.

Defining `c = mean(k)`

, it allocates an array of `nc`

`Int`

s, and takes approximately $nc^2$ time.

If `check_graphical=true`

makes sure that `k`

is a graphical sequence (see `is_graphical`

).

`G`

is the resulting graph type.

`Erdos.random_regular_digraph`

— Method`random_regular_digraph(n::Int, k::Int; dir::Symbol=:out, seed=-1)`

Creates a random directed regular graph with `n`

vertices, each with degree `k`

. The degree (in or out) can be specified using `dir=:in`

or `dir=:out`

.

For directed graphs, allocates an $n imes n$ sparse matrix of boolean as an adjacency matrix and uses that to generate the graph.

`Erdos.random_regular_graph`

— Method`random_regular_graph(n::Int, k::Int, G=Graph; seed=-1)`

Creates a random undirected regular graph with `n`

vertices, each with degree `k`

.

For undirected graphs, allocates an array of `nk`

`Int`

s, and takes approximately $nk^2$ time. For $k > n/2$, generates a graph of degree `n-k-1`

and returns its complement.

`G`

is the resulting graph type.

`Erdos.randomwalk`

— Method`randomwalk(g, s, niter)`

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.

`Erdos.range_shuffle!`

— MethodFast shuffle Array `a`

in UnitRange `r`

inplace.

`Erdos.readgraph`

— Method```
readgraph(filename, G=Graph)
readgraph(filename, t, G=Graph; compressed=false)
```

Reads a graph from `filename`

in the format `t`

. Returns a graph of type `G`

or the corresponding digraph/graph type. Compressed files can eventually be read.

Supported formats are `:gml, :dot, :graphml, :gexf, :net, :gt`

.

If no format is provided, it will be inferred from `filename`

.

`readgraph(s::Symbol, G=Graph)`

Read a graph identified by `s`

from Erdos datasets collection (e.g. `s=:karate`

). They are stored in the `gt`

binary format in the `datasets`

directory of the package. For a list of available graph refer to the documentation.

`Erdos.readnetwork`

— Method```
readnetwork(filename, G=Network)
readnetwork(filename, t, G=Network; compressed=false)
```

Read a network from `filename`

in the format `t`

. Returns a network of type `G`

(or the corresponding directed/undirected type if needed). Compressed files can eventually be read.

Supported formats are `:gml, :dot, :graphml, :gexf, :net, :gt`

. When possible, graph, edge, and vertex properties will be read as well.

If no format is provided, it will be inferred from the `filename`

.

`readnetwork(s::Symbol, G=Network)`

Read a network identified by `s`

from Erdos' datasets collection (e.g. `s=:karate`

). They are stored in the `gt`

binary format in the `datasets`

directory of the package. For a list of available graph refer to the documentation.

`Erdos.readpajek`

— Method`readpajek{G}(f::IO, ::Type{G})`

Reads a graph from file `f`

in the Pajek .net format. Returns 1 (number of graphs written).

`Erdos.rebuild!`

— Method`rebuild!(g)`

Check and restore the structure of `g`

, which could be corrupted by the use of unsafe functions (e. g. `unsafe_add_edge!`

)

`Erdos.relabel!`

— MethodRelabels a vertex with respect to its neighbors, to produce an admissable edge.

Requires arguments:

- g::ADiGraph # the input graph
- v # input vertex to be relabeled
- capacity_matrix::AbstractMatrix{T}
- flow_matrix::AbstractMatrix{T}
- excess::AbstractVector{T}
- height::AbstractVector{Int}
- active::AbstractVector{Bool}
- count::AbstractVector{Int}
- Q::AbstractVector{Int}

`Erdos.rem_edge!`

— Method`rem_edge!(g, e)`

Remove the edge `e`

.

`rem_edge!(g, u, v)`

Remove the edge from `u`

to `v`

.

Returns false if edge removal fails (e.g., if the edge does not exist) and true otherwise.

`Erdos.rem_edge_property!`

— Method`rem_edge_property!(g, name)`

Remove the edge property `name`

from `g`

.

`rem_eprop!`

is the short form of this function.

`Erdos.rem_eprop!`

— Function`Erdos.rem_gprop!`

— Function`Erdos.rem_graph_property!`

— Method`rem_graph_property!(g, name)`

Remove the property `name`

from `g`

.

`rem_gprop!`

is the short form of this function.

`Erdos.rem_vertex!`

— Method`rem_vertex!(g, v)`

Remove the vertex `v`

from graph `g`

. It will change the label of the last vertex of the old graph to `v`

.

See also `rem_vertices!`

.

`Erdos.rem_vertex_property!`

— Method`rem_vertex_property!(g, name)`

Remove the vertex property `name`

from `g`

.

`rem_vprop!`

is the short form of this function.

`Erdos.rem_vertices!`

— Method```
rem_vertices!(g, vs)
rem_vertices!(g, v1, v2, ....)
```

Remove the vertices in `vs`

from graph `g`

.

Some vertices of `g`

may be reindexed during the removal. To keep track of the reindexing, a vertex map is returned, associating vertices with changed indexes to their old indexes.

`Erdos.rem_vprop!`

— Function`Erdos.residual_graph`

— Method`residual_graph{G<:ADiGraph}(g::G, capacity, flow)`

Computers the residual graph of `g`

associated to given `flow`

and `capacity`

. See wikipedia.

`Erdos.sample!`

— Methodsample!([rng,] a, k; exclude = ())

Sample `k`

element from array `a`

without repetition and eventually excluding elements in `exclude`

. Pay attention, it changes the order of the elements in `a`

.

`Erdos.self_avoiding_randomwalk`

— Method`self_avoiding_randomwalk(g, s, niter)`

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.

`Erdos.set_graph_property!`

— Method`set_graph_property!(g, name, x)`

Set the property `name`

to value `x`

to `g`

. Creates the property if it doesn't exist. `gprop!`

can be conveniently used as a short form of this function.

**Example**

```
g = Network(10, 20)
set_graph_property!(g, "label", "My Network")
# or equivalently
gprop!(g, "label", "My Network")
```

`Erdos.shell_layout`

— Method`shell_layout(g, nlist) -> x, y`

Position the nodes of `g`

in concentric circles.

`nlist`

is a vector of vectors containing the nodes for each shell.

`Erdos.shortest_paths`

— Method`shortest_paths(g, x...; kws...)`

Computes shortest paths using Dijkstra's algorithm. See `dijkstra_shortest_paths`

.

`Erdos.slope`

— MethodFunction to get the slope of the restricted flow. The slope is initialized at 0 and is incremented for each non saturated edge in the restricted min-cut. Requires argument: flow*graph::ADiGraph, # the input graph capacity*matrix::AbstractMatrix{T}, # edge flow capacities cut::Vector{Int}, # cut information for vertices restriction::T # value of the restriction

`Erdos.spectral_distance`

— Method`spectral_distance(G₁, G₂ [, k])`

Compute the spectral distance between undirected n-vertex graphs G₁ and G₂ using the top k ≤ n greatest eigenvalues. If k is ommitted, uses full spectrum.

For further details, please refer to:

JOVANOVIC, I.; STANIC, Z., 2014. Spectral Distances of Graphs Based on their Different Matrix Representations

`Erdos.spring_layout`

— Method```
spring_layout(g;
k = 1 / √nv(g),
maxiter = 100,
inittemp = 2.0,
[x0, y0]) -> x, y
```

Return the positions of the nodes in graph `g`

according to Fruchterman and Reingold's spring/repulsion model. The forces as function of the distance `d`

beetween two nodes are given by

```
f_a(d) = d / k # attractive force
f_r(d) = -k^2 / d^2 # repulsive force:
```

`maxiter`

is the number of updates of the positions. `inittemp`

controls displacement per iteration.

Initial positions can passed though the argument `x0`

and `y0`

.

The positions are rescaled to fit the [-1, +1]^2 box.

This function is adapted from GraphLayout.jl.

`Erdos.src`

— Method`src(e)`

Returns the source of an edge.

`Erdos.static_fitness_model`

— Method```
static_fitness_model(m, fitness, G=Graph; seed=-1)
static_fitness_model(m, fitness_out, fitness_in, G=DiGraph; seed=-1)
```

Generates a random graph with `length(fitness)`

nodes and `m`

edges, in which the probability of the existence of edge `(i, j)`

is proportional to `fitness[i]*fitness[j]`

. Time complexity is O(|V| + |E| log |E|).

In and out fitness have to be supplied for generating directed graphs.

Reference:

- Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution

in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

`Erdos.static_scale_free`

— Method```
static_scale_free(n, m, α, G=Graph;
seed=-1, finite_size_correction=true)
```

Generates a random graph with `n`

vertices, `m`

edges and expected power-law degree distribution with exponent `α`

. `finite_size_correction`

determines whether to use the finite size correction proposed by Cho et al. This generator calls internally the `static_fitness_model function`

. Time complexity is O(|V| + |E| log |E|).

```
static_scale_free(n, m, α_out, α_in, G=DiGraph;
seed=-1, finite_size_correction=true)
```

Generates a random digraph.

References:

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002.

Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.

`Erdos.stochastic_block_model`

— Method```
stochastic_block_model(c::Matrix{Float64}, n::Vector{Int}; seed::Int = -1)
stochastic_block_model(cin::Float64, coff::Float64, n::Vector{Int}; seed::Int = -1)
```

Returns a Graph generated according to the Stochastic Block Model (SBM).

`c[a,b]`

: Mean number of neighbors of a vertex in block `a`

belonging to block `b`

. Only the upper triangular part is considered, since the lower traingular is determined by $c[b,a] = c[a,b] * n[a]/n[b]$. `n[a]`

: Number of vertices in block `a`

The second form samples from a SBM with `c[a,a]=cin`

, and `c[a,b]=coff`

.

For a dynamic version of the SBM see the `StochasticBlockModel`

type and related functions.

`Erdos.strongly_connected_components`

— Method`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 = DiGraph([0 1 0; 1 0 1; 0 0 0]);
julia> strongly_connected_components(g)
2-element Array{Array{Int64,1},1}:
[3]
[1, 2]
```

`Erdos.subgraph`

— Method```
subgraph(g, vlist) -> sg, vlist
subgraph(g, elist) -> sg, vlist
```

Returns the subgraph of `g`

induced by the vertices in `vlist`

or by the edges in `elist`

, along with `vlist`

itself (a newly created vector for the second method).

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`

.

For easy subgraph creation also `g[vlist]`

or `g[elist]`

can be used.

If `g`

is a network, vector and edge properties won't be converved `sg`

. You can preserve properties using the `subnetwork`

method.

**Usage Examples:**

```
g = CompleteGraph(10)
sg, vlist = subgraph(g, 5:8)
@assert g[5:8] == sg
@assert nv(sg) == 4
@assert ne(sg) == 6
@assert vm[4] == 8
sg, vlist = subgraph(g, [2,8,3,4])
@asssert sg == g[[2,8,3,4]]
elist = [Edge(1,2), Edge(3,4), Edge(4,8)]
sg, vlist = subgraph(g, elist)
@asssert sg == g[elist]
```

`Erdos.subnetwork`

— Method```
subnetwork(g, vlist) -> sg, vlist
subnetwork(g, elist) -> sg, vlist
```

Equivalent to `subgraph`

but preserves vertex and edge properties when `g`

is a network.

`Erdos.swap_vertices!`

— Method`swap_vertices!(g, u, v)`

Swap the labels of vertices `u`

and `v`

. In the new graph all old neighbors of vertex `u`

will be neighbors of `v`

and viceversa.

`Erdos.symmetric_difference`

— Method`symmetric_difference(g, h)`

Produces a graph with edges from graph `g`

that do not exist in graph `h`

, and vice versa.

Note that this function may produce a graph with 0-degree vertices.

`Erdos.tensor_product`

— Method`tensor_product(g, h)`

Returns the (tensor product)[https://en.wikipedia.org/wiki/Tensor*product*of_graphs] of `g`

and `h`

`Erdos.topological_sort_by_dfs`

— Method`topological_sort_by_dfs(g)`

Return a toplogical sort of a directed graph `g`

as a vector of vertices in topological order.

`Erdos.tree`

— Method`tree(parents)`

Convert a parents array into a directed graph.

`Erdos.triangles`

— Function`triangles(g, vlist = vertices(g))`

Returns a vector containing the number of triangles for vertices `vlist`

.

`Erdos.triangles`

— Method`triangles(g, v)`

Returns the number of triangles in the neighborhood for node `v`

.

`Erdos.unsafe_add_edge!`

— Method`unsafe_add_edge!(g, u, v)`

Possibly faster and unsafer version of `add_edge!`

, which doesn't guarantee some graph invariant properties.

For example, some graph types (e.g. `Graph`

) assume sorted adjacency lists as members. In this case order is not preserved while inserting new edges, resulting in a faster construction of the graph. As a consequence though, some functions such `has_edge(g, u, v)`

could give incorrect results.

To restore the correct behaviour, call `rebuild!`

(g) after the last call to `unsafe_add_edge!`

.

`Erdos.vertex_property`

— Method`vertex_property(g, name)`

Return an vertex map corresponding to property `name`

of vertices in `g`

.

`vertex_property(g)`

Returns a dictionary with elements `property_name => vertex_map`

.

`vertex_property(g, v)`

Returns a dictionary of the form `name => val`

containing all the properties associated to vertex `v`

.

`vertex_property(g, v, name)`

Equivalent to `vertex_property(g, v)[name]`

.

`vprop`

is the short form for this function.

`Erdos.vertextype`

— Method```
vertextype(g)
vertextype(G)
```

Returns the integer type of vertices of graph `g`

(or graph type `G`

).

`Erdos.vertices`

— Method`vertices(g)`

Returns an iterator to the vertices of a graph (i.e. 1:nv(g))

`Erdos.vote!`

— MethodReturn the most frequency label.

`Erdos.vprop`

— FunctionSee `vertex_property`

`Erdos.vprop!`

— Function`Erdos.watts_strogatz`

— Method`watts_strogatz(n, k, β, G=Graph; seed=-1)`

Creates a Watts-Strogatz small model random graph with `n`

vertices, each with degree `k`

. Edges are randomized per the model based on probability `β`

.

Undirected graphs are created by default. Directed graphs can be created passing a directed graph type as last argument (e.g. `DiGraph`

).

`Erdos.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 = DiGraph([0 1 0; 1 0 1; 0 0 0]);
julia> weakly_connected_components(g)
1-element Array{Array{Int64,1},1}:
[1, 2, 3]
```

`Erdos.weights`

— Method`weights(g)`

Returns an edge map containing the "weights" associated to edges. For simple graphs, the return value is ConstEdgeMap(g, 1). For networks, returns the "weights" edge property if defined, otherwise the constant map.

Notice that the edge map returned by `weights`

is the default value for the edge weights used in many flow and distance on graph algorithms.

`Erdos.writegml`

— Method`writegml(f, g)`

Writes a graph `g`

to a file `f`

in the GML format.

`Erdos.writegraph`

— Method```
writegraph(file, g)
writegraph(file, g, t; compress=false)
```

Save a graph `g`

to `file`

in the format `t`

.

Eventually the resulting file can be compressed in the gzip format.

Currently supported formats are `:gml, :graphml, :gexf, :dot, :net, :gt`

.

If no format is provided, it will be inferred from `file`

along with compression.

`Erdos.writenetwork`

— Method```
writenetwork(file, g)
writenetwork(file, g, t; compress=false)
```

Save a network `g`

to `file`

in the format `t`

.

Eventually the resulting file can be compressed in the gzip format.

Currently supported formats are `:gml, :graphml, :gexf, :dot, :net, :gt`

. When possible, graph, edge, and vertex properties will be written as well.

If no format is provided, it will be inferred from `file`

along with compression.

`Erdos.writepajek`

— MethodWrites a graph `g`

to a file `f`

in the Pajek .net format. Returns 1 (number of graphs written).

`SparseArrays.blockdiag`

— Method`blockdiag(g, h)`

Produces a graph with $|V(g)| + |V(h)|$ vertices and $|E(g)| + |E(h)|$ edges.

Put simply, the vertices and edges from graph `h`

are appended to graph `g`

.

`SparseArrays.sparse`

— Method`sparse(g)`

Equivalent to `adjacency_matrix`

.