jgrapht-users — JGraphT user list.

Re: [jgrapht-users] On extracting a directedsubgraph containing only elements reachable from a given vertex

[Davide C. <dav...@gm...>]

I guess *strongly connected
<http://en.wikipedia.org/wiki/Strongly_connected_component>* means that *every
vertex is reachable from every other vertex*, but this condition would be
far too strict for my needs.
I've managed to obtain the subgraph with:

   1. an in-depth visit to determine the subgraph *vertexSet*
   2. then filtering the graph *edgeSet* to keep only the ones for which
   both vertex belongs to the subgraph vertexSet.

Many thanks
Davide

PS: Follows a working groovy snippet for later reference... just my two
cents

import org.jgrapht.*
import org.jgrapht.graph.*
import org.jgrapht.alg.*
import org.jgrapht.traverse.*
import org.jgrapht.experimental.dag.*

@Grab(group='org.jgrapht', module='jgrapht-core', version='0.9.0')
DirectedGraph graph = new DirectedAcyclicGraph(DefaultEdge)
graph.addVertex ('A')
graph.addVertex ('B')
graph.addVertex ('C')
graph.addVertex ('D')
graph.addVertex ('E')
graph.addVertex ('F')
graph.addEdge ('A', 'B')
graph.addEdge ('B', 'C')
graph.addEdge ('B', 'D')
graph.addEdge ('D', 'C')
graph.addEdge ('A', 'E')
graph.addEdge ('E', 'F')
graph.addEdge ('F', 'D')

//println "graph: $graph"

Iterator iterator = new DepthFirstIterator (graph, 'B')
Set vertexSubset = [] as LinkedHashSet
//determine the vertexset for the subgraph
while (iterator.hasNext()) {
    vertexSubset << iterator.next()
}
//filter the full graph edgeset to obtain the subgraph one
Set edgeSubset = graph.edgeSet().findAll {edge->
    graph.getEdgeSource (edge) in vertexSubset && graph.getEdgeTarget
(edge) in vertexSubset
}
//create the subgraph
DirectedSubgraph subgraph = new DirectedSubgraph (graph, vertexSubset,
edgeSubset)
//println "subgraph: $subgraph"




2014-11-03 13:31 GMT+01:00 Szabolcs Besenyei <bes...@gm...>:

