jgrapht-users — JGraphT user list.

Re: [jgrapht-users] VertexLabelProvider, EdgeLabelProvider not called

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

Looks like you have to call setPrintLabels() first.

JVS

Oliver Schrenk wrote:
> Hi,
> 
> I have some trouble printing the labels using the GmlExporter, they are simply not called.
> 
> Any idea?
> 
> Best regards
> Oliver Schrenk
> 
> 
> public Network() {
> 		graph = new DirectedWeightedMultigraph<Node, Edge>(Edge.class);
> 		init();
> 	}
> 
> 	private void init() {
> 		Node previous = new Node(1, "label_1");
> 		Node current = new Node(2, "label_2");
> 
> 		graph.addVertex(previous);
> 		graph.addVertex(current);
> 		graph.addEdge(previous, current);
> 
> 	}
> 
> 	public void export() {
> 		GmlExporter<Node, Edge> exporter = new GmlExporter<Node, Edge>(
> 				new VertexIdProvider(), new VertexLabelProvider(),
> 				new EdgeIdProvider(), new EdgeLabelProvider());
> 		exporter.export(new BufferedWriter(new OutputStreamWriter(System.out)),
> 				(DirectedGraph<Node, Edge>) graph);
> 
> 	}
> 	
> 	class VertexIdProvider implements VertexNameProvider<Node> {
> 
> 		@Override
> 		public String getVertexName(Node node) {
> 			return Long.toString(node.getId());
> 		}
> 
> 	}
> 
> 	class VertexLabelProvider implements VertexNameProvider<Node> {
> 
> 		@Override
> 		public String getVertexName(Node node) {
> 			System.out.println("THIS IS NEVER CALLED");
> 			return node.getLabel();
> 		}
> 
> 	}
> 
> 	class EdgeIdProvider implements EdgeNameProvider<Edge> {
> 
> 		@Override
> 		public String getEdgeName(Edge edge) {
> 			return Long.toString(edge.getId());
> 		}
> 
> 	}
> 
> 	class EdgeLabelProvider implements EdgeNameProvider<Edge> {
> 
> 		@Override
> 		public String getEdgeName(Edge edge) {
> 			System.out.println("THIS IS NEVER CALLED");
> 			return edge.getLabel();
> 		}
> 
> 	} 
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Sprint
> What will you do first with EVO, the first 4G phone?
> Visit sprint.com/first -- http://p.sf.net/sfu/sprint-com-first
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> 

[jgrapht-users] VertexLabelProvider, EdgeLabelProvider not called

[Oliver S. <oli...@gm...>]

Hi,

I have some trouble printing the labels using the GmlExporter, they are simply not called.

Any idea?

Best regards
Oliver Schrenk


public Network() {
		graph = new DirectedWeightedMultigraph<Node, Edge>(Edge.class);
		init();
	}

	private void init() {
		Node previous = new Node(1, "label_1");
		Node current = new Node(2, "label_2");

		graph.addVertex(previous);
		graph.addVertex(current);
		graph.addEdge(previous, current);

	}

	public void export() {
		GmlExporter<Node, Edge> exporter = new GmlExporter<Node, Edge>(
				new VertexIdProvider(), new VertexLabelProvider(),
				new EdgeIdProvider(), new EdgeLabelProvider());
		exporter.export(new BufferedWriter(new OutputStreamWriter(System.out)),
				(DirectedGraph<Node, Edge>) graph);

	}
	
	class VertexIdProvider implements VertexNameProvider<Node> {

		@Override
		public String getVertexName(Node node) {
			return Long.toString(node.getId());
		}

	}

	class VertexLabelProvider implements VertexNameProvider<Node> {

		@Override
		public String getVertexName(Node node) {
			System.out.println("THIS IS NEVER CALLED");
			return node.getLabel();
		}

	}

	class EdgeIdProvider implements EdgeNameProvider<Edge> {

		@Override
		public String getEdgeName(Edge edge) {
			return Long.toString(edge.getId());
		}

	}

	class EdgeLabelProvider implements EdgeNameProvider<Edge> {

		@Override
		public String getEdgeName(Edge edge) {
			System.out.println("THIS IS NEVER CALLED");
			return edge.getLabel();
		}

	} 

