Path and Traversal
Erdos.jl provides several traversal and shortest-path algorithms, along with various utility functions. Where appropriate, edge distances may be passed in as a matrix of real number values.
Edge distances for most traversals may be passed in as a sparse or dense matrix of values, indexed by [src,dst]
vertices. That is, distmx[2,4] = 2.5
assigns the distance 2.5
to the (directed) edge connecting vertex 2 and vertex 4. Note that also for undirected graphs distmx[4,2]
has to be set.
Any graph traversal will traverse an edge only if it is present in the graph. When a distance matrix is passed in,
- distance values for undefined edges will be ignored, and
- any unassigned values (in sparse distance matrices), for edges that are present in the graph, will be assumed to take the default value of 1.0.
- any zero values (in sparse/dense distance matrices), for edges that are present in the graph, will instead have an implicit edge cost of 1.0.
Graph Traversal
Graph traversal refers to a process that traverses vertices of a graph following certain order (starting from user-input sources). This package implements three traversal schemes:
BreadthFirst
,DepthFirst
, andMaximumAdjacency
.
#
Erdos.BreadthFirst
— Type.
Conventions in Breadth First Search and Depth First Search VertexColorMap :
- color == 0 => unseen
- color < 0 => examined but not closed
- color > 0 => examined and closed
EdgeColorMap :
- color == 0 => unseen
- color == 1 => examined
#
Erdos.bfs_tree
— Method.
bfs_tree(g, s)
Provides a breadth-first traversal of the graph g
starting with source vertex s
, and returns a directed acyclic graph of vertices in the order they were discovered.
#
Erdos.bipartite_map
— Method.
bipartite_map(g)
If the graph is bipartite returns a vector c
of size nv(g)
containing the assignment of each vertex to one of the two sets (c[i] == 1
or c[i]==2
). If g
is not bipartite returns an empty vector.
#
Erdos.gdistances!
— Method.
gdistances!(g, source, dists) -> dists
Fills dists
with the geodesic distances of vertices in g
from vertex/vertices source
. dists
can be either a vector or a dictionary.
#
Erdos.gdistances
— Method.
gdistances(g, source) -> dists
Returns a vector filled with the geodesic distances of vertices in g
from vertex/vertices source
. For vertices in disconnected components the default distance is -1.
#
Erdos.is_bipartite
— Method.
is_bipartite(g)
is_bipartite(g, v)
Will return true
if graph g
is bipartite. If a node v
is specified, only the connected component to which it belongs is considered.
#
Erdos.DepthFirst
— Type.
Conventions in Breadth First Search and Depth First Search VertexColorMap :
- color == 0 => unseen
- color < 0 => examined but not closed
- color > 0 => examined and closed
EdgeColorMap :
- color == 0 => unseen
- color == 1 => examined
#
Erdos.dfs_tree
— Method.
dfs_tree(g, s)
Provides a depth-first traversal of the graph g
starting with source vertex s
, and returns a directed acyclic graph of vertices in the order they were discovered.
#
Erdos.has_cycles
— Method.
has_cycles(g)
Tests whether a graph contains a simple cycle through depth-first search. See also is_tree
.
#
Erdos.is_tree
— Method.
is_tree(g)
Check whether g
is a tree. Return false
whenever has_cycles
returns true
and viceversa.
#
Erdos.maximum_adjacency_visit
— Function.
maximum_adjacency_visit(
g,
distmx::AEdgeMap=ConstEdgeMap(g,1);
log::Bool=false,
io::IO=STDOUT
)
Returns the vertices in g
traversed by maximum adjacency search. An optional distmx
edge map 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.minimum_cut
— Method.
minimum_cut(g, dist_edge map=ConstEdgeMap(g,1))
Finds the cut
of minimum total weight.
Returns a tuple (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. An optional dist_matrix
edge map maybe specified; if omitted, edge distances are assumed to be 1.
Random walks
Erdos includes uniform random walks and self avoiding walks:
#
Erdos.nonbacktracking_randomwalk
— Method.
nonbacktracking_randomwalk(g, s, niter)
Performs a non-backtracking random walk on graph g
starting at vertex s
and continuing for a maximum of niter
steps. Returns a vector of vertices visited in order.
#
Erdos.randomwalk
— Method.
randomwalk(g, s, niter)
Performs a random walk on graph g
starting at vertex s
and continuing for a maximum of niter
steps. Returns a vector of vertices visited in order.
#
Erdos.self_avoiding_randomwalk
— Method.
self_avoiding_randomwalk(g, s, niter)
Performs a self-avoiding walk on graph g
starting at vertex s
and continuing for a maximum of niter
steps. Returns a vector of vertices visited in order.
Connectivity / Bipartiteness
Graph connectivity
functions are defined on both undirected and directed graphs:
#
Erdos.attracting_components
— Method.
attracting_components(g::ADiGraph)
Returns a vector of vectors of integers representing lists of attracting components in g
. The attracting components are a subset of the strongly connected components in which the components do not have any leaving edges.
#
Erdos.condensation
— Method.
condensation(g::ADiGraph)
Returns the condensation graph associated with g
. The condensation h
of a graph g
is the directed graph where every node in h
represents a strongly connected component in g
, and the presence of an edge between between nodes in h
indicates that there is at least one edge between the associated strongly connected components in g
. The node numbering in h
corresponds to the ordering of the components output from strongly_connected_components
.
#
Erdos.connected_components
— Method.
connected_components(g::AGraph)
Returns the connected components of g
as a vector of components, each represented by a vector of vertices belonging to the component.
See also weakly_connected_components
and strongly_connected_components
for directed graphs.
#
Erdos.is_connected
— Method.
is_connected(g)
Returns true
if g
is connected. For DiGraphs, this is equivalent to a test of weak connectivity.
#
Erdos.is_strongly_connected
— Method.
is_strongly_connected(g::ADiGraph)
Returns true
if g
is strongly connected.
See also strongly_connected_components
#
Erdos.is_weakly_connected
— Method.
is_weakly_connected(g::ADiGraph)
Returns true
if the undirected graph g
is weakly connected.
See also weakly_connected_components
.
#
Erdos.neighborhood
— Method.
neighborhood(g, v, d; dir=:out)
Returns a vector of the vertices in g
at distance less or equal to d
from v
. 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.
#
Erdos.period
— Method.
period(g::ADiGraph)
Computes the common period for all nodes in a strongly connected graph.
#
Erdos.strongly_connected_components
— Method.
strongly_connected_components(g::ADiGraph)
Computes the strongly connected components of a directed graph.
#
Erdos.weakly_connected_components
— Method.
weakly_connected_components(g::ADiGraph)
Returns the weakly connected components of undirected graph g
. It is equivalent to the connected components of the corresponding undirected graph, i.e. connected_components(graph(g))
.