> Given the problem a little bit more thought I think what you are trying to
> achieve is the same as determining the strongly connected components
> <http://en.wikipedia.org/wiki/Strongly_connected_component> of a given
> directed graph. The strongly connected components of an arbitrary directed
> graph form a partition into subgraphs that are themselves strongly
> connected.
> So the functionality of org.jgrapht.alg.StrongConnectivityInspector<V, E>
> meets the requirements of your problem.
>
>
> Regards,
>
> Szabolcs
>
> 2014-11-03 12:58 GMT+01:00 Davide Cavestro <dav...@gm...>:
>
>> Thankyou for the quick hint... but It seems that org.jgrapht.alg.ConnectivityInspector#pathExists
>> ignores edges direction (as  it is based on
>> org.jgrapht.alg.ConnectivityInspector#connectedSetOf)
>> Is there any way to determine the set of paths reachable from a given
>> vertex of a directed graph? This way I could use the results to create a
>> DirectedSubGraph
>>
>> 2014-11-01 1:04 GMT+01:00 Szabolcs Besenyei <bes...@gm...>:
>>
>>>
>>>
>>> 2014-10-31 18:23 GMT+01:00 Davide Cavestro <dav...@gm...>:
>>> > I'm trying to figure out a way to extract from a DirectedGraph
>>> instance a
>>> > DirectedSubgraph containing only the subset of vertex/edges reachable
>>> from a
>>> > given vertex (of the original graph).
>>> > Any help appreciated.
>>>
>>> ​Ta​
>>> ke a look at org.jgrapht.alg.ConnectivityInspector#pathExists.
>>>
>>> --
>>> Regards,
>>>
>>> Szabolcs
>>>
>>>
>>> ------------------------------------------------------------------------------
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>>
>>
>

Re: [jgrapht-users] On extracting a directedsubgraph containing only elements reachable from a given vertex

[Szabolcs B. <bes...@gm...>]

Given the problem a little bit more thought I think what you are trying to
achieve is the same as determining the strongly connected components
<http://en.wikipedia.org/wiki/Strongly_connected_component> of a given
directed graph. The strongly connected components of an arbitrary directed
graph form a partition into subgraphs that are themselves strongly
connected.
So the functionality of org.jgrapht.alg.StrongConnectivityInspector<V, E>
meets the requirements of your problem.


Regards,

Szabolcs

2014-11-03 12:58 GMT+01:00 Davide Cavestro <dav...@gm...>:

> Thankyou for the quick hint... but It seems that org.jgrapht.alg.ConnectivityInspector#pathExists
> ignores edges direction (as  it is based on
> org.jgrapht.alg.ConnectivityInspector#connectedSetOf)
> Is there any way to determine the set of paths reachable from a given
> vertex of a directed graph? This way I could use the results to create a
> DirectedSubGraph
>
> 2014-11-01 1:04 GMT+01:00 Szabolcs Besenyei <bes...@gm...>:
>
>>
>>
>> 2014-10-31 18:23 GMT+01:00 Davide Cavestro <dav...@gm...>:
>> > I'm trying to figure out a way to extract from a DirectedGraph instance
>> a
>> > DirectedSubgraph containing only the subset of vertex/edges reachable
>> from a
>> > given vertex (of the original graph).
>> > Any help appreciated.
>>
>> ​Ta​
>> ke a look at org.jgrapht.alg.ConnectivityInspector#pathExists.
>>
>> --
>> Regards,
>>
>> Szabolcs
>>
>>
>> ------------------------------------------------------------------------------
>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>

Re: [jgrapht-users] On extracting a directedsubgraph containing only elements reachable from a given vertex

[Davide C. <dav...@gm...>]

Thankyou for the quick hint... but It seems that
org.jgrapht.alg.ConnectivityInspector#pathExists
ignores edges direction (as  it is based on
org.jgrapht.alg.ConnectivityInspector#connectedSetOf)
Is there any way to determine the set of paths reachable from a given
vertex of a directed graph? This way I could use the results to create a
DirectedSubGraph

2014-11-01 1:04 GMT+01:00 Szabolcs Besenyei <bes...@gm...>:

>
>
> 2014-10-31 18:23 GMT+01:00 Davide Cavestro <dav...@gm...>:
> > I'm trying to figure out a way to extract from a DirectedGraph instance a
> > DirectedSubgraph containing only the subset of vertex/edges reachable
> from a
> > given vertex (of the original graph).
> > Any help appreciated.
>
> ​Ta​
> ke a look at org.jgrapht.alg.ConnectivityInspector#pathExists.
>
> --
> Regards,
>
> Szabolcs
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] On extracting a directedsubgraph containing only elements reachable from a given vertex

[Szabolcs B. <bes...@gm...>]

2014-10-31 18:23 GMT+01:00 Davide Cavestro <dav...@gm...>:
> I'm trying to figure out a way to extract from a DirectedGraph instance a
> DirectedSubgraph containing only the subset of vertex/edges reachable
from a
> given vertex (of the original graph).
> Any help appreciated.

​Ta​
ke a look at org.jgrapht.alg.ConnectivityInspector#pathExists.

-- 
Regards,

Szabolcs

[jgrapht-users] On extracting a directedsubgraph containing only elements reachable from a given vertex

[Davide C. <dav...@gm...>]

I'm trying to figure out a way to extract from a DirectedGraph instance a
DirectedSubgraph containing only the subset of vertex/edges reachable from
a given vertex (of the original graph).
Any help appreciated.

[jgrapht-users] Incrementally update strongly connected components and topological order

[delfa <de...@si...>]

Hello everyone,
I have a directed graph which I modify continuously. I need to 
calculate the connected components and the topology for each of these 
components, being performance critical. My questions are:

1. How do I get the components (not strong) from a DAG? I have seen 
that the ConnectivityInspector doesn't have any method to retrieve the 
list of components. The method connectedSets returns a list of sets of 
vertex, so I would need then to get the related edges for each set in 
the list and construct the corresponding component. Another way might be 
to create first the undirected graph and calculate the strongly 
connected components, but that seems to me a bit of overhead. Is there 
no other easier and faster(performance is critical) way to do that?

2. Every time I update the graph I would like to update boths, 
components and topology, in an incremental manner without the need of 
recalculating everything from scratch. Is it possible to do that?

Regards,
Juan

Re: [jgrapht-users] Get all paths

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

You need to be more specific. Do you want all edge disjoint, or vertex
disjoint paths, or just all paths that hare different from each other? Note
that finding all paths between two nodes is NP-hard. Devising an algorithm
to do so is however not necessarily very difficult. See e.g.:
http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes

For a number of easy-to-implement algorithms for finding edge/node disjoint
graphs and several variations, see:  Bhandari, Ramesh (1999),  *Survivable
Networks: Algorithms for Diverse Routing*, Springer-Verlag,  ISBN
<http://en.wikipedia.org/wiki/International_Standard_Book_Number>
978-0-7923-8381-9
<http://en.wikipedia.org/wiki/Special:BookSources/978-0-7923-8381-9>

br,

Joris Kinable


On Fri, Aug 29, 2014 at 2:16 PM, irisDeveloper <dev...@gm...>
wrote:

> Hi all,
>
> I want set of all the paths between any two vertices . Can anybody help me.
>
> Thanks
> Samby
>
>
>
> ------------------------------------------------------------------------------
> Slashdot TV.
> Video for Nerds.  Stuff that matters.
> http://tv.slashdot.org/
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] How to remove all edges of a certain vertex iteratively?

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

Java doesn't allow you to iterate over a list using a for each statement
and modify the list at the same time. That leads to an
ConcurrentModificationException. To resolve this issue, you either need to
create a separate list of vertices you want to delete and invoke
removeVertex on each of these vertices, or you should use an iterator and
invoke iterator.remove();

Finally, removeVertex also removes all edges incident to that vertex, so
you don't need a separate call to remove the edges of that vertex.

br,

Joris




On Fri, Aug 29, 2014 at 1:28 PM, Zhigang Wu <ep...@sc...> wrote:

> Dear jgrapht users,
>
>
>
> In my problem, I want to traverse the graph to find a certain vertex, then
> delete the vertex accompanied with all the edges connected to it. Then I
> will traverse the remained graph again, find another vertex by some special
> rules, deleted the vertex and all the connected edges…
>
>
>
> However, when I translate the procedure into JAVA codes, I always receive
> the same error message:
>
>
>
> java.util.ConcurrentModificationException
>
>          at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
>
>          at java.util.ArrayList$Itr.next(Unknown Source)
>
>          at java.util.Collections$UnmodifiableCollection$1.next(Unknown
> Source)
>
>          at
> org.jgrapht.graph.AbstractGraph.removeAllEdges(AbstractGraph.java:89)
>
>          ……
>
>
>
> The following is my JAVA code related to this:
>
>
>
>                             *for* (Node myNode : myNodeList) {
>
>                                    // Some codes to find the certain
> node, the name is myNode
>
>                                    // Some operations
>
>                                    myGraph.removeAllEdges(myGraph
> .edgesOf(myNode));
>
>                                    myGraph.removeVertex(myNode);
>
>                             }
>
>
>
> This problem has bothered me for quite a long time, many thanks in advance!
>
>
>
> Best Regards
>
>
>
> Zhigang Wu
>
>
> ------------------------------------------------------------------------------
> Slashdot TV.
> Video for Nerds.  Stuff that matters.
> http://tv.slashdot.org/
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Get all paths

[irisDeveloper <dev...@gm...>]

Hi all,

I want set of all the paths between any two vertices . Can anybody help me.

Thanks
Samby

[jgrapht-users] How to remove all edges of a certain vertex iteratively?

[Zhigang W. <ep...@sc...>]

Dear jgrapht users,

 

In my problem, I want to traverse the graph to find a certain vertex, then
delete the vertex accompanied with all the edges connected to it. Then I
will traverse the remained graph again, find another vertex by some special
rules, deleted the vertex and all the connected edges.

 

However, when I translate the procedure into JAVA codes, I always receive
the same error message: 

 

java.util.ConcurrentModificationException

         at java.util.ArrayList$Itr.checkForComodification(Unknown Source)

         at java.util.ArrayList$Itr.next(Unknown Source)

         at java.util.Collections$UnmodifiableCollection$1.next(Unknown
Source)

         at
org.jgrapht.graph.AbstractGraph.removeAllEdges(AbstractGraph.java:89)

         ..

 

The following is my JAVA code related to this:

 

                            for (Node myNode : myNodeList) {

                                   // Some codes to find the certain node,
the name is myNode

                                   // Some operations

 
myGraph.removeAllEdges(myGraph.edgesOf(myNode));

                                   myGraph.removeVertex(myNode);

                            }

 

This problem has bothered me for quite a long time, many thanks in advance!

 

Best Regards

 

Zhigang Wu

Re: [jgrapht-users] Creating a directed graph from xml documents

[laassem <el...@gm...>]

hi , i have a similar problem  did u found any solution ?



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Creating-a-directed-graph-from-xml-documents-tp3782735p4024930.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] KSP bugfix - performance

