A graph and network analysis package for julia.

const AGraphOrDiGraph = Union{AGraph, ADiGraph}

Union of AGraph and ADiGraph.

abstract ADiGraph

Abstract directed graph type

abstract type ADiNetwork <: ADiGraph end

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

abstract type AEdge end

An abstract edge type.

abstract type AEdgeMap{T} end

Type representing an abstract edge map with value type T.

abstract type AGraph end

Abstract undirected graph type

abstract type AIndexedEdge <: AEdge end

Edge types with unique indexes, accessed by idx

abstract type ANetwork <: AGraph end

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

abstract type AVertexMap{T} end

Type representing an abstract vertex map with value type T.

abstract type that allows users to pass in their preferred Algorithm

abstract type that allows users to pass in their preferred Algorithm

Forces the maximum_flow function to use the Boykov-Kolmogorov algorithm.

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.

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.

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

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.

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.

Forces the maximum_flow function to use Dinic's algorithm.

struct Edge
    src::Int
    dst::Int
end

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

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

Forces the maximum_flow function to use the Edmonds–Karp algorithm.

Forces the multiroute_flow function to use the Extended Multiroute Flow algorithm.

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.

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.

Forces the multiroute_flow function to use the Kishimoto algorithm.

Type to record neighbor labels and their counts.

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.

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

A type storing properties associated to networks.

Forces the maximum_flow function to use the Push-Relabel algorithm.

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

Redefinition 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

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.

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.

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.

reverse!(g::DiGraph)

In-place reverse (modifies the original graph).

reverse(e)

Returns an edge with swapped src(e) and dst(e).

reverse(g::ADiGraph)

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

size(g,i) provides 1:nv or 2:nv else 1

sum(g,i) provides 1:indegree or 2:outdegree vectors

