DAG
Trait to model the behavior of directed acyclic graph.
Type parameters
- E
-
the edge-attribute type.
- V
-
the (key) vertex-attribute type.
Attributes
- Graph
-
- Supertypes
-
trait Serializabletrait Producttrait Equalsclass AbstractGraph[V]trait Graph[V]trait Traversable[V]class Objecttrait Matchableclass AnyShow all
Members list
Value members
Concrete methods
Inherited methods
Computes and returns the total number of edges in the directed graph.
Computes and returns the total number of edges in the directed graph.
Attributes
- Returns
-
the number of directed edges present in the graph.
- Definition Classes
- Inherited from:
- DirectedGraph
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:
- AbstractGraph
Delegates to VertexMap.+[E], which calls ensure for both endpoints. This ensures the destination vertex exists in the map even if it has no outgoing edges — fixing Issue #16. This is consistent with UndirectedGraph.addEdge which also delegates to VertexMap.+[E].
Delegates to VertexMap.+[E], which calls ensure for both endpoints. This ensures the destination vertex exists in the map even if it has no outgoing edges — fixing Issue #16. This is consistent with UndirectedGraph.addEdge which also delegates to VertexMap.+[E].
Attributes
- Definition Classes
- Inherited from:
- DirectedGraph
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
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. - Inherited from:
- AbstractGraph
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.
- Inherited from:
- AbstractGraph
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
Retrieves all edges in the directed graph as an iterable collection of edges.
Retrieves all edges in the directed graph as an iterable collection of edges.
Attributes
- Returns
-
an iterable collection containing all edges of type
Edge[V, E]in the graph. - Inherited from:
- DirectedGraph
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:
- AbstractGraph
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 vertex associated with the given key.
Retrieves the vertex associated with the given key.
Value parameters
- key
-
the vertex attribute to look up.
Attributes
- Returns
-
Some(vertex)if found,Noneotherwise. - Inherited from:
- AbstractGraph
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
Not yet implemented for directed graphs.
Not yet implemented for directed graphs. For directed graphs, connectivity has two distinct notions: weak (treating edges as undirected) and strong (every vertex reachable from every other via directed paths). Use ConnectedComponents for undirected connectivity or Kosaraju for strongly connected components.
Not yet implemented for directed graphs. For directed graphs, connectivity has two distinct notions: weak (treating edges as undirected) and strong (every vertex reachable from every other via directed paths). Use ConnectedComponents for undirected connectivity or Kosaraju for strongly connected components.
Attributes
- Inherited from:
- DirectedGraph
Checks whether the directed graph contains a cycle.
Checks whether the directed graph contains a cycle.
This method determines if the graph is cyclic by attempting to perform a topological sort. A graph is cyclic if and only if a topological order cannot be established.
Attributes
- Returns
-
true if the graph is cyclic, false otherwise.
- Inherited from:
- DirectedGraph
Returns the number of self-loops in the graph (edges where both endpoints are the same vertex).
Returns the number of self-loops in the graph (edges where both endpoints are the same vertex).
Attributes
- Inherited from:
- EdgeGraph
An iterator over the names of all the elements of this product.
An iterator over the names of all the elements of this product.
Attributes
- Inherited from:
- Product
An iterator over all the elements of this product.
An iterator over all the elements of this product.
Attributes
- Returns
-
in the default implementation, an
Iterator[Any] - Inherited from:
- Product
Returns a new DirectedGraph with all edges reversed (every u→v becomes v→u). The vertex set is preserved, including any vertices with no outgoing edges.
Returns a new DirectedGraph with all edges reversed (every u→v becomes v→u). The vertex set is preserved, including any vertices with no outgoing edges.
This is the first step in Kosaraju's strongly-connected-components algorithm.
Attributes
- Returns
-
a new
DirectedGraph[V, E]with reversed edges. - Inherited from:
- DirectedGraph
Computes shortest paths from start using Bellman-Ford-Moore. Returns None if a negative cycle is reachable from start.
Computes shortest paths from start using Bellman-Ford-Moore. Returns None if a negative cycle is reachable from start.
Attributes
- Inherited from:
- DirectedGraph
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
Creates a new directed graph using the provided vertex map.
Creates a new directed graph using the provided vertex map.
Value parameters
- vertexMap
-
the vertex map to be used for constructing the graph. It defines the vertices and their adjacencies in the graph.
Attributes
- Returns
-
a new directed graph constructed with the given vertex map.
- Inherited from:
- DirectedGraph
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