[Hoeltzcke, Claus-D. (E. Ethon) <ext...@vo...>]

Hi,

the actual version history states: ... - More KSP bugfixes (spotted by Sebastian Mueller, fixed by Guillaume Boulmier) -  The main reason for me to update, because 0.8.3 was worse on KSP than 0.8.1.
Since 0.9.0 (bugfix tested OK on my unit tests)  the performance on KSP for multigraphs dramatically went down (feels like factor 50 slower!!!).
I did not change anything but the JGraphT version (0.8.1 -> 0.9.0)
Is there any chance to improve performance to what it was before, or is this the unchangeable side effect of the fix?

Thanks + Bye,
Claus

Re: [jgrapht-users] cycle detector in directed graph

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

Perhaps you may find what you need with Maven's DAG and CycleDetector:

http://plexus.codehaus.org/plexus-utils/apidocs/org/codehaus/plexus/util/dag/DAG.html

http://plexus.codehaus.org/plexus-utils/apidocs/org/codehaus/plexus/util/dag/CycleDetector.html

Artifact:
https://search.maven.org/remotecontent?filepath=org/codehaus/plexus/plexus-utils/3.0.17/plexus-utils-3.0.17.jar

Rob


On Thu, May 8, 2014 at 2:53 AM, Fariba Azizmohammadi <
far...@gm...> wrote:

> Hello,
> I am seraching for a java code for loop detecting in a directed graph and
> also the code should return the nodes which are in the loop in the graph.
> could you please help me to find the peseudo code for that. I have
> serarched in your site to find the code by still no result.
> Thanks,
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform
> available
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] TopologicalOrderIterator question

[Kevin R. <re...@go...>]

The topological order iterator is similar to something that I've recently
written and I'd like to reuse that class instead.  However, one of my
requirements is that I must be able to see the available top level nodes
without marking them as visited.

This is necessary because I'm working in a multi-threaded environment,
where dependencies for each node aren't "released" until that node has
finished executing.

Any thoughts on how this might be accomplished in the JGraphT library?

Sincerely,
Kevin Regan

[jgrapht-users] Grph: high performance graph library

[Luc H. <luc...@cn...>]

Dear (J)graph(T) community, 

I'm happy to tell you about the availability of a Java graph library targeted to performance. 
It's there: http://www.i3s.unice.fr/~hogie/grph/ 

I was a bit reluctant to advertise it here but Grph is by no means a competitor to JGraphT, in particular 
because it's data model is not object-oriented. It is especially well suited to many scientific, data-analysis applications. 

It implements numerous strategies to achieve great performance, and current works are to make it a 
distributed graph computation framework, in the same veine as PBGL (Parallel Boost) 

Grph is being developed and maintained at a Nice-Sophia Antipolis University (France). 
It already gathers many users. We'd be very happy if it could help you. 

Wish you a good day, 
Luc. 

-- 
Luc Hogie 
COMRED Research Unit (I3S(CNRS-UNS) INRIA) 
I3S Laboratory, University of Nice Sophia Antipolis 

http://www-sop.inria.fr/members/Luc.Hogie/ 
luc...@cn... 
+33 4 89 73 24 25 (office) 
+33 6 80 91 40 71 (mobile) 

[jgrapht-users] Problem with ListenableDirectedGraph with custom edge class

[Andreea S. <and...@ya...>]

Hi,

I have a problem when using a ListenableDirectedGraph with a custom edge, as shown below:

ListenableDirectedGraph<CypherBasicNode, CypherBasicEdge> dirGraph = 
new ListenableDirectedGraph<CypherBasicNode, CypherBasicEdge>(CypherBasicEdge.class);

Everything is displayed fine in the Applet, but when I issue a dirGraph.edgeSet() the set is not correct. The first value in the set it is correct, while all the rest are null. I was researching and saw that when an addEdge is made, the empty constructor of the custom edge class is called (which I don't understand why, because I create the edge beforehand and I add it using:

CypherBasicEdge edge = new CypherBasicEdge(relId);

dirGraph.addEdge(firstNode, secondNode, edge);


 ). If I delete the empty constructor I get a "java.lang.RuntimeException: Edge factory failed" exception, because in add newInstance() is called (which is weird considering that an edge Object is given as an argument to addEdge ). 
 
If I run this code:

CypherBasicEdge edge = new CypherBasicEdge(relId);

dirGraph.addEdge(firstNode, secondNode, edge);

System.out.println("first edge: " + edge);

System.out.println("second edge: " + dirGraph.getEdge(firstNode, secondNode));


I get the following output:

first edge: r2 {}
second edge: null {}
 
Which to me seems very unlikely to be correct. Meanwhile, the visual representation is correct. Also, if I change the graph from ListenableDirectedGraph to DefaultDirectedGraph, everything works correctly. 

I am not sure whether I have not understood how I should use the classes or there is some kind of bug. I would appreciated any help.

Best regards,
Andreea Sandu

[jgrapht-users] all-pairs shortest paths

[Kurt W. <kur...@ya...>]

Hi JGraphT users,


I wanted to use the FloydWarshallShortestPaths class with the getShortestPaths() method to get all-pairs shortest paths in a graph.  However, after trying to use the method, I was disappointed to discover that the method only gave one shortest path for each node pair.  If there was multiple shortest paths of the same length for a node pair, this method just gave me one of the shortest paths.  What should I do?  Is there a way that I can get all of the shortest paths, including multiple shortest paths (of the same length) for those node pairs which have multiple shortest paths?  In some situations there is more than just one shortest path.  Thanks for any help and information you have to offer me!

Best,
Kurt

