jgrapht-users

[jgrapht-users] Accessing nodes while iterating on graph.

[Serge Prud'h. <ser...@ya...>]

Greetings,

I recently discovered JGraphT and I have the following problem.

I need to do a project management tool which means I have an acyclic directed graph holding the duration of each activity in each node and edges between nodes representing the dependencies between the actvities.

example:

TaskA
 duration=3
 
TaskB
 duration=4
 
TaskC
 duration=5
 
TaskD
  duration=6
  
TaskA --> TaskC
TaskB --> TaskC
 TaskC --> TaskD
 

I want to do a traversal of the graph and for each node update a "leadTime" member to each node indicating the minimum time for the availability of each task.  
The lead time can be expressed as follow: the maximum leadTime of all the direct ancestors + task duration.


TaskA
duration =3
 leadTime=3

TaskB
 duration =4
  leadTime=4
 
TaskC
 duration =5
  leadTime=4    =max(3, 4)
 
TaskD
  duration =5
   leadTime=9    =max(3, 4) + 5
  

A TopologicalOrderIterator seems like a good fit but I cannot figure out how to access the information from the previous node while iterating.  The TraversalListener seemed promissing but I don't see how to access the source and destination nodes from the EdgeTraversalEvent. 

Ideas?

Thanks

  Serge





 between 0000-00-00 and 9999-99-99        

Re: [jgrapht-users] Accessing nodes while iterating on graph.

[Jonathan M. <jon...@it...>]

Why don't you use Graphs.predecessorListOf or iterate through the set  
given by DirectedGraph.incomingEdgesOf and use getEdgeSource?

There might be complexity issues here, and in particular the former  
solution might not give the direct predecessors but just all  
predecessors. (Devs> Isn't there some ambiguity (flaw) in the docs  
here? The graph-theoretic def. of predecessors is those nodes from  
which the node is reachable, right?) But for any practical purpose, at  
least the latter solution would be feasible, I believe.

/Jonathan

15 apr 2008 kl. 23.52 skrev Serge Prud'homme:

>
> Greetings,
>
> I recently discovered JGraphT and I have the following problem.
>
> I need to do a project management tool which means I have an acyclic  
> directed graph holding the duration of each activity in each node  
> and edges between nodes representing the dependencies between the  
> actvities.
>
> example:
>
> TaskA
> duration=3
>
> TaskB
> duration=4
>
> TaskC
> duration=5
>
> TaskD
> duration=6
>
> TaskA --> TaskC
> TaskB --> TaskC
> TaskC --> TaskD
>
>
> I want to do a traversal of the graph and for each node update a  
> "leadTime" member to each node indicating the minimum time for the  
> availability of each task.
> The lead time can be expressed as follow: the maximum leadTime of  
> all the direct ancestors + task duration.
>
>
> TaskA
> duration =3
> leadTime=3
>
> TaskB
> duration =4
> leadTime=4
>
> TaskC
> duration =5
> leadTime=4    =max(3, 4)
>
> TaskD
> duration =5
> leadTime=9    =max(3, 4) + 5
>
>
> A TopologicalOrderIterator seems like a good fit but I cannot figure  
> out how to access the information from the previous node while  
> iterating.  The TraversalListener seemed promissing but I don't see  
> how to access the source and destination nodes from the  
> EdgeTraversalEvent.
>
> Ideas?
>
> Thanks
>
>   Serge
>
>
>
>
> between 0000-00-00 and 9999-99-99   
> -------------------------------------------------------------------------
> This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
> Don't miss this year's exciting event. There's still time to save  
> $100.
> Use priority code J8TL2D2.
> http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone_______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Accessing nodes while iterating on graph.

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

Jonathan Mörndal wrote:
> There might be complexity issues here, and in particular the former  
> solution might not give the direct predecessors but just all  
> predecessors. (Devs> Isn't there some ambiguity (flaw) in the docs  
> here? The graph-theoretic def. of predecessors is those nodes from  
> which the node is reachable, right?) But for any practical purpose, at  
> least the latter solution would be feasible, I believe.

You're right, the documentation in Graphs needs refinement.  At a 
minimum, I will change the Javadoc to clarify that it's the direct 
predecessor/successor.

Beyond that, I could deprecate the methods (keeping them around for a 
few releases for backwards compatibility) and introduce new ones with 
longer names like directPredecessorListOf, but maybe in this case just 
clarifying the Javadoc is good enough?

JVS