I'm successfully sending immutable graphs through akka-remoting (so java serialization), and on the other end when receiving the message I'm able to do some operations, including DOT export.

However, last night I pulled my hair out for a few hours while trying to use the various node/edge traversers. I started with something simple like (graph get node).outerEdgeTraverser foreach println, and kept on calling more and more arcane methods like graph.outerNodeTraverser(node, params, _ => true, _ => true, graph.defaultNodeOrdering) ... to try to fix the copious NPEs I ran into, but was never successful. I haven't researched into the darker corners of java serialization, but what I noticed was in the Traverse code there are lots of defaults marked @transient final val x = x that are null when the object is deserialized. Some of the @transient lazy val x = x fields were successfully restored, however. As far as I know, those transient vals should be re-created upon deserialization, but they aren't.

I eventually came up with a workaround, val graph = (graphIn + dummyNode) - dummyNode, which created a new immutable Graph that was able to be traversed.

Tested on 1.8.0/1.9.0 with scala 2.10.4 on java 1.6.0_65

I'm exploring using scala-graph to represent an ontology. Nodes in our system are decorated with Set[String] metadata, and metadata can be updated. I'd like to use an immutable version of the graph. How do I update a label on an edge to get a new graph with the update?

Here's a minimal example, transforming Graph(0, 1, 10, 0~>10, 1~>10) to Graph(0, 1, 10, 1~>10), removing 0~>10 and leaving a 10~>10 that doesn't appear in the graph's edge set but does appear in 10's list of successors. In more complex graphs more than one additional edge can result from an edge's removal. Tested with version 1.10.0.

import scalax.collection.mutable.Graph
import scalax.collection.GraphEdge.DiEdge
import scalax.collection.GraphPredef._

object GFSEdgeRemoval {
  def main(args: Array[String]) {
    val g: Graph[Int, DiEdge] = Graph(0, 1, 10, 0~>10, 1~>10)

    println(g)
    println("%d nodes, %d edges, cyclic = %s".format(g.nodes.size, g.edges.size, g.isCyclic))
    g.nodes.foreach { i =>
      println("%s -> %s".format(i, i.diSuccessors))
    }

    val removedEdge = g.edges.head
    println("\nremoving %s\n".format(removedEdge))
    g -= removedEdge

    println(g)
    println("%d nodes, %d edges, cyclic = %s".format(g.nodes.size, g.edges.size, g.isCyclic))
    println("cycle: %s".format(g.findCycle))

    g.nodes.foreach { i =>
      println("%s -> %s".format(i, i.diSuccessors))
    }
  }
}

Graph(0, 1, 10, 0~>10, 1~>10)
3 nodes, 2 edges, cyclic = false
0 -> Set(10)
1 -> Set(10)
10 -> Set()

removing 0~>10

Graph(0, 1, 10, 1~>10)
3 nodes, 1 edges, cyclic = true
cycle: None
0 -> Set()
1 -> Set(10)
10 -> Set(10)

Hi,

This doesn't appear to be supported directly, but I was wondering if you all had any ideas. I'm trying to apply graph algorithms to an implicitly defined directed graph, i.e. a Graph[N, E] defined by a starting node and a neighbor function N => Iterator[(E, N)].

Any ideas? I'd like to be able to search through this graph without every node having to be instantiated. I was thinking of possibly extending the Graph trait to do this myself. Do you think I'd run into issues with that?

Thanks,
Tim

Requirement from https://groups.google.com/forum/?fromgroups=#!topic/scala-graph/UPqrtEau3CY

Hello,

I'm trying to use the library but I've found that chapter 4.10 does not match the actual code, since:

"value VisitorReturn is not a member of object scalax.collection.GraphTraversal"

How to write the examples in 4.10 with the new syntax?… what is the new syntax?

Thank you!

import scalax.collection.Graph
import scalax.collection.GraphEdge.DiEdge
import scalax.collection.GraphPredef._

object MainApp extends App {

  //Creates new graph
  def graph: Graph[String, DiEdge] = Graph(
    "A" ~> "B",
    "A" ~> "C",
    "A" ~> "D",
    "B" ~> "E",
    "B" ~> "F",
    "C" ~> "G",
    "C" ~> "H",
    "D" ~> "F",
    "D" ~> "G"
  )

  val results = 1 to 20 map { _ =>
    graph.topologicalSort.mkString("")
  }

  println(results.tail.forall(_ == results.head))
}

Given the above code, I expect to get same topological sort for the similar graphs created by graph method. But this app prints false and proves the opposite. All of the results of topologicalSort call do comply to topological sort but it's needed to have a mechanism for fixing this order for similar graphs.

Setting ordering in graph.componentTraverser(ordering = ...).topologicalSort does not fix the order for similar graphs.

I'm trying to define a graph with labeled (or custom) edges in a type-safe manner. LDiEdge provides no type safety whatsoever. Custom edges cannot, as far as I can tell, be restricted in a type-safe way as to what types of nodes they exist between.

If the object is to allow a variety of different types of edges and vertices within a graph, I see no impediment to the user of requiring that all edges/vertices derive from some particular type. Different edge types may be expressed as members of the type hierarchy or as an algebraic data type.

Am I missing something here? How can I define a graph where the edges are aware of the types of the nodes they exist between? The context for my problem is that I want to define a graph where vertices represent places, and edges represent transportation between places. Traversing the graph from one vertex to another represents moving between places, and as we traverse the edges, we emit instructions for travel. As such, the edge needs to know which two vertices it's connecting, and needs to know more than simply their identity (NodeT), it needs to know that NodeT is actually PlaceNode, so it can get more information about the place.