[jgrapht-users] cycle detector in directed graph

[Fariba A. <far...@gm...>]

Hello,
I am seraching for a java code for loop detecting in a directed graph and
also the code should return the nodes which are in the loop in the graph.
could you please help me to find the peseudo code for that. I have
serarched in your site to find the code by still no result.
Thanks,

Re: [jgrapht-users] Graph with loops and self-loop.

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

Hi,

I've never dealt with these kind of graphs so I'm not entirely sure what's
supported in jgrapht. However, it wouldn't surprise me that there is no
such algorithm in jgrapht. Any algorithm that computes a path from vertex x
to a vertex y keeps track of the vertices it visited in order to prevent
loops.
What you want however is not very difficult to implement. Simply use an
algorithm (like Breadth First Search) which computes all paths from x to y,
thereby ignoring the loops. This gives you a list of paths.

So based on your example this will give you path: A->B->C and A->. Then for
each vertex with a self loop, you can generate all the variations on this
path iteratively. For example if you have a loop on vertices B and A, this
would result in:

ABC (path you generated using BFS)
Expansions:
AABC
AABBC
ABBC

AC (path you generated using BFS)
Expansions:
AAC

Hope this helps.

br,

Joris


On Mon, Apr 28, 2014 at 1:19 PM, raphaelrodrigues <rap...@gm...>wrote:

> Hi, i have a Graph with loops and self-loop. The objective is to get all
> the
> possible paths.
>
> With the algorithms provide by JgraphT, i can't pass through the loops. The
> algorithms pass one time in the Vertex that has loops and after that the
> algoritm don't get the other possible paths from this Vertex .
>
> For example, if i have:
> A->B
> A->A
> A->C
>
> B->A
>
> >From (A To C) I wanna get:
> Path1: A ->B->A->C
> Path2: A->C
>
> With jgrapht i only get:
> Path1: A-> C
>
> What i wanna know is if there a possible way to find all the path with a
> limit of depth maybe? Or the best way to deal with self loops and loops?
>
> Thank you very much!
>
>
>
> --
> View this message in context:
> http://jgrapht-users.107614.n3.nabble.com/Graph-with-loops-and-self-loop-tp4024920.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.  Get
> unparalleled scalability from the best Selenium testing platform available.
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Graph with loops and self-loop.

[raphaelrodrigues <rap...@gm...>]

Hi, i have a Graph with loops and self-loop. The objective is to get all the
possible paths.

With the algorithms provide by JgraphT, i can't pass through the loops. The
algorithms pass one time in the Vertex that has loops and after that the
algoritm don't get the other possible paths from this Vertex . 

For example, if i have:
A->B
A->A
A->C

B->A

>From (A To C) I wanna get:
Path1: A ->B->A->C
Path2: A->C

With jgrapht i only get:
Path1: A-> C

What i wanna know is if there a possible way to find all the path with a
limit of depth maybe? Or the best way to deal with self loops and loops?

Thank you very much! 



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Graph-with-loops-and-self-loop-tp4024920.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Fibonacci heap vs binary heap

[solowd <dan...@gm...>]

I'm aware that the Fibonacci heap is asymptotically better, but there's a
common perception that binary heaps run faster in many applications. 

For example, the answers to  this question
<http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently>  
on stackoverflow.

I noticed that JGraphT uses a Fibonacci heap for the ClosestFirst iterator. 
Has anyone done testing to compare the performance of binary heaps to the
Fibonacci heap in this iterator? I'm especially interested in testing with
sparse graphs (as my application doesn't care about dense graphs).
	
I'll do some tests myself later on, but I'm curious if anyone has already
thought this through.
	
Thanks.



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Fibonacci-heap-vs-binary-heap-tp4024919.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] setting edge weights

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

Hi John,

Thanks for the follow up. You are right about the performance impact which
occurs if additional checks are performed such as edge ownership, or edge
occurrence in a graph. Perhaps we could add some assert statements to check
for these issues. Doing this would not affect production code as java
ignores the assert statements, whereas it would make debugging easier. This
way at least some trivial cases can be verified, such as whether the edge
is contained in the graph when invoking setEdgeWeight. However, this would
not resolve your tricky example wrt the edge adjacency problem as graph g2
has no notion of the existence of graph g1.

Wrt the documentation: depending on the quantity I would prefer to keep as
much documentation in the javadoc as this is simply more convenient.
However linking to an external wiki page would also be fine, especially if
the amount of documentation is large.

br,

Joris


On Wed, Apr 23, 2014 at 1:27 AM, John Sichi <js...@gm...> wrote:

> Hi Joris,
>
> Note that this is also true for edge adjacency (even for unweighted
> edges) due to the IntrusiveEdge implementation; i.e. if you add a
> DefaultEdge e1 to g1 between (v1,v2), and then add e1 to g2 between
> (v3,v4), e1 gets updated in both graphs (corrupting g1).
>
> This imperfect situation came about due to JGraphT's emphasis on
> performance:  it avoids the need for map lookups for traversing graphs
> and accessing weights, and in the common case of no sharing (or
> something like subgraph sharing where there's no discrepancy between
> the two graphs), all is well.
>
> In other cases where edge sharability is required, it's necessary to
> use your own edge class (avoiding inheritance from the Default*Edge
> classes), and override the graph's get/setEdgeWeight.
>
> Where do you think is a good place to document this?  I'm thinking
> maybe a wiki page explaining the pitfalls, and then links to it from
> various classes (although no matter how much documentation we do, it's
> still likely that developers will overlook this).
>
> On Tue, Apr 22, 2014 at 8:47 PM, Joris Kinable <de...@gm...> wrote:
> > Hi,
> >
> > I've encountered some issues with edge weights which potentially could
> cause
> > bugs. I was wondering whether some corrections in the code are required.
> >
> > Take the following simple code snippet:
> >
> > //Define graph4, consisting of a single edge (0,1) with edge weight 10
> > WeightedGraph<Integer, DefaultWeightedEdge> graph4=new
> > SimpleWeightedGraph<Integer,
> > DefaultWeightedEdge>(DefaultWeightedEdge.class);
> > graph4.addVertex(0);
> > graph4.addVertex(1);
> > DefaultWeightedEdge e1= graph4.addEdge(0, 1);
> > graph4.setEdgeWeight(e1, 10);
> > //Define graph5 without edges or vertices
> > SimpleWeightedGraph<Integer, DefaultWeightedEdge> graph5=new
> > SimpleWeightedGraph<Integer,
> > DefaultWeightedEdge>(DefaultWeightedEdge.class);
> > graph5.setEdgeWeight(e1, 5);
> >
> > System.out.println("Edge weight graph 4: "+graph4.getEdgeWeight(e1));
> > //OUTPUT: Edge weight graph 4: 5.0
> >
> > Notice that jgrapht allowed me to change the weight of edge e1 in graph4
> > through graph5 which does not even contain this edge. This seems pretty
> > awkward?
> >
> > 1. the setEdgeWeight should only work if the graph contains the edge.
> > 2. I think that it would be a good idea to update the documentation of
> the
> > DefaultWeightedEdge, thereby emphasizing that edge weights are stored on
> the
> > edges, and not in the graph. Lets say you have 2 graphs, g1 and g2 both
> > containing the same edge e (same object). Invoking g1.setEdgeWeight(e,
> 10)
> > will also change the weight of this edge in graph g2.
> >
> > I'm not sure how to accomplish the following:
> > Given a weighted graph g1, create a subgraph g2 containing a subset of
> the
> > edges of g1 with *different* weights. Then for a given edge e which is
> > contained in both g1 and g2, I would like to invoke:
> > "Weight of e in g1: "+ g1.getEdgeWeight(e);
> > "Weight of e in g2: "+ g2.getEdgeWeight(e);
> > I could do something ugly by creating a mapping from edges in graph g1 to
> > different edges in graph g2. Then for a given edge e in g1 I could
> invoke:
> > Map<DefaultWeightedEdge, DefaultWeightedEdge> edgeMapping=...;
> > "Weight of e in g1: "+ g1.getEdgeWeight(e);
> > "Weight of e in g2: "+ g2.getEdgeWeight(edgeMapping.get(e));
> > I would be happy to learn about cleaner methods.
> >
> >
> > br,
> >
> > Joris
> >
> >
> ------------------------------------------------------------------------------
> > Start Your Social Network Today - Download eXo Platform
> > Build your Enterprise Intranet with eXo Platform Software
> > Java Based Open Source Intranet - Social, Extensible, Cloud Ready
> > Get Started Now And Turn Your Intranet Into A Collaboration Platform
> > http://p.sf.net/sfu/ExoPlatform
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
>

[jgrapht-users] Fwd: Bug in HamiltonianCycle

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

This reply was supposed to go over the mailing list.

br,

Joris

---------- Forwarded message ----------
From: Joris Kinable <de...@gm...>
Date: Wed, Apr 23, 2014 at 1:38 PM
Subject: Re: [jgrapht-users] Bug in HamiltonianCycle
To: Simon Heinen <sim...@gm...>


Hi Simon,

In your post you have several questions.

Q1: Is there also a Hamiltonian cycle algorithm implementation which
produces an exact solution?
No there is not. HC is an NP-hard problem, meaning that it is very
difficult to solve. There are entire libraries dedicated to solving just
this problem, which is way beyond jgrapht. What you might want to do is to
look into Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html) which
currently is the fastest solver. It can solve the HC problem to optimality
for very large instances in reasonable time.