[jgrapht-users] Question about network partitions

[武志刚 <epz...@gm...>]

Hi, guys,

I am a freshman of JGraphT. I wonder if there are some network partitioning
algorithms to deal with weighted graphs? Or could somebody give me some
suggestion to realize the algorithm with the help of JGraphT? Many thanks in
advance!

Best regards

Zhigang Wu

[jgrapht-users] How to stop traversing at a given node

[Robert L. <rob...@gm...>]

Can someone please tell me how to traverse a graph breadth first (depth
first OK too) and to stop going down the current branch based on information
that's stored in the just-visited node.
Using *<http://www.jgrapht.org/javadoc/org/jgrapht/traverse/BreadthFirstIterator.html>
*BreadthFirstIterator<V,E> seems to be the way to go but I can't figure out
how to tell the traverser to stop going down the path once I've visited a
node and recognized it as a stopping point.

Any thoughts?

Re: [jgrapht-users] Weighted graphs

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

The default edge implementations are optimized to be "intrusive"; that 
is, they contain direct references to their vertices.

When the graph sees an edge class that extends a default edge, it 
assumes that it can use these references rather than maintaining the 
edge/vertex association indirectly via a HashMap (which is more expensive).

In your case, you are creating a new edge on the fly, so when the graph 
examines it, the references are null.  When you use a non-default 
implementation everything works because then the new GRFEdge probably 
Object.equals some existing edge in the graph.

JVS

Fabian K wrote:
> my graph class:
> public class GRFGraph extends DefaultDirectedWeightedGraph<GRFNode, GRFEdge>
> 
> my Edge class:
> public class GRFEdge extends DefaultWeightedEdge
> 
> following method doesn't work anymore, it returns null.
> GRFNode srcNode = graph.getEdgeTarget(new GRFEdge(1));
> 
> when my GRFEdge doesnt extend DefaultWeightedEdge it works fine. It will
> return the node.
> 
> What is wrong with this call?
> 
> FYI:
> in my GRFEdge class I override getWeight method already.
> 
> @Override
> public double getWeight() {
>         return weight;
> } 

Re: [jgrapht-users] Weighted graphs

[Fabian K <fab...@gm...>]

my graph class:
public class GRFGraph extends DefaultDirectedWeightedGraph<GRFNode, GRFEdge>

my Edge class:
public class GRFEdge extends DefaultWeightedEdge

following method doesn't work anymore, it returns null.
GRFNode srcNode = graph.getEdgeTarget(new GRFEdge(1));

when my GRFEdge doesnt extend DefaultWeightedEdge it works fine. It will
return the node.

What is wrong with this call?

FYI:
in my GRFEdge class I override getWeight method already.

@Override
public double getWeight() {
        return weight;
} 
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Weighted-graphs-tp107885p890947.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Weighted graphs

[Fabian K <fab...@gm...>]

my graph class:
public class GRFGraph extends DefaultDirectedWeightedGraph<GRFNode, GRFEdge>

my Edge class:
public class GRFEdge extends DefaultWeightedEdge

following method doesn't work anymore, it returns null.
GRFNode srcNode = graph.getEdgeTarget(new GRFEdge(1));

when my GRFEdge doesnt extend DefaultWeightedEdge it works fine. It will
return the node.

What is wrong with this call?

FYI:
in my GRFEdge class I override getWeight method already.

@Override
public double getWeight() {
	return weight;
}
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Weighted-graphs-tp107885p890828.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Using JGraphT with DrJava

[Keith B. <krb...@ya...>]