For Graphs with DiEdge there should be a method to allow a topological sort. See https://groups.google.com/forum/#!topic/scala-graph/2x207RGtBSE

I'd like to use scala-graph in an SBT plugin, but 1.9.1 is not published for Scala 2.10.

In the default implementation of the PathBuilder we can find the following:

  def newPathBuilder(
      start: NodeT)(
      implicit sizeHint: Int = defaultPathSize,
      edgeSelector:      (NodeT, NodeT) => Option[EdgeT] = anyEdgeSelector): PathBuilder

The problematic point here is defaultPathSize.

  @inline final protected def defaultPathSize: Int = min(256, nodes.size * 2)

As it turns out, this is calculated using size of TraversableOnce, which is linear time, i.e. O(n). This impacts performance heavily when used on larger graphs, when looking at my profiling results. Especially when many paths are constructed.

A workaround is providing a sizeHint to the newPathBuilder function.

However, when using Graph.nodes.size I was faced with the same issue, which required me to cache the node size externally.

On http://www.scala-graph.org/guides/core-inner-outer.html toEdgeIn is used as an example, but it has been deprecated for toOuter.

I'm trying to find an inner node in a graph that matches some predicate. Here's my attempt:

   val graph = Graph[MyType, DiEdge]()
   ...
   graph.nodes.find((node: MyType) => true) match {
      case Some(root) => println("Yay")
      case None => println("Boo")
    }

This produces a compiler error:

[error] both method find in trait IterableLike of type (p: _51.NodeT => Boolean)Option[_57.NodeT]
[error] and  method find in trait TraversableOnce of type (p: scalax.collection.mutable.Graph[MyType,scalax.collection.GraphEdge.DiEdge]#NodeT => Boolean)Option[scalax.collection.mutable.Graph[MyType,scalax.collection.GraphEdge.DiEdge]#NodeT]
[error] match argument types (MyType => Boolean)

Any idea how to get around this?

Thanks!
-Colin

Hi,

does this library also contain algorithms?

I would need to computes the transitive closure of a graph,
such as http://jgrapht.org/javadoc/index.html?org/jgrapht/alg/TransitiveClosure.html
is this one implemented?

and an alg for finding the graph cycles?

I'm confused by some behavior of the componentTraverser method:

scala> val ns = List(11, 12, 13, 14)
scala> val es = List(11~>12, 13~>14)
scala> val g = Graph.from(ns, es)
scala> for { c <- g.componentTraverser() } yield { c.nodes }
res12: Traversable[Set[g2.NodeT]] = List(Set(12), Set(13, 14), Set(11, 12))

Why is there the Set(12)? Or why is there no Set(14) then?

On version 1.9.4:

I have a Graph[T, DiEdge] containing thousands of edges and vertices. When I attempt to serialize it, I get a StackOverFlow:

        at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1178)
        at java.io.ObjectOutputStream.defaultWriteFields(ObjectOutputStream.java:1548)
        at java.io.ObjectOutputStream.writeSerialData(ObjectOutputStream.java:1509)
        at java.io.ObjectOutputStream.writeOrdinaryObject(ObjectOutputStream.java:1432)
        at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1178)
        at java.io.ObjectOutputStream.defaultWriteFields(ObjectOutputStream.java:1548)
        at java.io.ObjectOutputStream.writeSerialData(ObjectOutputStream.java:1509)
        at java.io.ObjectOutputStream.writeOrdinaryObject(ObjectOutputStream.java:1432)
        at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1178)
        at java.io.ObjectOutputStream.defaultWriteFields(ObjectOutputStream.java:1548)
        at java.io.ObjectOutputStream.writeSerialData(ObjectOutputStream.java:1509)
        at java.io.ObjectOutputStream.writeOrdinaryObject(ObjectOutputStream.java:1432)
        at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1178)
...

For what it's worth, my T type is a case class without pointers.

It looks like scala-graph does define custom readObject and writeObject methods; however, perhaps there are still data structures with pointers somewhere within Graph?

It looks like an empty node name can cause this:

scala> val dot = g.toDot(root, edgeTransformer)
java.util.NoSuchElementException: next on empty iterator
at scala.collection.Iterator$$anon$2.next(Iterator.scala:39)
at scala.collection.Iterator$$anon$2.next(Iterator.scala:37)
at scala.collection.IndexedSeqLike$Elements.next(IndexedSeqLike.scala:64)
at scala.collection.IterableLike$class.head(IterableLike.scala:91)
at scala.collection.immutable.StringOps.scala$collection$IndexedSeqOptimized$$super$head(StringOps.scala:31)
at scala.collection.IndexedSeqOptimized$class.head(IndexedSeqOptimized.scala:120)
at scala.collection.immutable.StringOps.head(StringOps.scala:31)
at scalax.collection.io.dot.Export$$anonfun$1.scalax$collection$io$dot$Export$$anonfun$$toID$1(Export.scala:137)
at scalax.collection.io.dot.Export$$anonfun$1$$anonfun$apply$7.apply(Export.scala:185)
at scalax.collection.io.dot.Export$$anonfun$1$$anonfun$apply$7.apply(Export.scala:178)

Seems like line 137 of Export.scala should check if s.isEmpty

First of all, thanks for this great library. I do enjoy using it!

