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, and
MaximumAdjacency.

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

GitHub « Previous Next »