Graph algorithms

[YorT]

Hi Guys,

Are there any good places to read up on graph algorithms? (which are explained for simple people like myself :-)

I am hitting a brick wall with a part of a project I am working on and I believe there should be a graph algorithm out there which can handle the query I want to put together, however I have no idea the name of it so cant search for it.

The issue I am running into is around a weighted (negative and positive), possible self referencing, vertex problem, where I would like to find all possible paths or single path along the way. (I am sure I have just described every possible graph algo out there)

Any directions would be appreciated.

Cheers

YorT/Troy

[Marko A. Rodriguez]

HI Yort,

Are there any good places to read up on graph algorithms? (which are explained for simple people like myself :-)

My favorite book on network/graph analysis is:

http://www.amazon.com/Network-Analysis-Methodological-Foundations-Theoretical/dp/3540249796/ref=pd_sim_b_42

The issue I am running into is around a weighted (negative and positive), possible self referencing, vertex problem, where I would like to find all possible paths or single path along the way. (I am sure I have just described every possible graph algo out there)

Djikstras (though it doesn't work for negative weighted graphs)

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

Floyd Warshall 

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

HTH,

Marko.

http://markorodriguez.com

[Daniel Quest]

Marko, 

I really enjoy it when you post reading recommendations.  Flow Based Programming was a great read!

Got a copy of this one too!

Dan

Sent from my iPad

--
 
 

[Marko A. Rodriguez]

Hey,

> I really enjoy it when you post reading recommendations. Flow Based Programming was a great read!
> Got a copy of this one too!

Cool. Good books are good.

Marko.

[YorT]

Hi Marko,

I have had a look into my problem a bit more and it sounds like it is going to be a clique based problem (http://en.wikipedia.org/wiki/Clique_problem)

Do you have any advice on how I should go about handling such an algorithm in a graph database?

This is seriously testing my math capacity as it is, anything to make it simpler or maybe change the problem would be appreciated.

Thanks

YorT

[ecniv]

Hi there,

A maximum clique detection algotrithm is available in JGraphT, so if you don't feel reimplementing this algorithm yourself, you could do something similar to the JUNG outplementation of blueprints, i.e. implementing a JGraphT graph that would wrap a Blueprints Graph. This would involve a bit of coding but nothing really challenging in terms of algorithms / math.

This way, you will be able to apply any algorithm from JGraphT on any Blueprints graph, keeping in mind that JGraphT is memory-based: the clique algorithm of JGraphT for example, as far as I remember, stores all vertices in a list, which means that it will be difficult to apply it on a large graph database,

Vincent

[YorT]

Thanks Vincent, good find, ill look into this.

--
 
 

[SeH]

Here is an experimental and untested fork of JGraphT like you've described:
https://github.com/automenta/jgrapht

I just committed it and decided to search the mailing list for JGraphT and your message was the only one.  It is similar to your explanation except I've modified the JGraphT root interfaces to provide new Iterator methods using Java 8 default methods.  In the subclasses which use the Set methods, I override these to reverse the flow, calling set.iterator() so they are unaffected by this change.  There may be parts of JGraphT like certain wrapper classes and generators which do not depend on a Set which could run more efficiently without instantiating Collections.  The vertexSet and edgeSet methods still rely on Set's at this point, but can be modified in the same way to make it Collection-less.  The next step would be to cleanly separate the Collection methods into a subinterface so there is no confusion.  A further separation into read-only and mutable graphs might also apply.

After this, the Blueprints WrapperGraph interface was straightforward to add.  But I haven't tested it yet.  However all of the original JGraphT unit tests still pass.

I used JUNG several years ago.  On a recent project needing fast in-memory graphs we decided on JGraphT since it's newer and seemed more active, with more included algorithms:

• https://github.com/jgrapht/jgrapht/tree/master/jgrapht-core/src/main/java/org/jgrapht/alg
• https://github.com/agouge/Java-Network-Analyzer (another JGraphT library with more algorithms)

Maybe we can switch to Blueprints TinkerGraph instead of JGraphT.  For example, this might be rewriteable as a Furnace vertex program:

• https://github.com/opennars/opennars/blob/graphplan1/nars_java/nars/inference/GraphExecutive.java#L152

Here's the original suggestion for a JUNG interface:

• https://groups.google.com/d/msg/gremlin-users/O_DxlNiz6ro/pdbSgZei1sEJ

Thanks!