Iterators

BFSIterator(graph, source; depth_limit=nothing, neighbors_type=outneighbors)

BFSIterator is used to iterate through graph vertices using a breadth-first search. A source node(s) must be supplied as an Int or an array-like type that can be indexed if supplying multiple sources. It is also possible to specify a depth_limit which will stop the search once all nodes at that depth are visited and a neighbors_type which specifies what kind of neighbors of a node should be considered when exploring the graph.

Examples

julia> g = smallgraph(:house)
{5, 6} undirected simple Int64 graph

julia> for node in BFSIterator(g,3)
           display(node)
       end
3
1
4
5
2

DFSIterator

DFSIterator is used to iterate through graph vertices using a depth-first search. A source node(s) is optionally supplied as an Int or an array-like type that can be indexed if supplying multiple sources.

Examples

julia> g = smallgraph(:house)
{5, 6} undirected simple Int64 graph

julia> for node in DFSIterator(g, 3)
           display(node)
       end
1
2
4
3
5

BFSVertexIteratorState

BFSVertexIteratorState is a struct to hold the current state of iteration in BFS which is needed for the Base.iterate() function. We use two vectors, one for the current level nodes and one from the next level nodes to visit the graph. Since new levels can contains repetitions of already visited nodes, we also keep track of that in a BitVector so as to skip those nodes.

Base.iterate(t::BFSIterator, state::VertexIteratorState)

Iterator to visit vertices in a graph using breadth-first search.

Base.iterate(t::BFSIterator)

First iteration to visit vertices in a graph using breadth-first search.

DFSVertexIteratorState

DFSVertexIteratorState is a struct to hold the current state of iteration in DFS which is needed for the Base.iterate() function. A queue is used to keep track of the vertices which will be visited during DFS. Since the queue can contains repetitions of already visited nodes, we also keep track of that in a BitVector so that to skip those nodes.

Base.iterate(t::DFSIterator, state::VertexIteratorState)

Iterator to visit vertices in a graph using depth-first search.

Base.iterate(t::DFSIterator)

First iteration to visit vertices in a graph using depth-first search.