You can subscribe to this list here.
2003 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(2) 
_{Nov}

_{Dec}


2004 
_{Jan}
(1) 
_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}
(1) 
_{Jul}
(1) 
_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(2) 
2005 
_{Jan}

_{Feb}
(1) 
_{Mar}
(5) 
_{Apr}
(1) 
_{May}

_{Jun}
(12) 
_{Jul}
(6) 
_{Aug}
(7) 
_{Sep}
(2) 
_{Oct}

_{Nov}
(1) 
_{Dec}

2006 
_{Jan}
(4) 
_{Feb}
(3) 
_{Mar}
(2) 
_{Apr}
(3) 
_{May}
(6) 
_{Jun}
(2) 
_{Jul}
(3) 
_{Aug}
(12) 
_{Sep}
(6) 
_{Oct}
(3) 
_{Nov}
(12) 
_{Dec}

2007 
_{Jan}
(6) 
_{Feb}

_{Mar}
(6) 
_{Apr}
(8) 
_{May}
(2) 
_{Jun}
(8) 
_{Jul}
(2) 
_{Aug}
(3) 
_{Sep}
(7) 
_{Oct}
(3) 
_{Nov}

_{Dec}
(1) 
2008 
_{Jan}
(11) 
_{Feb}
(4) 
_{Mar}
(8) 
_{Apr}
(3) 
_{May}
(4) 
_{Jun}
(1) 
_{Jul}

_{Aug}
(3) 
_{Sep}
(1) 
_{Oct}
(4) 
_{Nov}
(5) 
_{Dec}
(5) 
2009 
_{Jan}
(3) 
_{Feb}
(12) 
_{Mar}
(14) 
_{Apr}
(9) 
_{May}
(8) 
_{Jun}
(1) 
_{Jul}
(4) 
_{Aug}
(10) 
_{Sep}

_{Oct}
(10) 
_{Nov}

_{Dec}
(4) 
2010 
_{Jan}
(9) 
_{Feb}
(16) 
_{Mar}
(14) 
_{Apr}
(19) 
_{May}
(1) 
_{Jun}
(3) 
_{Jul}
(17) 
_{Aug}
(9) 
_{Sep}
(4) 
_{Oct}
(4) 
_{Nov}
(11) 
_{Dec}
(8) 
2011 
_{Jan}
(10) 
_{Feb}
(11) 
_{Mar}
(10) 
_{Apr}
(14) 
_{May}
(6) 
_{Jun}
(8) 
_{Jul}
(9) 
_{Aug}
(11) 
_{Sep}
(13) 
_{Oct}
(7) 
_{Nov}
(9) 
_{Dec}
(1) 
2012 
_{Jan}
(5) 
_{Feb}
(14) 
_{Mar}
(4) 
_{Apr}
(25) 
_{May}
(18) 
_{Jun}
(18) 
_{Jul}
(3) 
_{Aug}
(6) 
_{Sep}
(3) 
_{Oct}
(16) 
_{Nov}
(5) 
_{Dec}
(12) 
2013 
_{Jan}
(1) 
_{Feb}
(6) 
_{Mar}
(14) 
_{Apr}
(34) 
_{May}
(9) 
_{Jun}
(3) 
_{Jul}
(8) 
_{Aug}

_{Sep}
(10) 
_{Oct}
(11) 
_{Nov}
(11) 
_{Dec}
(15) 
2014 
_{Jan}
(2) 
_{Feb}
(6) 
_{Mar}
(11) 
_{Apr}
(12) 
_{May}
(6) 
_{Jun}
(7) 
_{Jul}

