Graph traversal and modifying edge properties

[Florent Empis]

Hi,

(I'm stuck in a waiting room so I started drawing a few ideas. I'll
report back later on the movie recommender thing)

Here my idea/problem

As you probably know, ants find their way to food by marking their
path. The more odor they smell, the busiest the road (the english word
is, i think pheromone).

I have a network of "ant cities" with roads between them. (They can go
from any city to any city directly)

I have spies in every city that tell me "1 ant walk from A to B". To
reflect that in my graph, I want to update the counter property of the
edge between vertice a and b.

I think that to do that I have to:
1. Find vertex A in the global graph ( i'll have about 10000 city vertices)
2. Get outgoing edges for vertex A and filter to find the one that
goes to B or create it if needed
3.Alter the property counter of the edge +1

Of course I could do it sequentially but I guess it wouldn't be efficient?
So I thought about traversing and modifying the graph all at once
using pipes, but for some reason I find that scary (coming from a
rdbms world...)

Second problem. Now I also want to remember for a few minutes (say,
15) that the ant going from a to b is ant x.
So that i can query the graph "where did ant x go in the last
15minutes" and get the answer "it went from a to b to c and when in c,
it entered the c' casino"

How would you model these data?

I could add a property "passingAnt" to each edge which is a list of
ants which is periodically cleaned by some process, but it would be
quite slow i guess
I could add a property "casino" to vertices to list all ants that got
into the casino, but the same remark applies.

So, i guess i have to have a vertex for each ant, but how would i
attach it to 2 city vertices? In uml, that would be a
composition/aggregate (i never remember the right name).

I think i'm also "perveted" by my background in petri nets, where one
of my CS professor invented "object tokens" where the tokens has
properties, methods. In a petri net with object tokens, the token
would be the ant....


I know my use case is a bit strange with ants going around and in
casinos, but i can't really explain my real world case. It's'basically
exactly that,except i'm not working with ants :p

Thanks!

Florent

2012/6/7, Alfredo Serafini <ser...@gmail.com>:
> Hi Marko reading twice the post i've notice that has been removed the pgm
> part... are there any plans to re-introduce support for some key-value
> storage or mongodb then?
> If i'm not wrong Titan too it's on a similat perspective? :-)
>
>
>
> Il giorno giovedì 7 giugno 2012 13:13:30 UTC+2, Marko A. Rodriguez ha
> scritto:
>>
>> Hi,
>>
>> There have been lots of confusions about Blueprints 2. Given that the API
>>
>> has changed so drastically, it is important that we outline what the major
>>
>> differences are. Moreover, this is something we should have provided the
>> community initially.
>>
>>
>> https://github.com/tinkerpop/blueprints/wiki/The-Major-Differences-Between-Blueprints-1.x-and-2.x
>>
>> This list was given off the top of my head. If you can think of anything
>> else I'm missing, please add a section and either write it up or tell me
>> so
>> I can write it up.
>>
>> Matthias, I left a blank on the transactional semantics section. Can you
>> please fill that out?
>>
>> Thanks everyone,
>> Marko.
>>
>> http://markorodriguez.com
>>
>>

--
Envoyé avec mon mobile

[Marko Rodriguez]

Hey,

One technique I would use to do this is to "modify" the graph as you walk.

g.v(1).out.sideEffect{it.counter++}.loop(...)
// do something with your counters
g.stopTransaction(FAILURE)

In this way, you only modify the graph in the transaction and when you fail, it all rollsback.

However, for "particle-based energy diffusion"-type algorithms (e.g. ant algorithms) that are local (i.e. not touching the entire graph), you can make use of an in-memory map of vertex->counter.

g.v(1).out.sideEffect{map[it]++}.loop(...)

Now everything you have touched is in the map and accessible in one location.

I didn't read the last part of your email... will do later.

Take care,
Marko.

http://markorodriguez.com

[Florent Empis]

Hi,

Sorry to bother you again with my questions but could you please take a look at the second part of my email?

Basically, I am wondering if I should model these data in two distinct data structures:

• One energy-diffusion graph for long term statistics
• Another data structure, graph or not, which list the last cities (and casino in cities) all the living ants have visited in the last 15 minutes

Conceptually, the data are exactly the same, only aggregated in part 1 and "personal" data in part 2.

As I said, I come from a Java background, so I'd be tempted to implement something like:

• Blueprint/Graph based for long term stats
• HashMap<Ant, List<City>> for short term, live data, with an automated 15min TTL on data

Would you, as experienced graph devs, do the same, or would you implement it both with graphs and, if so, all inside the very same graph?

BR,

Florent

2012/6/7 Marko Rodriguez <okram...@gmail.com>

[Stephen Mallette]

Florent,

The way you've described the problem makes it sound as though the "ants" themselves are not really part of the graph domain model.  Adding each ant as a vertex doesn't seem to fit your need.  Ants seem more like data in the system, in which case, updating their statistics within the context of the other graph elements or externalizing the statistics in a HashMap both seem to make more sense.  Of those two options, I think your idea for a HashMap<Ant, List<City>> sounds like a sensible way to do it (I'm assuming you have some mechanism by which you can construct that HashMap from your "spies" as it happens and then refresh the statistics ever 15 minutes as you want).    Seems like you're basically on the right track with your thinking.

Stephen

On Sunday, June 10, 2012 7:16:20 PM UTC-4, Florent Empis wrote:

Hi,

Sorry to bother you again with my questions but could you please take a look at the second part of my email?

Basically, I am wondering if I should model these data in two distinct data structures:

• One energy-diffusion graph for long term statistics
• Another data structure, graph or not, which list the last cities (and casino in cities) all the living ants have visited in the last 15 minutes

Conceptually, the data are exactly the same, only aggregated in part 1 and "personal" data in part 2.

As I said, I come from a Java background, so I'd be tempted to implement something like:

• Blueprint/Graph based for long term stats
• HashMap<Ant, List<City>> for short term, live data, with an automated 15min TTL on data

Would you, as experienced graph devs, do the same, or would you implement it both with graphs and, if so, all inside the very same graph?

BR,

Florent

2012/6/7 Marko Rodriguez

Hey,