Traversable
Trait to define the behavior of a graph-like structure which can be traversed by dfs, dfsAll, and bfs.
The traversal engine is provided by Visitor V1.2.0. The mutable discovered flag pattern has been replaced by the immutable VisitedSet[V] typeclass. Callers continue to pass a Visitor in and receive an updated Visitor back; the new typeclass machinery is an implementation detail.
Type parameters
- V
-
the underlying key (attribute) type for a vertex.
Attributes
- Graph
-
- Supertypes
-
class Objecttrait Matchableclass Any
- Known subtypes
Members list
Value members
Abstract methods
Returns the number of edges in the graph.
Returns the number of edges in the graph.
Attributes
- Returns
-
the number of edges in the graph.
Returns the number of vertices in the graph.
Returns the number of vertices in the graph.
Attributes
- Returns
-
the number of vertices in the graph.
Retrieves the adjacent vertices connected to the specified vertex.
Retrieves the adjacent vertices connected to the specified vertex.
Value parameters
- v
-
the vertex whose adjacent vertices are to be returned.
Attributes
- Returns
-
an iterator over the vertices adjacent to the specified vertex.
Performs a breadth-first search (BFS) traversal starting from the specified vertex.
Performs a breadth-first search (BFS) traversal starting from the specified vertex.
Type parameters
- J
-
the journal type.
- R
-
the result type extracted from each node.
Value parameters
- goal
-
an optional early-termination predicate; traversal halts after recording the first node for which
goalreturns true. - v
-
the starting vertex.
- visitor
-
the visitor, accumulating results into its journal.
Attributes
- Returns
-
the updated visitor after traversal.
Performs a BFS traversal visiting edges rather than vertices, starting from v. Traversal stops when goal returns true for a destination vertex.
Performs a BFS traversal visiting edges rather than vertices, starting from v. Traversal stops when goal returns true for a destination vertex.
Type parameters
- E
-
the type of the edge attribute.
- J
-
the journal type.
- R
-
the result type.
Value parameters
- goal
-
early-termination predicate on destination vertices.
- v
-
the starting vertex.
- visitor
-
the visitor responsible for processing edges.
Attributes
- Returns
-
the visitor after traversal.
Performs a depth-first search (DFS) traversal starting from the specified vertex.
Performs a depth-first search (DFS) traversal starting from the specified vertex.
Internally uses Traversal.dfs from Visitor V1.2.0. A given GraphNeighbours[V] is derived from adjacentVertices and a given Evaluable[V, R] must be in scope at the call site (or provided implicitly by the implementation).
Type parameters
- J
-
the journal type.
- R
-
the result type extracted from each node by
Evaluable.
Value parameters
- v
-
the starting vertex.
- visitor
-
the visitor, accumulating results into its journal.
Attributes
- Returns
-
the updated visitor after traversal.
Performs a DFS traversal for all vertices in the graph using the supplied visitor. Vertices not reachable from the first traversal are visited in subsequent passes.
Performs a DFS traversal for all vertices in the graph using the supplied visitor. Vertices not reachable from the first traversal are visited in subsequent passes.
Type parameters
- J
-
the journal type.
- R
-
the result type extracted from each node.
Value parameters
- visitor
-
the visitor, accumulating results into its journal.
Attributes
- Returns
-
the updated visitor after traversing all vertices.
Filters the adjacencies of a given vertex based on a specified predicate.
Filters the adjacencies of a given vertex based on a specified predicate.
Value parameters
- predicate
-
a function that evaluates each
Adjacency[V]and returns true if the adjacency satisfies the specified condition. - v
-
the vertex whose adjacencies are to be filtered.
Attributes
- Returns
-
an iterator over the adjacencies of the given vertex that satisfy the predicate.
Retrieves the vertex associated with the given key.
Retrieves the vertex associated with the given key.
Value parameters
- key
-
the key of type V for which the associated vertex is to be retrieved.
Attributes
- Returns
-
an Option containing the associated Vertex if found, or None if not.
Concrete methods
Filters the adjacent vertices of a given vertex based on a specified predicate.
Filters the adjacent vertices of a given vertex based on a specified predicate.
Value parameters
- predicate
-
a function that evaluates each adjacent vertex and returns true if the vertex satisfies the specified condition.
- v
-
the vertex whose adjacent vertices are to be filtered.
Attributes
- Returns
-
an iterator over the vertices that are adjacent to v and satisfy the predicate.
Retrieves the connexions (edges) reachable from start via DFS.
Retrieves the connexions (edges) reachable from start via DFS.
Type parameters
- E
-
the type of the edges in the graph.
Value parameters
- start
-
the starting vertex.
Attributes
- Returns
-
a
Connexions[V, E]object representing the discovered connexions.
Derives a GraphNeighbours[V] instance from adjacentVertices. Used internally by the default implementations of vertexMappedTraversalDfs, vertexMappedTraversalBfs, and getConnexions.
Derives a GraphNeighbours[V] instance from adjacentVertices. Used internally by the default implementations of vertexMappedTraversalDfs, vertexMappedTraversalBfs, and getConnexions.
CONSIDER making this protected again but that requires multiple instances in each type of Traversal.
NOTE: do not be tempted to add a default Random implementation for this context. We need to enforce consistency of Random instances.
Attributes
Performs a BFS traversal applying fulfill to each visited vertex and returns a VertexTraversalResult mapping each vertex to its result.
Performs a BFS traversal applying fulfill to each visited vertex and returns a VertexTraversalResult mapping each vertex to its result.
Type parameters
- T
-
the result type produced by
fulfill.
Value parameters
- fulfill
-
transformation function applied to each vertex.
- start
-
the starting vertex.
Attributes
- Returns
-
Try[TraversalResult[V, T]]containing the traversal result or a failure.
Performs a DFS traversal applying fulfill to each visited vertex and returns a VertexTraversalResult mapping each vertex to its result.
Performs a DFS traversal applying fulfill to each visited vertex and returns a VertexTraversalResult mapping each vertex to its result.
Type parameters
- T
-
the result type produced by
fulfill.
Value parameters
- fulfill
-
transformation function applied to each vertex.
- start
-
the starting vertex.
Attributes
- Returns
-
Try[TraversalResult[V, T]]containing the traversal result or a failure.