Q2: Is there an implementation which yields better but not necessary
optimal solutions?
Currently not, but I've checked the implementation and there are fairly
easy ways to improve the quality of the solutions with a reasonable
increase in runtime. What you could do is take the solution produced by the
Hamiltonian cycle implementation and run a local search on top of it,
thereby performing a certain number of so-called 2-opt moves (
http://en.wikipedia.org/wiki/2-opt). This procedure is known to give good
results in general (but obviously doesn't guarantee to find the optimal
solution).
What I would do is the following:
1. Use HamiltonianCycle.java to get a initial solution
2. Given the tour, find the best 2-opt move out of all possible 2-opt
moves. If this move improves the solution, perform the move. If not, stop.
This is very easy and fast to implement, especially if you are dealing with
complete graphs. This would also make a nice extension of the
HamiltonianCycle class implementation :).


Q3: Is there a bug in the code? That's difficult to say from your example
as there are so many data points. From the looks of it, the solution seems
to satisfy the definition of a hamiltonian cycle:
-every vertex has an incoming and an outgoing edge
-there are no subtours e.g. it's one tour, not a collection of several
tours.
Check whether your solution meets these criteria.
Due to the greedy nature of the algorithm the resulting tour may however be
very far away from any optimal solution. In the example you showed us,
performing 2-opt moves will most likely provide you with the optimal
solution.
Note: the HamiltonianCycle class requires that your graph is complete
(check this!), see comment below. Also, to guarantee a 2-approximation, all
edge weights must satisfy the triangle inequality.


Note to developers:
We should update the java doc of HamiltonianCycle.java. In the code I found
this:
     * This method will return an approximate minimal traveling salesman
tour
     * (hamiltonian cycle). This algorithm requires that the graph be
complete
     * and the triangle inequality exists (if x,y,z are vertices then
     * d(x,y)+d(y,z)<d(x,z) for all x,y,z) then this algorithm will
guarantee a
     * hamiltonian cycle such that the total weight of the cycle is less
than or
     * equal to double the total weight of the optimal hamiltonian cycle.
The
     * optimal solution is NP-complete, so this is a decent approximation
that
     * runs in polynomial time.
This should be mentioned in the javadoc as well, preferably at the
beginning. If I have a bit of spare time in the weekend I'll write a brief
description for the algorithm used in the HamiltonianCycle class. There
should also be a note on the runtime complexity.

br,

Joris


On Tue, Apr 22, 2014 at 4:51 AM, Simon Heinen <sim...@gm...>wrote:

> Hello jGraphT users,
> I think I found a bug in the HamiltonianCycle algorithm. I wrote it
> down in detail here:
>
> https://github.com/jgrapht/jgrapht/issues/83
>
> If someone has an idea why this happens, it would be great to get some
> feedback about this.
>
> Thanks,
> Simon
>
>
> ------------------------------------------------------------------------------
> Start Your Social Network Today - Download eXo Platform
> Build your Enterprise Intranet with eXo Platform Software
> Java Based Open Source Intranet - Social, Extensible, Cloud Ready
> Get Started Now And Turn Your Intranet Into A Collaboration Platform
> http://p.sf.net/sfu/ExoPlatform
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] setting edge weights

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

Hi Joris,

Note that this is also true for edge adjacency (even for unweighted
edges) due to the IntrusiveEdge implementation; i.e. if you add a
DefaultEdge e1 to g1 between (v1,v2), and then add e1 to g2 between
(v3,v4), e1 gets updated in both graphs (corrupting g1).

This imperfect situation came about due to JGraphT's emphasis on
performance:  it avoids the need for map lookups for traversing graphs
and accessing weights, and in the common case of no sharing (or
something like subgraph sharing where there's no discrepancy between
the two graphs), all is well.

In other cases where edge sharability is required, it's necessary to
use your own edge class (avoiding inheritance from the Default*Edge
classes), and override the graph's get/setEdgeWeight.

Where do you think is a good place to document this?  I'm thinking
maybe a wiki page explaining the pitfalls, and then links to it from
various classes (although no matter how much documentation we do, it's
still likely that developers will overlook this).

