jgrapht-users — JGraphT user list.

Re: [jgrapht-users] Changing target or source / merge vertices

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

Remove it from the graph and then add it back with

http://jgrapht.org/javadoc/org/jgrapht/Graph.html#addEdge(V, V, E)

On Fri, Jul 5, 2013 at 9:19 AM, Rikless <eri...@gm...> wrote:
> Hi,
>
> Once an edge is created, how can I change its target or edge ?
> I've created a MyEdge Class with its own target and source fields which
> extends DefaultWeightedEdge, but source and target are not accessible from
> the DefaultWeightedEdge class.
>
> Actually, I need to process merging vertices into one, so related edges have
> to be modified.
>
> Any idea ?
> Thanks,
>
> Eric
>
>
>
> --
> View this message in context: http://jgrapht-users.107614.n3.nabble.com/Changing-target-or-source-merge-vertices-tp4024832.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Windows:
>
> Build for Windows Store.
>
> http://p.sf.net/sfu/windows-dev2dev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

[persteffen <per...@gm...>]

I had a similar problem, it turned out I had forgotten to implement the
hashCode() method. See:

https://github.com/jgrapht/jgrapht/wiki/EqualsAndHashCode




--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/graph-must-contain-the-start-vertex-when-running-KShortestPaths-tp4024797p4024833.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Changing target or source / merge vertices

[Rikless <eri...@gm...>]

Hi,

Once an edge is created, how can I change its target or edge ?
I've created a MyEdge Class with its own target and source fields which
extends DefaultWeightedEdge, but source and target are not accessible from
the DefaultWeightedEdge class.

Actually, I need to process merging vertices into one, so related edges have
to be modified.

Any idea ?
Thanks,

Eric



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Changing-target-or-source-merge-vertices-tp4024832.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] JGraphModelAdapter$ShieldedGraph is not Serializable

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

Probably no one tested serialization after adding ShieldedGraph.  Go
ahead and create a bug (and ideally submit a pull request).

Thanks!
JVS


On Wed, Jun 12, 2013 at 4:25 PM, Matt Futterman <m.f...@gm...> wrote:
> When I attempt to serialize an instance of JGraph constructed using a
> JGraphModelAdapter I get a java.io.NotSerializableException:
>    ...java.io.NotSerializableException:
> org.jgrapht.ext.JGraphModelAdapter$ShieldedGraph
>
> Looking at the source code I see:
>
>     private class ShieldedGraph
>     {
>         private final Graph<V, E> graph;
>
>         ShieldedGraph(Graph<V, E> graph)
>         {
>             this.graph = graph;
>         }
>      ...
>     }
>
> That is, the inner class ShieldedGraph does not implement Serializable. I
> can report this as a bug or change the source code, except I'm wondering if
> I'm missing something (the "right" way to serialize a JGraph) since
> otherwise this seems like a pretty obvious bug that would have been caught
> long ago. So, before I report this as a bug, etc., can anyone advise me on
> what would be the best way to proceed?
>
> Thank you,
> Matt
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Windows:
>
> Build for Windows Store.
>
> http://p.sf.net/sfu/windows-dev2dev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] JGraphModelAdapter$ShieldedGraph is not Serializable

[Matt F. <m.f...@gm...>]

When I attempt to serialize an instance of JGraph constructed using a
JGraphModelAdapter I get a java.io.NotSerializableException:
   ...java.io.NotSerializableException:
org.jgrapht.ext.JGraphModelAdapter$ShieldedGraph

Looking at the source code I see:

    private class ShieldedGraph
    {
        private final Graph<V, E> graph;

        ShieldedGraph(Graph<V, E> graph)
        {
            this.graph = graph;
        }
     ...
    }

That is, the inner class ShieldedGraph does not implement Serializable. I
can report this as a bug or change the source code, except I'm wondering if
I'm missing something (the "right" way to serialize a JGraph) since
otherwise this seems like a pretty obvious bug that would have been caught
long ago. So, before I report this as a bug, etc., can anyone advise me on
what would be the best way to proceed?

Thank you,
Matt

[jgrapht-users] Round vertices

[Juliane K. <1ju...@go...>]

Hello,
I would like to use a graph visualization with round vertizes. Is
there a possibility to change the angular form of the nodes to a round
form?

Re: [jgrapht-users] Licensing: Dual license JGraphT under EPL and LGPL

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

Hey everyone, Oliver has also posted this information on a wiki page:

https://github.com/jgrapht/jgrapht/wiki/Relicensing

If you have opinions on this effort, let's discuss them here on the
mailing list while we're in the process of contacting contributors,
which is going to take a while.

Thanks!
JVS

