A trait representing an abstract graph structure composed of vertices.
All traversal methods delegate to the VertexMap which in turn uses the Visitor V1.2.0 typeclass engine (Traversal.dfs / Traversal.bfs). The mutable discovered flag pattern has been removed throughout; visited-node tracking is handled by the immutable VisitedSet[V] inside the engine.
Type parameters
- V
-
the type representing the vertex attributes (invariant).
Attributes
- Companion
- object
- Graph
-
- Supertypes
- Known subtypes
-
class AbstractGraph[V]
Members list
Value members
Abstract methods
Returns true if this graph is bipartite (2-colorable).
Returns true if this graph is bipartite (2-colorable).
For undirected graphs: true iff the graph contains no odd-length cycle. For directed graphs: not yet implemented — throws UnsupportedOperationException.
Attributes
Returns true if this graph is connected.
Returns true if this graph is connected.
For undirected graphs: true iff every vertex is reachable from every other. For directed graphs: semantics (strong vs weak connectivity) are implementation-defined and not yet supported — throws UnsupportedOperationException.
Attributes
Determines if the graph contains any cycles.
Determines if the graph contains any cycles.
Attributes
- Returns
-
true if the graph has at least one cycle, false otherwise.
Creates a new graph using the provided vertex map.
Creates a new graph using the provided vertex map.
Value parameters
- vertexMap
-
the vertex map for the new graph.
Attributes
- Returns
-
a new graph instance.
Concrete methods
Adds a new vertex to the graph, returning a new graph instance.
Adds a new vertex to the graph, returning a new graph instance.
Value parameters
- vertex
-
the vertex to be added.
Attributes
- Returns
-
a new graph containing the added vertex.
Performs BFS from v, accumulating results into visitor.
Performs BFS from v, accumulating results into visitor.
Type parameters
- J
-
the journal type.
- R
-
the result type.
Value parameters
- goal
-
early-termination predicate (default: never stop early).
- v
-
the starting vertex.
- visitor
-
the visitor accumulating results.
Attributes
- Returns
-
the updated visitor after traversal.
BFS over edges rather than vertices.
BFS over edges rather than vertices.
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 processing edges.
Attributes
- Returns
-
the visitor after traversal.
Performs DFS from v, accumulating results into visitor.
Performs DFS from v, accumulating results into visitor.
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.
Attributes
- Returns
-
the updated visitor after traversal.
Performs DFS for all vertices in the graph, including those unreachable from any single start vertex.
Performs DFS for all vertices in the graph, including those unreachable from any single start vertex.
Type parameters
- J
-
the journal type.
- R
-
the result type.
Value parameters
- visitor
-
the visitor accumulating results.
Attributes
- Returns
-
the updated visitor after traversing all vertices.
Returns the directed edges reachable from v.
Returns the directed edges reachable from v.
Attributes
Returns the vertices reachable via attributed directed edges from v. Useful for testing and inspection; the traversal engine manages visited state internally via VisitedSet.
Returns the vertices reachable via attributed directed edges from v. Useful for testing and inspection; the traversal engine manages visited state internally via VisitedSet.
Attributes
Inherited 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.
- Inherited from:
- Traversable
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. - Inherited from:
- Traversable
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
- Inherited from:
- Traversable
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. - Inherited from:
- Traversable
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. - Inherited from:
- Traversable
Inherited and 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.
- Inherited from:
- Traversable
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.
- Inherited from:
- Traversable
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.
- Inherited from:
- Traversable
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.
- Inherited from:
- Traversable
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.
- Inherited from:
- Traversable