val g = Graph(2~3, 3~1) g mkString "," // "1,2,3,2~3,3~1" g.nodes mkString "-" // "1-2-3" g.edges mkString " " // "2~3 3~1"
As to
Graph
instance you get all nodes
and all edges. Graph
extends Set[GraphParam]
.
GraphParam
is an algebraic type for outer nodes, outer edges,
inner nodes and inner edges.
nodes
returns the node set which in turn is an instance of
Set[NodeT]
.
edges
returns the edge set which in turn is an instance of
Set[EdgeT]
.
Both Graph
and its inner classes NodeSet
and
EdgeSet
extend scala.collection.Set
.
Thus, you can call the gamut of well-known TraversableLike
methods
on these such as filter
, foreach
etc.
val g = Graph(1~2) g find 1 // Option[g.NodeT] = Some(1) g find 3 // Option[g.NodeT] = None g get 1 // g.NodeT = 1 g get 3 // NoSuchElementException g find 1 ~ 2 // Option[g.EdgeT] = Some(1~2) g find (g having (node = _.toOuter == 1)) // g.NodeT = 1 val h = mutable.Graph.empty[Int,UnDiEdge] ++ g g addAndGet 5 // g.NodeT = 5
As to
1
.
1
.
Call get
with caution. It is ok in test code if you know that the node exists.
3
.
1 ~ 2
. Looking up edges works in the same manner as for nodes.
_ == 1
. having
may take a node
and/or an edge
argument.
g
.
Graph
, adds 5
to the node set and returns the new inner node. This method
couples adding and getting the same node.
Looking up nodes and edges is necessary to invoke graph functionality at a specific
element of the graph. With respect to an operation we also call an inner node the "root node".
Looking up is similar to getting a value of a Map
entry by passing a key to the map.
In case of Graph
the "key" is an outer node or edge and the returned
"value" is the inner node or edge.
Look up is implemented in terms of hashCode
and ==
.
val g = Graph(1~2) (g get 1) == 1 // true (g get 1 ~ 2) == 2 ~ 1 // true (g get 1 ~ 2) eq 2 ~ 1 // false (g get 1 ~ 2) == 2 ~ 2 // false
As to
1
equals to the outer node 1
.
1 ~ 2
equals to the outer edge 2 ~ 1
.
This example also demonstrates, that in case of undirected edges the
order of nodes does not influence equality.
eq
fails, because an inner edge can never be the
same instance as an outer edge.1~2
does not equal to 2 ~ 2
.
val g = Graph(1, 2~3) // immutable or mutable g + 1 // g unchanged g + 0 // Graph(0, 1, 2, 3, 2 ~ 3) g + 1.2 // error: overloaded method... g + 0~1 // Graph(0, 1, 2, 3, 0 ~ 1, 2 ~ 3) g ++ List(1~2, 2~3) // Graph(1, 2, 3, 1 ~ 2, 2 ~ 3) g ++ List[Param[Int,UnDiEdge]](1~2, 2~3, 0) // Graph(0, 1, 2, 3, 1 ~ 2, 2 ~ 3) g - 0 // g g - 1 // Graph(2, 3, 2 ~ 3) g - 2 // Graph(1, 3) g -? 2 // g g - 2~3 // Graph(1, 2, 3) g -! 2~3 // Graph(1) g -- List[Param[Int,UnDiEdge]](2, 3 ~ 3) // Graph(1, 3) def h = mutable.Graph.empty[Int,UnDiEdge] ++ g h += 0 // Graph(0, 1, 2, 3, 2 ~ 3) h += (3 ~> 1) // Graph(1, 2, 3, 2 ~ 3, 3 ~> 1) implicit val factory = scalax.collection.edge.LDiEdge h.addLEdge(3,4)("red") // true
As to
1
is not added because it is already
contained, so the same instance is returned.
Graph
instance.
Double
is incompatible with Int
so
the compiler will issue an error.0~1
is added to a new Graph
instance.
Graph
instance.
Graph
instance.
0
is not removed because it is not
contained, so the same instance is returned.
1
is removed from a new Graph
instance. This node was not incident with any edge.
2
along with 2~3
is ripple removed
from a new Graph
instance. Node 2
was incident
with 2~3
.
2
is not removed because this gentle removal
succeeds only if the node is not incident with any edge.
2~3
is removed from a new Graph
instance
leaving its incident nodes in place.
2~3
along with its incident nodes 2
and
3
is removed from a new Graph
instance.
Incident nodes will only be removed if they are not incident with
any other edge.
Graph
instance.
Graph
equaling to g
.
addLEdge
(same as +~+=
) adds a
labeled edge to a mutable graph passing the connected nodes and the label.
This kind of method has an implicit
edge factory parameter.
The Graph
operators +
, +=
for adding
and -
, -=
for subtracting may have an inner or outer
node or edge at the right hand side.
Graph for Scala guarantees a consistent state of the node and
edge sets after any operation including duplicate node/edge prevention
as demonstrated on line 5.
Both ripple and gentle removal schemas are supported.
Using the standard operators -
and -=
, removals comply
with the definition of node and edge removal in graph theory:
ripple removal of nodes as on the lines 9 to 11 and
gentle removal of edges as on line 13.
In addition, gentle removal of nodes by -?
and
-?=
as on line 12 as well as ripple removal of edges by
-!
and -!=
as on line 13 are also supported.
It is also possible to add elements to or subtract elements from node and edge sets. However, these operations have less practical relevance as the result is always a decoupled immutable set.
In case of mutable graphs, two kinds of edge addition are supported:
+=
requiring an instance of EdgeLike
at the right hand side
–
see example d).
add*
methods or the corresponding operators having the incident nodes and
optionally an edge weight and label as arguments. The edge factory to
be used for internal edge creation must be defined as implicit
val
- see example q). Factory based addition should
slightly outperform standard addition.
For adding or subtracting elements of another Graph
instance in bulk
see 4.5.
val g = mutable.Graph(1~2, 2~3, 2~4, 3~5, 4~5) val h = Graph(3 ~ 4, 3 ~ 5, 4 ~ 6, 5 ~ 6) g union h // Graph(1 ~ 2, 2 ~ 3, 2 ~ 4, 3 ~ 5, 4 ~ 5, 3 ~ 4, 4 ~ 6, 5 ~ 6) g diff h // Graph(1 ~ 2) g intersect h // Graph(4, 3 ~ 5) g &= h // Graph(4, 3 ~ 5), mutated instance
Also union
(same as ++
), difference (diff
same as --
) and intersection (intersec
same as
&
) work in compliance with the corresponding definitions in
graph theory. Use any of the previous operators followed by =
for the mutable variants.
val uE = 3 ~ 4 // UnDiEdge[Int] uE._1 * uE._2 // Int = 12 uE.product // Int = 12 uE match { case n ~ m => n * m } // Int = 12 val dE = 1~>2 // DiEdge[Int] dE.source - dE.target // Int = -1 uE.arity == dE.arity // true dE match { case s ~> t => s - t } // Int = -1 val hE = 1 ~ 2 ~ 11 ~ 12 // HyperEdge[Int] hE._n(hE.arity - 1) // Int = 12 hE.sum // Int = 26
As to
_1
and _2
provide access to the first and
second node of an edge.
Iterable
with respect to the connected nodes.
_1
or source
, the second by _2
or target
.
uE
and dE
have an arity
of 2.
_n
also enables direct access. Here we access the
last node of hE
.
Iterable
s.
import scalax.collection.edge.Implicits._ val g = Graph((1 ~+> 2)("A"), (1 ~+> 1)("AB")) import scalax.collection.edge.LBase._ object StringLabel extends LEdgeImplicits[String] import StringLabel._ (0 /: g.edges)((sum, e) => e.edge match { case s :~> t + (l: String) if l contains 'A' => sum + s.outDegree + t.outDegree }) // Int = 6
Edge patterns are especially handy when extracting the attributes
of weighted and/or labeled edges. The above fold
calculates the
sum of the out-degrees of edge endpoints restricted to edges with a label
containing 'A'
by applying an infix operator pattern to each edge
of the graph.
The constructor pattern LDiEdge(s, t, l)
would be an alternative
to s :~> t + l
. Operator names have been selected in compliance
with edge constructor shortcuts: :~
matches undirected, :~>
directed edges. %
, +
and %+
match weighted,
labeled and weighted-labeled edges, respectively.
Note that you need to dereference inner edges of type EdgeT
by
calling the accessor method edge
to facilitate the predefined edge
extractors. You'll find more edge pattern matching examples in
TEdge.scala.
val g = Graph(0, 1~3, 3~>2) def n(outer: Int): g.NodeT = g get outer def e(outer: UnDiEdge[Int]): g.EdgeT = g get outer n(0).diSuccessors // Set[g.NodeT] = Set() n(2).diSuccessors.isEmpty // true n(3).diSuccessors // Set[g.NodeT] = Set(1, 2) n(3).diPredecessors // Set[g.NodeT] = Set(1) n(2).incoming // Set[g.EdgeT] = Set(3 ~> 2) n(3) ~>? n2 // Option[g.EdgeT] = Some(3 ~> 2)
As to
n(0)
is independent so the set of direct
successor nodes is empty.
n(2)
is reachable but has no direct successor
so the set of its out-neighbors is empty, too.
n(3)
, 1
and 2
are reachable.
n(3)
is node 1
.
n(2)
there is only one
incoming edge namely 3~>2
.
~>?
is a synonym to findOutgoingTo
.
All in all, given a specific node, the following methods are available to inspect incident edges and neighbors:
Result Type | Method name | Synonyms |
Set[NodeT] |
diSuccessors |
outNeighbors , ~>|
|
diPredecessors |
inNeighbors , <~|
|
|
neighbors |
~| |
|
Set[EdgeT] |
outgoing |
~> |
outgoingTo |
~> |
|
incoming |
<~ |
|
incomingFrom |
<~ |
|
Option[EdgeT] |
findOutgoingTo |
~>? |
findIncomingFrom |
<~? |
See also:
object scalax.collection.Graph#InnerNodeLike
.
val g = Graph(2 ~> 3, 3 ~ 1, 5) g.nodes filter (_.toOuter > 2) // Set[g.NodeT] = Set(5, 3) g.nodes filter (_.degree > 1) // Set[g.NodeT] = Set(3) g.edges filter (_.diSuccessors.isEmpty) // Set[g.EdgeT] = Set() g filter ((i: Int) => i >= 2) // Graph(2, 3, 5, 2 ~> 3) g filter g.having(node = _ >= 2) // Graph(2, 3, 5, 2 ~> 3) g filter g.having(edge = _.directed) // Graph(2, 3, 2 ~> 3) g count g.having(node = _.toOuter >= 3, edge = _.isDirected) // Int = 3
As to
(NodeT) => _.toOuter > 2
.
degree > 1
.
g
with nodes satisfying
_ >= 2
and their incident edges.
having
. Method having
,
returning a partial function, helps to reduce code by internally
match
ing nodes and edges.
g
consisting of directed
edges only. Note that filtering g.edges
is not an
alternative because it would return a set of contained edges, not a
subgraph.
Graph
queries may start at the node set nodes
,
the edge set edges
or at the Graph
instance.
Filtering a graph results in a subgraph obtained by node and/or edge
predicates.
Assume g
being the mixed graph in chapter
Traversing Graphs. Then
import scalax.collection.edge.Implicits._ val g = Graph(1 ~ 2 % 4, 2 ~ 3 % 2, 1 ~> 3 % 5, 1 ~ 5 % 3, 3 ~ 5 % 2, 3 ~ 4 % 1, 4 ~> 4 % 1, 4 ~> 5 % 0) g.order // Int = 5 g.graphSize // Int = 8 g.size // Int = 13 g.totalDegree // Int = 16 g.degreeSet // TreeSet(4, 3, 2) g.degreeNodeSeq(g.InDegree) // List((4, 3), (3, 5), (2, 1), (2, 2), (2, 4)) g.degreeNodesMap // Map(2->Set(2), 3->Set(5, 1), 4->Set(3, 4)) g.degreeNodesMap(degreeFilter = _ > 3) // Map(4 -> Set(3, 4))
As to
g
.
g
.
g
.
g
.
g
.
g
with inner node references.
g
with nodes
having the degree of key.
3
.
All degree methods have implicit parameters to query in- or out-degrees and filtering degrees.
val g = Graph(1, 2~>3) g.isConnected // false (g + 2 ~> 1).isConnected // true (g get 2).findConnected(_.toOuter == 3) // Some(3) g.isCyclic // false (g + 3 ~> 2).isCyclic // true g.isComplete // false (g ++ List(1 ~> 2, 1 ~> 3, 2 ~> 1, 3 ~> 1, 3 ~> 2)).isComplete // true g.isDirected // true g.isHyper // false g.isMulti // false
As to
g
is connected it is
also possible to call findConnected
at a specific node.
findCycle
on the graph instance or
starting at a specific node.
g.nodes find (_.inDegree > g.order / 5) orElse g.nodes.headOption
Graph for Scala is designed for functional style programming meaning that you chain method calls as you feel inclined.