On Sat, May 25, 2013 at 1:26 AM, Oliver Kopp <ko...@gm...> wrote:
> Dear JGraphT users and developers,
>
> Currently, the JGraphT project is released under the LGPL. The Eclipse
> Software Foundation, however, decided to disallow LGPL libraries in their
> projects (http://mmilinkov.wordpress.com/2009/04/30/lgpl-pain/). A similar
> issue applies for projects under the umbrella of the Apache Software
> Foundation (http://www.apache.org/legal/3party.html).
>
> As a reciprocal license, LGPL requires anyone redistributing JGraphT to
> publish any source code changes they make. As the Eclipse Public License
> (EPL) also requires this, and is compatible with the regulations of the
> Apache Software Foundation ("Category B: Reciprocal Licenses" in
> http://www.apache.org/legal/3party.html), it seems like a good choice for
> resolving the incompatibilities. Hence we've started this initiative to dual
> license JGraphT under LGPL and EPL. This has been successfully done for the
> Logback project (http://logback.qos.ch/license.html) and the qooxdoo project
> (http://qooxdoo.org/license).
>
> It is not proposed to relicense JGraphT under BSD, MIT, or Apache 2.0
> license as it is acknowledged that the original authors may want
> modifications of their code being published, and these kind of licenses do
> not enforce that.
>
> All in all, we propose to relicense JGraphT under the following terms:
>
> --cut--
> JGraphT Licensing Information
> =============================
>
> JGraphT may be used under the terms of either the
>
>   * GNU Lesser General Public License (LGPL) 2.1
>     http://www.gnu.org/licenses/lgpl-2.1.html
>
> or the
>
>   * Eclipse Public License (EPL)
>     http://www.eclipse.org/org/documents/epl-v10.php
>
> As a recipient of JGraphT, you may choose which license to receive the code
> under.
> --end--
>
> This also includes future commits. Contributions will only be accepted with
> the understanding that the contributor's code will be released under both
> licenses and that a user may freely choose between one of the licenses.
>
> Contributions to JGraphT have up to this point been LGPL-only, with no
> Copyright License Assignment (CLA) required from contributors. As such,
> relicensing requires seeking the consent of all contributors (or possibly
> removing contributions for which such consent has been withheld). We will
> make a best effort to contact all past contributors and request their
> consent. JGraphT has a long history (going back ten years to 2003),
> including many small contributions from one-time contributors. If we don't
> hear back from someone within a few months, we'll assume Qui tacet
> consentiret. Until copyright expiration, this may leave a very small amount
> of unavoidable legal risk for those who choose to rely on the EPL licensing
> option. There is no risk for those who continue to use JGraphT under the
> LGPL option.
>
> We collected all contributors from the git authors, from the authors and
> contributors listed in each java file, and from CONTRIBUTORS.md. These are
> 65 persons. We will try to find out the contact data of everyone and ask
> them if they agree to additionally license their work under EPL.
>
> Looking forward to hearing your opinion.
>
> Greetings,
>
> Oliver and John
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Licensing: Dual license JGraphT under EPL and LGPL

[Oliver K. <ko...@gm...>]

Dear JGraphT users and developers,

Currently, the JGraphT project is released under the LGPL. The Eclipse
Software Foundation, however, decided to disallow LGPL libraries in their
projects (http://mmilinkov.wordpress.com/2009/04/30/lgpl-pain/). A similar
issue applies for projects under the umbrella of the Apache Software
Foundation (http://www.apache.org/legal/3party.html).

As a reciprocal license, LGPL requires anyone redistributing JGraphT to
publish any source code changes they make. As the Eclipse Public License
(EPL) also requires this, and is compatible with the regulations of the
Apache Software Foundation ("Category B: Reciprocal Licenses" in
http://www.apache.org/legal/3party.html), it seems like a good choice for
resolving the incompatibilities. Hence we've started this initiative to
dual license JGraphT under LGPL and EPL. This has been successfully done
for the Logback project (http://logback.qos.ch/license.html) and the
qooxdoo project (http://qooxdoo.org/license).

It is not proposed to relicense JGraphT under BSD, MIT, or Apache 2.0
license as it is acknowledged that the original authors may want
modifications of their code being published, and these kind of licenses do
not enforce that.

All in all, we propose to relicense JGraphT under the following terms:

--cut--
JGraphT Licensing Information
=============================

JGraphT may be used under the terms of either the

  * GNU Lesser General Public License (LGPL) 2.1
    http://www.gnu.org/licenses/lgpl-2.1.html

or the

  * Eclipse Public License (EPL)
    http://www.eclipse.org/org/documents/epl-v10.php

As a recipient of JGraphT, you may choose which license to receive the code
under.
--end--

This also includes future commits. Contributions will only be accepted with
the understanding that the contributor's code will be released under both
licenses and that a user may freely choose between one of the licenses.

Contributions to JGraphT have up to this point been LGPL-only, with no
Copyright License Assignment (CLA) required from contributors. As such,
relicensing requires seeking the consent of all contributors (or possibly
removing contributions for which such consent has been withheld). We will
make a best effort to contact all past contributors and request their
consent. JGraphT has a long history (going back ten years to 2003),
including many small contributions from one-time contributors. If we don't
hear back from someone within a few months, we'll assume Qui tacet
consentiret. Until copyright expiration, this may leave a very small amount
of unavoidable legal risk for those who choose to rely on the EPL licensing
option. There is no risk for those who continue to use JGraphT under the
LGPL option.

We collected all contributors from the git authors, from the authors and
contributors listed in each java file, and from CONTRIBUTORS.md. These are
65 persons. We will try to find out the contact data of everyone and ask
them if they agree to additionally license their work under EPL.

Looking forward to hearing your opinion.

Greetings,

Oliver and John

Re: [jgrapht-users] strange output when running the example from [https://github.com/jgrapht/jgrapht/wiki/LabeledEdges]

[Jim - FooBar(); <jim...@gm...>]

I am so sorry guys - my bad....the code wasn't *exactly* the same per ce...

massive apologies for the noise :(

Jim


On 20/05/13 21:13, Jim - FooBar(); wrote:
> Hi everyone,
>
> this is my very first post on this list so I apologise if this has 
> been asked before but I couldn't find anything relevant on the web...
>
> I followed the example found here : 
> https://github.com/jgrapht/jgrapht/wiki/LabeledEdges but I am getting 
> the following output:
>
> //I have replaced /"is a friend of"/ with "likes" & /"is an enemy of"/ 
> with "hates"
>
> _John likes John_
> John hates John
> _John likes James_
> John hates James
> _John likes Sarah_
> John hates Sarah
> _John likes Jessica_
> John hates Jessica
> James likes John
> _James hates John_
> _Jessica likes James_
> Jessica hates James
> _Jessica likes Sarah_
> Jessica hates Sarah
> Sarah likes James
> _Sarah hates James_
>
> Surely something is wrong here... For starters, I should only have 8 
> edges, not 16 and simply  doing graph.edgeSet() does confirm 8 edges! 
> But the loop prints 16 and I have no idea where the non-underlined 
> ones come from...
>
> Has anyone else run into this? I am extremely confused...I'm trying to 
> get up to speed with JGraphT but such a simple example fails 
> miserably... :(
>
> thanks a lot in advance,
>
> Jim

[jgrapht-users] strange output when running the example from [https://github.com/jgrapht/jgrapht/wiki/LabeledEdges]

[Jim - FooBar(); <jim...@gm...>]

Hi everyone,

this is my very first post on this list so I apologise if this has been 
asked before but I couldn't find anything relevant on the web...

I followed the example found here : 
https://github.com/jgrapht/jgrapht/wiki/LabeledEdges but I am getting 
the following output:

//I have replaced /"is a friend of"/ with "likes" & /"is an enemy of"/ 
with "hates"

_John likes John_
John hates John
_John likes James_
John hates James
_John likes Sarah_
John hates Sarah
_John likes Jessica_
John hates Jessica
James likes John
_James hates John_
_Jessica likes James_
Jessica hates James
_Jessica likes Sarah_
Jessica hates Sarah
Sarah likes James
_Sarah hates James_

Surely something is wrong here... For starters, I should only have 8 
edges, not 16 and simply  doing graph.edgeSet() does confirm 8 edges! 
But the loop prints 16 and I have no idea where the non-underlined ones 
come from...

Has anyone else run into this? I am extremely confused...I'm trying to 
get up to speed with JGraphT but such a simple example fails miserably... :(

thanks a lot in advance,

Jim

Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths

[Sebastian M. <woo...@gm...>]

Osama,

it is included in the latest commit on github: 
https://github.com/jgrapht/jgrapht


Sebastian


Am 06.05.2013 14:30, schrieb Osama Elswah:
> Hello
> Where can I find the fix to this problem ?
>
>
>
> On Tue, Apr 30, 2013 at 11:53 AM, gu boulmi <bou...@ya... 
> <mailto:bou...@ya...>> wrote:
>
>     I really also hope that it is the last ==/equals bug in the KSP
>     algorithm !
>
>     Your remark about the String ID's is good and it makes think that
>     the bug raised by Sebastian could only apply to graphs constructed
>     this way. Good point !
>
>     Guillaume
>
>     ------------------------------------------------------------------------
>     *De :* John Sichi <js...@gm... <mailto:js...@gm...>>
>     *À :* gu boulmi <bou...@ya... <mailto:bou...@ya...>>
>     *Cc :* "jgr...@li...
>     <mailto:jgr...@li...>"
>     <jgr...@li...
>     <mailto:jgr...@li...>>
>     *Envoyé le :* Mardi 30 avril 2013 7h12
>     *Objet :* Re: [jgrapht-users] Tr : "graph must contain the start
>     vertex" when running KShortestPaths
>
>     Thanks a lot for following up.  I've applied all of the changes for
>     completeness.
>
>     Regarding your PS, I do not believe that any ID's actually "changed"
>     during the execution.  It's just that when the strings are read in
>     from the text file, multiple String objects are created with the same
>     value.  And even though there's only one D007 vertex object added to
>     the graph, there can be different String objects in the edges which
>     reference it.
>
>     I hope that is the last ==/equals bug (we've had the same problem show
>     up in other algorithms).  It's hard to write a findbugs rule to catch
>     it since there are legitimate reasons to use == in some cases.
>
>     JVS
>
>
>     On Mon, Apr 29, 2013 at 8:02 AM, gu boulmi <bou...@ya...
>     <mailto:bou...@ya...>> wrote:
>     > I forgot the mailing list...
>     >
>     > ----- Mail transféré -----
>     > De : gu boulmi <bou...@ya... <mailto:bou...@ya...>>
>     > À : John Sichi <js...@gm... <mailto:js...@gm...>>
>     > Cc : Sebastian Müller <woo...@gm...
>     <mailto:woo...@gm...>>
>     > Envoyé le : Samedi 27 avril 2013 15h32
>     >
>     > Objet : Re: [jgrapht-users] "graph must contain the start
>     vertex" when
>     > running KShortestPaths
>     >
>     > Hi,
>     > Actually a lost of JUnit tests on graphs with cycles (e.g. all
>     the tests on
>     > complete graphs) already exists and it works.
>     >
>     > In fact, I think that the initial isSimplePath method would work
>     fine on any
>     > graph provided that a String vertex does not
>     > change id during the execution of the KSP algorithm (see my
>     comments in my
>     > mail 17.04.2013).
>     >
>     > The root cause of the problem encountered by Sebastian about the
>     non-simple
>     > paths result is rather (again) the use of the != instead of
>     !equals  in a
>     > method, namely in the
>     KShortestPathsIterator#updateOutgoingVertices method :
>     >    // check if the path does not loop over the start vertex.
>     >    if (vertexReachedByEdge != this.startVertex)
>     >
>     > instead it should be :
>     >    if (!vertexReachedByEdge.equals(this.startVertex))
>     >
>     > The correction from my previous mail 24.04.2013 of the
>     isSimplePath method
>     > can be preserved however.
>     > Indeed, accordinf to the name of the method is should return
>     true only for a
>     > path path with no repeated vertices and the
>     > former implementation made an exception to that for the start
>     vertex.
>     >
>     > To sum up, the correction attached to the KShortestPathsIterator
>     class would
>     > be enough. Nevertheless the correction from my mail 24.04.2013
>     can be
>     > preserved anyway for the sake of clarity of the isSimplePath method.
>     >
>     > Best regards,
>     > Guillaume
>     >
>     > P.S. : I do not know yet why a String vertex like D007 would
>     change id
>     > during the execution of the algorithm. I guess it is specific to
>     String
>     > vertices...
>     >
>     >
>     > De : John Sichi <js...@gm... <mailto:js...@gm...>>
>     > À : gu boulmi <bou...@ya... <mailto:bou...@ya...>>
>     > Cc : Sebastian Müller <woo...@gm...
>     <mailto:woo...@gm...>>;
>     > "jgr...@li...
>     <mailto:jgr...@li...>"
>     <jgr...@li...
>     <mailto:jgr...@li...>>
>     > Envoyé le : Jeudi 25 avril 2013 9h08
>     > Objet : Re: [jgrapht-users] "graph must contain the start
>     vertex" when
>     > running KShortestPaths
>     >
>     > Thanks!  I will update github.  Probably the reason the existing
>     tests
>     > didn't catch the problem is that they use a graph without cycles?
>     >
>     > Looks like in the past it has already been spotted out there in
>     the wild, so
>     > I am glad it is getting fixed!
>     >
>     >
>     http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-td4024711.html
>     >
>     > JVS
>     >
>     > On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <bou...@ya...
>     <mailto:bou...@ya...>> wrote:
>     >
>     > Hi,
>     > You're so right with the do/while.
>     > Please find attached a new correction to the
>     RankingPathElementList class
>     > along with a JUnit test (reproducing the test program of
>     Sebastian that led
>     > to the IllegalArgumentException with text "graph must contain
>     the start
>     > vertex").
>     > I just wonder why this error did not pop up earlier with the
>     existing JUnit
>     > tests about the number of paths returned by the KSP algorithm.
>     >
>     > I think that there is no problem with the PathMask constructor.
>     No change
>     > needed.
>     >
>     > Best regards,
>     > Guillaume
>     >
>     > De : John Sichi <js...@gm... <mailto:js...@gm...>>
>     > À : Sebastian Müller <woo...@gm...
>     <mailto:woo...@gm...>>
>     > Cc : "jgr...@li...
>     <mailto:jgr...@li...>"
>     > <jgr...@li...
>     <mailto:jgr...@li...>>
>     > Envoyé le : Jeudi 18 avril 2013 0h18
>     > Objet : Re: [jgrapht-users] "graph must contain the start
>     vertex" when
>     > running KShortestPaths
>     >
>     > Guillaume:  thanks for looking into this!
>     >
>     > Sebastian:  you're right about the non-simple paths.  Looking at
>     the same
>     > isSimplePath method, it looks like it should be using a do/while
>     construct
>     > instead of a while/do construct.  If I make that change, then
>     with your test
>     > case, I get back only simple paths (which are longer than the
>     "cheating by
>     > running around in circles" non-simple paths).  Guillaume, do you
>     think I
>     > should make this change?  If so do I need to make a
>     corresponding change in
>     > the PathMask constructor?
>     >
>     >
>     > On Wed, Apr 17, 2013 at 3:49 AM, Sebastian Müller
>     <woo...@gm... <mailto:woo...@gm...>>
>     > wrote:
>     >
>     > Hi all,
>     >
>     > I can confirm that the exception is now gone. Thanks for the
>     quick fix!
>     > Just one more thing. The javadoc for KShortestPaths states 'The
>     algorithm
>     > determines the k shortest simple paths [...]'. According to my
>     understanding
>     > the paths calculated by KShortestPaths are not simple. See my
>     example below.
>     >
>     > [code]
>     > <M042    M013    0.90>    : 0.90
>     > <M042    M043    0.76>    <M043   M042    0.76>    <M042    M013
>     > 0.909439166411278>    : 2.43
>     > <M042    M029    0.87>    <M029   M042    0.96>    <M042    M013
>     0.90>
>     > : 2.74
>     > <M042    M044    0.92>    <M044   M043    0.76>    <M043    M042
>     0.76>
>     > <M042    M013    0.90>    : 3.36
>     > <M042    M028    0.91>    <M028   M043    0.81>    <M043    M042
>     0.76>
>     > <M042    M013    0.90>    : 3.39
>     > [/code]
>     >
>     >
>     > Thanks for the great work with JGraphT, all!
>     >
>     > Sebastian
>     >
>     >
>     > Am 17.04.2013 11:52, schrieb gu boulmi:
>     >
>     > Hi all,
>     > I just made a debug thanks to the test provided by Sebastian.
>     > See attached the correction.
>     >
>     > I came to the conclusion that was a mistake in the way to test
>     whether there
>     > is a loop in a path (i.e. two of the same vertex in the path) in
>     the method
>     > org.jgrapht.alg.RankingPathElementList#isSimplePath
>     >
>     > Actually, the test failed when testing the simple path property
>     of a path
>     > resulting from adding the edge M004-D007 at the end of path
>     > M014-D010-D007-M004. Of course the resulting path is not simple
>     (twice
>     > D007), however it returned true.
>     > When debugging, it appears that the id of the D007 vertex of the
>     edge
>     > M004-D007 and the id of the D007 vertex of the path
>     M014-D010-D007-M004 were
>     > not the same, although they represent the same vertex (namely
>     D007). The
>     > existing implementation wrongly returned true because the ids of
>     D007 were
>     > not the same while it tested the equality with the == method.
>     >
>     > I changed it by replacing the == by the equals method and it
>     just works.
>     > New implementation is now :
>     > private boolean isSimplePath(
>     >        RankingPathElement<V, E> prevPathElement,
>     >        E edge)
>     >    {
>     >        RankingPathElement<V, E> pathElementToTest = prevPathElement;
>     >        while (pathElementToTest.getPrevEdge() != null) {
>     >            if (pathElementToTest.getVertex().equals(this.vertex)) {
>     >                return false;
>     >            } else {
>     >                pathElementToTest =
>     pathElementToTest.getPrevPathElement();
>     >            }
>     >        }
>     >
>     >        return true;
>     >    }
>     >
>     > Strange anyway : no guess why a String vertex like D007 would
>     change id
>     > during the execution of the algorithm.
>     >
>     > Best regards,
>     > Guillaume
>     >
>     > De : John Sichi <js...@gm... <mailto:js...@gm...>>
>     > À : Osama Elswah <osa...@gm...
>     <mailto:osa...@gm...>>
>     > Cc : "jgr...@li...
>     <mailto:jgr...@li...>"
>     > <jgr...@li...
>     <mailto:jgr...@li...>>
>     > Envoyé le : Mardi 16 avril 2013 23h04
>     > Objet : Re: [jgrapht-users] "graph must contain the start
>     vertex" when
>     > running KShortestPaths
>     >
>     > Before my previous reply, I reproduced Sebastian's problem by
>     running his
>     > code, which is why I say it's a bug.  His input graph is correctly
>     > constructed, so there's no reason that assertion should be hit.
>     >
>     >
>     > On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah
>     <osa...@gm... <mailto:osa...@gm...>>
>     > wrote:
>     >
>     > I have been using KShortestPath for some time now, and it has
>     been doing its
>     > purpose. I am not sure it has a bug.
>     > This is how I use it
>     >
>     > for(V n : network.vertexSet())
>     >        {
>     >            KShortestPaths<V, E> k = new KShortestPaths<V,
>     E>(network, n,
>     > k);
>     >            for(Demand<V> d : demands.getAllDemands())
>     >            {
>     > if((d.getSourceNode().equals(n)))
>     >                {
>     >                    demand_paths = k.getPaths(d.getTargetNode());
>     > pathsMap.put(d.getSourceNode(), d.getTargetNode(),
>     > demand_paths);
>     >                }
>     >            }
>     >        }
>     >    }
>     >
>     > What is the output of this line ?
>     >
>     > DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>     >
>     > I believe if you debug more there you will find the problem
>     >
>     > good luck
>     >
>     >
>     > On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...
>     <mailto:js...@gm...>> wrote:
>     >
>     > Looks like a bug in KShortestPaths. Internally, the algorithm
>     uses a masked
>     > version of the original graph, and the mask omits a vertex on
>     which the
>     > algorithm attempts the connectivity test, leading to the
>     assertion failure.
>     > Anyone know the algorithm well enough to submit a fix with
>     confidence?
>     >
>     > JVS
>     >
>     >
>     >
>     > On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller
>     <woo...@gm... <mailto:woo...@gm...>>
>     > wrote:
>     >
>     > Hello,
>     >
>     > sorry this is such a long mail, but I included a test program,
>     and my graph
>     > is quite large.
>     >
>     > I am using JGraphT to create graphs of my data with great
>     success so far.
>     > However, now I am trying to calculate the shortest paths between
>     two nodes
>     > using KShortestPaths, and I only receive the following exception:
>     >
>     > [code]
>     > java.lang.IllegalArgumentException: graph must contain the start
>     vertex
>     >    at
>     >
>     org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
>     >    at
>     >
>     org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
>     >    at
>     >
>     org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
>     >    at
>     >
>     org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
>     >    at
>     >
>     org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
>     >    at
>     >
>     org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
>     >    at
>     >
>     org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
>     >    at
>     >
>     org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
>     >    at
>     >
>     org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
>     >    at
>     >
>     org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
>     >    at
>     org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
>     >    at KShortestPathsMain.main(KShortestPathsMain.java:97)
>     > [/code]
>     >
>     > Note that I am only getting this exception with that one, large
>     graph I
>     > created from my data. When I create a graph by hand, it does not
>     occur. Here
>     > is my test program. The graph is attached.
>     >
>     > [code]
>     > import java.io.BufferedReader;
>     > import java.io.FileNotFoundException;
>     > import java.io.FileReader;
>     > import java.io.IOException;
>     > import java.util.List;
>     >
>     > import org.jgrapht.GraphPath;
>     > import org.jgrapht.alg.KShortestPaths;
>     > import org.jgrapht.graph.DefaultWeightedEdge;
>     > import org.jgrapht.graph.SimpleWeightedGraph;
>     >
>     > public class KShortestPathsMain {
>     >
>     >    public KShortestPathsMain() {}
>     >
>     >    public static void main(String[] args) {
>     >
>     >        SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
>     > SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>     >
>     >            FileReader fstream = null;
>     >            try {
>     >                fstream = new FileReader("edges.txt");
>     >            } catch (FileNotFoundException e1) {
>     >                e1.printStackTrace();
>     >            }
>     >            BufferedReader in = new BufferedReader(fstream);
>     >
>     >            String[] edgeText;
>     >            DefaultWeightedEdge ed;
>     >            String line = null;
>     >            try {
>     >                line = in.readLine();
>     >            } catch (IOException e1) {
>     >                // TODO Auto-generated catch block
>     >                e1.printStackTrace();
>     >            }
>     >            while(line != null) {
>     >                edgeText = line.split("\t");
>     >
>     > graph.addVertex(edgeText[0]);
>     > graph.addVertex(edgeText[1]);
>     >                ed = graph.addEdge(edgeText[0], edgeText[1]);
>     >                graph.setEdgeWeight(ed,
>     Double.parseDouble(edgeText[2]));
>     >
>     >                try {
>     >                    line = in.readLine();
>     >                } catch (IOException e) {
>     >                    e.printStackTrace();
>     >                }
>     >            }
>     >
>     >            // Close the input stream
>     >            try {
>     >                in.close();
>     >            } catch (IOException e1) {
>     >                e1.printStackTrace();
>     >            }
>     >
>     >        DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>     >
>     >        KShortestPaths<String, DefaultWeightedEdge> kPaths = new
>     > KShortestPaths<String, DefaultWeightedEdge>(
>     >                graph, graph.getEdgeSource(src), 5);
>     > List<GraphPath<String,DefaultWeightedEdge>> paths = null;
>     >
>     >        try {
>     >            paths = kPaths.getPaths(graph.getEdgeTarget(src));
>     >            for (GraphPath<String, DefaultWeightedEdge> path :
>     paths) {
>     >                for (DefaultWeightedEdge edge : path.getEdgeList()) {
>     > System.out.print("<" + graph.getEdgeSource(edge) + "\t"
>     >                            + graph.getEdgeTarget(edge) + "\t" +
>     edge +
>     > ">\t");
>     >                }
>     >                System.out.println(": " + path.getWeight());
>     >            }
>     >        } catch (IllegalArgumentException e) {
>     >            e.printStackTrace();
>     >        }
>     >    }
>     > }
>     >
>     > [/code]
>     >
>     > I tried different edges, and directed and undirected graphs.
>     Same result. If
>     > anyone has a clue what might be going on here, I'd very much
>     appreciate
>     > help.
>     >
>     >
>     > Sebastian
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Precog is a next-generation analytics platform capable of advanced
>     > analytics on semi-structured data. The platform includes APIs
>     for building
>     > apps and a phenomenal toolset for data science. Developers can use
>     > our toolset for easy data analysis & visualization. Get a free
>     account!
>     > http://www2.precog.com/precogplatform/slashdotnewsletter
>     > _______________________________________________
>     > jgrapht-users mailing list
>     > jgr...@li...
>     <mailto:jgr...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>     >
>     >
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Precog is a next-generation analytics platform capable of advanced
>     > analytics on semi-structured data. The platform includes APIs
>     for building
>     > apps and a phenomenal toolset for data science. Developers can use
>     > our toolset for easy data analysis & visualization. Get a free
>     account!
>     > http://www2.precog.com/precogplatform/slashdotnewsletter
>     > _______________________________________________
>     > jgrapht-users mailing list
>     > jgr...@li...
>     <mailto:jgr...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>     >
>     >
>     >
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Precog is a next-generation analytics platform capable of advanced
>     > analytics on semi-structured data. The platform includes APIs
>     for building
>     > apps and a phenomenal toolset for data science. Developers can use
>     > our toolset for easy data analysis & visualization. Get a free
>     account!
>     > http://www2.precog.com/precogplatform/slashdotnewsletter
>     > _______________________________________________
>     > jgrapht-users mailing list
>     > jgr...@li...
>     <mailto:jgr...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>     >
>     >
>     >
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Precog is a next-generation analytics platform capable of advanced
>     > analytics on semi-structured data. The platform includes APIs
>     for building
>     > apps and a phenomenal toolset for data science. Developers can use
>     > our toolset for easy data analysis & visualization. Get a free
>     account!
>     > http://www2.precog.com/precogplatform/slashdotnewsletter
>     >
>     >
>     >
>     > _______________________________________________
>     > jgrapht-users mailing list
>     > jgr...@li...
>     <mailto:jgr...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>     >
>     >
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Precog is a next-generation analytics platform capable of advanced
>     > analytics on semi-structured data. The platform includes APIs
>     for building
>     > apps and a phenomenal toolset for data science. Developers can use
>     > our toolset for easy data analysis & visualization. Get a free
>     account!
>     > http://www2.precog.com/precogplatform/slashdotnewsletter
>     > _______________________________________________
>     > jgrapht-users mailing list
>     > jgr...@li...
>     <mailto:jgr...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>     >
>     >
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Precog is a next-generation analytics platform capable of advanced
>     > analytics on semi-structured data. The platform includes APIs
>     for building
>     > apps and a phenomenal toolset for data science. Developers can use
>     > our toolset for easy data analysis & visualization. Get a free
>     account!
>     > http://www2.precog.com/precogplatform/slashdotnewsletter
>     > _______________________________________________
>     > jgrapht-users mailing list
>     > jgr...@li...
>     <mailto:jgr...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>     >
>     >
>     >
>     >
>     >
>     >
>     >
>     >
>     >
>     ------------------------------------------------------------------------------
>     > Try New Relic Now & We'll Send You this Cool Shirt
>     > New Relic is the only SaaS-based application performance
>     monitoring service
>     > that delivers powerful full stack analytics. Optimize and
>     monitor your
>     > browser, app, & servers with just a few lines of code. Try New Relic
>     > and get this awesome Nerd Life shirt!
>     http://p.sf.net/sfu/newrelic_d2d_apr
>     > _______________________________________________
>     > jgrapht-users mailing list
>     > jgr...@li...
>     <mailto:jgr...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>     >
>
>     ------------------------------------------------------------------------------
>     Introducing AppDynamics Lite, a free troubleshooting tool for
>     Java/.NET
>     Get 100% visibility into your production application - at no cost.
>     Code-level diagnostics for performance bottlenecks with <2% overhead
>     Download for free and get started troubleshooting in minutes.
>     http://p.sf.net/sfu/appdyn_d2d_ap1
>     _______________________________________________
>     jgrapht-users mailing list
>     jgr...@li...
>     <mailto:jgr...@li...>
>     https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>     ------------------------------------------------------------------------------
>     Introducing AppDynamics Lite, a free troubleshooting tool for
>     Java/.NET
>     Get 100% visibility into your production application - at no cost.
>     Code-level diagnostics for performance bottlenecks with <2% overhead
>     Download for free and get started troubleshooting in minutes.
>     http://p.sf.net/sfu/appdyn_d2d_ap1
>     _______________________________________________
>     jgrapht-users mailing list
>     jgr...@li...
>     <mailto:jgr...@li...>
>     https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Introducing AppDynamics Lite, a free troubleshooting tool for Java/.NET
> Get 100% visibility into your production application - at no cost.
> Code-level diagnostics for performance bottlenecks with <2% overhead
> Download for free and get started troubleshooting in minutes.
> http://p.sf.net/sfu/appdyn_d2d_ap1
>
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths

[Osama E. <osa...@gm...>]

Hello
Where can I find the fix to this problem ?



On Tue, Apr 30, 2013 at 11:53 AM, gu boulmi <bou...@ya...> wrote:

> I really also hope that it is the last ==/equals bug in the KSP algorithm
> !
>
> Your remark about the String ID's is good and it makes think that the bug
> raised by Sebastian could only apply to graphs constructed this way. Good
> point !
>
> Guillaume
>
>   ------------------------------
>  *De :* John Sichi <js...@gm...>
> *À :* gu boulmi <bou...@ya...>
> *Cc :* "jgr...@li..." <
> jgr...@li...>
> *Envoyé le :* Mardi 30 avril 2013 7h12
> *Objet :* Re: [jgrapht-users] Tr : "graph must contain the start vertex"
> when running KShortestPaths
>
> Thanks a lot for following up.  I've applied all of the changes for
> completeness.
>
> Regarding your PS, I do not believe that any ID's actually "changed"
> during the execution.  It's just that when the strings are read in
> from the text file, multiple String objects are created with the same
> value.  And even though there's only one D007 vertex object added to
> the graph, there can be different String objects in the edges which
> reference it.
>
> I hope that is the last ==/equals bug (we've had the same problem show
> up in other algorithms).  It's hard to write a findbugs rule to catch
> it since there are legitimate reasons to use == in some cases.
>
> JVS
>
>
> On Mon, Apr 29, 2013 at 8:02 AM, gu boulmi <bou...@ya...> wrote:
> > I forgot the mailing list...
> >
> > ----- Mail transféré -----
> > De : gu boulmi <bou...@ya...>
> > À : John Sichi <js...@gm...>
> > Cc : Sebastian Müller <woo...@gm...>
> > Envoyé le : Samedi 27 avril 2013 15h32
> >
> > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> > running KShortestPaths
> >
> > Hi,
> > Actually a lost of JUnit tests on graphs with cycles (e.g. all the tests
> on
> > complete graphs) already exists and it works.
> >
> > In fact, I think that the initial isSimplePath method would work fine on
> any
> > graph provided that a String vertex does not
> > change id during the execution of the KSP algorithm (see my comments in
> my
> > mail 17.04.2013).
> >
> > The root cause of the problem encountered by Sebastian about the
> non-simple
> > paths result is rather (again) the use of the != instead of !equals  in a
> > method, namely in the KShortestPathsIterator#updateOutgoingVertices
> method :
> >    // check if the path does not loop over the start vertex.
> >    if (vertexReachedByEdge != this.startVertex)
> >
> > instead it should be :
> >    if (!vertexReachedByEdge.equals(this.startVertex))
> >
> > The correction from my previous mail 24.04.2013 of the isSimplePath
> method
> > can be preserved however.
> > Indeed, accordinf to the name of the method is should return true only
> for a
> > path path with no repeated vertices and the
> > former implementation made an exception to that for the start vertex.
> >
> > To sum up, the correction attached to the KShortestPathsIterator class
> would
> > be enough. Nevertheless the correction from my mail 24.04.2013 can be
> > preserved anyway for the sake of clarity of the isSimplePath method.
> >
> > Best regards,
> > Guillaume
> >
> > P.S. : I do not know yet why a String vertex like D007 would change id
> > during the execution of the algorithm. I guess it is specific to String
> > vertices...
> >
> >
> > De : John Sichi <js...@gm...>
> > À : gu boulmi <bou...@ya...>
> > Cc : Sebastian Müller <woo...@gm...>;
> > "jgr...@li..." <
> jgr...@li...>
> > Envoyé le : Jeudi 25 avril 2013 9h08
> > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> > running KShortestPaths
> >
> > Thanks!  I will update github.  Probably the reason the existing tests
> > didn't catch the problem is that they use a graph without cycles?
> >
> > Looks like in the past it has already been spotted out there in the
> wild, so
> > I am glad it is getting fixed!
> >
> >
> http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-td4024711.html
> >
> > JVS
> >
> > On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <bou...@ya...> wrote:
> >
> > Hi,
> > You're so right with the do/while.
> > Please find attached a new correction to the RankingPathElementList class
> > along with a JUnit test (reproducing the test program of Sebastian that
> led
> > to the IllegalArgumentException with text "graph must contain the start
> > vertex").
> > I just wonder why this error did not pop up earlier with the existing
> JUnit
> > tests about the number of paths returned by the KSP algorithm.
> >
> > I think that there is no problem with the PathMask constructor. No change
> > needed.
> >
> > Best regards,
> > Guillaume
> >
> > De : John Sichi <js...@gm...>
> > À : Sebastian Müller <woo...@gm...>
> > Cc : "jgr...@li..."
> > <jgr...@li...>
> > Envoyé le : Jeudi 18 avril 2013 0h18
> > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> > running KShortestPaths
> >
> > Guillaume:  thanks for looking into this!
> >
> > Sebastian:  you're right about the non-simple paths.  Looking at the same
> > isSimplePath method, it looks like it should be using a do/while
> construct
> > instead of a while/do construct.  If I make that change, then with your
> test
> > case, I get back only simple paths (which are longer than the "cheating
> by
> > running around in circles" non-simple paths).  Guillaume, do you think I
> > should make this change?  If so do I need to make a corresponding change
> in
> > the PathMask constructor?
> >
> >
> > On Wed, Apr 17, 2013 at 3:49 AM, Sebastian Müller <woo...@gm...>
> > wrote:
> >
> > Hi all,
> >
> > I can confirm that the exception is now gone. Thanks for the quick fix!
> > Just one more thing. The javadoc for KShortestPaths states 'The algorithm
> > determines the k shortest simple paths [...]'. According to my
> understanding
> > the paths calculated by KShortestPaths are not simple. See my example
> below.
> >
> > [code]
> > <M042    M013    0.90>    : 0.90
> > <M042    M043    0.76>    <M043    M042    0.76>    <M042    M013
> > 0.909439166411278>    : 2.43
> > <M042    M029    0.87>    <M029    M042    0.96>    <M042    M013
> 0.90>
> > : 2.74
> > <M042    M044    0.92>    <M044    M043    0.76>    <M043    M042
> 0.76>
> > <M042    M013    0.90>    : 3.36
> > <M042    M028    0.91>    <M028    M043    0.81>    <M043    M042
> 0.76>
> > <M042    M013    0.90>    : 3.39
> > [/code]
> >
> >
> > Thanks for the great work with JGraphT, all!
> >
> > Sebastian
> >
> >
> > Am 17.04.2013 11:52, schrieb gu boulmi:
> >
> > Hi all,
> > I just made a debug thanks to the test provided by Sebastian.
> > See attached the correction.
> >
> > I came to the conclusion that was a mistake in the way to test whether
> there
> > is a loop in a path (i.e. two of the same vertex in the path) in the
> method
> > org.jgrapht.alg.RankingPathElementList#isSimplePath
> >
> > Actually, the test failed when testing the simple path property of a path
> > resulting from adding the edge M004-D007 at the end of path
> > M014-D010-D007-M004. Of course the resulting path is not simple (twice
> > D007), however it returned true.
> > When debugging, it appears that the id of the D007 vertex of the edge
> > M004-D007 and the id of the D007 vertex of the path M014-D010-D007-M004
> were
> > not the same, although they represent the same vertex (namely D007). The
> > existing implementation wrongly returned true because the ids of D007
> were
> > not the same while it tested the equality with the == method.
> >
> > I changed it by replacing the == by the equals method and it just works.
> > New implementation is now :
> > private boolean isSimplePath(
> >        RankingPathElement<V, E> prevPathElement,
> >        E edge)
> >    {
> >        RankingPathElement<V, E> pathElementToTest = prevPathElement;
> >        while (pathElementToTest.getPrevEdge() != null) {
> >            if (pathElementToTest.getVertex().equals(this.vertex)) {
> >                return false;
> >            } else {
> >                pathElementToTest =
> pathElementToTest.getPrevPathElement();
> >            }
> >        }
> >
> >        return true;
> >    }
> >
> > Strange anyway : no guess why a String vertex like D007 would change id
> > during the execution of the algorithm.
> >
> > Best regards,
> > Guillaume
> >
> > De : John Sichi <js...@gm...>
> > À : Osama Elswah <osa...@gm...>
> > Cc : "jgr...@li..."
> > <jgr...@li...>
> > Envoyé le : Mardi 16 avril 2013 23h04
> > Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> > running KShortestPaths
> >
> > Before my previous reply, I reproduced Sebastian's problem by running his
> > code, which is why I say it's a bug.  His input graph is correctly
> > constructed, so there's no reason that assertion should be hit.
> >
> >
> > On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah <
> osa...@gm...>
> > wrote:
> >
> > I have been using KShortestPath for some time now, and it has been doing
> its
> > purpose. I am not sure it has a bug.
> > This is how I use it
> >
> > for(V n : network.vertexSet())
> >        {
> >            KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n,
> > k);
> >            for(Demand<V> d : demands.getAllDemands())
> >            {
> >                if((d.getSourceNode().equals(n)))
> >                {
> >                    demand_paths = k.getPaths(d.getTargetNode());
> >                    pathsMap.put(d.getSourceNode(), d.getTargetNode(),
> > demand_paths);
> >                }
> >            }
> >        }
> >    }
> >
> > What is the output of this line ?
> >
> > DefaultWeightedEdge src = graph.getEdge("M013", "M014");
> >
> > I believe if you debug more there you will find the problem
> >
> > good luck
> >
> >
> > On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote:
> >
> > Looks like a bug in KShortestPaths.  Internally, the algorithm uses a
> masked
> > version of the original graph, and the mask omits a vertex on which the
> > algorithm attempts the connectivity test, leading to the assertion
> failure.
> > Anyone know the algorithm well enough to submit a fix with confidence?
> >
> > JVS
> >
> >
> >
> > On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>
> > wrote:
> >
> > Hello,
> >
> > sorry this is such a long mail, but I included a test program, and my
> graph
> > is quite large.
> >
> > I am using JGraphT to create graphs of my data with great success so far.
> > However, now I am trying to calculate the shortest paths between two
> nodes
> > using KShortestPaths, and I only receive the following exception:
> >
> > [code]
> > java.lang.IllegalArgumentException: graph must contain the start vertex
> >    at
> >
> org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
> >    at
> >
> org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
> >    at
> >
> org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
> >    at
> >
> org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
> >    at
> >
> org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
> >    at
> >
> org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
> >    at
> >
> org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
> >    at
> >
> org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
> >    at
> >
> org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
> >    at
> >
> org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
> >    at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
> >    at KShortestPathsMain.main(KShortestPathsMain.java:97)
> > [/code]
> >
> > Note that I am only getting this exception with that one, large graph I
> > created from my data. When I create a graph by hand, it does not occur.
> Here
> > is my test program. The graph is attached.
> >
> > [code]
> > import java.io.BufferedReader;
> > import java.io.FileNotFoundException;
> > import java.io.FileReader;
> > import java.io.IOException;
> > import java.util.List;
> >
> > import org.jgrapht.GraphPath;
> > import org.jgrapht.alg.KShortestPaths;
> > import org.jgrapht.graph.DefaultWeightedEdge;
> > import org.jgrapht.graph.SimpleWeightedGraph;
> >
> > public class KShortestPathsMain {
> >
> >    public KShortestPathsMain() {}
> >
> >    public static void main(String[] args) {
> >
> >        SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
> > SimpleWeightedGraph<>(DefaultWeightedEdge.class);
> >
> >            FileReader fstream = null;
> >            try {
> >                fstream = new FileReader("edges.txt");
> >            } catch (FileNotFoundException e1) {
> >                e1.printStackTrace();
> >            }
> >            BufferedReader in = new BufferedReader(fstream);
> >
> >            String[] edgeText;
> >            DefaultWeightedEdge ed;
> >            String line = null;
> >            try {
> >                line = in.readLine();
> >            } catch (IOException e1) {
> >                // TODO Auto-generated catch block
> >                e1.printStackTrace();
> >            }
> >            while(line != null) {
> >                edgeText = line.split("\t");
> >
> >                graph.addVertex(edgeText[0]);
> >                graph.addVertex(edgeText[1]);
> >                ed = graph.addEdge(edgeText[0], edgeText[1]);
> >                graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]));
> >
> >                try {
> >                    line = in.readLine();
> >                } catch (IOException e) {
> >                    e.printStackTrace();
> >                }
> >            }
> >
> >            // Close the input stream
> >            try {
> >                in.close();
> >            } catch (IOException e1) {
> >                e1.printStackTrace();
> >            }
> >
> >        DefaultWeightedEdge src = graph.getEdge("M013", "M014");
> >
> >        KShortestPaths<String, DefaultWeightedEdge> kPaths = new
> > KShortestPaths<String, DefaultWeightedEdge>(
> >                graph, graph.getEdgeSource(src), 5);
> >        List<GraphPath<String,DefaultWeightedEdge>> paths = null;
> >
> >        try {
> >            paths = kPaths.getPaths(graph.getEdgeTarget(src));
> >            for (GraphPath<String, DefaultWeightedEdge> path : paths) {
> >                for (DefaultWeightedEdge edge : path.getEdgeList()) {
> >                    System.out.print("<" + graph.getEdgeSource(edge) +
> "\t"
> >                            + graph.getEdgeTarget(edge) + "\t" + edge +
> > ">\t");
> >                }
> >                System.out.println(": " + path.getWeight());
> >            }
> >        } catch (IllegalArgumentException e) {
> >            e.printStackTrace();
> >        }
> >    }
> > }
> >
> > [/code]
> >
> > I tried different edges, and directed and undirected graphs. Same
> result. If
> > anyone has a clue what might be going on here, I'd very much appreciate
> > help.
> >
> >
> > Sebastian
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> > http://www2.precog.com/precogplatform/slashdotnewsletter
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> > http://www2.precog.com/precogplatform/slashdotnewsletter
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> > http://www2.precog.com/precogplatform/slashdotnewsletter
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> > http://www2.precog.com/precogplatform/slashdotnewsletter
> >
> >
> >
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> > http://www2.precog.com/precogplatform/slashdotnewsletter
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> > http://www2.precog.com/precogplatform/slashdotnewsletter
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
> >
> >
> >
> >
> >
> >
> >
> >
> ------------------------------------------------------------------------------
> > Try New Relic Now & We'll Send You this Cool Shirt
> > New Relic is the only SaaS-based application performance monitoring
> service
> > that delivers powerful full stack analytics. Optimize and monitor your
> > browser, app, & servers with just a few lines of code. Try New Relic
> > and get this awesome Nerd Life shirt!
> http://p.sf.net/sfu/newrelic_d2d_apr
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
>
>
> ------------------------------------------------------------------------------
> Introducing AppDynamics Lite, a free troubleshooting tool for Java/.NET
> Get 100% visibility into your production application - at no cost.
> Code-level diagnostics for performance bottlenecks with <2% overhead
> Download for free and get started troubleshooting in minutes.
> http://p.sf.net/sfu/appdyn_d2d_ap1
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
> ------------------------------------------------------------------------------
> Introducing AppDynamics Lite, a free troubleshooting tool for Java/.NET
> Get 100% visibility into your production application - at no cost.
> Code-level diagnostics for performance bottlenecks with <2% overhead
> Download for free and get started troubleshooting in minutes.
> http://p.sf.net/sfu/appdyn_d2d_ap1
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Visited vertex list

[Davis J. <dav...@gm...>]

Hello all,

I'm working on my bachelor thesis and everything has worked perfectly with
JGraphT for now. Is it possible to get the vertex list which routing
algorithm visited while searching for the route? I can get the vertex list
from shortest path but I'm also interested in visited vertex list. I'm
using Dijkstra, Floyd-Warshall and Bellman-Ford algorithms.

Thanks in advance,
Davis Jaunzems

Re: [jgrapht-users] SimpleDirectGraph generation with a group of known vertex

[Georg H. <geo...@go...>]

yes you can use the complete graph generator for this, just build a vertex
factory how produces the needed coordinate-vertices.
or you just build a simple graph by yourself and use two loops for building
all possible edges.
for getting the linestring between the two vertices, you probably need to
retriev them by yourself for every edge.
Or you set them for every edge when you create them, but then you will have
to use your own loops for building the edges, I think.

Hope I could help



On 3 May 2013 02:05, pmgmendes <p.m...@gm...> wrote:

> Hi list,
> I have a set of Coordinates that I consider Vertex. Is it possible to feed
> them to a graph generator so it can result in a direct graph from which I
> can get all the generate edges (Linestring between the Coordinates )?
>
> Thanks in advance!
>
> Pedro Mendes.
>
>
>
> --
> View this message in context:
> http://jgrapht-users.107614.n3.nabble.com/SimpleDirectGraph-generation-with-a-group-of-known-vertex-tp4024820.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
>
> ------------------------------------------------------------------------------
> Introducing AppDynamics Lite, a free troubleshooting tool for Java/.NET
> Get 100% visibility into your production application - at no cost.
> Code-level diagnostics for performance bottlenecks with <2% overhead
> Download for free and get started troubleshooting in minutes.
> http://p.sf.net/sfu/appdyn_d2d_ap1
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] SimpleDirectGraph generation with a group of known vertex

[pmgmendes <p.m...@gm...>]

Hi list,
I have a set of Coordinates that I consider Vertex. Is it possible to feed
them to a graph generator so it can result in a direct graph from which I
can get all the generate edges (Linestring between the Coordinates )?

Thanks in advance!

Pedro Mendes.



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/SimpleDirectGraph-generation-with-a-group-of-known-vertex-tp4024820.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths

[gu b. <bou...@ya...>]

I really also hope that it is the last ==/equals bug in the KSP algorithm !


Your remark about the String ID's is good and it makes think that the bug raised by Sebastian could only apply to graphs constructed this way. Good point !


Guillaume



________________________________
 De : John Sichi <js...@gm...>
À : gu boulmi <bou...@ya...> 
Cc : "jgr...@li..." <jgr...@li...> 
Envoyé le : Mardi 30 avril 2013 7h12
Objet : Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths
 

Thanks a lot for following up.  I've applied all of the changes for
completeness.

Regarding your PS, I do not believe that any ID's actually "changed"
during the execution.  It's just that when the strings are read in
from the text file, multiple String objects are created with the same
value.  And even though there's only one D007 vertex object added to
the graph, there can be different String objects in the edges which
reference it.

I hope that is the last ==/equals bug (we've had the same problem show
up in other algorithms).  It's hard to write a findbugs rule to catch
it since there are legitimate reasons to use == in some cases.

JVS


On Mon, Apr 29, 2013 at 8:02 AM, gu boulmi <bou...@ya...> wrote:
> I forgot the mailing list...
>
> ----- Mail transféré -----
> De : gu boulmi <bou...@ya...>
> À : John Sichi <js...@gm...>
> Cc : Sebastian Müller <woo...@gm...>
> Envoyé le : Samedi 27 avril 2013 15h32
>
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Hi,
> Actually a lost of JUnit tests on graphs with cycles (e.g. all the tests on
> complete graphs) already exists and it works.
>
> In fact, I think that the initial isSimplePath method would work fine on any
> graph provided that a String vertex does not
> change id during the execution of the KSP algorithm (see my comments in my
> mail 17.04.2013).
>
> The root cause of the problem encountered by Sebastian about the non-simple
> paths result is rather (again) the use of the != instead of !equals  in a
> method, namely in the KShortestPathsIterator#updateOutgoingVertices method :
>     // check if the path does not loop over the start vertex.
>     if (vertexReachedByEdge != this.startVertex)
>
> instead it should be :
>     if (!vertexReachedByEdge.equals(this.startVertex))
>
> The correction from my previous mail 24.04.2013 of the isSimplePath method
> can be preserved however.
> Indeed, accordinf to the name of the method is should return true only for a
> path path with no repeated vertices and the
> former implementation made an exception to that for the start vertex.
>
> To sum up, the correction attached to the KShortestPathsIterator class would
> be enough. Nevertheless the correction from my mail 24.04.2013 can be
> preserved anyway for the sake of clarity of the isSimplePath method.
>
> Best regards,
> Guillaume
>
> P.S. : I do not know yet why a String vertex like D007 would change id
> during the execution of the algorithm. I guess it is specific to String
> vertices...
>
>
> De : John Sichi <js...@gm...>
> À : gu boulmi <bou...@ya...>
> Cc : Sebastian Müller <woo...@gm...>;
> "jgr...@li..." <jgr...@li...>
> Envoyé le : Jeudi 25 avril 2013 9h08
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Thanks!  I will update github.  Probably the reason the existing tests
> didn't catch the problem is that they use a graph without cycles?
>
> Looks like in the past it has already been spotted out there in the wild, so
> I am glad it is getting fixed!
>
> http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-td4024711.html
>
> JVS
>
> On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <bou...@ya...> wrote:
>
> Hi,
> You're so right with the do/while.
> Please find attached a new correction to the RankingPathElementList class
> along with a JUnit test (reproducing the test program of Sebastian that led
> to the IllegalArgumentException with text "graph must contain the start
> vertex").
> I just wonder why this error did not pop up earlier with the existing JUnit
> tests about the number of paths returned by the KSP algorithm.
>
> I think that there is no problem with the PathMask constructor. No change
> needed.
>
> Best regards,
> Guillaume
>
> De : John Sichi <js...@gm...>
> À : Sebastian Müller <woo...@gm...>
> Cc : "jgr...@li..."
> <jgr...@li...>
> Envoyé le : Jeudi 18 avril 2013 0h18
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Guillaume:  thanks for looking into this!
>
> Sebastian:  you're right about the non-simple paths.  Looking at the same
> isSimplePath method, it looks like it should be using a do/while construct
> instead of a while/do construct.  If I make that change, then with your test
> case, I get back only simple paths (which are longer than the "cheating by
> running around in circles" non-simple paths).  Guillaume, do you think I
> should make this change?  If so do I need to make a corresponding change in
> the PathMask constructor?
>
>
> On Wed, Apr 17, 2013 at 3:49 AM, Sebastian Müller <woo...@gm...>
> wrote:
>
> Hi all,
>
> I can confirm that the exception is now gone. Thanks for the quick fix!
> Just one more thing. The javadoc for KShortestPaths states 'The algorithm
> determines the k shortest simple paths [...]'. According to my understanding
> the paths calculated by KShortestPaths are not simple. See my example below.
>
> [code]
> <M042    M013    0.90>    : 0.90
> <M042    M043    0.76>    <M043    M042    0.76>    <M042    M013
> 0.909439166411278>    : 2.43
> <M042    M029    0.87>    <M029    M042    0.96>    <M042    M013    0.90>
> : 2.74
> <M042    M044    0.92>    <M044    M043    0.76>    <M043    M042    0.76>
> <M042    M013    0.90>    : 3.36
> <M042    M028    0.91>    <M028    M043    0.81>    <M043    M042    0.76>
> <M042    M013    0.90>    : 3.39
> [/code]
>
>
> Thanks for the great work with JGraphT, all!
>
> Sebastian
>
>
> Am 17.04.2013 11:52, schrieb gu boulmi:
>
> Hi all,
> I just made a debug thanks to the test provided by Sebastian.
> See attached the correction.
>
> I came to the conclusion that was a mistake in the way to test whether there
> is a loop in a path (i.e. two of the same vertex in the path) in the method
> org.jgrapht.alg.RankingPathElementList#isSimplePath
>
> Actually, the test failed when testing the simple path property of a path
> resulting from adding the edge M004-D007 at the end of path
> M014-D010-D007-M004. Of course the resulting path is not simple (twice
> D007), however it returned true.
> When debugging, it appears that the id of the D007 vertex of the edge
> M004-D007 and the id of the D007 vertex of the path M014-D010-D007-M004 were
> not the same, although they represent the same vertex (namely D007). The
> existing implementation wrongly returned true because the ids of D007 were
> not the same while it tested the equality with the == method.
>
> I changed it by replacing the == by the equals method and it just works.
> New implementation is now :
> private boolean isSimplePath(
>         RankingPathElement<V, E> prevPathElement,
>         E edge)
>     {
>         RankingPathElement<V, E> pathElementToTest = prevPathElement;
>         while (pathElementToTest.getPrevEdge() != null) {
>             if (pathElementToTest.getVertex().equals(this.vertex)) {
>                 return false;
>             } else {
>                 pathElementToTest = pathElementToTest.getPrevPathElement();
>             }
>         }
>
>         return true;
>     }
>
> Strange anyway : no guess why a String vertex like D007 would change id
> during the execution of the algorithm.
>
> Best regards,
> Guillaume
>
> De : John Sichi <js...@gm...>
> À : Osama Elswah <osa...@gm...>
> Cc : "jgr...@li..."
> <jgr...@li...>
> Envoyé le : Mardi 16 avril 2013 23h04
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Before my previous reply, I reproduced Sebastian's problem by running his
> code, which is why I say it's a bug.  His input graph is correctly
> constructed, so there's no reason that assertion should be hit.
>
>
> On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah <osa...@gm...>
> wrote:
>
> I have been using KShortestPath for some time now, and it has been doing its
> purpose. I am not sure it has a bug.
> This is how I use it
>
> for(V n : network.vertexSet())
>         {
>             KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n,
> k);
>             for(Demand<V> d : demands.getAllDemands())
>             {
>                 if((d.getSourceNode().equals(n)))
>                 {
>                     demand_paths = k.getPaths(d.getTargetNode());
>                     pathsMap.put(d.getSourceNode(), d.getTargetNode(),
> demand_paths);
>                 }
>             }
>         }
>     }
>
> What is the output of this line ?
>
> DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
> I believe if you debug more there you will find the problem
>
> good luck
>
>
> On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote:
>
> Looks like a bug in KShortestPaths.  Internally, the algorithm uses a masked
> version of the original graph, and the mask omits a vertex on which the
> algorithm attempts the connectivity test, leading to the assertion failure.
> Anyone know the algorithm well enough to submit a fix with confidence?
>
> JVS
>
>
>
> On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>
> wrote:
>
> Hello,
>
> sorry this is such a long mail, but I included a test program, and my graph
> is quite large.
>
> I am using JGraphT to create graphs of my data with great success so far.
> However, now I am trying to calculate the shortest paths between two nodes
> using KShortestPaths, and I only receive the following exception:
>
> [code]
> java.lang.IllegalArgumentException: graph must contain the start vertex
>     at
> org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
>     at
> org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
>     at
> org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
>     at
> org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
>     at
> org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
>     at
> org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
>     at
> org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
>     at
> org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
>     at
> org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
>     at
> org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
>     at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
>     at KShortestPathsMain.main(KShortestPathsMain.java:97)
> [/code]
>
> Note that I am only getting this exception with that one, large graph I
> created from my data. When I create a graph by hand, it does not occur. Here
> is my test program. The graph is attached.
>
> [code]
> import java.io.BufferedReader;
> import java.io.FileNotFoundException;
> import java.io.FileReader;
> import java.io.IOException;
> import java.util.List;
>
> import org.jgrapht.GraphPath;
> import org.jgrapht.alg.KShortestPaths;
> import org.jgrapht.graph.DefaultWeightedEdge;
> import org.jgrapht.graph.SimpleWeightedGraph;
>
> public class KShortestPathsMain {
>
>     public KShortestPathsMain() {}
>
>     public static void main(String[] args) {
>
>         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>
>             FileReader fstream = null;
>             try {
>                 fstream = new FileReader("edges.txt");
>             } catch (FileNotFoundException e1) {
>                 e1.printStackTrace();
>             }
>             BufferedReader in = new BufferedReader(fstream);
>
>             String[] edgeText;
>             DefaultWeightedEdge ed;
>             String line = null;
>             try {
>                 line = in.readLine();
>             } catch (IOException e1) {
>                 // TODO Auto-generated catch block
>                 e1.printStackTrace();
>             }
>             while(line != null) {
>                 edgeText = line.split("\t");
>
>                 graph.addVertex(edgeText[0]);
>                 graph.addVertex(edgeText[1]);
>                 ed = graph.addEdge(edgeText[0], edgeText[1]);
>                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]));
>
>                 try {
>                     line = in.readLine();
>                 } catch (IOException e) {
>                     e.printStackTrace();
>                 }
>             }
>
>             // Close the input stream
>             try {
>                 in.close();
>             } catch (IOException e1) {
>                 e1.printStackTrace();
>             }
>
>         DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>         KShortestPaths<String, DefaultWeightedEdge> kPaths = new
> KShortestPaths<String, DefaultWeightedEdge>(
>                 graph, graph.getEdgeSource(src), 5);
>         List<GraphPath<String,DefaultWeightedEdge>> paths = null;
>
>         try {
>             paths = kPaths.getPaths(graph.getEdgeTarget(src));
>             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
>                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
>                     System.out.print("<" + graph.getEdgeSource(edge) + "\t"
>                             + graph.getEdgeTarget(edge) + "\t" + edge +
> ">\t");
>                 }
>                 System.out.println(": " + path.getWeight());
>             }
>         } catch (IllegalArgumentException e) {
>             e.printStackTrace();
>         }
>     }
> }
>
> [/code]
>
> I tried different edges, and directed and undirected graphs. Same result. If
> anyone has a clue what might be going on here, I'd very much appreciate
> help.
>
>
> Sebastian
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
>
>
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
>
>
>
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

------------------------------------------------------------------------------
Introducing AppDynamics Lite, a free troubleshooting tool for Java/.NET
Get 100% visibility into your production application - at no cost.
Code-level diagnostics for performance bottlenecks with <2% overhead
Download for free and get started troubleshooting in minutes.
http://p.sf.net/sfu/appdyn_d2d_ap1
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Tr : "graph must contain the start vertex" when running KShortestPaths

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

Thanks a lot for following up.  I've applied all of the changes for
completeness.

Regarding your PS, I do not believe that any ID's actually "changed"
during the execution.  It's just that when the strings are read in
from the text file, multiple String objects are created with the same
value.  And even though there's only one D007 vertex object added to
the graph, there can be different String objects in the edges which
reference it.

I hope that is the last ==/equals bug (we've had the same problem show
up in other algorithms).  It's hard to write a findbugs rule to catch
it since there are legitimate reasons to use == in some cases.

JVS


On Mon, Apr 29, 2013 at 8:02 AM, gu boulmi <bou...@ya...> wrote:
> I forgot the mailing list...
>
> ----- Mail transféré -----
> De : gu boulmi <bou...@ya...>
> À : John Sichi <js...@gm...>
> Cc : Sebastian Müller <woo...@gm...>
> Envoyé le : Samedi 27 avril 2013 15h32
>
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Hi,
> Actually a lost of JUnit tests on graphs with cycles (e.g. all the tests on
> complete graphs) already exists and it works.
>
> In fact, I think that the initial isSimplePath method would work fine on any
> graph provided that a String vertex does not
> change id during the execution of the KSP algorithm (see my comments in my
> mail 17.04.2013).
>
> The root cause of the problem encountered by Sebastian about the non-simple
> paths result is rather (again) the use of the != instead of !equals  in a
> method, namely in the KShortestPathsIterator#updateOutgoingVertices method :
>     // check if the path does not loop over the start vertex.
>     if (vertexReachedByEdge != this.startVertex)
>
> instead it should be :
>     if (!vertexReachedByEdge.equals(this.startVertex))
>
> The correction from my previous mail 24.04.2013 of the isSimplePath method
> can be preserved however.
> Indeed, accordinf to the name of the method is should return true only for a
> path path with no repeated vertices and the
> former implementation made an exception to that for the start vertex.
>
> To sum up, the correction attached to the KShortestPathsIterator class would
> be enough. Nevertheless the correction from my mail 24.04.2013 can be
> preserved anyway for the sake of clarity of the isSimplePath method.
>
> Best regards,
> Guillaume
>
> P.S. : I do not know yet why a String vertex like D007 would change id
> during the execution of the algorithm. I guess it is specific to String
> vertices...
>
>
> De : John Sichi <js...@gm...>
> À : gu boulmi <bou...@ya...>
> Cc : Sebastian Müller <woo...@gm...>;
> "jgr...@li..." <jgr...@li...>
> Envoyé le : Jeudi 25 avril 2013 9h08
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Thanks!  I will update github.  Probably the reason the existing tests
> didn't catch the problem is that they use a graph without cycles?
>
> Looks like in the past it has already been spotted out there in the wild, so
> I am glad it is getting fixed!
>
> http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-td4024711.html
>
> JVS
>
> On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <bou...@ya...> wrote:
>
> Hi,
> You're so right with the do/while.
> Please find attached a new correction to the RankingPathElementList class
> along with a JUnit test (reproducing the test program of Sebastian that led
> to the IllegalArgumentException with text "graph must contain the start
> vertex").
> I just wonder why this error did not pop up earlier with the existing JUnit
> tests about the number of paths returned by the KSP algorithm.
>
> I think that there is no problem with the PathMask constructor. No change
> needed.
>
> Best regards,
> Guillaume
>
> De : John Sichi <js...@gm...>
> À : Sebastian Müller <woo...@gm...>
> Cc : "jgr...@li..."
> <jgr...@li...>
> Envoyé le : Jeudi 18 avril 2013 0h18
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Guillaume:  thanks for looking into this!
>
> Sebastian:  you're right about the non-simple paths.  Looking at the same
> isSimplePath method, it looks like it should be using a do/while construct
> instead of a while/do construct.  If I make that change, then with your test
> case, I get back only simple paths (which are longer than the "cheating by
> running around in circles" non-simple paths).  Guillaume, do you think I
> should make this change?  If so do I need to make a corresponding change in
> the PathMask constructor?
>
>
> On Wed, Apr 17, 2013 at 3:49 AM, Sebastian Müller <woo...@gm...>
> wrote:
>
> Hi all,
>
> I can confirm that the exception is now gone. Thanks for the quick fix!
> Just one more thing. The javadoc for KShortestPaths states 'The algorithm
> determines the k shortest simple paths [...]'. According to my understanding
> the paths calculated by KShortestPaths are not simple. See my example below.
>
> [code]
> <M042    M013    0.90>    : 0.90
> <M042    M043    0.76>    <M043    M042    0.76>    <M042    M013
> 0.909439166411278>    : 2.43
> <M042    M029    0.87>    <M029    M042    0.96>    <M042    M013    0.90>
> : 2.74
> <M042    M044    0.92>    <M044    M043    0.76>    <M043    M042    0.76>
> <M042    M013    0.90>    : 3.36
> <M042    M028    0.91>    <M028    M043    0.81>    <M043    M042    0.76>
> <M042    M013    0.90>    : 3.39
> [/code]
>
>
> Thanks for the great work with JGraphT, all!
>
> Sebastian
>
>
> Am 17.04.2013 11:52, schrieb gu boulmi:
>
> Hi all,
> I just made a debug thanks to the test provided by Sebastian.
> See attached the correction.
>
> I came to the conclusion that was a mistake in the way to test whether there
> is a loop in a path (i.e. two of the same vertex in the path) in the method
> org.jgrapht.alg.RankingPathElementList#isSimplePath
>
> Actually, the test failed when testing the simple path property of a path
> resulting from adding the edge M004-D007 at the end of path
> M014-D010-D007-M004. Of course the resulting path is not simple (twice
> D007), however it returned true.
> When debugging, it appears that the id of the D007 vertex of the edge
> M004-D007 and the id of the D007 vertex of the path M014-D010-D007-M004 were
> not the same, although they represent the same vertex (namely D007). The
> existing implementation wrongly returned true because the ids of D007 were
> not the same while it tested the equality with the == method.
>
> I changed it by replacing the == by the equals method and it just works.
> New implementation is now :
> private boolean isSimplePath(
>         RankingPathElement<V, E> prevPathElement,
>         E edge)
>     {
>         RankingPathElement<V, E> pathElementToTest = prevPathElement;
>         while (pathElementToTest.getPrevEdge() != null) {
>             if (pathElementToTest.getVertex().equals(this.vertex)) {
>                 return false;
>             } else {
>                 pathElementToTest = pathElementToTest.getPrevPathElement();
>             }
>         }
>
>         return true;
>     }
>
> Strange anyway : no guess why a String vertex like D007 would change id
> during the execution of the algorithm.
>
> Best regards,
> Guillaume
>
> De : John Sichi <js...@gm...>
> À : Osama Elswah <osa...@gm...>
> Cc : "jgr...@li..."
> <jgr...@li...>
> Envoyé le : Mardi 16 avril 2013 23h04
> Objet : Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Before my previous reply, I reproduced Sebastian's problem by running his
> code, which is why I say it's a bug.  His input graph is correctly
> constructed, so there's no reason that assertion should be hit.
>
>
> On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah <osa...@gm...>
> wrote:
>
> I have been using KShortestPath for some time now, and it has been doing its
> purpose. I am not sure it has a bug.
> This is how I use it
>
> for(V n : network.vertexSet())
>         {
>             KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n,
> k);
>             for(Demand<V> d : demands.getAllDemands())
>             {
>                 if((d.getSourceNode().equals(n)))
>                 {
>                     demand_paths = k.getPaths(d.getTargetNode());
>                     pathsMap.put(d.getSourceNode(), d.getTargetNode(),
> demand_paths);
>                 }
>             }
>         }
>     }
>
> What is the output of this line ?
>
> DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
> I believe if you debug more there you will find the problem
>
> good luck
>
>
> On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote:
>
> Looks like a bug in KShortestPaths.  Internally, the algorithm uses a masked
> version of the original graph, and the mask omits a vertex on which the
> algorithm attempts the connectivity test, leading to the assertion failure.
> Anyone know the algorithm well enough to submit a fix with confidence?
>
> JVS
>
>
>
> On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>
> wrote:
>
> Hello,
>
> sorry this is such a long mail, but I included a test program, and my graph
> is quite large.
>
> I am using JGraphT to create graphs of my data with great success so far.
> However, now I am trying to calculate the shortest paths between two nodes
> using KShortestPaths, and I only receive the following exception:
>
> [code]
> java.lang.IllegalArgumentException: graph must contain the start vertex
>     at
> org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
>     at
> org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
>     at
> org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
>     at
> org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
>     at
> org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
>     at
> org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
>     at
> org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
>     at
> org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
>     at
> org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
>     at
> org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
>     at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
>     at KShortestPathsMain.main(KShortestPathsMain.java:97)
> [/code]
>
> Note that I am only getting this exception with that one, large graph I
> created from my data. When I create a graph by hand, it does not occur. Here
> is my test program. The graph is attached.
>
> [code]
> import java.io.BufferedReader;
> import java.io.FileNotFoundException;
> import java.io.FileReader;
> import java.io.IOException;
> import java.util.List;
>
> import org.jgrapht.GraphPath;
> import org.jgrapht.alg.KShortestPaths;
> import org.jgrapht.graph.DefaultWeightedEdge;
> import org.jgrapht.graph.SimpleWeightedGraph;
>
> public class KShortestPathsMain {
>
>     public KShortestPathsMain() {}
>
>     public static void main(String[] args) {
>
>         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>
>             FileReader fstream = null;
>             try {
>                 fstream = new FileReader("edges.txt");
>             } catch (FileNotFoundException e1) {
>                 e1.printStackTrace();
>             }
>             BufferedReader in = new BufferedReader(fstream);
>
>             String[] edgeText;
>             DefaultWeightedEdge ed;
>             String line = null;
>             try {
>                 line = in.readLine();
>             } catch (IOException e1) {
>                 // TODO Auto-generated catch block
>                 e1.printStackTrace();
>             }
>             while(line != null) {
>                 edgeText = line.split("\t");
>
>                 graph.addVertex(edgeText[0]);
>                 graph.addVertex(edgeText[1]);
>                 ed = graph.addEdge(edgeText[0], edgeText[1]);
>                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]));
>
>                 try {
>                     line = in.readLine();
>                 } catch (IOException e) {
>                     e.printStackTrace();
>                 }
>             }
>
>             // Close the input stream
>             try {
>                 in.close();
>             } catch (IOException e1) {
>                 e1.printStackTrace();
>             }
>
>         DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>         KShortestPaths<String, DefaultWeightedEdge> kPaths = new
> KShortestPaths<String, DefaultWeightedEdge>(
>                 graph, graph.getEdgeSource(src), 5);
>         List<GraphPath<String,DefaultWeightedEdge>> paths = null;
>
>         try {
>             paths = kPaths.getPaths(graph.getEdgeTarget(src));
>             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
>                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
>                     System.out.print("<" + graph.getEdgeSource(edge) + "\t"
>                             + graph.getEdgeTarget(edge) + "\t" + edge +
> ">\t");
>                 }
>                 System.out.println(": " + path.getWeight());
>             }
>         } catch (IllegalArgumentException e) {
>             e.printStackTrace();
>         }
>     }
> }
>
> [/code]
>
> I tried different edges, and directed and undirected graphs. Same result. If
> anyone has a clue what might be going on here, I'd very much appreciate
> help.
>
>
> Sebastian
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
>
>
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
>
>
>
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Help about custom vertex

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

>From the looks of it, your error is probably in the equals() method. In
your initial post, you wrote that the data type of your variable data is of
the type String.
In your code, you write:

Node temp = (Node) obj;
return data == temp.data;

This obviously only works if your nodes have the same data object. For
example:

public class Node{
  String data;
  public Node(String data){
     this.data=data;
  }
}

String s1="a";
String s2="a";

Node n1=new Node(s1);
Node n2=new Node(s2);
Node n3=new Node(s1);

n1.equals(n2); //This wil return false using your equals implementation.
n1.equals(n3); //This will return true.

You probably want this instead in your equals method:
 Node temp = (Node) obj;
  return data.equals(temp.data);


This issues however is a basic java implementation issues and doesn't
really have anything to do with jgraph. Perhaps it would be better to
restrict the conversation to jgraph related issues.


On Fri, Apr 26, 2013 at 3:17 PM, arastoo bozorgi <ara...@ya...> wrote:

> Hello
> I have overwriten the equal and hashCode as below:
>
>  @Override
>     public boolean equals(Object obj) {
>         if (obj == this) {
>             return true;
>         }
>         if (obj == null || obj.getClass() != this.getClass()) {
>             return false;
>         }
>
>         Node temp = (Node) obj;
>         return data == temp.data;
>
>     }
>
>     @Override
>     public int hashCode() {
>         final int prime = 31;
>         int result = 1;
>         result = prime * result
>                 + ((data == null) ? 0 : data.hashCode());
>         return result;
>
>
>     }
>
> its equal method works correct. alse i test the hashCode method. i make to
> nodes by my own Node Class and return their hash code, both of them are the
> same, but when i call the containsVertex(V v), it does not work
> correctlly.
> i dont know where is my fault.
>
>   ------------------------------
>  *From:* Joris Kinable <de...@gm...>
> *To:* arastoo bozorgi <ara...@ya...>; "
> jgr...@li..." <jgr...@li...>
>
> *Sent:* Friday, April 26, 2013 3:31 PM
>
> *Subject:* Re: [jgrapht-users] Help about custom vertex
>
> The answer to your question is in the jgrapht javadoc:
>
> boolean *addVertex*(V <http://jgrapht.org/javadoc/org/jgrapht/Graph.html> v)
>
> Adds the specified vertex to this graph if not already present. More
> formally, adds the specified vertex, v, to this graph if this graph
> contains no vertex u such that u.equals(v). If this graph already
> contains such vertex, the call leaves this graph unchanged and returns
> false. In combination with the restriction on constructors, this ensures
> that graphs never contain duplicate vertices.
>
>
> So your own Vertex class needs to override the equals (and also the
> hashcode) methods. See for example this tutorial on how to do that:
> http://javarevisited.blogspot.be/2011/02/how-to-write-equals-method-in-java.html
>
> Note that it is very important that your own Vertex class overrides both
> equals and hashcode, otherwise, the addVertex(V v) won't work as expected
> (as you noticed), but also methods like containsVertex(V v) will fail.
>
> br,
>
> Joris
>
>
> On Fri, Apr 26, 2013 at 12:45 PM, arastoo bozorgi <ara...@ya...>wrote:
>
> hello Joris
> thank you for your answer
> But i have another problem. when i use the class as:
> SimpleWeightedGraph<String, DefaultWeightedEdge>
> myGraph=new SimpleWeightedGraph<String,
> DefaultWeightedEdge>(DefaultWeightedEdge.class)
> and when i add a new vertex, it will check if there is a same node before,
> if a same node with this new one has inserted to the graph, the addVertex
> method does not insert the new node again.
> but when i use a class as you said for my nodes:
> SimpleWeightedGraph<Vertex,DefaultWeightedEdge>
> myGraph=new SimpleWeightedGraph<Vertex
> ,DefaultWeightedEdge>(DefaultWeightedEdge.class)
> when i insert a node that has been inserted before, it does not prevent
> inserting the node, because the new node is a new instance of the Vertex
> class, just thier data are the same, and by this, my graph become useless.
> how can i chech that a new node is inserted to the graph or not
>
> best wishes
>
>
>    ------------------------------
>  *From:* Joris Kinable <de...@gm...>
> *To:* arastoo bozorgi <ara...@ya...>
> *Cc:* "jgr...@li..." <
> jgr...@li...>
> *Sent:* Thursday, April 25, 2013 8:10 PM
> *Subject:* Re: [jgrapht-users] Help about custom vertex
>
> Dear,
>
> Have a look at the hello world example:
> https://github.com/jgrapht/jgrapht/wiki/HelloWorld
> There, an undirected graph is created where the vertices are of the type
> String.
>
> Basically what you need to do is the following:
> 1. Create a new class that models your vertex, e.g.:
> public class Vertex{
>  String data;
>  double teta;
>  String status;
>   public Vertex(){
>      ...Constructor implementation here....
>    }
> }
>
> Next you create a new undirected weighted graph using your newly created
> Vertex class as follows:
> SimpleWeightedGraph<Vertex,DefaultWeightedEdge>
> myGraph=new SimpleWeightedGraph<Vertex,DefaultWeightedEdge>(DefaultWeightedEdge.class);
>
> And then you can start adding vertices/edges, e.g.:
> myGraph.addVertex(new Vertex());
>
> br,
>
> Joris
>
>
>
> On Wed, Apr 24, 2013 at 7:22 PM, arastoo bozorgi <ara...@ya...>wrote:
>
> Hello
> i am new in jgrapht and i have download it 2 days ago.
> i want to make an undirect weighted graph with custom vertex structure.
> the vertex should have these properties:
> 1-string data
> 2-double teta
> 3-string status
>
> i dont know how to define these vertex structure in JGrapht and make my
> graph with this vertex structure, also i dont know which type of graph
> should i use
>
> please help me
>
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
>
>
>
>

Re: [jgrapht-users] Help about custom vertex

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

The answer to your question is in the jgrapht javadoc:

boolean *addVertex*(V <http://jgrapht.org/javadoc/org/jgrapht/Graph.html> v)

Adds the specified vertex to this graph if not already present. More
formally, adds the specified vertex, v, to this graph if this graph
contains no vertex u such that u.equals(v). If this graph already contains
such vertex, the call leaves this graph unchanged and returns false. In
combination with the restriction on constructors, this ensures that graphs
never contain duplicate vertices.


So your own Vertex class needs to override the equals (and also the
hashcode) methods. See for example this tutorial on how to do that:
http://javarevisited.blogspot.be/2011/02/how-to-write-equals-method-in-java.html

Note that it is very important that your own Vertex class overrides both
equals and hashcode, otherwise, the addVertex(V v) won't work as expected
(as you noticed), but also methods like containsVertex(V v) will fail.

br,

Joris


On Fri, Apr 26, 2013 at 12:45 PM, arastoo bozorgi <ara...@ya...>wrote:

> hello Joris
> thank you for your answer
> But i have another problem. when i use the class as:
> SimpleWeightedGraph<String, DefaultWeightedEdge>
> myGraph=new SimpleWeightedGraph<String,
> DefaultWeightedEdge>(DefaultWeightedEdge.class)
> and when i add a new vertex, it will check if there is a same node before,
> if a same node with this new one has inserted to the graph, the addVertex
> method does not insert the new node again.
> but when i use a class as you said for my nodes:
> SimpleWeightedGraph<Vertex,DefaultWeightedEdge>
> myGraph=new SimpleWeightedGraph<Vertex
> ,DefaultWeightedEdge>(DefaultWeightedEdge.class)
> when i insert a node that has been inserted before, it does not prevent
> inserting the node, because the new node is a new instance of the Vertex
> class, just thier data are the same, and by this, my graph become useless.
> how can i chech that a new node is inserted to the graph or not
>
> best wishes
>
>
>   ------------------------------
>  *From:* Joris Kinable <de...@gm...>
> *To:* arastoo bozorgi <ara...@ya...>
> *Cc:* "jgr...@li..." <
> jgr...@li...>
> *Sent:* Thursday, April 25, 2013 8:10 PM
> *Subject:* Re: [jgrapht-users] Help about custom vertex
>
> Dear,
>
> Have a look at the hello world example:
> https://github.com/jgrapht/jgrapht/wiki/HelloWorld
> There, an undirected graph is created where the vertices are of the type
> String.
>
> Basically what you need to do is the following:
> 1. Create a new class that models your vertex, e.g.:
> public class Vertex{
>  String data;
>  double teta;
>  String status;
>   public Vertex(){
>      ...Constructor implementation here....
>    }
> }
>
> Next you create a new undirected weighted graph using your newly created
> Vertex class as follows:
> SimpleWeightedGraph<Vertex,DefaultWeightedEdge>
> myGraph=new SimpleWeightedGraph<Vertex,DefaultWeightedEdge>(DefaultWeightedEdge.class);
>
> And then you can start adding vertices/edges, e.g.:
> myGraph.addVertex(new Vertex());
>
> br,
>
> Joris
>
>
>
> On Wed, Apr 24, 2013 at 7:22 PM, arastoo bozorgi <ara...@ya...>wrote:
>
> Hello
> i am new in jgrapht and i have download it 2 days ago.
> i want to make an undirect weighted graph with custom vertex structure.
> the vertex should have these properties:
> 1-string data
> 2-double teta
> 3-string status
>
> i dont know how to define these vertex structure in JGrapht and make my
> graph with this vertex structure, also i dont know which type of graph
> should i use
>
> please help me
>
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
>

Re: [jgrapht-users] Help about custom vertex

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

Dear,

Have a look at the hello world example:
https://github.com/jgrapht/jgrapht/wiki/HelloWorld
There, an undirected graph is created where the vertices are of the type
String.

Basically what you need to do is the following:
1. Create a new class that models your vertex, e.g.:
public class Vertex{
 String data;
 double teta;
 String status;
  public Vertex(){
     ...Constructor implementation here....
   }
}

Next you create a new undirected weighted graph using your newly created
Vertex class as follows:
SimpleWeightedGraph<Vertex,DefaultWeightedEdge>
myGraph=new SimpleWeightedGraph<Vertex,DefaultWeightedEdge>(DefaultWeightedEdge.class);

And then you can start adding vertices/edges, e.g.:
myGraph.addVertex(new Vertex());

br,

Joris



On Wed, Apr 24, 2013 at 7:22 PM, arastoo bozorgi <ara...@ya...> wrote:

> Hello
> i am new in jgrapht and i have download it 2 days ago.
> i want to make an undirect weighted graph with custom vertex structure.
> the vertex should have these properties:
> 1-string data
> 2-double teta
> 3-string status
>
> i dont know how to define these vertex structure in JGrapht and make my
> graph with this vertex structure, also i dont know which type of graph
> should i use
>
> please help me
>
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] "graph must contain the start vertex" when running KShortestPaths

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

Thanks!  I will update github.  Probably the reason the existing tests
didn't catch the problem is that they use a graph without cycles?

Looks like in the past it has already been spotted out there in the wild,
so I am glad it is getting fixed!

http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-td4024711.html

JVS

On Wed, Apr 24, 2013 at 4:50 AM, gu boulmi <bou...@ya...> wrote:

> Hi,
> You're so right with the do/while.
> Please find attached a new correction to the RankingPathElementList class along
> with a JUnit test (reproducing the test program of Sebastian that led to
> the IllegalArgumentException with text "graph must contain the start
> vertex").
> I just wonder why this error did not pop up earlier with the existing
> JUnit tests about the number of paths returned by the KSP algorithm.
>
> I think that there is no problem with the PathMask constructor. No change
> needed.
>
> Best regards,
> Guillaume
>
>   ------------------------------
>  *De :* John Sichi <js...@gm...>
> *À :* Sebastian Müller <woo...@gm...>
> *Cc :* "jgr...@li..." <
> jgr...@li...>
> *Envoyé le :* Jeudi 18 avril 2013 0h18
> *Objet :* Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
> Guillaume:  thanks for looking into this!
>
> Sebastian:  you're right about the non-simple paths.  Looking at the same
> isSimplePath method, it looks like it should be using a do/while construct
> instead of a while/do construct.  If I make that change, then with your
> test case, I get back only simple paths (which are longer than the
> "cheating by running around in circles" non-simple paths).  Guillaume, do
> you think I should make this change?  If so do I need to make a
> corresponding change in the PathMask constructor?
>
>
> On Wed, Apr 17, 2013 at 3:49 AM, Sebastian Müller <woo...@gm...>wrote:
>
>  Hi all,
>
> I can confirm that the exception is now gone. Thanks for the quick fix!
> Just one more thing. The javadoc for KShortestPaths states 'The algorithm
> determines the k shortest simple paths [...]'. According to my
> understanding the paths calculated by KShortestPaths are not simple. See my
> example below.
>
> [code]
> <M042    M013    0.90>    : 0.90
> <M042    M043    0.76>    <M043    M042    0.76>    <M042    M013
> 0.909439166411278>    : 2.43
> <M042    M029    0.87>    <M029    M042    0.96>    <M042    M013
> 0.90>    : 2.74
> <M042    M044    0.92>    <M044    M043    0.76>    <M043    M042
> 0.76>    <M042    M013    0.90>    : 3.36
> <M042    M028    0.91>    <M028    M043    0.81>    <M043    M042
> 0.76>    <M042    M013    0.90>    : 3.39
> [/code]
>
>
> Thanks for the great work with JGraphT, all!
>
> Sebastian
>
>
> Am 17.04.2013 11:52, schrieb gu boulmi:
>
> Hi all,
> I just made a debug thanks to the test provided by Sebastian.
> See attached the correction.
>
> I came to the conclusion that was a mistake in the way to test whether
> there is a loop in a path (i.e. two of the same vertex in the path) in the
> method org.jgrapht.alg.RankingPathElementList#isSimplePath
>
> Actually, the test failed when testing the simple path property of a path
> resulting from adding the edge M004-D007 at the end of path
> M014-D010-D007-M004. Of course the resulting path is not simple (twice
> D007), however it returned true.
> When debugging, it appears that the id of the D007 vertex of the edge
> M004-D007 and the id of the D007 vertex of the path M014-D010-D007-M004
> were not the same, although they represent the same vertex (namely D007).
> The existing implementation wrongly returned true because the ids of D007
> were not the same while it tested the equality with the == method.
>
> I changed it by replacing the == by the equals method and it just works.
> New implementation is now :
>  private boolean isSimplePath(
>         RankingPathElement<V, E> prevPathElement,
>         E edge)
>     {
>         RankingPathElement<V, E> pathElementToTest = prevPathElement;
>         while (pathElementToTest.getPrevEdge() != null) {
>             if (pathElementToTest.getVertex().equals(this.vertex)) {
>                 return false;
>             } else {
>                 pathElementToTest = pathElementToTest.getPrevPathElement();
>             }
>         }
>
>         return true;
>     }
>
> Strange anyway : no guess why a String vertex like D007 would change id
> during the execution of the algorithm.
>
> Best regards,
> Guillaume
>
>   ------------------------------
>  *De :* John Sichi <js...@gm...> <js...@gm...>
> *À :* Osama Elswah <osa...@gm...><osa...@gm...>
> *Cc :* "jgr...@li..."<jgr...@li...>
> <jgr...@li...><jgr...@li...>
> *Envoyé le :* Mardi 16 avril 2013 23h04
> *Objet :* Re: [jgrapht-users] "graph must contain the start vertex" when
> running KShortestPaths
>
>  Before my previous reply, I reproduced Sebastian's problem by running
> his code, which is why I say it's a bug.  His input graph is correctly
> constructed, so there's no reason that assertion should be hit.
>
>
> On Tue, Apr 16, 2013 at 7:48 AM, Osama Elswah <osa...@gm...>wrote:
>
>   I have been using KShortestPath for some time now, and it has been
> doing its purpose. I am not sure it has a bug.
>  This is how I use it
>
> for(V n : network.vertexSet())
>         {
>             KShortestPaths<V, E> k = new KShortestPaths<V, E>(network, n,
> k);
>             for(Demand<V> d : demands.getAllDemands())
>             {
>                 if((d.getSourceNode().equals(n)))
>                 {
>                     demand_paths = k.getPaths(d.getTargetNode());
>                     pathsMap.put(d.getSourceNode(), d.getTargetNode(),
> demand_paths);
>                 }
>             }
>         }
>     }
>
>  What is the output of this line ?
>
> DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>  I believe if you debug more there you will find the problem
>
>  good luck
>
>
> On Tue, Apr 16, 2013 at 10:03 AM, John Sichi <js...@gm...> wrote:
>
> Looks like a bug in KShortestPaths.  Internally, the algorithm uses a
> masked version of the original graph, and the mask omits a vertex on which
> the algorithm attempts the connectivity test, leading to the assertion
> failure.  Anyone know the algorithm well enough to submit a fix with
> confidence?
>
>  JVS
>
>
>
> On Mon, Apr 15, 2013 at 1:29 PM, Sebastian Müller <woo...@gm...>wrote:
>
> Hello,
>
> sorry this is such a long mail, but I included a test program, and my
> graph is quite large.
>
> I am using JGraphT to create graphs of my data with great success so far.
> However, now I am trying to calculate the shortest paths between two nodes
> using KShortestPaths, and I only receive the following exception:
>
> [code]
> java.lang.IllegalArgumentException: graph must contain the start vertex
>     at
> org.jgrapht.traverse.CrossComponentIterator.<init>(CrossComponentIterator.java:170)
>     at
> org.jgrapht.traverse.BreadthFirstIterator.<init>(BreadthFirstIterator.java:92)
>     at
> org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
>     at
> org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
>     at
> org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
>     at
> org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
>     at
> org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
>     at
> org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
>     at
> org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
>     at
> org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
>     at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
>     at KShortestPathsMain.main(KShortestPathsMain.java:97)
> [/code]
>
> Note that I am only getting this exception with that one, large graph I
> created from my data. When I create a graph by hand, it does not occur.
> Here is my test program. The graph is attached.
>
> [code]
> import java.io.BufferedReader;
> import java.io.FileNotFoundException;
> import java.io.FileReader;
> import java.io.IOException;
> import java.util.List;
>
> import org.jgrapht.GraphPath;
> import org.jgrapht.alg.KShortestPaths;
> import org.jgrapht.graph.DefaultWeightedEdge;
> import org.jgrapht.graph.SimpleWeightedGraph;
>
> public class KShortestPathsMain {
>
>     public KShortestPathsMain() {}
>
>     public static void main(String[] args) {
>
>         SimpleWeightedGraph<String, DefaultWeightedEdge> graph = new
> SimpleWeightedGraph<>(DefaultWeightedEdge.class);
>
>             FileReader fstream = null;
>             try {
>                 fstream = new FileReader("edges.txt");
>             } catch (FileNotFoundException e1) {
>                 e1.printStackTrace();
>             }
>             BufferedReader in = new BufferedReader(fstream);
>
>             String[] edgeText;
>             DefaultWeightedEdge ed;
>             String line = null;
>             try {
>                 line = in.readLine();
>             } catch (IOException e1) {
>                 // TODO Auto-generated catch block
>                 e1.printStackTrace();
>             }
>             while(line != null) {
>                 edgeText = line.split("\t");
>
>                 graph.addVertex(edgeText[0]);
>                 graph.addVertex(edgeText[1]);
>                 ed = graph.addEdge(edgeText[0], edgeText[1]);
>                 graph.setEdgeWeight(ed, Double.parseDouble(edgeText[2]));
>
>                 try {
>                     line = in.readLine();
>                 } catch (IOException e) {
>                     e.printStackTrace();
>                 }
>             }
>
>             // Close the input stream
>             try {
>                 in.close();
>             } catch (IOException e1) {
>                 e1.printStackTrace();
>             }
>
>         DefaultWeightedEdge src = graph.getEdge("M013", "M014");
>
>         KShortestPaths<String, DefaultWeightedEdge> kPaths = new
> KShortestPaths<String, DefaultWeightedEdge>(
>                 graph, graph.getEdgeSource(src), 5);
>         List<GraphPath<String,DefaultWeightedEdge>> paths = null;
>
>         try {
>             paths = kPaths.getPaths(graph.getEdgeTarget(src));
>             for (GraphPath<String, DefaultWeightedEdge> path : paths) {
>                 for (DefaultWeightedEdge edge : path.getEdgeList()) {
>                     System.out.print("<" + graph.getEdgeSource(edge) + "\t"
>                             + graph.getEdgeTarget(edge) + "\t" + edge +
> ">\t");
>                 }
>                 System.out.println(": " + path.getWeight());
>             }
>         } catch (IllegalArgumentException e) {
>             e.printStackTrace();
>         }
>     }
> }
>
> [/code]
>
> I tried different edges, and directed and undirected graphs. Same result.
> If anyone has a clue what might be going on here, I'd very much appreciate
> help.
>
>
> Sebastian
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!http://www2.precog.com/precogplatform/slashdotnewsletter
>
>
>
> _______________________________________________
> jgrapht-users mailing lis...@li...https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>
>

[jgrapht-users] Help about custom vertex

[arastoo b. <ara...@ya...>]

Hello
i am new in jgrapht and i have download it 2 days ago.
i want to make an undirect weighted graph with custom vertex structure. the vertex should have these properties:
1-string data
2-double teta
3-string status

i dont know how to define these vertex structure in JGrapht and make my graph with this vertex structure, also i dont know which type of graph should i use

please help me

[jgrapht-users] (no subject)

[arastoo b. <ara...@ya...>]

ara...@ya...

Re: [jgrapht-users] closeSimpleDirectedGraph() doesn't return

[Yi L. <qi...@gm...>]

Yes, you are right.. I tried to be more patient waiting for the result 
and did get the transitive closure.

Also thanks to Georg Hieronimus for letting me know the difference 
between loop and cycle.

Regards,
Yi

On 23/04/13 10:40 , John Sichi wrote:
> In general, directed graphs are not required to be acyclic, which is
> why you don't receive any warning.  Class
> org.jgrapht.experimental.dag.DirectedAcyclicGraph is intended for when
> you need to prevent loops from being created.
>
> If you have a huge graph, maybe it just takes a long time?  Looks like
> the worst case running time for the current implementation should be
> log2(|V|)*|E|^2.  FloydWarshall would probably do better.
>
> JVS
>
>
> On Mon, Apr 22, 2013 at 1:19 AM, Yi Lin <qi...@gm...> wrote:
>> Hi all,
>>
>> I am trying to use JGraphT in my project.
>>
>> I used SimpleDirectedGraph to store my graph (the graph is dynamically
>> generated, and huge). All the vertices and edges are added to the graph,
>> it seems fine - no warning to say there is a loop.
>>
>> Then I tried to get transitive closure on the graph. So I called
>> TransitiveClosure.INSTANCE.closeSimpleDirectedGraph(myGraph);
>> However, the execution got stuck in this method and it didn't return.
>>
>> I tried to call new CycleDetector<V, E>(myGraph).detectCycles() before
>> computing transitive closure, and it returns true.
>>
>> It seems weird to me now, since SimpleDirectedGraph should prompt a
>> warning if there is any loop when an edge is added. There wasn't any
>> warning, but CycleDectector reported cycles.
>>
>> Thus I am not sure what the problem is now. Possible cycles in the
>> graph, or I used those APIs in a wrong way, or any known implementation
>> problem with JGraphT (with
>> CycleDetector/TransitiveClosure/SimpleDirectedGraph)?
>>
>> I could dump the graph, and check through it. But the graph is huge, I
>> would rather not to walk through it unless I have to.
>> I think I would better ask the question here for some suggestions. Any
>> help would be appreciated. Thank you very much.
>>
>> Regards,
>> Yi
>>
>> ------------------------------------------------------------------------------
>> Precog is a next-generation analytics platform capable of advanced
>> analytics on semi-structured data. The platform includes APIs for building
>> apps and a phenomenal toolset for data science. Developers can use
>> our toolset for easy data analysis & visualization. Get a free account!
>> http://www2.precog.com/precogplatform/slashdotnewsletter
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] closeSimpleDirectedGraph() doesn't return

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

In general, directed graphs are not required to be acyclic, which is
why you don't receive any warning.  Class
org.jgrapht.experimental.dag.DirectedAcyclicGraph is intended for when
you need to prevent loops from being created.

If you have a huge graph, maybe it just takes a long time?  Looks like
the worst case running time for the current implementation should be
log2(|V|)*|E|^2.  FloydWarshall would probably do better.

JVS


On Mon, Apr 22, 2013 at 1:19 AM, Yi Lin <qi...@gm...> wrote:
> Hi all,
>
> I am trying to use JGraphT in my project.
>
> I used SimpleDirectedGraph to store my graph (the graph is dynamically
> generated, and huge). All the vertices and edges are added to the graph,
> it seems fine - no warning to say there is a loop.
>
> Then I tried to get transitive closure on the graph. So I called
> TransitiveClosure.INSTANCE.closeSimpleDirectedGraph(myGraph);
> However, the execution got stuck in this method and it didn't return.
>
> I tried to call new CycleDetector<V, E>(myGraph).detectCycles() before
> computing transitive closure, and it returns true.
>
> It seems weird to me now, since SimpleDirectedGraph should prompt a
> warning if there is any loop when an edge is added. There wasn't any
> warning, but CycleDectector reported cycles.
>
> Thus I am not sure what the problem is now. Possible cycles in the
> graph, or I used those APIs in a wrong way, or any known implementation
> problem with JGraphT (with
> CycleDetector/TransitiveClosure/SimpleDirectedGraph)?
>
> I could dump the graph, and check through it. But the graph is huge, I
> would rather not to walk through it unless I have to.
> I think I would better ask the question here for some suggestions. Any
> help would be appreciated. Thank you very much.
>
> Regards,
> Yi
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users