class DiGraph[T] extends AnyRef
Represents common behavior of all directed graphs
- Source
- DiGraph.scala
- Alphabetic
- By Inheritance
- DiGraph
- AnyRef
- Any
- by any2stringadd
- by StringFormat
- by Ensuring
- by ArrowAssoc
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new DiGraph(edges: LinkedHashMap[T, LinkedHashSet[T]])
Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- def +(that: DiGraph[T]): DiGraph[T]
Graph sum of
this
andthat
Graph sum of
this
andthat
- that
a second DiGraph[T]
- returns
a DiGraph[T] containing all vertices and edges of each graph
- def ->[B](y: B): (DiGraph[T], B)
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- def BFS(root: T, blacklist: Set[T]): Map[T, T]
Performs breadth-first search on the directed graph, with a blacklist of nodes
Performs breadth-first search on the directed graph, with a blacklist of nodes
- root
the start node
- blacklist
list of nodes to avoid visiting, if encountered
- returns
a Map[T,T] from each visited node to its predecessor in the traversal
- def BFS(root: T): Map[T, T]
Performs breadth-first search on the directed graph
Performs breadth-first search on the directed graph
- root
the start node
- returns
a Map[T,T] from each visited node to its predecessor in the traversal
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native()
- def contains(v: T): Boolean
Check whether the graph contains vertex v
- def ensuring(cond: (DiGraph[T]) => Boolean, msg: => Any): DiGraph[T]
- def ensuring(cond: (DiGraph[T]) => Boolean): DiGraph[T]
- def ensuring(cond: Boolean, msg: => Any): DiGraph[T]
- def ensuring(cond: Boolean): DiGraph[T]
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable])
- def findLoopAtNode(node: T): Seq[T]
Finds a Seq of Nodes that form a loop
Finds a Seq of Nodes that form a loop
- node
Node to start loop path search from.
- returns
The found Seq, the Seq is empty if there is no loop
- def findSCCs: Seq[Seq[T]]
Finds the strongly connected components in the graph
Finds the strongly connected components in the graph
- returns
a Seq of Seq[T], each containing nodes of an SCC in traversable order
- def findSinks: Set[T]
Find all sinks in the graph
Find all sinks in the graph
- returns
a Set[T] of sink nodes
- def findSources: Set[T]
Find all sources in the graph
Find all sources in the graph
- returns
a Set[T] of source nodes
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- def getEdgeMap: Map[T, Set[T]]
- def getEdges(v: T): Set[T]
Get all edges of a node
Get all edges of a node
- v
the specified node
- returns
a Set[T] of all vertices that v has edges to
- def getVertices: Set[T]
Get all vertices in the graph
Get all vertices in the graph
- returns
a Set[T] of all vertices in the graph
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- def linearize: Seq[T]
Linearizes (topologically sorts) a DAG
Linearizes (topologically sorts) a DAG
- returns
a Seq[T] describing the topological order of the DAG traversal
- Exceptions thrown
CyclicException
if the graph is cyclic
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- def path(start: T, end: T, blacklist: Set[T]): Seq[T]
Finds a path (if one exists) from one node to another, with a blacklist
Finds a path (if one exists) from one node to another, with a blacklist
- start
the start node
- end
the destination node
- blacklist
list of nodes which break path, if encountered
- returns
a Seq[T] of nodes defining an arbitrary valid path
- Exceptions thrown
- def path(start: T, end: T): Seq[T]
Finds a path (if one exists) from one node to another
Finds a path (if one exists) from one node to another
- start
the start node
- end
the destination node
- returns
a Seq[T] of nodes defining an arbitrary valid path
- Exceptions thrown
- def pathsInDAG(start: T): LinkedHashMap[T, Seq[Seq[T]]]
Finds all paths starting at a particular node in a DAG
Finds all paths starting at a particular node in a DAG
WARNING: This is an exponential time algorithm (as any algorithm must be for this problem), but is useful for flattening circuit graph hierarchies. Each path is represented by a Seq[T] of nodes in a traversable order.
- start
the node to start at
- returns
a Map[T,Seq[Seq[T]]] where the value associated with v is the Seq of all paths from start to v
- def prettyTree(charSet: CharSet = PrettyCharSet)(implicit ev: =:=[T, String]): String
Serializes a
DiGraph[String]
as a pretty treeSerializes a
DiGraph[String]
as a pretty treeMultiple roots are supported, but cycles are not.
- def reachableFrom(root: T, blacklist: Set[T]): LinkedHashSet[T]
Finds the set of nodes reachable from a particular node, with a blacklist.
Finds the set of nodes reachable from a particular node, with a blacklist. The semantics of adding a node to the blacklist is that any of its inedges will be ignored in the traversal. The
root
node is *not* included in the returned set unless it is possible to reachroot
along a non-trivial path beginning atroot
; i.e., if the graph has a cycle that containsroot
.- root
the start node
- blacklist
list of nodes to stop searching, if encountered
- returns
a Set[T] of nodes reachable from
root
- def reachableFrom(root: T): LinkedHashSet[T]
Finds the set of nodes reachable from a particular node.
Finds the set of nodes reachable from a particular node. The
root
node is *not* included in the returned set unless it is possible to reachroot
along a non-trivial path beginning atroot
; i.e., if the graph has a cycle that containsroot
.- root
the start node
- returns
a Set[T] of nodes reachable from
root
- def reverse: DiGraph[T]
Returns a graph with all edges reversed
- def simplify(vprime: Set[T]): DiGraph[T]
Return a simplified connectivity graph with only a subset of the nodes
Return a simplified connectivity graph with only a subset of the nodes
Any path between two non-deleted nodes (u,v) in the original graph will be transformed into an edge (u,v).
- vprime
the Set[T] of desired vertices
- returns
the simplified graph
- Exceptions thrown
java.lang.IllegalArgumentException
if vprime is not a subset of V
- def subgraph(vprime: Set[T]): DiGraph[T]
Return a graph with only a subset of the nodes
Return a graph with only a subset of the nodes
Any edge including a deleted node will be deleted
- vprime
the Set[T] of desired vertices
- returns
the subgraph
- Exceptions thrown
java.lang.IllegalArgumentException
if vprime is not a subset of V
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- def transformNodes[Q](f: (T) => Q): DiGraph[Q]
Return a graph with all the nodes of the current graph transformed by a function.
Return a graph with all the nodes of the current graph transformed by a function. Edge connectivity will be the same as the current graph.
- f
A function {(T) => Q} that transforms each node
- returns
a transformed DiGraph[Q]
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
Shadowed Implicit Value Members
- def +(other: String): String
- Implicit
- This member is added by an implicit conversion from DiGraph[T] toany2stringadd[DiGraph[T]] performed by method any2stringadd in scala.Predef.
- Shadowing
- This implicitly inherited member is shadowed by one or more members in this class.
To access this member you can use a type ascription:(diGraph: any2stringadd[DiGraph[T]]).+(other)
- Definition Classes
- any2stringadd
Deprecated Value Members
- def formatted(fmtstr: String): String
- Implicit
- This member is added by an implicit conversion from DiGraph[T] toStringFormat[DiGraph[T]] performed by method StringFormat in scala.Predef.
- Definition Classes
- StringFormat
- Annotations
- @deprecated @inline()
- Deprecated
(Since version 2.12.16) Use
formatString.format(value)
instead ofvalue.formatted(formatString)
, or use thef""
string interpolator. In Java 15 and later,formatted
resolves to the new method in String which has reversed parameters.
- def →[B](y: B): (DiGraph[T], B)
- Implicit
- This member is added by an implicit conversion from DiGraph[T] toArrowAssoc[DiGraph[T]] performed by method ArrowAssoc in scala.Predef.
- Definition Classes
- ArrowAssoc
- Annotations
- @deprecated
- Deprecated
(Since version 2.13.0) Use
->
instead. If you still wish to display it as one character, consider using a font with programming ligatures such as Fira Code.