Currently I need quite some boilerplate code to search for nodes/edges. A graph.find() that returns Node or Edge objects depending on the test function would help a lot.
Here is a function I wrote that works for nodes:

    def find[N, E[X]<:EdgeLikeIn[X]](graph: Graph[N,E], condition: N => Boolean): Option[graph.NodeT] = {
        val param = graph.find(condition)
        param match {
            case None => None
            case value: Some[Param[N, E]] => value.get match {
                case node: graph.NodeT => Some(node)
                case _ => None
            }
        }
    }

I didn't manage to get the one for edges to work (I can't get the type parameters right), but something along those lines should do it:

    def find[N, E[N]<:EdgeLikeIn[N]](graph: Graph[N,E], condition: InnerEdgeParam[N, E, N, E] => Boolean): Option[graph.EdgeT] = {
        val param = graph.find(condition)
        param match {
            case None => None
            case value: Some[Param[N, E]] => value.get match {
                case edge: graph.EdgeT => Some(edge)
                case _ => None
            }
        }
    }

There is a commented out version of predicateToEdgePredicate in scalax.collection.GraphPredef. Can we have that? It would allow using graph.exists() with an edge predicate.

Currently I have to do something like the following:

    graph exists ((param: Param[Cell,DiEdge]) => {
        param match {
            case edge: DiEdge[Cell] => ... some condition ...
            case _ => false
        }
    })

Which is loads of boilerplate. I hope something like the following is possible to make work:

    graph exists ((edge: DiEdge[Cell]) => ... some condition ...)

I'm trying the following code:

val graph: Graph[String, DiEdge] = Graph(
      "A" ~> "C",
      "A" ~> "B",
      "C" ~> "B"
)
val root = graph.get("A")
println(graph.topologicalTraverser(root).toList)

but I get compiler error:

