Transitive edges

Daniel Sobral

unread,

Feb 25, 2020, 1:28:30 PM2/25/20

to scala-graph

I'm new to Scala Graph and, so far, I'm rather impressed by its API. I'm trying to figure out a way of identifying if two directly connected nodes are also transitively connected. Is there anything that would help me with that?

Peter Empen

unread,

Feb 26, 2020, 9:16:23 AM2/26/20

to scala-graph

Hi Daniel,

I'm not sure what you mean by "transitively connected nodes". Are you referring to the transitive closure of a graph or something else?

If so you won't find direct support for it. What we can do is to find out how to get the desired result once the definition is clear.

It might also help if you posted an example.

Peter

Daniel Sobral

unread,

Feb 26, 2020, 12:50:41 PM2/26/20

to Peter Empen, scala-graph

I think "tred" (from graphviz) might be the best example of what I'm talking about. But let's say I have Graph(1 ~> 2, 2 ~> 3, 3 ~> 4, 1 ~> 3). Node 1 is directly connected to both 2 and 3 but not 4, and transitively connected to 3 and 4 but not 2.

Right now I'm doing this:

def isTrans(src: String, dst: String) = graph.get(src).innerNodeTraverser.withSubgraph(edges = _ != graph.get(src ~> dst)).hasSuccessor(graph.get(dst))

--

Daniel C. Sobral

--
You received this message because you are subscribed to the Google Groups "scala-graph" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-graph...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/scala-graph/00b9e0b9-c4a8-4369-8452-93ca26a25d15%40googlegroups.com.

Peter Empen

unread,

Mar 1, 2020, 4:14:03 AM3/1/20

to scala-graph

We have no direct support for this. What you are doing is fine. I'd brush it up a little to

be generic with respect to multi edges and
use path-dependent types rather than get and check lookup results or any other preconditions beforehand

like

def transitivelyReachable(src: graph.NodeT, dst: graph.NodeT): Boolean =
 src outgoingTo dst pipe { toExclude =>
   src.innerNodeTraverser.withSubgraph(edges = !toExclude.contains(_)) hasSuccessor dst
 }