Re: [jgrapht-users] Bounded out-degree digraphs

[John V. S. <js...@gm...>]

Hi Jonathan,

See this thread for the background:

http://sourceforge.net/mailarchive/forum.php?thread_name=000201c67294%241e41e8c0%240300a8c0%40neo&forum_name=jgrapht-developers

If you don't care about performance for random-access to successors, or 
if you can amortize by always accessing all of the successors together, 
then you can get away with no changes by using

Graphs.successorListOf(g, v)

For anything better, we would need to define the OrderableGraph 
interface mentioned in the thread above, and then implement it by 
exposing the (currently hidden) listiness in DirectedEdgeContainer via 
the corresponding List-based interfaces.

The way things are defined may seem silly if you only look at the 
in-memory graph representation, but if you consider that the Graph 
interface can be just as well implemented via SQL queries against a 
RDBMS schema, then it may make more sense (maintaining a deterministic 
edge ordering there might not be practical depending on the schema).

JVS

Jonathan Mörndal wrote:
> I'd like to use the JGraphT library as a basis for a prototype in my  
> research on pointer analysis for linked data structures, but I'd like  
> to tailor the implementation to fit my needs. Specifically, I'd like  
> to deal with digraphs that have at most k successors, and I'd like to  
> distinguish between successor 0, 1, 2 and so forth. Even more  
> specifically, I'd like to have a method getSuccessor(V vertex, int i)  
> that returns the i:th successor of vertex. I tried to prod about in  
> the AbstractBaseGraph, but I got lost in the DirectedEdgeContainer. As  
> I understand it, there is the place to extend to achieve my goal, but  
> incoming and outgoing are Sets, so how do I do this the best way?
> 
> Or is the way to go the extremely ugly one, namely using  
> DirectedWeightedGraph and just mine the outGoingEdges for the edge  
> with the correct weight (letting the weights symbolise the number of  
> the successor). It seems like such a sad abuse of an otherwise  
> extrordinary framework...
> 
> Regards
> Jonathan
>