sum(g)` provides the number of edges in the graph

union(g, h)

Merges graphs g and h by taking the set union of all vertices and edges.

BinaryTree(levels, G=Graph)

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

Similar to MinkowskiCost, but ensures costs smaller than 2τ.

CliqueGraph(k, n, G=Graph)

This function generates a graph with n k-cliques connected circularly by n edges.

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.

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

CompleteGraph(n, G = Graph)

Creates a complete graph of type G with n vertices. A complete graph has edges connecting each pair of vertices.

Creates a cycle digraph with n vertices. A cycle digraph is a closed path digraph.

CycleGraph(n, G=Graph)

Creates a cycle graph with n vertices. A cycle graph is a closed path graph.

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.

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.

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

PathDiGraph(n, G = DiGraph)

Creates a path digraph with n vertices. A path graph connects each successive vertex by a single directed edge.

PathGraph(n, G = Graph)

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

The Roach Graph from Guattery and Miller 1998

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

StarGraph(n, G = Graph)

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

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

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.

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.

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.

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)

add_vertex!(g)

Add a new vertex to the graph g.

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.

add_vertices!(g, n)

Add n new vertices to the graph g. Returns the final number of vertices.

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.

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

all_edges(g, v)

Iterates over all in and out edges of vertex v in g.

all_neighbors(g, v)

Iterates over all distinct in/out neighbors of vertex v in g.

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]

Calculates 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

Output 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

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.

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.

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.

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

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.

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

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

blockingflow! Preallocated version of blockingflow.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: residualgraph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacitymatrix::AbstractMatrix{T} # edge flow capacities flow_matrix::AbstractMatrix{T} # the current flow matrix P::AbstractVector{Int} # Parent vector to store Level Graph

Uses 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: residualgraph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacitymatrix::AbstractMatrix{T} # edge flow capacities flow_matrix::AbstractMatrix{T} # the current flow matrix

Computes 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: residualgraph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacitymatrix::AbstractMatrix{T} # edge flow capacities

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

Calculates 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

cartesian_product(g, h)

Returns the (cartesian product)[https://en.wikipedia.org/wiki/Cartesianproductof_graphs] of g and h

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.

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.

clean_vertex!(g, v)

Remove all incident edges on vertex v in g.

Calculates the closeness centrality of the graph g.

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.

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.

complement(g)

Produces the graph complement of a graph.

complete!(g::ADiGraph)

For each edge (u, v) in g, adds to g its reverse, i.e. (v, u).

complete(g::ADiGraph)

Returns a digraph containing both the edges (u, v) of g and their reverse (v, u). See also complete!.

components(labels)

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

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.

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

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.

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]

contract!(g, vs)
contract!(g, v1, v2, ....)

Merge the vertices in vs into a unique vertex.

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

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.

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.

crosspath(g::AGraph, n::Integer)

Replicate n times g and connect each vertex with its copies in a path.

degree(g, v)

Return the number of edges from the vertex v.

Calculates the degree centrality of the graph g, with optional (default) normalization.

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.

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.

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.

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.

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.

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

Build a digraph with n vertices, type G, and given edgelist.

digraph(s::Symbol, G = DiGraph)

Creates a notorious digraph s of type G. Admissible values for s are:

digraphtype{G<:AGraphOrDiGraph}(::Type{G})

The digraph type corresponding to G. If G<:ADiGraph returns G, if G<:AGraph returns a type H<:ADiGraph.

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.

Computes 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: residualgraph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacitymatrix::AbstractMatrix{T} # edge flow capacities

Drains 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

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)

dismantle_ci_init(g, l)

Initialization part of dismantle_ci algorithm. Returns (gnew, heap, lneigs).

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.

dst(e)

Returns the destination of an edge.

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

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.

edge(g, u, v)

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

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.

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

edges(g, v)

Returns an iterator to the edges in g coming from vertex v. v == src(e) for each returned edge e.

It is equivalent to out_edges.

For digraphs, use all_edges to iterate over both in and out edges.

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

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)

Computes 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

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

Computes 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

Pushes inactive nodes into the queue and activates them.

Requires arguments:

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

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.

See edge_property

See add_edge_property!

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.

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.

A preallocated version of fetchpaths. 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: residualgraph::ADiGraph # the input graph source # the source vertex target # the target vertex flowmatrix::AbstractMatrix{T} # the current flow matrix capacitymatrix::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

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

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)$).

Implements 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

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.

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.

adds a child s to el if it doesn't exist

global_clustering_coefficient(g)

Computes the global clustering coefficient.

See graph_property

See set_graph_property!

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

Build a graph with n vertices, of type G, and given edgelist.

graph(s::Symbol, G = Graph)

Creates a notorious graph s of type G. Admissible values for s are:

A collection of real world graphs is available through the readgraph function.

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.

graphtype{G<:AGraphOrDiGraph}(::Type{G})

The graph type corresponding to G. If G<:AGraph returns G, if G<:ADiGraph returns a type H<:AGraph.

has_cycles(g)

Return true if graph g contains a cycle.

Implementation Notes

Uses DFS.

has_edge(g, e)
has_edge(g, u, v)

Returns true if the graph g has an edge e (from u to v).

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.

See has_edge_property

See has_graph_property

has_graph_property(g, name)

Check if network g has a graph property named name.

has_gprop is the short form of this function.

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.

has_self_loops(g)

Returns true if g has any self loops.

has_vertex(g, v)

Return true if v is a vertex of g.

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.

See has_vertex_property

idx(e::AIndexedEdge)

Returns the index of edge e.

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.

in_degree(g, v)

Returns the number of edges which start at vertex v.

Calculates the degree centrality of the graph g, with optional (default) normalization.

in_edges(g, v)

Returns an iterator to the edges in g going to vertex v. v == dst(e) for each returned edge e.

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.

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.

Computes the intersection between:

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

Requires argument:

1. • x1, y1, a1, x2, y2, a2::T<:AbstractFloat # Coordinates/slopes
2. • points::Vector{Tuple{T, T, Int}} # vector of points with T<:AbstractFloat
   • k::R<:Real # number of routes (slope of the line)

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

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

is_directed(g)

Check if g a graph with directed edges.

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)

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

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

isgraphical(degs)

Return true if the degree sequence degs is graphical, according to Erdös-Gallai condition.

Performance

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

Calculates the Katz centrality of the graph g.

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

Computes 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

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

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.

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.

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.

local_clustering_coefficient(g, vlist = vertices(g))

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

local_clustering_coefficient(g, v)

Computes the local clustering coefficient for node v.

Finds 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]

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.

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

Generic maximumflow 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 capacitymatrix.

All algorithms return a tuple with

1. the maximum flow
2. the flow matrix
3. 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())

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.

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.

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.

Function 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

modularity(g, c)

Computes Newman's modularity Q for graph g given the partitioning c.

The 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 maxflow section for options about flowalgorithm 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)

ne(g)

The number of edges in g.

Time Complexity: O(1)

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

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)

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.

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.

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

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.

num_self_loops(g)

Returns the number of self loops in g.

nv(g)

The number of vertices in g.

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.

out_degree(g, v)

Returns the number of edges which end at vertex v.

Calculates the degree centrality of the graph g, with optional (default) normalization.

out_edges(g, v)

Returns an iterator to the edges in g coming from vertex v. v == src(e) for each returned edge e.

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.

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.

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

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.

pop_vertex!(g)

Remove the last vertex of g. Equivalent to rem_vertex!(g, nv(g)).

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

Pushes 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

Implementation 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

Performs Quick-Find algorithm on a given pair of nodes pand q, and makes a connection between them in the vector nodes.

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.

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.

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.

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 Ints, 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.

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.

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 Ints, 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.

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.

Fast shuffle Array a in UnitRange r inplace.

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.

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.

readpajek{G}(f::IO, ::Type{G})

Reads a graph from file f in the Pajek .net format. Returns 1 (number of graphs written).

rebuild!(g)

Check and restore the structure of g, which could be corrupted by the use of unsafe functions (e. g. unsafe_add_edge!)

Relabels 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}

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.

rem_edge_property!(g, name)

Remove the edge property name from g.

rem_eprop! is the short form of this function.

See rem_edge_property!

See rem_graph_property!

rem_graph_property!(g, name)

Remove the property name from g.

rem_gprop! is the short form of this function.

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

rem_vertex_property!(g, name)

Remove the vertex property name from g.

rem_vprop! is the short form of this function.

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.

See rem_vertex_property!

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

Computers the residual graph of g associated to given flow and capacity. See wikipedia.

sample!([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.

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.

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")

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.

shortest_paths(g, x...; kws...)

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

Function 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: flowgraph::ADiGraph, # the input graph capacitymatrix::AbstractMatrix{T}, # edge flow capacities cut::Vector{Int}, # cut information for vertices restriction::T # value of the restriction

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

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.

src(e)

Returns the source of an edge.

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.

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.

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.

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]

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]

subnetwork(g, vlist) -> sg, vlist
subnetwork(g, elist) -> sg, vlist

Equivalent to subgraph but preserves vertex and edge properties when g is a network.

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.

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.

tensor_product(g, h)

Returns the (tensor product)[https://en.wikipedia.org/wiki/Tensorproductof_graphs] of g and h

topological_sort_by_dfs(g)

Return a toplogical sort of a directed graph g as a vector of vertices in topological order.

tree(parents)

Convert a parents array into a directed graph.

triangles(g, vlist = vertices(g))

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

triangles(g, v)

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

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

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.

vertextype(g)
vertextype(G)

Returns the integer type of vertices of graph g (or graph type G).

vertices(g)

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

Return the most frequency label.

See vertex_property

See add_vertex_property!

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

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]

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.

writegml(f, g)

Writes a graph g to a file f in the GML format.

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.

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.

Writes a graph g to a file f in the Pajek .net format. Returns 1 (number of graphs written).

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.

sparse(g)

Equivalent to adjacency_matrix.