Erdos.Erdos
— ModuleA graph and network analysis package for julia.
Erdos.AGraphOrDiGraph
— ConstantErdos.ADiGraph
— Typeabstract ADiGraph
Abstract directed graph type
Erdos.ADiNetwork
— Typeabstract type ADiNetwork <: ADiGraph end
An abstract directed graph with the additional possibility to attach properties to vertices and edges.
Erdos.AEdge
— Typeabstract type AEdge end
An abstract edge type.
Erdos.AEdgeMap
— Typeabstract type AEdgeMap{T} end
Type representing an abstract edge map with value type T
.
Erdos.AGraph
— Typeabstract type AGraph end
Abstract undirected graph type
Erdos.AIndexedEdge
— Typeabstract type AIndexedEdge <: AEdge end
Edge types with unique indexes, accessed by idx
Erdos.ANetwork
— Typeabstract type ANetwork <: AGraph end
An abstract graph with the additional possibility to attach properties to vertices and edges.
Erdos.AVertexMap
— Typeabstract type AVertexMap{T} end
Type representing an abstract vertex map with value type T
.
Erdos.BoykovKolmogorovAlgorithm
— TypeForces the maximum_flow function to use the Boykov-Kolmogorov algorithm.
Erdos.ConstEdgeMap
— Typestruct 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
— Typestruct 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.DiGraph
— Typemutable 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
— Typemutable struct DiNetwork <: ADiNetwork
ne::Int
edge_index_range::Int
out_edges::Vector{Vector{Pair{Int,Int}}} #unordered out_adjlist
in_edges::Vector{Vector{Pair{Int,Int}}} #unordered in_adjlist
epos::Vector{Pair{Int,Int}} # position of the edge in out_edges
# the first in the pair is the vertex
# with lower index
free_indexes::Vector{Int} # indexes of deleted edges to be used up
# for new edges to avoid very large
# indexes, and unnecessary property map
# memory use
props::PropertyStore
end
A type representing an directed graph with indexed edges.
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
— Typestruct Edge
src::Int
dst::Int
end
A type representing an edge between two vertices of a graph.
Erdos.EdgeMap
— Typemutable 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
— Typemutable struct Graph{T<:Integer} <: AGraph
ne::Int
fadjlist::Vector{Vector{T}}
end
A simple graph type based on an adjacency list.
Graph{T}(n=0)
Graph(n=0) = Graph{Int}(n)
Construct 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
— Typestruct 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.Network
— Typemutable struct Network <: ANetwork
ne::Int
edge_index_range::Int
out_edges::Vector{Vector{Pair{Int,Int}}} #unordered adjlist
epos::Vector{Pair{Int,Int}} # position of the edge in out_edges
free_indexes::Vector{Int} # indexes of deleted edges to be used up
# for new edges to avoid very large
# indexes, and unnecessary property map
# memory used
props::PropertyStore
end
A type representing a directed graph with indexed edges.
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
— Typemutable 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
— Typemutable struct VertexMap{G <: AGraphOrDiGraph, T, D} <: AVertexMap{T}
g::G
vtype::Type{T}
data::D
end
Type implementing an edge 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 each u=1:nv(g)
.
Base.intersect
— Methodintersect(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
— Methodjoin(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!
— Methodreverse!(g::DiGraph)
In-place reverse (modifies the original graph).
Base.reverse
— Methodreverse(e)
Returns an edge with swapped src(e)
and dst(e)
.
Base.reverse
— Methodreverse(g::ADiGraph)
Produces a graph where all edges are reversed from the original.
Base.union
— Methodunion(g, h)
Merges graphs g
and h
by taking the set union of all vertices and edges.
Erdos.BinaryTree
— MethodBinaryTree(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
— MethodCliqueGraph(k, n, G=Graph)
This function generates a graph with n
k
-cliques connected circularly by n
edges.
Erdos.CompleteBipartiteGraph
— MethodCompleteBipartiteGraph(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
— MethodCompleteDiGraph(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
— MethodCompleteGraph(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
— MethodCycleGraph(n, G=Graph)
Creates a cycle graph with n
vertices. A cycle graph is a closed path graph.
Erdos.DoubleBinaryTree
— MethodDoubleBinaryTree(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
— MethodGrid(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
— MethodPathDiGraph(n, G = DiGraph)
Creates a path digraph with n
vertices. A path graph connects each successive vertex by a single directed edge.
Erdos.PathGraph
— MethodPathGraph(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
— MethodStarGraph(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
— MethodWheelGraph(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
— Functiona_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!
— Methodadd_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!
— Methodadd_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!
— Methodadd_vertex!(g)
Add a new vertex to the graph g
.
Erdos.add_vertex_property!
— Methodadd_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!
— Methodadd_vertices!(g, n)
Add n
new vertices to the graph g
. Returns the final number of vertices.
Erdos.adjacency_list
— Methodadjacency_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
— Functionadjacency_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
— Methodall_edges(g, v)
Iterates over all in and out edges of vertex v
in g
.
Erdos.all_neighbors
— Methodall_neighbors(g, v)
Iterates over all distinct in/out neighbors of vertex v
in g
.
Erdos.attracting_components
— Methodattracting_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.barabasi_albert!
— Methodbarabasi_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
— Methodbarabasi_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
— Methodbellman_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
— Methodbetweenness_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:
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_tree
— Methodbfs_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
— Methodbipartite_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.cartesian_product
— Methodcartesian_product(g, h)
Returns the (cartesian product)[https://en.wikipedia.org/wiki/Cartesianproductof_graphs] of g
and h
Erdos.center
— Methodcenter(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.clean_vertex!
— Methodclean_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
— Functioncommunity_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
— Methodcommunity_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
— Methodcomplement(g)
Produces the graph complement of a graph.
Erdos.complete!
— Methodcomplete!(g::ADiGraph)
For each edge (u, v)
in g
, adds to g
its reverse, i.e. (v, u)
.
Erdos.complete
— Methodcomplete(g::ADiGraph)
Returns a digraph containing both the edges (u, v)
of g
and their reverse (v, u)
. See also complete!
.
Erdos.condensation
— Methodcondensation(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
— Methodconnected_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!
— Methodcontract!(g, vs)
contract!(g, v1, v2, ....)
Merge the vertices in vs
into a unique vertex.
Erdos.core_periphery_deg
— Methodcore_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
— Methodcores(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
— Methodcount_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
— Methodcrosspath(g::AGraph, n::Integer)
Replicate n
times g
and connect each vertex with its copies in a path.
Erdos.degree
— Methoddegree(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
— Methoddensity(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_tree
— Methoddfs_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
— Functiondiameter(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
— Methoddifference(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
— Methoddigraph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
G = Graph)
Build a digraph with n
vertices, type G
, and given edgelist
.
Erdos.digraph
— Methoddigraph(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
— Methoddigraphtype{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
— Functiondijkstra_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.dismantle_ci
— Methoddismantle_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
— Methoddismantle_ci_init(g, l)
Initialization part of dismantle_ci
algorithm. Returns (gnew, heap, lneigs)
.
Erdos.dismantle_ci_oneiter!
— Methoddismantle_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
— Methoddst(e)
Returns the destination of an edge.
Erdos.eccentricities
— Functioneccentricities(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
— Functioneccentricity(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
— Methodedge(g, u, v)
Returns an edge from 'u' to 'v'. The edge doesn't necessarily exists in g
.
Erdos.edge_property
— Methodedge_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)
Returns a dictionary of the form name => val
containing all the properties associated to edge e
.
eprop
is the short form of this function.
Erdos.edgemap2adjlist
— Methodedgemap2adjlist(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
— MethodErdos.edgetype
— Methodedgetype(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
— Methodedit_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.egonet
— Methodegonet(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.enumerate_paths
— Methodenumerate_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!
— FunctionErdos.erdos_renyi
— Methoderdos_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
— Methodeuclidean_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.floyd_warshall_shortest_paths
— Functionfloyd_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.gdistances!
— Methodgdistances!(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
— Methodgdistances(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.global_clustering_coefficient
— Methodglobal_clustering_coefficient(g)
Computes the global clustering coefficient.
Erdos.gprop
— FunctionSee graph_property
Erdos.gprop!
— FunctionErdos.graph
— Methodgraph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
G = Graph)
Build a graph with n
vertices, of type G
, and given edgelist
.
Erdos.graph
— Methodgraph(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
— Methodgraph_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
— Methodgraphtype{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_edge
— Methodhas_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
— Methodhas_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
— FunctionErdos.has_gprop
— FunctionErdos.has_graph_property
— Methodhas_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
— Methodhas_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
— Methodhas_self_loops(g)
Returns true if g
has any self loops.
Erdos.has_vertex
— Methodhas_vertex(g, v)
Return true if v
is a vertex of g
.
Erdos.has_vertex_property
— Methodhas_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
— FunctionErdos.idx
— Methodidx(e::AIndexedEdge)
Returns the index of edge e
.
Erdos.in_degree
— Methodin_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
— Methodin_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
— Methodin_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
— Functionincidence_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.is_bipartite
— Methodis_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
— Methodis_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
— Methodis_directed(g)
Check if g
a graph with directed edges.
Erdos.is_graphical
— Methodis_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
— Methodis_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
— Methodis_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.katz_centrality
— FunctionCalculates the Katz centrality of the graph g
.
Erdos.kcore
— Methodkcore(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.label_propagation
— Methodlabel_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
— Functionlaplacian_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
— Functionlocal_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
— Methodlocal_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
— Functionlocal_clustering_coefficient(g, vlist = vertices(g))
Returns a vector containing the local clustering coefficients for vertices vlist
.
Erdos.local_clustering_coefficient
— Methodlocal_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
— Methodmaximum_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
— Methodmaximum_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
- 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
— Methodminimum_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
— Methodminimum_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
— Methodminimum_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.modularity
— Methodmodularity(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 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)
Erdos.ne
— Methodne(g)
The number of edges in g
.
Time Complexity: O(1)
Erdos.neighborhood
— Functionneighborhood(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
: Ifg
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.neighbors
— Methodneighbors(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
— Methodnonbacktrack_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
— Methodnonbacktracking_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
— Methodnonbacktracking_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
— Methodnum_self_loops(g)
Returns the number of self loops in g
.
Erdos.nv
— Methodnv(g)
The number of vertices in g
.
Erdos.out_degree
— Methodout_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
— Methodout_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
— Methodout_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
— Functionpagerank(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
— Methodperiod(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
— Methodperiphery(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!
— Methodpop_vertex!(g)
Remove the last vertex of g
. Equivalent to rem_vertex!(g, nv(g)).
Erdos.radius
— Functionradius(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_configuration_model
— Methodrandom_configuration_model(n::Int, k::Vector{Int}; seed=-1, check_graphical=false)
Creates a random undirected graph according to the configuraton 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
).
Erdos.random_regular_digraph
— Methodrandom_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
. The default is dir=:out
.
For directed graphs, allocates an $n imes n$ sparse matrix of boolean as an adjacency matrix and uses that to generate the directed graph.
Erdos.random_regular_graph
— Methodrandom_regular_graph(n::Int, k::Int; 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.
Erdos.randomwalk
— Methodrandomwalk(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.readgraph
— Methodreadgraph(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
— Methodreadnetwork(filename, G=Graph)
readnetwork(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
.
readnetwork(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.rebuild!
— Methodrebuild!(g)
Check and restore the structure of g
, which could be corrupted by the use of unsafe functions (e. g. unsafe_add_edge!
)
Erdos.rem_edge!
— Methodrem_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!
— Methodrem_edge_property!(g, name)
Remove the edge property name
from g
.
rem_eprop!
is the short form of this function.
Erdos.rem_eprop!
— FunctionErdos.rem_gprop!
— FunctionErdos.rem_graph_property!
— Methodrem_graph_property!(g, name)
Remove the property name
from g
.
rem_gprop!
is the short form of this function.
Erdos.rem_vertex!
— Methodrem_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!
— Methodrem_vertex_property!(g, name)
Remove the vertex property name
from g
.
rem_vprop!
is the short form of this function.
Erdos.rem_vertices!
— Methodrem_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!
— FunctionErdos.self_avoiding_randomwalk
— Methodself_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!
— Methodset_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.shortest_paths
— Methodshortest_paths(g, x...; kws...)
Computes shortest paths using Dijkstra's algorithm. See dijkstra_shortest_paths
.
Erdos.spectral_distance
— Methodspectral_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.src
— Methodsrc(e)
Returns the source of an edge.
Erdos.static_fitness_model
— Methodstatic_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
— Methodfunction 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|).
function 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
— Methodstochastic_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
— Methodstrongly_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
— Methodsubgraph(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
— Methodsubnetwork(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!
— Methodswap_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
— Methodsymmetric_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
— Methodtensor_product(g, h)
Returns the (tensor product)[https://en.wikipedia.org/wiki/Tensorproductof_graphs] of g
and h
Erdos.topological_sort_by_dfs
— Methodtopological_sort_by_dfs(g)
Return a toplogical sort of a directed graph g
as a vector of vertices in topological order.
Erdos.triangles
— Functiontriangles(g, vlist = vertices(g))
Returns a vector containing the number of triangles for vertices vlist
.
Erdos.triangles
— Methodtriangles(g, v)
Returns the number of triangles in the neighborhood for node v
.
Erdos.unsafe_add_edge!
— Methodunsafe_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
— Methodvertex_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
.
Erdos.vertextype
— Methodvertextype(g)
vertextype(G)
Returns the integer type of vertices of graph g
(or graph type G
).
Erdos.vertices
— Methodvertices(g)
Returns an iterator to the vertices of a graph (i.e. 1:nv(g))
Erdos.vprop
— FunctionSee vertex_property
Erdos.vprop!
— FunctionErdos.watts_strogatz
— Methodwatts_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
— Methodweakly_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
— Methodweights(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.writegraph
— Methodwritegraph(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
— Methodwritenetwork(file, g)
writenetwork(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.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.DefaultCapacity
— TypeType that returns 1 if a forward edge exists, and 0 otherwise
Erdos.NeighComm
— TypeType to record neighbor labels and their counts.
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
— Methodg[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.size
— Methodsize(g,i)
provides 1:nv or 2:nv else 1
Base.sum
— Methodsum(g,i) provides 1:indegree or 2:outdegree vectors
Base.sum
— Methodsum(g)
` provides the number of edges in the graph
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.bfs_parents
— Methodbfs_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.blocking_flow!
— Methodblockingflow! 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
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: 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
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: 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)
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.components
— Methodcomponents(labels)
Given a vector of component labels, return a vector of vectors representing the vertices associated with a given component id.
Erdos.components_dict
— Methodcomponents_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.connected_components!
— Methodconnected_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.dfs_parents
— Methoddfs_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.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: residualgraph::ADiGraph # the input graph source::Int # the source vertex target::Int # the target vertex capacitymatrix::AbstractMatrix{T} # edge flow capacities
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.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.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.fetch_path!
— MethodA 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
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.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.getchild!
— Methodadds a child s
to el
if it doesn't exist
Erdos.has_cycycles
— Methodhas_cycles(g)
Return true
if graph g
contains a cycle.
Implementation Notes
Uses DFS.
Erdos.in_adjlist
— Methodin_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.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.isgraphical
— Methodisgraphical(degs)
Return true if the degree sequence degs
is graphical, according to Erdös-Gallai condition.
Performance
Time complexity: ``\mathcal{O}(|degs|^2)``
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.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.neighborhood_dists
— Methodneighborhood_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
: Ifg
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.out_adjlist
— Methodout_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.poslist
— Methodpl[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.range_shuffle!
— MethodFast shuffle Array a
in UnitRange r
inplace.
Erdos.readpajek
— Methodreadpajek{G}(f::IO, ::Type{G})
Reads a graph from file f
in the Pajek .net format. Returns 1 (number of graphs written).
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.residual_graph
— Methodresidual_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.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: flowgraph::ADiGraph, # the input graph capacitymatrix::AbstractMatrix{T}, # edge flow capacities cut::Vector{Int}, # cut information for vertices restriction::T # value of the restriction
Erdos.tree
— Methodtree(parents)
Convert a parents array into a directed graph.
Erdos.vote!
— MethodReturn the most frequency label.
Erdos.writegml
— Methodwritegml(f, g)
Writes a graph g
to a file f
in the GML format.
Erdos.writepajek
— MethodWrites a graph g
to a file f
in the Pajek .net format. Returns 1 (number of graphs written).
SparseArrays.blockdiag
— Methodblockdiag(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
— Methodsparse(g)
Equivalent to adjacency_matrix
.