_{Aug}
(4) 
_{Sep}
(1) 
_{Oct}
(1) 
_{Nov}
(5) 
_{Dec}
(6) 
2015 
_{Jan}
(15) 
_{Feb}
(4) 
_{Mar}
(7) 
_{Apr}
(8) 
_{May}
(1) 
_{Jun}
(18) 
_{Jul}
(27) 
_{Aug}
(13) 
_{Sep}
(4) 
_{Oct}
(8) 
_{Nov}
(7) 
_{Dec}
(6) 
2016 
_{Jan}
(4) 
_{Feb}
(5) 
_{Mar}

_{Apr}
(15) 
_{May}
(5) 
_{Jun}
(4) 
_{Jul}
(1) 
_{Aug}
(1) 
_{Sep}
(7) 
_{Oct}
(2) 
_{Nov}
(4) 
_{Dec}
(2) 
2017 
_{Jan}
(7) 
_{Feb}
(1) 
_{Mar}
(17) 
_{Apr}
(2) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(3) 
_{Sep}
(3) 
_{Oct}

_{Nov}
(5) 
_{Dec}

S  M  T  W  T  F  S 





1
(1) 
2
(2) 
3

4
(2) 
5
(2) 
6
(2) 
7

8

9

10

11

12

13
(2) 
14

15
(4) 
16

17

18

19

20
(1) 
21
(2) 
22

23

24

25

26

27
(1) 
28

29

30


From: John V. Sichi <jsichi@gm...>  20100427 05:16:08

Done. Rather than making the data members protected, I added protected accessor methods. And rather than biasing from V to E, I used the generic parameter T :) JVS André wrote: > http://n3.nabble.com/file/n739340/UnionFind.java UnionFind.java > > Hi, > > I attached the UnionFind.java with the small changes I made to it. > > Can someone check this in, please? > > André 
From: André <akreienbring@on...>  20100421 07:48:18

http://n3.nabble.com/file/n739340/UnionFind.java UnionFind.java Hi, I attached the UnionFind.java with the small changes I made to it. Can someone check this in, please? André  View this message in context: http://n3.nabble.com/ConnectedComponentLabelingwithunionfinddatastructuretp721453p739340.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: John V. Sichi <jsichi@gm...>  20100421 05:09:52

