Using the JUNG algorithm package in Gremlin

[Marko A. Rodriguez]

Hi everyone,

I've done some more work on connecting JUNG and Gremlin.

http://wiki.github.com/tinkerpop/gremlin/working-with-jung-algorithms

JUNG algorithms are intended for single-relational graphs (that is,
graphs with unlabeled edges). However, Gremlin was developed to
process multi-relational graphs (that is, graph with labeled edges).
Gremlin was intended to provide the expressibility of the path algebra
defined here http://arxiv.org/abs/0806.2274, but through graph
traversal techniques (not matrix techniques) (see http://arxiv.org/abs/0803.4355)
. While its possible to implement multi-relational graph algorithms in
Gremlin (as thats its intention), there is a wealth of existing
toolkits and packages that come with a rich set of algorithms (e.g.
JUNG).

Currently, I've been able to "trick" JUNG into ignoring certain edges
if desired. That is, for example, calculate PageRank over ONLY "knows"
edges (ignore all other edges). To be able to do more complicated path
expressions (e.g. calculate PageRank over "knows my friends friends"
"edges"), I think I have a technique to also "trick" JUNG into this.
Thus, when Pavel and I make functions and paths first class citizens
(a future release of Gremlin), I think it will be possible to
expression computations like this:

gremlin> $path := path co-developer
./outE[@label='created']/inV/inE[@label='created]/inV[g:except($_)]
end
gremlin> jung:pagerank($g, $path)

Take care,
Marko.

http://markorodriguez.com
http://gremlin.tinkerpop.com

P.S. Gremlin 0.2 is nearly ready for release. 0.2.x versions of
Gremlin will simply add more and more of the JUNG algorithms to Gremlin.

[S H]

Marko A. Rodriguez wrote:
> Hi everyone,
>
> I've done some more work on connecting JUNG and Gremlin.
>
> http://wiki.github.com/tinkerpop/gremlin/working-with-jung-algorithms
>
> JUNG algorithms are intended for single-relational graphs (that is,
> graphs with unlabeled edges). However, Gremlin was developed to
> process multi-relational graphs (that is, graph with labeled edges).
> Gremlin was intended to provide the

I'm using JUNG for graphs with labeled edges: I use any type of object
as my edge (making sure an effective hashCode() and proper equals()).
Please clarify what you mean.

> expressibility of the path algebra defined here
> http://arxiv.org/abs/0806.2274, but through graph traversal techniques

> (not matrix techniques) (see http://arxiv.org/abs/0803.4355). While

> its possible to implement multi-relational graph algorithms in Gremlin
> (as thats its intention), there is a wealth of existing toolkits and
> packages that come with a rich set of algorithms (e.g. JUNG).
>
> Currently, I've been able to "trick" JUNG into ignoring certain edges
> if desired. That is, for example, calculate PageRank over ONLY "knows"
> edges (ignore all other edges). To be able to do more complicated path
> expressions (e.g. calculate PageRank over "knows my friends friends"
> "edges"), I think I have a technique to also "trick" JUNG into this.
> Thus, when

Can't you use the Edge Predicate parameter to PageRank?

[Marko A. Rodriguez]

Hi,

I'm using JUNG for graphs with labeled edges: I use any type of object as my edge (making sure an effective hashCode() and proper equals()).  Please clarify what you mean.

Well yes---given that a JUNG graph is defined as Graph<V,E>, E can be anything. Thus, it can be something that has a "label". However, what I mean is that their graph algorithms do not account for edges labels---(though this is not completely true, read my next comment).

Can't you use the Edge Predicate parameter to PageRank?

You can use the edge transformer model provided with JUNG to yield weights for edges:

PageRank(Hypergraph<V,E> graph, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weight, double alpha)

In PageRank, the edge weight is the outgoing edge's probability and thus, must be less than 1.0 and the total outgoing edge weight must sum to 1.0 (note the normalize parameter in JUNG/Gremlin). However, you can "trick" JUNG to acknowledge edge labels by rending weights of 0.0 for edges whose labels you want to exclude. This works for PageRank. For Dijkstra's, edge weights represent distance. Thus, to ignore edges, you have to have the transformer yield a weight of Double.MAX_VALUE. Finally, all of this is only for a single edge (a transformer yields a number for an edge). How do you yield a number for a path traversal? This is where the transformer model breaks down --- though, I think (just in my head -- not worked out fully yet) I have a way to "trick" JUNG to allow for the computation of its algorithms over paths, not just single edges.

Take care,

Marko.

http://markorodriguez.com

http://linkedprocess.org

[S H]

>> I'm using JUNG for graphs with labeled edges: I use any type of
>> object as my edge (making sure an effective hashCode() and proper
>> equals()). Please clarify what you mean.
>
> Well yes---given that a JUNG graph is defined as Graph<V,E>, E can be
> anything. Thus, it can be something that has a "label". However, what
> I mean is that their graph algorithms do not account for edges
> labels---(though this is not completely true, read my next comment).

understood :) thanks for the explanation

[Giancarlo]

Hi Mark,

I have seen several posts on integrating libraries Jung with gremlin .

Since I would use a Hypergraph you think it is possible exploit the class Hypergraph Jung and integrate it with gremlin ?

Best regards,

Giancarlo

[Marko Rodriguez]

Hi,

That post about JUNG was from 2010. If my cells replace themselves every 7 years, then that person speaking in that email is not me.

Next, I don't know what you are trying to do. But you can always implement the Hypergraph API in JUNG against TinkerPop and see how it works for you --- i.e. what methods are possible, which are not, etc.

In other words, try and see.

Marko.

http://markorodriguez.com

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/ba3406eb-620f-444c-a8db-9595c2e3882d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.