Represents a directed graph structure that supports operations on vertexMap and edges. This class is a concrete implementation of the EdgeGraph trait, and models directed relationships between vertices with edges.
Type parameters
- E
-
the type of attributes for the edges in the graph (invariant).
- V
-
the type of attributes for the vertexMap in the graph (invariant).
Value parameters
- vertexMap
-
the
VertexMapthat represents thisGraph.
Attributes
- Companion
- object
- 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
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.
- Definition Classes
Adds an edge to the directed graph, creating or updating the vertices and their adjacencies accordingly. The edge is connected between its from and black vertices.
Adds an edge to the directed graph, creating or updating the vertices and their adjacencies accordingly. The edge is connected between its from and black vertices.
CONSIDER eliminating this method.
Value parameters
- edge
-
the edge to be added to the graph. It contains a starting vertex (
from), an ending vertex (black), and an associated attribute that defines the edge.
Attributes
- Returns
-
a new instance of the graph that includes the specified edge and updated vertices.
Returns the degree of vertex v — the number of edges incident to it.
Returns the degree of vertex v — the number of edges incident to it.
Attributes
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.
Returns true if this undirected graph is bipartite — i.e. its vertices can be partitioned into two sets such that every edge connects vertices in different sets. Equivalently, the graph contains no odd-length cycle.
Returns true if this undirected graph is bipartite — i.e. its vertices can be partitioned into two sets such that every edge connects vertices in different sets. Equivalently, the graph contains no odd-length cycle.
Uses DFS with 2-coloring. Handles disconnected graphs by seeding each unvisited component in turn.
Attributes
Returns true if this undirected graph is connected — i.e. every vertex is reachable from every other via some path.
Returns true if this undirected graph is connected — i.e. every vertex is reachable from every other via some path.
Performs a single DFS from an arbitrary start vertex and checks whether all N vertices were visited.
Attributes
Determines whether the graph contains a cycle using DFS to detect is we encounter a previously visited vertex.
Determines whether the graph contains a cycle using DFS to detect is we encounter a previously visited vertex.
Attributes
- Returns
-
true if the graph is cyclic (i.e., it contains at least one cycle), false otherwise.
Returns the maximum degree of any vertex in the graph.
Returns the maximum degree of any vertex in the graph.
Attributes
Returns the mean degree across all vertices in the graph.
Returns the mean degree across all vertices in the graph.
Attributes
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 methods
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
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
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
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 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