Thanks Andre. For connected components specifically of graphs, we already have ConnectivityInspector, but if someone needs the generic connected component labeling via unionfind as a helper algorithm in some new class, they can incorporate the code you posted here. JVS André wrote: > I extended the existing UnionFind class to use it for the labeling of > connected components. > > Therefore I made the two maps visible for subclasses and added an empty > constructor. > > As I can not decide if such an extension is useful for jgrapht I'll post my > code here for anybody who might have similar needs: > > /** > * Supports the creation of the classical twopass algorithm for finding > connected components. > * An example of this algorithm for the application in image systems can be > found here: > * http://en.wikipedia.org/wiki/Connected_Component_Labeling Wikipedia > Connected Component Labeling > * > * The implementation uses an <code>UnionFind</code> data structure. > * @author André Kreienbring > * @since Apr 17, 2010 > */ > public class ComponentConnector<E> extends UnionFind<E>{ > > /** > * Creates an instance with all of the elements in > * separate sets. > * @param elements A <code>Set</code> of elements > */ > public ComponentConnector(Set<E> elements) > { > super(elements); > } > > /** > * Creates an instance without any initial elements > */ > public ComponentConnector(){ > super(); > } > > /** > * Finds the label of the smallest element from the list of given elements > and then > * labels the given element with this label. > * > * After that all other elements from the list are united with the minimum > element. > * @param element This element is labeled with the minimum label from the > connected elements > * @param connectedElements A <code>List</code> of elements that are > connected with the given element. > */ > public void uniteConnected(E element, List<E> connectedElements){ > //assign the current pixel to the minimum label > E minElement = getMinimumLabel(connectedElements); > this.setLabel(element, minElement); > > //unite the nonminimum labels > for(E label : connectedElements){ > if(label != minElement){ > super.union(minElement, label); > } > } > } > > /** > * Get an iterator over all elements that were added before. > * It is intended that find() is called for every key to get it's > representing element. > * Keys with the same representing element belong to the same component. > * @return An iterator that can be used to iterate over all elements. > */ > public Iterator<E> iterator(){ > return super.parentMap.keySet().iterator(); > } > > > /** > * Associate (connect) element1 with element2. > * Before the two elements are connected the upmost parent from element2 is > looked up to keep the tree structure flat. > * If element1 is not in the internal set, then it is created. > * @param element1 The element that is connected to element2 > * @param element2 element1 is connected to this element. > * @throws IllegalArgumentException if element2 does not exist. > */ > private void setLabel(E element1, E element2){ > if(!super.parentMap.containsKey(element2)){ > throw new IllegalArgumentException("parent label does not exist"); > } > > //try to find the parent of the new parent for a flat structure > E parent = find(element2); > > //return if the element equals the actual parent > if(element1.equals(parent)  > element1.equals(super.parentMap.get(parent))){ > return; > } > > //remove the element if it exists > if(super.parentMap.containsKey(element1)){ > super.parentMap.remove(element1); > super.rankMap.remove(element1); > } > > //and put it back in the list while maintaining the rank. > int rank = super.rankMap.get(parent); > super.parentMap.put(element1, parent); > super.rankMap.put(element1, rank + 1); > } > > > /** > * Given a list of elements this method finds the one with the lowest rank > * @param elements A <code>List</code> of Elements > * @return The element with the lowest rank > */ > private E getMinimumLabel(List<E> elements){ > int minimum = Integer.MAX_VALUE; > E minElement = null; > for(E element : elements){ > int rank = super.rankMap.get(element); > > if(rank < minimum){ > minimum = rank; > minElement = element; > } > } > > return minElement; > } > > } > André wrote: >> Ok... found it. >> >> I just got the latest version from trunk and there it is! >> >> I'll check it out and report if it can be used for that component labeling >> purpose. >> >> Thanks. >> > 
From: André <akreienbring@on...>  20100420 07:03:27

I extended the existing UnionFind class to use it for the labeling of connected components. Therefore I made the two maps visible for subclasses and added an empty constructor. As I can not decide if such an extension is useful for jgrapht I'll post my code here for anybody who might have similar needs: /** * Supports the creation of the classical twopass algorithm for finding connected components. * An example of this algorithm for the application in image systems can be found here: * http://en.wikipedia.org/wiki/Connected_Component_Labeling Wikipedia Connected Component Labeling * * The implementation uses an <code>UnionFind</code> data structure. * @author André Kreienbring * @since Apr 17, 2010 */ public class ComponentConnector<E> extends UnionFind<E>{ /** * Creates an instance with all of the elements in * separate sets. * @param elements A <code>Set</code> of elements */ public ComponentConnector(Set<E> elements) { super(elements); } /** * Creates an instance without any initial elements */ public ComponentConnector(){ super(); } /** * Finds the label of the smallest element from the list of given elements and then * labels the given element with this label. * * After that all other elements from the list are united with the minimum element. * @param element This element is labeled with the minimum label from the connected elements * @param connectedElements A <code>List</code> of elements that are connected with the given element. */ public void uniteConnected(E element, List<E> connectedElements){ //assign the current pixel to the minimum label E minElement = getMinimumLabel(connectedElements); this.setLabel(element, minElement); //unite the nonminimum labels for(E label : connectedElements){ if(label != minElement){ super.union(minElement, label); } } } /** * Get an iterator over all elements that were added before. * It is intended that find() is called for every key to get it's representing element. * Keys with the same representing element belong to the same component. * @return An iterator that can be used to iterate over all elements. */ public Iterator<E> iterator(){ return super.parentMap.keySet().iterator(); } /** * Associate (connect) element1 with element2. * Before the two elements are connected the upmost parent from element2 is looked up to keep the tree structure flat. * If element1 is not in the internal set, then it is created. * @param element1 The element that is connected to element2 * @param element2 element1 is connected to this element. * @throws IllegalArgumentException if element2 does not exist. */ private void setLabel(E element1, E element2){ if(!super.parentMap.containsKey(element2)){ throw new IllegalArgumentException("parent label does not exist"); } //try to find the parent of the new parent for a flat structure E parent = find(element2); //return if the element equals the actual parent if(element1.equals(parent)  element1.equals(super.parentMap.get(parent))){ return; } //remove the element if it exists if(super.parentMap.containsKey(element1)){ super.parentMap.remove(element1); super.rankMap.remove(element1); } //and put it back in the list while maintaining the rank. int rank = super.rankMap.get(parent); super.parentMap.put(element1, parent); super.rankMap.put(element1, rank + 1); } /** * Given a list of elements this method finds the one with the lowest rank * @param elements A <code>List</code> of Elements * @return The element with the lowest rank */ private E getMinimumLabel(List<E> elements){ int minimum = Integer.MAX_VALUE; E minElement = null; for(E element : elements){ int rank = super.rankMap.get(element); if(rank < minimum){ minimum = rank; minElement = element; } } return minElement; } } André wrote: > > Ok... found it. > > I just got the latest version from trunk and there it is! > > I'll check it out and report if it can be used for that component labeling > purpose. > > Thanks. >  View this message in context: http://n3.nabble.com/ConnectedComponentLabelingwithunionfinddatastructuretp721453p731535.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: André <akreienbring@on...>  20100415 18:45:18

Ok... found it. I just got the latest version from trunk and there it is! I'll check it out and report if it can be used for that component labeling purpose. Thanks.  View this message in context: http://n3.nabble.com/ConnectedComponentLabelingwithunionfinddatastructuretp721453p722008.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: Tom Conerly <theycallhimtom@gm...>  20100415 17:20:16

Hey, There is an implementation of union find in Jgrapht (see src/org/jgrapht/alg/util/UnionFind.java) that has all the functionality you need. It is an implementation of this algorithm: http://en.wikipedia.org/wiki/Union_find. Hope that helps. Tom On Thu, Apr 15, 2010 at 11:29 AM, André <akreienbring@...> wrote: > > I wonder if jgrapht can help with this task: > > I want to implement connected component labeling as described here: > http://en.wikipedia.org/wiki/Connected_Component_Labeling > http://en.wikipedia.org/wiki/Connected_Component_Labeling > > The proposed twopass algo uses a unionfind datastructure that provides > the > following functions: > > The first pass finds connected components following this rule: >  if you find an unconnected component generate a new label and store it in > the datastructure. > >  if the component is connected to one or more other components label it > with the smallest label of the other components and also store the > equivalenz to all the connected components in the datastructure. > > Thinking of a hirarchical structure like a tree, the latter woul mean: > union > / merge the trees of both components. > > Finally, during the second pass the stored equivalences are resolved. > > Again, thinking of a hirarchical structure that means that every label > resulting from pass one is replaced by the root of the component tree. > > For me that sounds as if some intelligent implementation could speed things > up. > In particular the >  union >  find >  min > functions... > > I looked at the fibonacci heap and thought about storing > SimpleDirectedGraph > in it but I can't figure it out completely. > > Maybe anybody worked on such a task before? > > André > > >  > View this message in context: > http://n3.nabble.com/ConnectedComponentLabelingwithunionfinddatastructuretp721453p721453.html > Sent from the jgraphtusers mailing list archive at Nabble.com. > > >  > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and finetune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intelswdev > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: André <akreienbring@on...>  20100415 15:29:49

I wonder if jgrapht can help with this task: I want to implement connected component labeling as described here: http://en.wikipedia.org/wiki/Connected_Component_Labeling http://en.wikipedia.org/wiki/Connected_Component_Labeling The proposed twopass algo uses a unionfind datastructure that provides the following functions: The first pass finds connected components following this rule:  if you find an unconnected component generate a new label and store it in the datastructure.  if the component is connected to one or more other components label it with the smallest label of the other components and also store the equivalenz to all the connected components in the datastructure. Thinking of a hirarchical structure like a tree, the latter woul mean: union / merge the trees of both components. Finally, during the second pass the stored equivalences are resolved. Again, thinking of a hirarchical structure that means that every label resulting from pass one is replaced by the root of the component tree. For me that sounds as if some intelligent implementation could speed things up. In particular the  union  find  min functions... I looked at the fibonacci heap and thought about storing SimpleDirectedGraph in it but I can't figure it out completely. Maybe anybody worked on such a task before? André  View this message in context: http://n3.nabble.com/ConnectedComponentLabelingwithunionfinddatastructuretp721453p721453.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: André <akreienbring@on...>  20100415 14:49:55

First of all: thank you for answering. I was not aware of the answer as i just sent the mail to the mailing list that time and never got any feedback... That time I even had not subsribed to the list. Don't know why it was submitted to be honest... Anyway: In the mean time I found the following aproach that works for me: I use a ClosestFirstIterator and whenever it comes to an endVertex I find the (shortest) path (edgeList) from that vertex to the source. I get the average length (cost) of that path with iterator.getShortestPathLength(endVertex) / edgeList.size(). When the iteration is done I keep the smallest avarage cost as the result... I think this is more or less what you described with you hints. BTW: It's not a school assingment :) André  View this message in context: http://n3.nabble.com/DijkstraFloydWarshallorEdmondstp696330p721340.html Sent from the jgraphtusers mailing list archive at Nabble.com. 
From: Nick Wiggill <nick.wiggill@gm...>  20100413 13:17:59

Never mind. I found the answer here<http://n3.nabble.com/Accessingnodeswhileiteratingongraphtd107901.html#a107903>; . On 13 April 2010 12:12, Nick Wiggill <nick.wiggill@...> wrote: > Hi > > Using BreadthFirstIterator, how do I get the immediate predecessor/parent > vertex to the one I'm currently visiting? I can set up a client class > to listen for traversal events, but I can't see how to find the immediate > predecessor. (Note, I don't want to subclass BreadthFirstIterator to do > this). > > TIA, > >  > Nick Wiggill > http://www.handcraftedgames.net >  Nick Wiggill http://www.handcraftedgames.net 
From: Nick Wiggill <nick.wiggill@gm...>  20100413 11:12:47

Hi Using BreadthFirstIterator, how do I get the immediate predecessor/parent vertex to the one I'm currently visiting? I can set up a client class to listen for traversal events, but I can't see how to find the immediate predecessor. (Note, I don't want to subclass BreadthFirstIterator to do this). TIA,  Nick Wiggill http://www.handcraftedgames.net 
From: Jonathan Cederberg <jonathan.cederberg@it...>  20100406 06:44:41

I am pretty certain that the definition of a backedge, if there is a canonical such definition, is relative. Therefore your question is rather incomplete. Anyway, there is no such functionality that I know of in the lib. In general, the implemented algorithms are the most well known and widely used ones. This makes a standard reference book on graph algorithms, such as CLRS, a very good starting point to find a solution. Regards Jonathan On 6 apr 2010, at 07.24, dinesh chhatani wrote: > Hi, > I want to know whether a particular edge is a backedge or not(loop).How can I get that > >  > Regards, > Dinesh Chhatani >  > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and finetune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intelswdev_______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers 
From: dinesh chhatani <dinustudy@gm...>  20100406 05:24:36

Hi, I want to know whether a particular edge is a backedge or not(loop).How can I get that  Regards, Dinesh Chhatani 
From: dinesh chhatani <dinustudy@gm...>  20100405 11:57:50

for a DirectedMultiGraph , Input : 2 vertices what I want?(Output) All the paths between those two vertices(if there is a backedge tthere are more than one path) so I want all of them.  Regards, Dinesh Chhatani 
From: Joris Kinable <deus87@gm...>  20100405 10:58:51

Hey, If I understand you correctly, you are not looking for the cheapest path, which is provided by Dijkstra's algorithm, nor are you interested in finding the shortest path to each vertex (FloydWarshall). What you do want to find is the path with the lowest average cost, where the average cost is defined as: sum the cost of all edges in the path and divide by the number of edges. As you conclude yourself, this is not necessary the shortest path. Take for example the following two paths from source to a sink: Path 1: cost: 4, length 1 Path 2: cost: 5, length 2 Obviously, the cheapest path is Path 1, but the path with the lowest average edge cost is Path 2. There is an easy way to implement this, but not with branch and bound (because you cannot bound), using a modified version of Dijkstra's shortest path algorithm. Since this looks like a school assignment, I'm not going to give you a final solution, but I can give you some hints. Have a look at the pseudo code of Dijkstra's shortest path: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm As you can see, this algorithm tries to find the shortest path from a source to any destination. As soon as the target destination is found, the algorithm terminates. So what you have to do is alter the implementation of Dijkstra's algorithm a bit as follows: 1. In the original Dijkstra, the distance d(u,v) from vertex u to v, equals the sum of the edge cost in the path from u to v. You have to change this path cost to the average path cost, which is the sum of the edge cost in the path from u to v divided by the path length. 2. You have to continue the algorithm until the entire graph has been explored. You cannot stop once you have found the first sink (think about this: bounding is not possible)! As soon as the entire graph has been explored, you simply iterate over your sinks, until you have found the one with the lowest average cost. Hope this helps, br, Joris On Sun, Apr 4, 2010 at 1:10 PM, André Kreienbring <akreienbring@...> wrote: > Hello, > > I would apreciate some help with using jgrapht. > > Here's my task: > > I have created a acyclic SimpleDirectedWeightedGraph where the edge weights > can be interpreted as cost to visit the target vertex. > > The graph has a single source and several sinks. Usually there are several > hundred vertices in the graph. > > Now I want to find the path from the source to a sink vertex that produces > the minimum average cost. > > That is not necessarily the shortest path, I think it is the path where the > sum of all weights divided by the length of the path is minimized. > > However, i first used Dijkstras algorithm to solve the problem. For every > sink vertex i get the (Dijkstra) shortest path from source to sink and > calculate the minimum costs by inspecting the edge list of the path. > > I compared that solution to the FloydWarshall algorithm. In contrast to > Dijkstra it finds the shortest path's between ALL vertices of the whole tree > in one flow. The minimum cost must still be found by inspecting the > resulting edge list of every shortest path from source to sink. > > The result of the comparison seems obvious. FloydWarshall is faster > than Dijkstra if only a few vertices are in the tree. The advantage of using > Dijkstra: I only need to calculate the path's from source to sink. > > BUT: I think there must be a much better way to solve this kind of problem. > In fact this seems to be a 'optimum branching' problem as described here: > http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm > > Am I right? What is the best way to solve this by using jgrapht? > > Thanks in advance, > > André > >  > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and finetune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intelswdev > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > 
From: John V. Sichi <jsichi@gm...>  20100404 18:13:14

We don't currently supply an algorithm which enumerates all the cycles. Keep in mind that for a complete graph with n nodes, there are n! different cycles, so that enumeration could take a looooong time. JVS Rui Chang wrote: > Hi all, > I am a newbie in using JGraphT. So, please forgive me if my question is > too easy. > I have a directed graph containing many cycles, and I'd like to use > JGraphT to find all these cycles (nodes in the cycle) in this directed > graph. I am now trying to use the class: StrongConnectivityInspector and > its methods: stronglyConnectedSubgraphs. However, it will not return all > cycles. > > Is there a way to use any class in JGraphT to find all cycles? > > Thanks! > Rui > >  > The New Busy is not the old busy. Search, chat and email from your > inbox. Get started. > <http://www.windowslive.com/campaign/thenewbusy?ocid=PID27925::T:WLMTAGL:ON:WL:enUS:WM_HMP:032010_3>; > > >  > >  > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and finetune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intelswdev > > >  > > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers 
From: André Kreienbring <akreienbring@on...>  20100404 11:11:14

Hello, I would apreciate some help with using jgrapht. Here's my task: I have created a acyclic SimpleDirectedWeightedGraph where the edge weights can be interpreted as cost to visit the target vertex. The graph has a single source and several sinks. Usually there are several hundred vertices in the graph. Now I want to find the path from the source to a sink vertex that produces the minimum average cost. That is not necessarily the shortest path, I think it is the path where the sum of all weights divided by the length of the path is minimized. However, i first used Dijkstras algorithm to solve the problem. For every sink vertex i get the (Dijkstra) shortest path from source to sink and calculate the minimum costs by inspecting the edge list of the path. I compared that solution to the FloydWarshall algorithm. In contrast to Dijkstra it finds the shortest path's between ALL vertices of the whole tree in one flow. The minimum cost must still be found by inspecting the resulting edge list of every shortest path from source to sink. The result of the comparison seems obvious. FloydWarshall is faster than Dijkstra if only a few vertices are in the tree. The advantage of using Dijkstra: I only need to calculate the path's from source to sink. BUT: I think there must be a much better way to solve this kind of problem. In fact this seems to be a 'optimum branching' problem as described here: http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm Am I right? What is the best way to solve this by using jgrapht? Thanks in advance, André 
From: Arun Iyer <aruniyer@ym...>  20100402 21:18:11

Hi John, Thanks for the reply. I will try to see if I can give a rigid test case. I will get back to you, when I have a good test case with me :). Regards, Arun  On Mon, 3/22/10, John V. Sichi <jsichi@...> wrote: From: John V. Sichi <jsichi@...> Subject: Re: [jgraphtusers] KShortest Path implementation To: "Arun Iyer" <aruniyer@...> Cc: jgraphtusers@... Date: Monday, March 22, 2010, 4:20 PM Arun Iyer wrote: > Hi, > I am using JGraphT's KShortestPath implementation. In the code that I have, I have to create a new graph for every run and compute KShortestPath on it. I find that KShortestPath gives the right answers almost all the time, but sometimes, it doesn't give the right answers (on the same graph on which it gave the right answer before). I was wondering, why is this nondeterministic? Is there threading involved (either in graph creation or in kshortestpath computation) ? It does not use threading. It does use HashMaps, which can result in nondeterminism in cases where ordering is arbitrary. It would help if you can provide a small isolated test case which can be run repeatedly in order to reproduce your problem reliably. Without that, it's impossible to find and fix it. JVS 
From: Rui Chang <chang.rui@ho...>  20100402 02:41:37

Hi all, I am a newbie in using JGraphT. So, please forgive me if my question is too easy. I have a directed graph containing many cycles, and I'd like to use JGraphT to find all these cycles (nodes in the cycle) in this directed graph. I am now trying to use the class: StrongConnectivityInspector and its methods: stronglyConnectedSubgraphs. However, it will not return all cycles. Is there a way to use any class in JGraphT to find all cycles? Thanks!Rui _________________________________________________________________ The New Busy is not the old busy. Search, chat and email from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID27925::T:WLMTAGL:ON:WL:enUS:WM_HMP:032010_3 
From: dinesh chhatani <dinustudy@gm...>  20100401 04:50:32

For a given vertex ,if I want to know all the possible ways(paths) to reach that vertex? how can I get that. There may be more than one way to reach a particular vertex in a DirectedMultiGraph.so how can I get all Waiting for a quick answer Thanks  Regards, Dinesh Chhatani 