AbstractGraph
An abstract base class for graph implementations backed by a VertexMap.
Type parameters
- V
-
the type of the vertex attributes (invariant).
Value parameters
- vertexMap
-
the
VertexMapholding the vertices of this graph.
Attributes
- Graph
-
- Supertypes
- Known subtypes
Members list
Value members
Concrete 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 an iterator over all adjacencies in the graph.
Retrieves an iterator over all adjacencies in the graph.
Attributes
- Returns
-
an iterator of
Adjacency[V]across all vertices.
Returns an iterator over the vertices adjacent to v.
Returns an iterator over the vertices adjacent to v.
Value parameters
- v
-
the vertex to query.
Attributes
- Returns
-
an iterator of adjacent vertex attributes.
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 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.
- Inherited from:
- Graph
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.
- Inherited from:
- Graph
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.
- Inherited from:
- Graph
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.
- Inherited from:
- Graph
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.
- Inherited from:
- Graph
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
Returns the directed edges reachable from v.
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 from:
- Graph
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 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
- Inherited from:
- Graph
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
- Inherited from:
- Graph
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.
- Inherited from:
- Graph