What is the proper way to extract and use a package like JGraphT with DrJava on Windows XP?  My working folder is "C:\_java", and I would like to place the JGraphT package (and other packages) in a single library (say "C:\_java\library").  I tried extracting the zip file directly to that folder, but that placed everything in "C:\_java\library\jgrapht-0.8\jgrapht-0.8.1", which would necessitate a separate, fairly-long, version-specific classpath for each package I wanted to use, instead of a single common pointer to a "C:\_java\library".  Is there a standard way of establishing these libraries and having a programming environment like DrJava find them automatically?  Is there already a location set aside for users to add their own package libraries?  Neither the JGraphT nor the DrJava documentation seems to go into detail in this regard.

Thanks in advance for any assistance you can provide.



      

Re: [jgrapht-users] Connected Component Labeling with union find datastructure

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

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é

Re: [jgrapht-users] Connected Component Labeling with union find datastructure

[André <akr...@on...>]

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/Connected-Component-Labeling-with-union-find-datastructure-tp721453p739340.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Connected Component Labeling with union find datastructure

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

Thanks Andre.  For connected components specifically of graphs, we 
already have ConnectivityInspector, but if someone needs the generic 
connected component labeling via union-find 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 two-pass 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 non-minimum 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.
>>
> 

Re: [jgrapht-users] Connected Component Labeling with union find datastructure

[André <akr...@on...>]

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 two-pass 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 non-minimum 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/Connected-Component-Labeling-with-union-find-datastructure-tp721453p731535.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Connected Component Labeling with union find datastructure

[André <akr...@on...>]

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/Connected-Component-Labeling-with-union-find-datastructure-tp721453p722008.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Connected Component Labeling with union find datastructure

[Tom C. <the...@gm...>]

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é <akr...@on...> 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 two-pass algo uses a union-find 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/Connected-Component-Labeling-with-union-find-datastructure-tp721453p721453.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Connected Component Labeling with union find datastructure

[André <akr...@on...>]

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 two-pass algo uses a union-find 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/Connected-Component-Labeling-with-union-find-datastructure-tp721453p721453.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Dijkstra, FloydWarshall or Edmonds?

[André <akr...@on...>]

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/Dijkstra-FloydWarshall-or-Edmonds-tp696330p721340.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] BFS -- immediate predecessor across an edge?

[Nick W. <nic...@gm...>]

Never mind. I found the answer
here<http://n3.nabble.com/Accessing-nodes-while-iterating-on-graph-td107901.html#a107903>
.

On 13 April 2010 12:12, Nick Wiggill <nic...@gm...> 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
> www.handcraftedgames.net
>



-- 
Nick Wiggill
www.handcraftedgames.net

[jgrapht-users] BFS -- immediate predecessor across an edge?

[Nick W. <nic...@gm...>]

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
www.handcraftedgames.net

Re: [jgrapht-users] back edges

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

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 fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev_______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

[jgrapht-users] back edges

[dinesh c. <din...@gm...>]

Hi,
I want to know whether a particular edge is a backedge or not(loop).How can
I get that

-- 
Regards,
Dinesh Chhatani

[jgrapht-users] All paths

[dinesh c. <din...@gm...>]

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

Re: [jgrapht-users] Dijkstra, FloydWarshall or Edmonds?

[Joris K. <de...@gm...>]

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
<akr...@on...> 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&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] An question on using JgraphT to find all strongly connected components of a directed graph

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

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 e-mail from your 
> inbox. Get started. 
> <http://www.windowslive.com/campaign/thenewbusy?ocid=PID27925::T:WLMTAGL:ON:WL:en-US:WM_HMP:032010_3>
> 
> 
> ------------------------------------------------------------------------
> 
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

[jgrapht-users] Dijkstra, FloydWarshall or Edmonds?

[André K. <akr...@on...>]

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é
 

Re: [jgrapht-users] KShortest Path implementation

[Arun I. <aru...@ym...>]

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 <js...@gm...> wrote:

From: John V. Sichi <js...@gm...>
Subject: Re: [jgrapht-users] KShortest Path implementation
To: "Arun Iyer" <aru...@ym...>
Cc: jgr...@li...
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 non-deterministic? Is there threading involved (either in graph creation or in k-shortestpath computation) ?

It does not use threading.  It does use HashMaps, which can result in non-determinism 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