Error:(87, 40) type mismatch;
 found   : root.type (with underlying type scalax.collection.Graph[String,scalax.collection.GraphEdge.DiEdge]#NodeT)
 required: qual$1.NodeT
    println(graph.topologicalTraverser(root).toList)
                                       ^

What is the expected way to use it?

Hi Peter,

Do you develop on a Mac? I'm having a problem on the mac using the dependency:

"com.assembla.scala-incubator" % "graph-core_2.10" % "1.6.1"

with the following imports:

import scalax.collection.Graph                                                  
import scalax.collection.GraphPredef._                                          
import scalax.collection.GraphEdge._

I keep getting the following compiler warning:

GraphSimple/Main.scala:2: imported `Graph' is permanently hidden by definition of object Graph
[warn] import scalax.collection.Graph

which prevents me from having things like:

val g1 = Graph(UnDiEdge(3, 1), 5)

working.

Doing the same thing on linux seems to work fine; not sure if cleaning out my ivy cache will help, just wondering if it's something you've run into.

Cheers, Jason.

Hi,

equality for (directed) hyperedges that connect to the same node multiple times is not evaluated correctly:

val g = Graph[Int, DiHyperEdge]()
val e1 = DiHyperEdge(1,2,2)
g += e1
g.contains(e1) // returns false
g.edges.head.toOuter == e1 // Likewise returns false, despite being the same edge

This doesn't occur with undirected hyperedges, but with (I think) every version of directed hyperedges.

I'm not sure NodeDescriptor should or should not serialize object/case object, architecturally.
However, graph should accept the static object node as its node, and so either NodeDescriptor should serialize/deserialize the object node, or avoid the static object node to be included in the json, might be better.

Currently, if the graph include static object node and called toJson, following exception occured.

JSON-Graph error: No 'NodeDescriptor' capable of processing type "package$StaticNode" found

Maybe this occured cause of scala, scala does not provide type for static object.

We can still avoid this exception using val instead of object, but have to be care about the existence of the nodes.

// object StaticNode extends Node
val StaticNode = Node()

If a new set is created by ++ of an empty result of diSuccessors (in first place) and of some other non-emplty node set, the new set erroneously contains null in place of the empty set.

Consider the following code snippet:

import scalax.collection.Graph
import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._
import scalax.collection.edge._

val g = Graph(1 ~> 2, 2 ~> 3)
((g get 3) diSuccessors) ++ ((g get 1) diSuccessors) //ORDER MATTERS!

The last expession yields to Set(null, 2) rather than Set(2).

I used graph-core_2.9.2-1.6.2.jar from Maven with Scala 2.9.3.

In https://github.com/scala-graph/scala-graph/blob/master/core/src/main/scala/scalax/collection/Graph.scala,
we have:

@transient lazy val isDirected =
    edgeT.tpe.baseClasses contains (typeOf[DiHyperEdgeLike[_]].typeSymbol)

Shouldn't this be defined as below instead?

@transient lazy val isDirected =
    edgeT.tpe.baseClasses contains (typeOf[DiEdgeLike[_]].typeSymbol)

Current documentation of scala-graph is very confusing in section devoted to Type Parameter Inference

Here is how it is in documentation:

a) val g = Graph()
// Graph[Nothing,Nothing]
b) val g = Graph(1)
c) val g = Graph(1~>2); g += 1.2

And here what types will be inferred when you simple copy-past the code form docs

import scalax.collection.Graph
import scalax.collection.GraphPredef._
import scalax.collection.GraphEdge._

val g1: Graph[Nothing, Nothing] = Graph()// Graph[Nothing,Nothing]
val g2: Graph[Int, Nothing] = Graph(1) // Graph[Int,Nothing]
val g3: Graph[DiEdge[Int], Nothing] = Graph(1~>2)
val g4: Graph[DiEdge[Int], Nothing] = Graph(1~>2)

UPDATE:
I figured out the issue. It is an IntellijIDEA bug, Intellij IDEA treat val g = Graph(1~>2) differently and instead of Graph[Int, DiEdge] as it is in ScalaIDE and as it should be, returns Graph[DiEdge[Int], Nothing]
I've already reported this issue on Jetbrains bug tracker http://youtrack.jetbrains.com/issue/SCL-5554 Please check the bug yourself and vote for this issue to speed up this bugfixing.

About a half of scala community uses Intellij IDEA, so it is rather important issue and cannot be ignored (nobody will switch to ScalaIDE for the sake of one library). Until they fix it, please tell me what is a workaround for IDEA What construction should be used instead of Graph(2~1) to get something like Graph[Int, DiEdge] that will work in IDEA as well?

P.S. Overall reading pdfs is not convenient, what about moving docs to github wiki?

Something like

val g = Graph("a" ~> "b" % 3, "a" ~> "c" % 2, "b" ~> "c" % -2)
println(g.get("a").shortestPathTo(g.get("c")).get.weight)

will print 2, which is wrong(should be 1)

Hello,

for undirected hyperedges that are loops, the equality operator is not symmetric. For example

HyperEdge(1,1) == HyperEdge(1,2) // correctly evaluates to "false", but
HyperEdge(1,2) == HyperEdge(1,1) // evaluates to "true".

As far as I can see this only affects (L)(k)HyperEdge, while the directed variants, and UnDiEdge work as expected.

I'm pretty new to scala, so maybe just missing something, but help to figure it out please.
Here in the docs "~" is defined as a shortcut for UnDiEdge. But my IDE (and compiler as well) cannot resolve this symbol. I looked into scalax.collection.edge.Implicits and did not find it as well.
Is it a bug in the code or documentation or am I missing something?

In the following example

def adjacentEdge[G <: Graph[Node, UnDiEdge]](from: G#NodeT, to: G#NodeT) : Option[G#EdgeT] = {
    from.findOutgoingTo(to)
}

I get the following error:

Error:(43, 23) type mismatch;
 found   : to.type (with underlying type G#NodeT)
 required: _73.NodeT where val _73: G
        from.findOutgoingTo(to)
                            ^

But I would expect to get an edge of type G#EdgeT.
To get an edge of the path-dependent graph type G#EdgeT, the user would have to do g.get(edge.toOuter), where g is the graph of type G.

Please add extractors for edges to support pattern matching. Use case:

case class Airport(code: String, country: String)
val rheims = Airport("RHE", "fr")
val dijon = Airport("DIJ", "fr")
val chester = Airport("CEG", "uk")

val g = Graph(dijon ~> chester,
              chester ~> rheims,
              rheims ~> dijon)

// get starting airport of all flights to a french airport
g.edges.collect{case from ~> Airport(_, "fr") => from}
// = Set(Airport(CEG,uk), Airport(RHE,fr))

The following works for edges outside of graphs (e.g., a list of the three edges above):

object ~> {
  def unapply[N](e: DiEdge[N]) = Some((e._1, e._2))
}

However, edges stored in the EdgeSet returned by Graph#edges seem not to type match DiEdge.

I don't know if this is possible, but support for weighted edges would be nice, to do things like case from ~> Airport(_, "fr") % distance if distance > 100 => ...

The subdirectories constrained, core, dot, json, misc, and testutil are part of the download. The sbt build expects the source to be in Core, Dot, Json, TestUtil, and Misc subdirectories. This is OK on Windows but does not work on Macs or Linux machines.

% git diff project/GraphBuild.scala
diff --git a/project/GraphBuild.scala b/project/GraphBuild.scala
index ee044ae..ac0f3e2 100644
--- a/project/GraphBuild.scala
+++ b/project/GraphBuild.scala
@@ -16,7 +16,7 @@ object GraphBuild extends Build {

lazy val core = Project(
id = "Graph-core",

• base = file("Core"),
• base = file("core"),
  settings = defaultSettings ++ Seq(
  name := "Graph Core",
  version := Version.core,
  @@ -26,7 +26,7 @@ object GraphBuild extends Build {

lazy val constrained = Project(
id = "Graph-constrained",

• base = file("Constrained"),
• base = file("constrained"),
  settings = defaultSettings ++ Seq(
  name := "Graph Constrained",
  version := Version.constrained
  @@ -35,7 +35,7 @@ object GraphBuild extends Build {

lazy val dot = Project(
id = "Graph-dot",

• base = file("Dot"),
• base = file("dot"),
  settings = defaultSettings ++ Seq(
  name := "Graph DOT",
  version := Version.dot
  @@ -44,7 +44,7 @@ object GraphBuild extends Build {

lazy val json = Project(
id = "Graph-json",

• base = file("Json"),
• base = file("json"),
  settings = defaultSettings ++ Seq(
  name := "Graph JSON",
  version := Version.json,
  @@ -54,7 +54,7 @@ object GraphBuild extends Build {

lazy val test = Project(
id = "Graph-test",

• base = file("TestUtil"),
• base = file("testutil"),
  settings = defaultSettings ++ Seq(
  name := "Graph Test",
  version := Version.test,
  @@ -64,7 +64,7 @@ object GraphBuild extends Build {

lazy val misc = Project(
id = "Graph-misc",

• base = file("Misc"),
• base = file("misc"),
  settings = defaultSettings ++ Seq(
  name := "Graph Miscellaneous",
  version := Version.misc,

final class ExtGraphNode[N, E[X] <: EdgeLikeIn[X]](node_ : Graph[N, E]#NodeT) {
  type NodeT = graph.NodeT
  val graph = node_.containingGraph
  val node = node_.asInstanceOf[NodeT]

  def inHead = node.inNeighbors.head
}

implicit def nodeToExtN[N, E[X] <: EdgeLikeIn[X]](node: Graph[N, E]#NodeT) = 
  new ExtGraphNode[N, E](node)

val g = Graph(1 ~> 2, 2 ~> 3)
(g get 1).inHead.shortestPathTo(g get 3)

The code above will not compile due to the type mismatch of the node returned by the extension method inHead and the node of the graph. Not sure if it is a scala-graph or Scala 2.10.1 compiler issues. Perhaps I'm doing something wrong here?

shortestPathTo implements Dijkstra's algorithm for selecting the shortest path between two nodes. It appears that the implementation is incorrect, and the wrong answer is sometimes given.

From http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.

However, the priority queue used to select the next node uses the node's distance from one of its predecessors, not the current smallest tentative distance from the start. This may mean that new nodes (which should already have a large distance) may be visited before earlier nodes, and the algorithm may terminate incorrectly.

I want to try and find a shortest path of a constant maximum length. To do this, I tried using the withMaxDepth filter for traversals. This works nicely with pathTo, but shortestPathTo ignores the restrictions.

Example:

import scalax.collection.GraphEdge._
import scalax.collection.GraphPredef._
import scalax.collection.immutable.Graph

val g = Graph(1~2, 2~3, 3~4)
val traversal = g.get(1).withSubgraph(nodes = _ < 2)
traversal.pathTo(g.get(3))
// res1: Option[g.Path] = None

val traversal2 = g.get(1).withMaxDepth(1)
traversal2.pathTo(g.get(3))
// res2: Option[g.Path] = None

traversal2.shortestPathTo(g.get(3))
// res3: Option[g.Path] = Some(Path(1, 1~2, 2, 2~3, 3))

I expect that the shortestPathTo return None, but instead it returns a complete path.

Calculating the shortest path in parallel sometimes gives a None instead of a path, which certainly exists.

import scalax.collection.GraphEdge._
import scalax.collection.GraphPredef._
import scalax.collection.immutable.Graph

val g = Graph[Int, UnDiEdge](1 ~ 2, 2 ~ 3)

val seq = Seq.fill(100000){
    g.get(1)
}

// Parallel case.
seq.par.map { node =>
    node.shortestPathTo(g.get(3))
} forall {
    _.isDefined
} // res0: Boolean = false
// Should be true.

// Sequential case
seq.map { node =>
    node.shortestPathTo(g.get(3))
} forall {
    _.isDefined
} // res1: Boolean = true
// Correct.

With less entries in the Seq it sometimes results in true, so I think this is caused by a racing condition.

I stumbled upon this when trying to speed up the calculation of thousands of paths using shortestPathTo.

Hi,

I am using twitter chill to serialize my objects, after adding Scala-Graph to my case class and try to serialize I got this :

Caused by: java.lang.IllegalArgumentException: Unable to create serializer "com.esotericsoftware.kryo.serializers.FieldSerializer" for class: scalax.collection.GraphBase$Edge$

Any suggestion ?

During profiling I noticed that calling foreach on an EqHashSet, in this case the neighbours of a node, uses an excessive amount of time to construct an iterator (about 25% of a total time of 270s). It seems that foreach constructs an iterator called EqHashSetIterator. In the constructor of EqHashSetIterator the method size is used, which is O(n), since it uses the TraversableOnce implementation of size. I find it strange that during the construction of an iterator it is required to iterate through the entire collection.

I'm using the edges method of a Path to check if two paths are of the same length. However, I noticed that a certain edge occured twice in my path, which should not be possible (as it is a duplicate). It also seemed to traverse the same edge twice in a row.

The following minimal code will produce the bug:

import scalax.collection.immutable.Graph
import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._

val g = Graph[Int, UnDiEdge](1 ~ 2, 2 ~ 3)
val builder = g.newPathBuilder(g.get(1))
builder.add(g.get(2))

val builder2 = g.newPathBuilder(g.get(3))
builder2.add(g.get(2))
val path2 = builder2.result()

builder ++=(path2)
val path = builder.result() //path: g.Path = Path(1, 1~2, 2, 2~3, 3)
path.edges //res3: Traversable[g.EdgeT] = ArrayBuffer(1~2, 2~3, 2~3)
// Should be: ArrayBuffer(1~2, 2~3)

It seems to be related to the order paths process edges, because this instead does not produce the bug:

val g = Graph[Int, UnDiEdge](1 ~ 2, 2 ~ 3)
val builder = g.newPathBuilder(g.get(1))
builder.add(g.get(2))

val builder2 = g.newPathBuilder(g.get(2))
builder2.add(g.get(3))
val path2 = builder2.result()

builder ++=(path2)
val path = builder.result() //path: g.Path = Path(1, 1~2, 2, 2~3, 3)
path.edges //res3: Traversable[g.EdgeT] = ArrayBuffer(1~2, 2~3)
// Correct!

I would assume that if pathTo finds a path, shortestPathTo must aswell.
This is not the case, I have found.
Maybe I'll be able to provide a proper test case.

I can't figure out what I'm doing wrong. Here is a toy example:

package example

import net.liftweb.json.JsonAST.JString
import net.liftweb.json.JsonParser.ParseException
import net.liftweb.json._

import scalax.collection.GraphEdge.DiEdge
import scalax.collection.GraphPredef._
import scalax.collection.immutable.Graph
import scalax.collection.io.json._

// A model just for the graph so that Role and Permission do not need to share an inheritance hierarchy
sealed trait RoleOrPermissionGraphNode {
  def `type`: Symbol
  def name: String
}
case class RoleGraphNode(name: String) extends RoleOrPermissionGraphNode {
  override def `type`: Symbol = 'Role
}
case class PermissionGraphNode(name: String) extends RoleOrPermissionGraphNode {
  override def `type`: Symbol = 'Permission
}

case class AllowedRoleGraphNode(allowedRoles: Graph[RoleOrPermissionGraphNode, DiEdge])
object AllowedRoleGraphNode {

  val roleNodeLiftSerializer = new CustomSerializer[RoleGraphNode](implicit formats => ( {
    case JString(name) => RoleGraphNode(name)
  }, {
    case r: RoleGraphNode => JString(r.name)
  }))

  val permissionNodeLiftSerializer = new CustomSerializer[PermissionGraphNode](implicit formats => ( {
    case JString(name) => PermissionGraphNode(name)
  }, {
    case r: PermissionGraphNode => JString(r.name)
  }))

  val permissionGraphNodeDescriptor = new NodeDescriptor[PermissionGraphNode](
    typeId = "Permissions",
    customSerializers = Seq(permissionNodeLiftSerializer)
  ) {
    override def id(node: Any): String = node match {
      case p: PermissionGraphNode => p.name
    }
  }

  val roleGraphNodeDescriptor = new NodeDescriptor[RoleGraphNode](
    typeId = "Roles",
    customSerializers = Seq(roleNodeLiftSerializer)
  ) {
    override def id(node: Any): String = node match {
      case r: RoleGraphNode => r.name
    }
  }

  val roleOrPermissionDescriptor = new NodeDescriptor[RoleOrPermissionGraphNode](
    customSerializers = Seq(roleNodeLiftSerializer, permissionNodeLiftSerializer)
  ) {
    override def id(node: Any): String = node match {
      case p: PermissionGraphNode => p.name
      case r: RoleGraphNode => r.name
    }
  }

  val roleOrPermissionEdgeDescriptor = new EdgeDescriptor[RoleOrPermissionGraphNode, DiEdge, DiEdge.type](
    DiEdge, typeId = "HasPermission")
  val roleOrPermissionGraphJsonDescriptor = new Descriptor[RoleOrPermissionGraphNode](
    roleOrPermissionDescriptor,
    roleOrPermissionEdgeDescriptor,
    namedNodeDescriptors = Seq(roleGraphNodeDescriptor, permissionGraphNodeDescriptor),
    namedEdgeDescriptors = Seq(roleOrPermissionEdgeDescriptor)
  )
}

object JsonErrorExample {

  import AllowedRoleGraphNode._

  def main(args: Array[String]): Unit = {
    val model = AllowedRoleGraphNode(Graph(
      RoleGraphNode("jn"),
      RoleGraphNode("ncbfrRro3nspyzfppulromDmeks3j7xz3untVi8jn5flfJ7wLecuTwrUzjqqngswcfr8vwHnrjlFmiqx3mYqzjavqcWunsa2i"),
      RoleGraphNode("reilbk62qNrnikqnu5lm5cchmmxgmwpwP2juegxdhRea6GHKcmpghdIwNhurq1smibzerft9Heysoo6tdD5tmkkcyidYqs"),
      RoleGraphNode("jn")~>RoleGraphNode("jn"),
      RoleGraphNode("jn")~>RoleGraphNode("reilbk62qNrnikqnu5lm5cchmmxgmwpwP2juegxdhRea6GHKcmpghdIwNhurq1smibzerft9Heysoo6tdD5tmkkcyidYqs"),
      RoleGraphNode("ncbfrRro3nspyzfppulromDmeks3j7xz3untVi8jn5flfJ7wLecuTwrUzjqqngswcfr8vwHnrjlFmiqx3mYqzjavqcWunsa2i")~>RoleGraphNode("jn"),
      RoleGraphNode("reilbk62qNrnikqnu5lm5cchmmxgmwpwP2juegxdhRea6GHKcmpghdIwNhurq1smibzerft9Heysoo6tdD5tmkkcyidYqs")~>RoleGraphNode("ncbfrRro3nspyzfppulromDmeks3j7xz3untVi8jn5flfJ7wLecuTwrUzjqqngswcfr8vwHnrjlFmiqx3mYqzjavqcWunsa2i"),
      RoleGraphNode("reilbk62qNrnikqnu5lm5cchmmxgmwpwP2juegxdhRea6GHKcmpghdIwNhurq1smibzerft9Heysoo6tdD5tmkkcyidYqs")~>RoleGraphNode("reilbk62qNrnikqnu5lm5cchmmxgmwpwP2juegxdhRea6GHKcmpghdIwNhurq1smibzerft9Heysoo6tdD5tmkkcyidYqs")))
    val rolesGraphJsonString = new JsonGraph(model.allowedRoles).toJson(roleOrPermissionGraphJsonDescriptor)

    // Fails to parse, because {"nodes": "Roles": [...]} is invalid json
    try JsonParser.parse(rolesGraphJsonString)
    catch {
      case parse: ParseException => println(s"Failed to parse: $rolesGraphJsonString")
    }
  }
}

What I want

I want to be able to create a graph of roles and permissions where roles can have other roles or permissions as children and be able to export it as Json.

Additionally

I notice that Permissions can have other Permissions as children. This isn't what I want, but I don't know how to fix that. Any suggestions for how to accomplish this?

In a simple two nodes graph with two edges connecting these nodes I'm expecting to find a cycle, but getting None instead:

import scalax.collection.Graph
import scalax.collection.edge.LkUnDiEdge

val g = Graph[Int, LkUnDiEdge](LkUnDiEdge(1, 2)(0), LkUnDiEdge(1, 2)(1))
assert(g.findCycle.isEmpty)

Domain Type hierarchies are not honoured in scala-graph

I just created a hierarchy of types:

abstract class RootOfAllNode {
  def identifiedAs: String
}

class SubClassNodeA (id: Int) extends RootOfAllNode {
  def identifiedAs = "SubCLassNodeA (" + id  + ")"
}


class SubClassNodeB (price: Float) extends RootOfAllNode {
  def identifiedAs = "SubClassNodeB with price (" + price + ")"
}


// DateTime is actually org.joda.time.DateTime
class SubClassNodeC (createdOn: DateTime) extends RootOfAllNode {
  def identifiedAs = "SubClassNodeC (" + createdOn + ")"
}

Now, I intend to create a (Directed) Graph whose inhabitants are objects of the aforementioned types, thus:

import scalax.collection.GraphPredef._
import scalax.collection.GraphEdge._
import scalax.collection.GraphEdge.DiEdge
import scalax.collection.edge.LDiEdge     // labeled directed edge
import scalax.collection.edge.Implicits._ // shortcuts


import scalax.collection.edge.LBase._
object StringLabel extends LEdgeImplicits[String]


import StringLabel._


class Population {


  val a = new SubClassNodeA(9)
  val anotherA = new SubClassNodeA(10)
  val b = new SubClassNodeB(12.67f)
  val c = new SubClassNodeC(new DateTime(System.currentTimeMillis()))


  val family = Graph (
    (a ~+> b)("Loves"),                    // Works
    (b ~+> c)("Hates"),                    // Works
    (b ~+> a)("Ignores"),                  // Works
    (a ~+> anotherA)("notIntroducedYet")   // Doesn't work


  )
}

What the compiler comes back with is a mouthful! :-)

Error:(34, 8) type mismatch;
 found   : scalax.collection.edge.LDiEdge[org.nirmalya.graphExplore.SubClassNodeA] with scalax.collection.GraphEdge.EdgeCopy[scalax.collection.edge.LDiEdge]{type L1 = String}
 required: scalax.collection.GraphPredef.Param[org.nirmalya.graphExplore.RootOfAllNode,scalax.collection.edge.LDiEdge]
Note: org.nirmalya.graphExplore.SubClassNodeA <: org.nirmalya.graphExplore.RootOfAllNode (and scalax.collection.edge.LDiEdge[org.nirmalya.graphExplore.SubClassNodeA] with scalax.collection.GraphEdge.EdgeCopy[scalax.collection.edge.LDiEdge]{type L1 = String} <: scalax.collection.GraphPredef.Param[org.nirmalya.graphExplore.SubClassNodeA,scalax.collection.edge.LDiEdge]), but trait Param is invariant in type N.
You may wish to define N as +N instead. (SLS 4.5)
    (a ~+> anotherA)("notIntroducedYet")

If I create a Graph of objects of the Domain that application works in, it is quite likely that a Domain Class Hierarchy will exist. More so, because these objects will be created outside the Graph and then be held inside the Graph for easy access based on the relationships that exist between them. Therefore, somewhere, it will be expected that while it is being created, the Graph infers the Relationships between the Objects correctly.

Referring to the example I had provided, I am relating a SubClassNodeA to a SubClassNodeA, in the same way as a SubClassNodeA to a SubClassNodeB, because both of them IsA RootOfAllNode . In the Application Domain, this hierarchy is established. In the Graph, this is not honoured.

This is probably not a bug of this library but in consequence it means that any concurrent usage of this library is broken. From the quick look into the usages of Scala reflection in this library, I'd say that there should be a simpler solution that doesn't depend on Scala reflection.

at scala.reflect.runtime.SymbolLoaders$PackageScope.lookupEntry(SymbolLoaders.scala:126)
    at scala.reflect.runtime.SymbolLoaders$PackageScope.lookupEntry(SymbolLoaders.scala:126)
    at scala.reflect.internal.pickling.UnPickler.unpickle(UnPickler.scala:45)
    at scala.reflect.runtime.JavaMirrors$JavaMirror.unpickleClass(JavaMirrors.scala:565)
    at scala.reflect.runtime.SymbolLoaders$TopClassCompleter.complete(SymbolLoaders.scala:32)
    at scala.reflect.internal.Symbols$Symbol.info(Symbols.scala:1231)
    at scala.reflect.internal.BuildUtils$BuildImpl.select(BuildUtils.scala:20)
    at scala.reflect.internal.BuildUtils$BuildImpl.selectTerm(BuildUtils.scala:14)
    at scala.reflect.internal.BuildUtils$BuildImpl.selectTerm(BuildUtils.scala:8)
    at scalax.collection.GraphLike$$typecreator1$1.apply(Graph.scala:44)
    at scala.reflect.api.TypeTags$WeakTypeTagImpl.tpe$lzycompute(TypeTags.scala:231)
    at scala.reflect.api.TypeTags$WeakTypeTagImpl.tpe(TypeTags.scala:231)
    at scala.reflect.api.TypeTags$class.typeOf(TypeTags.scala:335)
    at scala.reflect.api.Universe.typeOf(Universe.scala:59)
    at scalax.collection.GraphLike$class.isDirected(Graph.scala:44)
    at scalax.collection.mutable.DefaultGraphImpl.isDirected$lzycompute(Graph.scala:264)
    at scalax.collection.mutable.DefaultGraphImpl.isDirected(Graph.scala:264)
    at scalax.collection.TraverserImpl$Impl$Runner$$anonfun$dfsWGB$1.apply(TraverserImpl.scala:457)
    at scalax.collection.TraverserImpl$Impl$Runner$$anonfun$dfsWGB$1.apply(TraverserImpl.scala:448)
    at scalax.collection.State$class.withHandles(State.scala:98)
    at scalax.collection.mutable.DefaultGraphImpl.withHandles(Graph.scala:264)
    at scalax.collection.TraverserImpl$Impl$Runner.dfsWGB(TraverserImpl.scala:448)
    at scalax.collection.GraphTraversalImpl$ComponentTraverser$$anonfun$findCycle$1$$anonfun$apply$12.apply(GraphTraversalImpl.scala:234)
    at scalax.collection.GraphTraversalImpl$ComponentTraverser$$anonfun$findCycle$1$$anonfun$apply$12.apply(GraphTraversalImpl.scala:232)
    at scala.collection.TraversableLike$WithFilter$$anonfun$foreach$1.apply(TraversableLike.scala:772)
    at scala.collection.Iterator$class.foreach(Iterator.scala:727)
    at scala.collection.AbstractIterator.foreach(Iterator.scala:1157)
    at scala.collection.IterableLike$class.foreach(IterableLike.scala:72)
    at scalax.collection.mutable.AdjacencyListGraph$NodeSet.foreach(AdjacencyListGraph.scala:75)
    at scala.collection.TraversableLike$WithFilter.foreach(TraversableLike.scala:771)
    at scalax.collection.GraphTraversalImpl$ComponentTraverser$$anonfun$findCycle$1.apply(GraphTraversalImpl.scala:232)
    at scalax.collection.GraphTraversalImpl$ComponentTraverser$$anonfun$findCycle$1.apply(GraphTraversalImpl.scala:230)
    at scalax.collection.State$class.withHandles(State.scala:98)
    at scalax.collection.mutable.DefaultGraphImpl.withHandles(Graph.scala:264)
    at scalax.collection.GraphTraversalImpl$ComponentTraverser.findCycle(GraphTraversalImpl.scala:230)
    at scalax.collection.GraphTraversal$class.findCycle(GraphTraversal.scala:94)
    at scalax.collection.mutable.DefaultGraphImpl.findCycle(Graph.scala:264)

Also see akka/akka#16109

The page http://www.scala-graph.org/guides/core-initializing.html isn't rendering properly on debian 8 + chrome

I ran into this with a unit test recently which should have failed but did not.

In the Scala console:

scala> Graph("a"~"b"%1) == Graph("a"~"b"%2)
res6: Boolean = true

This is quite surprising! I wouldn't consider those two graphs equal, since their edges have different weights.

Is there a way to compare two graphs for equality, including the weights?

cc @ryan-williams

The graph difference operation only finds missing nodes between two graphs, but not missing edges. See the following REPL session with the latest git version of Graph-core.

scala> val g1 = Graph(1,2,3, 2~3)
g1: scalax.collection.Graph[Int,scalax.collection.GraphEdge.UnDiEdge] = Graph(1, 2, 3, 2~3)

scala> val g2 = Graph(1,2,3, 2~3, 1~2)
g2: scalax.collection.Graph[Int,scalax.collection.GraphEdge.UnDiEdge] = Graph(1, 2, 3, 1~2, 2~3)

scala> g2 diff g1 // Should return Graph(1~2)
res11: scalax.collection.Graph[Int,scalax.collection.GraphEdge.UnDiEdge] = Graph()

Using the package graph-core_2.10 version 1.6.1, a call to Graph(1 ~> 2, "a" ~> 2) fails to add the node 1 to the graph. See the following excerpt from a REPL session. "res13" is the one that failed. The other three calls work as expected.

import scalax.collection.Graph
import scalax.collection.GraphPredef._
import scalax.collection.GraphEdge._

scala> Graph(1 ~> 2)
res11: scalax.collection.Graph[Int,scalax.collection.GraphEdge.DiEdge] = Graph(1, 2, 1~>2)

scala> Graph("a" ~> 2)
res12: scalax.collection.Graph[Any,scalax.collection.GraphEdge.DiEdge] = Graph(2, a, a~>2)

scala> Graph(1 ~> 2, "a" ~> 2)
res13: scalax.collection.Graph[Any,scalax.collection.GraphEdge.DiEdge] = Graph(2, a, 1~>2, a~>2)

scala> Graph(1 ~> 2, 3 ~> 2)
res14: scalax.collection.Graph[Int,scalax.collection.GraphEdge.DiEdge] = Graph(1, 2, 3, 1~>2, 3~>2)

Hi,

Is it possible to map scala-graph to scala-js lib?
Is there any usage of reflection or java dependency in it?

thanks

I generate a digraph using Mrecord shapes.
This is the last line of my edgeTransformer function:

Some(root, DotEdgeStmt(sFrom, sTo, attrs))

All my Mrecord nodes have a unique ID. Quotation marks are added around the connections and IMHO it should not. Nodes are not found. If I remove them, the diagram is generated correctly.

"003:01" -> "002:00" [label = "bool->bool"]
// Works with 003:01 -> 002:00 [label = "bool->bool"]

003  [label = "{{}|Not [3]\nNOT gate|{<01>out\n}}"]
001  [label = "{{}|Constant [1]\nconstant generator\n(true)|{<00>out\n}}"]

See the digraph structs file from the official documentation.
Any idea ?

Tested with Scala 2.11.1, graph and dot version 1.9.0.