On Tue, Apr 22, 2014 at 8:47 PM, Joris Kinable <de...@gm...> wrote:
> Hi,
>
> I've encountered some issues with edge weights which potentially could cause
> bugs. I was wondering whether some corrections in the code are required.
>
> Take the following simple code snippet:
>
> //Define graph4, consisting of a single edge (0,1) with edge weight 10
> WeightedGraph<Integer, DefaultWeightedEdge> graph4=new
> SimpleWeightedGraph<Integer,
> DefaultWeightedEdge>(DefaultWeightedEdge.class);
> graph4.addVertex(0);
> graph4.addVertex(1);
> DefaultWeightedEdge e1= graph4.addEdge(0, 1);
> graph4.setEdgeWeight(e1, 10);
> //Define graph5 without edges or vertices
> SimpleWeightedGraph<Integer, DefaultWeightedEdge> graph5=new
> SimpleWeightedGraph<Integer,
> DefaultWeightedEdge>(DefaultWeightedEdge.class);
> graph5.setEdgeWeight(e1, 5);
>
> System.out.println("Edge weight graph 4: "+graph4.getEdgeWeight(e1));
> //OUTPUT: Edge weight graph 4: 5.0
>
> Notice that jgrapht allowed me to change the weight of edge e1 in graph4
> through graph5 which does not even contain this edge. This seems pretty
> awkward?
>
> 1. the setEdgeWeight should only work if the graph contains the edge.
> 2. I think that it would be a good idea to update the documentation of the
> DefaultWeightedEdge, thereby emphasizing that edge weights are stored on the
> edges, and not in the graph. Lets say you have 2 graphs, g1 and g2 both
> containing the same edge e (same object). Invoking g1.setEdgeWeight(e, 10)
> will also change the weight of this edge in graph g2.
>
> I'm not sure how to accomplish the following:
> Given a weighted graph g1, create a subgraph g2 containing a subset of the
> edges of g1 with *different* weights. Then for a given edge e which is
> contained in both g1 and g2, I would like to invoke:
> "Weight of e in g1: "+ g1.getEdgeWeight(e);
> "Weight of e in g2: "+ g2.getEdgeWeight(e);
> I could do something ugly by creating a mapping from edges in graph g1 to
> different edges in graph g2. Then for a given edge e in g1 I could invoke:
> Map<DefaultWeightedEdge, DefaultWeightedEdge> edgeMapping=...;
> "Weight of e in g1: "+ g1.getEdgeWeight(e);
> "Weight of e in g2: "+ g2.getEdgeWeight(edgeMapping.get(e));
> I would be happy to learn about cleaner methods.
>
>
> br,
>
> Joris
>
> ------------------------------------------------------------------------------
> Start Your Social Network Today - Download eXo Platform
> Build your Enterprise Intranet with eXo Platform Software
> Java Based Open Source Intranet - Social, Extensible, Cloud Ready
> Get Started Now And Turn Your Intranet Into A Collaboration Platform
> http://p.sf.net/sfu/ExoPlatform
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] setting edge weights

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

Hi,

I've encountered some issues with edge weights which potentially could
cause bugs. I was wondering whether some corrections in the code are
required.

Take the following simple code snippet:

//Define graph4, consisting of a single edge (0,1) *with edge weight 10*
WeightedGraph<Integer, DefaultWeightedEdge> graph4=new
SimpleWeightedGraph<Integer,
DefaultWeightedEdge>(DefaultWeightedEdge.class);
graph4.addVertex(0);
graph4.addVertex(1);
DefaultWeightedEdge e1= graph4.addEdge(0, 1);
graph4.setEdgeWeight(e1, *10*);
//Define graph5 without edges or vertices
SimpleWeightedGraph<Integer, DefaultWeightedEdge> graph5=new
SimpleWeightedGraph<Integer,
DefaultWeightedEdge>(DefaultWeightedEdge.class);
graph5.setEdgeWeight(e1, 5);

System.out.println("Edge weight graph 4: "+graph4.getEdgeWeight(e1));
*//OUTPUT: Edge weight graph 4: 5.0*

Notice that jgrapht allowed me to change the weight of edge e1 in graph4
through graph5 which does not even contain this edge. This seems pretty
awkward?

1. the setEdgeWeight should only work if the graph contains the edge.
2. I think that it would be a good idea to update the documentation of the
DefaultWeightedEdge, thereby emphasizing that edge weights are stored on
the edges, and not in the graph. Lets say you have 2 graphs, g1 and g2 both
containing the same edge e (same object). Invoking g1.setEdgeWeight(e, 10)
will also change the weight of this edge in graph g2.

I'm not sure how to accomplish the following:
Given a weighted graph g1, create a subgraph g2 containing a subset of the
edges of g1 with *different* weights. Then for a given edge e which is
contained in both g1 and g2, I would like to invoke:
"Weight of e in g1: "+ g1.getEdgeWeight(e);
"Weight of e in g2: "+ g2.getEdgeWeight(e);
I could do something ugly by creating a mapping from edges in graph g1 to
different edges in graph g2. Then for a given edge e in g1 I could invoke:
Map<DefaultWeightedEdge, DefaultWeightedEdge> edgeMapping=...;
"Weight of e in g1: "+ g1.getEdgeWeight(e);
"Weight of e in g2: "+ g2.getEdgeWeight(edgeMapping.get(e));
I would be happy to learn about cleaner methods.


br,

Joris