jgrapht-users — JGraphT user list.

Re: [jgrapht-users] ChromaticNumber always 1

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

Ernst,

Ah yes, I had foolishly left the auto-generated delegated .equals() to the
String contained in the vertex, but then that String did not equal the
encapsulating object it was being compared against!

It is working as expected now.

Thanks,

Nick

On 10 December 2012 16:13, H.N. de Ridder <hnr...@gr...> wrote:

> On Wed, Dec 05, 2012 at 11:44:43AM +0000, Nick England wrote:
>
> > I have just started using JGraphT and have got it to produce a graph from
> > my data. I can get the edgeSet().size() and vertexSet().size fine, but
> if I
> > try to calculate the Chromatic number I get 1 no matter what the number
> of
> > edges and vertices!
>
> My guess would be you got hit by this:
> https://github.com/jgrapht/jgrapht/wiki/EqualsAndHashCode
>
> Regards,
>    Ernst
>
> --
> Information System on Graph Classes and their Inclusions (ISGCI)
> http://www.graphclasses.org
>
>
> ------------------------------------------------------------------------------
> LogMeIn Rescue: Anywhere, Anytime Remote support for IT. Free Trial
> Remotely access PCs and mobile devices and provide instant support
> Improve your efficiency, and focus on delivering more value-add services
> Discover what IT Professionals Know. Rescue delivers
> http://p.sf.net/sfu/logmein_12329d2d
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] StoerWagnerMinimumCut bugged?

[H.N. de R. <hnr...@gr...>]

On Thu, Nov 01, 2012 at 05:43:59PM +0100, Joris Kinable wrote:

> It seems that the StoerWagnerMinimumCut is bugged in jgrapht 0.8.3.
> Attached are two small code samples, both resulting in a runtime
> error.

I took a quick peek at the code of StoerWagnerMinimumCut and there are two
things wrong with it:
1) It accepts DirectedGraphs, although the algorithm only works for
undirected graphs.
2) The main loop runs while |V| > 2, instead of |V| > 1.

Is this issue still current, or did somebody already create a fix for it?

Regards,
   Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

Re: [jgrapht-users] ChromaticNumber always 1

[H.N. de R. <hnr...@gr...>]

On Wed, Dec 05, 2012 at 11:44:43AM +0000, Nick England wrote:

> I have just started using JGraphT and have got it to produce a graph from
> my data. I can get the edgeSet().size() and vertexSet().size fine, but if I
> try to calculate the Chromatic number I get 1 no matter what the number of
> edges and vertices!

My guess would be you got hit by this:
https://github.com/jgrapht/jgrapht/wiki/EqualsAndHashCode

Regards,
   Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

[jgrapht-users] ChromaticNumber always 1

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

Dear all,

I have just started using JGraphT and have got it to produce a graph from
my data. I can get the edgeSet().size() and vertexSet().size fine, but if I
try to calculate the Chromatic number I get 1 no matter what the number of
edges and vertices!

The code I am using is bellow: (where create.getCluster(x) returns a graph
generated from some data).

UndirectedGraph<StringCount, DefaultEdge> graph = create.getCluster(x);
      int colour=ChromaticNumber.findGreedyChromaticNumber(graph);
      System.out.println("Cluster with "+graph.edgeSet().size()+" edges and
"+graph.vertexSet().size()+" verticies "+" colours:"+colour);


which gives the output bellow:

Cluster with 8 edges and 5 vertices  colours:1
Cluster with 47 edges and 14 vertices  colours:1
Cluster with 4 edges and 4 vertices  colours:1
Cluster with 478 edges and 90 vertices  colours:1
Cluster with 34 edges and 14 vertices  colours:1
Cluster with 13 edges and 24 vertices  colours:1

It seems a bit unusual that .findGreedyChromaticNumber always returns 1!

My Vertex class is a Pair of a String and an int which delegates the
hashCode() and equals() methods to the string it contains.

Any help would be appreciated!

Thanks

Nick England

Re: [jgrapht-users] remove all edges and vertices

[Alex M. <am...@di...>]

That works, thanks.

 

From: m....@go... [mailto:m....@go...] On Behalf Of Georg Hieronimus
Sent: Monday, November 19, 2012 3:38 PM
To: Alex Moir; jgr...@li...
Subject: Re: [jgrapht-users] remove all edges and vertices

 

i use this:

 

public static <V,E> void removeAllEdges(Graph<V, E> graph) {

                        LinkedList<E> copy = new LinkedList<E>();

                        for (E e : graph.edgeSet()) {

                                    copy.add(e);

                        }

                        graph.removeAllEdges(copy);

            }

 

            public static <V,E> void clearGraph(Graph<V, E> graph) {

                        removeAllEdges(graph);

                        removeAllVertices(graph);

            }

            

 

            public static <V,E> void removeAllVertices(Graph<V, E> graph) {

                        LinkedList<V> copy = new LinkedList<V>();

                        for (V v : graph.vertexSet()) {

                                    copy.add(v);

                        }

                        graph.removeAllVertices(copy);

            }

 

On 20 November 2012 00:23, Alex Moir <am...@di...> wrote:

Does anyone know a way to reset an entire graph?  I tried the following methods and in all cases I got a ConcurrentModificationException…

 

Attempt #1

     graph.removeAllEdges( graph.edgeSet() );

     graph.removeAllVertices( graph.vertexSet() );

 

Attempt #2

      Set<RelationshipEdge> allEdges = graph.edgeSet();

     for ( RelationshipEdge aEdge : allEdges )

      { 

         graph.removeEdge( aEdge );

      }

 

Attempt #3

      Set<RelationshipEdge> allEdges = graph.edgeSet();

      allEdges.clear();

 

 

Thanks,

Alex


------------------------------------------------------------------------------
Monitor your physical, virtual and cloud infrastructure from a single
web console. Get in-depth insight into apps, servers, databases, vmware,
SAP, cloud infrastructure, etc. Download 30-day Free Trial.
Pricing starts from $795 for 25 servers or applications!
http://p.sf.net/sfu/zoho_dev2dev_nov
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

 

Re: [jgrapht-users] remove all edges and vertices

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

i use this:

public static <V,E> void removeAllEdges(Graph<V, E> graph) {
LinkedList<E> copy = new LinkedList<E>();
 for (E e : graph.edgeSet()) {
copy.add(e);
}
 graph.removeAllEdges(copy);
}

public static <V,E> void clearGraph(Graph<V, E> graph) {
 removeAllEdges(graph);
removeAllVertices(graph);
}

public static <V,E> void removeAllVertices(Graph<V, E> graph) {
 LinkedList<V> copy = new LinkedList<V>();
for (V v : graph.vertexSet()) {
 copy.add(v);
}
graph.removeAllVertices(copy);
 }

On 20 November 2012 00:23, Alex Moir <am...@di...> wrote:

> Does anyone know a way to reset an entire graph?  I tried the following
> methods and in all cases I got a ConcurrentModificationException…****
>
> ** **
>
> Attempt #1****
>
>      graph.removeAllEdges( graph.edgeSet() );****
>
>      graph.removeAllVertices( graph.vertexSet() );****
>
> ** **
>
> Attempt #2****
>
>       Set<RelationshipEdge> allEdges = graph.edgeSet();****
>
>      for ( RelationshipEdge aEdge : allEdges )****
>
>       { ****
>
>          graph.removeEdge( aEdge );****
>
>       }****
>
> ** **
>
> Attempt #3****
>
>       Set<RelationshipEdge> allEdges = graph.edgeSet();****
>
>       allEdges.clear();****
>
> ** **
>
> ** **
>
> Thanks,****
>
> Alex****
>
>
> ------------------------------------------------------------------------------
> Monitor your physical, virtual and cloud infrastructure from a single
> web console. Get in-depth insight into apps, servers, databases, vmware,
> SAP, cloud infrastructure, etc. Download 30-day Free Trial.
> Pricing starts from $795 for 25 servers or applications!
> http://p.sf.net/sfu/zoho_dev2dev_nov
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] remove all edges and vertices

[Alex M. <am...@di...>]

Does anyone know a way to reset an entire graph?  I tried the following
methods and in all cases I got a ConcurrentModificationException.

 

Attempt #1

     graph.removeAllEdges( graph.edgeSet() );

     graph.removeAllVertices( graph.vertexSet() );

 

Attempt #2

      Set<RelationshipEdge> allEdges = graph.edgeSet();

     for ( RelationshipEdge aEdge : allEdges )

      { 

         graph.removeEdge( aEdge );

      }

 

Attempt #3

      Set<RelationshipEdge> allEdges = graph.edgeSet();

      allEdges.clear();

 

 

Thanks,

Alex

Re: [jgrapht-users] StoerWagnerMinimumCut bugged?

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

Thanks, I've fixed the links on the home page.

For StoerWagnerMinimumCut, do you want to send a pull request with a fix?

JVS

On Thu, Nov 1, 2012 at 9:43 AM, Joris Kinable <de...@gm...> wrote:
> Dear,
>
> It seems that the StoerWagnerMinimumCut is bugged in jgrapht 0.8.3.
> Attached are two small code samples, both resulting in a runtime
> error.
>
> Sample Test2. The graph contains just 2 vertices, joined with an edge.
> StoerWagner fails to return a minimum cut for this trivial case. When
> a third vertex+edge is added, StoerWagner works correctly.
> Suggestion: either verify that this is a bug, or specify in the
> documentation that the graph requires at least 3 vertices and 2 edges.
>
> Sample Test. StoerWagner's constructor takes a WeightedGraph<V,E>
> graph. So per definition, I should be able to run it on a
> DefaultDirectedWeightedGraph. This however results in a runtime error:
> Exception in thread "main" java.lang.NullPointerException
>         at org.jgrapht.graph.AbstractBaseGraph.setEdgeWeight(Unknown Source)
>         at org.jgrapht.alg.StoerWagnerMinimumCut.<init>(Unknown Source)
>         at algorithms.mip.Test.<init>(Test.java:37)
>         at algorithms.mip.Test.main(Test.java:44)
>
> When I however switch the DefaultDirectedWeightedGraph to a
> SimpleWeightedGraph, everything works fine again. Suggestion: either
> verify that this is a bug, or change the constructor of the class such
> that it only accepts a SimpleWeightedGraph.
>
> br,
>
> Joris
>
> Ps. The bug report link on the home page of jgrapht returns an error:
> Permission Denied
> Access to this page is restricted (either to project members or to
> project administrators) and you do not meet the requirements to access
> this page. Please contact the administrator of this project for
> further assistance.
>
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_sfd2d_oct
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] StoerWagnerMinimumCut bugged?

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

Dear,

It seems that the StoerWagnerMinimumCut is bugged in jgrapht 0.8.3.
Attached are two small code samples, both resulting in a runtime
error.

Sample Test2. The graph contains just 2 vertices, joined with an edge.
StoerWagner fails to return a minimum cut for this trivial case. When
a third vertex+edge is added, StoerWagner works correctly.
Suggestion: either verify that this is a bug, or specify in the
documentation that the graph requires at least 3 vertices and 2 edges.

Sample Test. StoerWagner's constructor takes a WeightedGraph<V,E>
graph. So per definition, I should be able to run it on a
DefaultDirectedWeightedGraph. This however results in a runtime error:
Exception in thread "main" java.lang.NullPointerException
	at org.jgrapht.graph.AbstractBaseGraph.setEdgeWeight(Unknown Source)
	at org.jgrapht.alg.StoerWagnerMinimumCut.<init>(Unknown Source)
	at algorithms.mip.Test.<init>(Test.java:37)
	at algorithms.mip.Test.main(Test.java:44)

When I however switch the DefaultDirectedWeightedGraph to a
SimpleWeightedGraph, everything works fine again. Suggestion: either
verify that this is a bug, or change the constructor of the class such
that it only accepts a SimpleWeightedGraph.

br,

Joris

Ps. The bug report link on the home page of jgrapht returns an error:
Permission Denied
Access to this page is restricted (either to project members or to
project administrators) and you do not meet the requirements to access
this page. Please contact the administrator of this project for
further assistance.

[jgrapht-users] How to make a ListenableDirectedWeightedMultigraph

[Alex M. <am...@di...>]

For some reason this does not exist.  I am trying to make one on my own and am getting compile errors.  This is what I have…

 

    public class ListenableDirectedWeightedMultigraph<V, E>

        extends ListenableDirectedWeightedGraph<V, E>

        implements WeightedGraph<V, E>

    {

 

        public ListenableDirectedWeightedMultigraph(Class<E> edgeClass)

        {

            this(new DirectedWeightedMultigraph<V, E>(edgeClass));

        }

        

        

        public ListenableDirectedWeightedMultigraph(WeightedMultigraph<V, E> base)

        {

            super((DirectedGraph<V, E>(base));

        }

    }

 

Any help appreciated.


Thanks,

Alex

Re: [jgrapht-users] jgraph question

[Alex M. <am...@di...>]

Thanks for the link.  I am able to run the given JGraphXAdapter code
successfully, but when I try to integrate it in my own code I get a blank
screen.  Maybe it's because of the cell location stuff.  In that link
somebody said "The most trickey for me was having to set-up the cell
location and dimension, before applying layouts."  I'm not sure what that
means, but I have a feeling I am having the same problem.  When I try to
apply my own layout by modifying the JGraphXAdapter, I added the following
code in the main() method:

      mxIGraphLayout layout = new mxFastOrganicLayout( graph );

      // layout using morphing
      graph.getModel().beginUpdate();
      try
      {
         layout.execute( graph.getDefaultParent() );
      }
      finally
      {
         mxMorphing morph = new mxMorphing( graphComponent, 20, 1.2, 20 );

         morph.addListener( mxEvent.DONE, new mxIEventListener()
         {
            @Override
            public void invoke( Object arg0, mxEventObject arg1 )
            {
               graph.getModel().endUpdate();
               // fitViewport();
            }
         } );

         morph.startAnimation();
      }

But I got this exception:
Exception in thread "main" java.lang.NullPointerException
	at com.mxgraph.layout.mxGraphLayout.getVertexBounds(Unknown Source)
	at com.mxgraph.layout.mxFastOrganicLayout.execute(Unknown Source)
	at com.dii.fuzzy.gui.JGraphXAdapter.main(JGraphXAdapter.java:243)

Then I tried this code instead to do the layout and got the exact same
exception.

      mxFastOrganicLayout layout = new mxFastOrganicLayout( graph );

      // set some properties
      
      layout.setForceConstant( 40 ); // the higher, the more separated
      layout.setDisableEdgeStyle( false ); // true transforms the edges and
makes them direct lines

      // layout graph
      layout.execute( graph.getDefaultParent() );

Does anyone have an idea on how to avoid this exception when trying to
layout the graph?  Is it because I don't have the right cell location or
dimensions like that person posted?

Thanks,
Alex

Re: [jgrapht-users] set edges length

[<hnr...@gr...>]

Hi Cyril,

create g as a WeightedGraph and use g.setEdgeWeight().

Regards,
   Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org

----- Reply message -----
From: "Cyril Auburtin" <cyr...@gm...>
To: <jgr...@li...>
Subject: [jgrapht-users] set edges length
Date: Tue, Oct 23, 2012 20:24
I'd like yo know if it's possible to set a defined length for edges, and update it  programmatically
 // add the vertices g.addVertex(amazon); g.addVertex(yahoo);

 g.addVertex(ebay);
 // add edges to create linking structure g.addEdge(yahoo, amazon); g.addEdge(yahoo, ebay);
for example above, set a third argument to specify the edge length

Thx

[jgrapht-users] set edges length

[Cyril A. <cyr...@gm...>]

I'd like yo know if it's possible to set a defined length for edges, and
update it  programmatically

 // add the vertices
 g.addVertex(amazon);
 g.addVertex(yahoo);
 g.addVertex(ebay);

 // add edges to create linking structure
 g.addEdge(yahoo, amazon);
 g.addEdge(yahoo, ebay);

for example above, set a third argument to specify the edge length
Thx

Re: [jgrapht-users] jgraph question

[Philip A G. II <pg...@da...>]

Alex,

 

The JGraph adapter and the associated demo are for a previous version of
JGraph.  If you use the jgraph jar file that is in the lib directory of the
jgrapht distro, you can make the demo work.

 

The current version of JGraph was re-written to align with the JavaScript
version, and repackaged as mxGraph (because that's what the JavaScript API
is called).  The API is completely different and the adapter won't work with
it - and there's not an easy path to make it work.

 

I did find a very simple adapter that someone wrote that works one-way with
the mxGraph API, but it's incomplete and needs some work.  You can find it
here:

 

http://forum.jgraph.com/questions/133/using-jgraphx-to-visualize-jgrapht

 

Hope this helps,

Phil

 

From: Alex Moir [mailto:am...@di...] 
Sent: Friday, October 19, 2012 7:25 PM
To: jgr...@li...
Subject: [jgrapht-users] jgraph question

 

Hey All,

 

So I tried downloading the latest jgraph from jgraph.com.  All I seem to be
getting is some mxgraph stuff, even in the jar file called jgraph.jar.  I am
trying to compile my version of the JGraphAdapterDemo using the latest
jgraphx.jar from that website but it can't find some of the basic files like
JGraph.class which I also don't see in the jar file.  Is the
JGraphAdapterDemo just out of date and uses an old version of JGraph?

 

Thanks,

Alex

[jgrapht-users] jgraph question

[Alex M. <am...@di...>]

Hey All,

 

So I tried downloading the latest jgraph from jgraph.com.  All I seem to be
getting is some mxgraph stuff, even in the jar file called jgraph.jar.  I am
trying to compile my version of the JGraphAdapterDemo using the latest
jgraphx.jar from that website but it can't find some of the basic files like
JGraph.class which I also don't see in the jar file.  Is the
JGraphAdapterDemo just out of date and uses an old version of JGraph?

 

Thanks,

Alex

[jgrapht-users] Graph visualization

[Nilo <nil...@gm...>]

Hi all.

Just started to use JGrapht. It's an excelent library, and very usefull for
my needs.

I would like to know how can I visualize a graph I've created by JGrapht on
a swing window, just for debugging purposes of my code.

The JGrapht site suggests me to use JGraph (that have its name altered to
JGraphx, I think), but the sample code doesn't even compile.

As indicated on site, as a starting point I tried to use:

*// create a JGraphT graph*

ListenableGraph g = *new* ListenableDirectedGraph( DefaultEdge.class );

*// create a visualization using JGraph, via the adapter*

JGraph jgraph = *new* JGraph( *new* JGraphModelAdapter( g ) );


but this code produces compilation errors.

I'm using last version of both JGraph and JGraphx, as obtained from his
respective sites.

Can someone give me some hint or sample?

Sorry about poor english. It's not my native language...

TIA,
-- 

Nilo Roberto C Paim
TinyCobol Development Team
Brasília - DF - Brazil

[jgrapht-users] Override Edge Caption

[Thomas H. <tho...@ru...>]

Dear Community,

I am enthusiastically using JGraphT for my graph theoretical researches.
Hence, I want to change something about the visualization with the
included JGraph-File:

Let G be a directed graph with weighted edges. When "drawing" G, the
appled sets the captions for each edge like "(source-vertex :
destination-vertex)".
How can I customize this pattern? I actually want the edge's weight be
printed on the screen; not its vertexes.

Is there a way to do this?

Thank you very much!

Kind Regards
Thomas

Re: [jgrapht-users] get all vertices of a certain type

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

Dear Alex,

I'm doing something similar in my code. I'll show you what I did

1. I created a class Vertex, and two subclasses 'Student' and 'Stop',
which both extend the class Vertex.
2. Next I created a class SBRGraph which extends
ListenableUndirectedWeightedGraph<Vertex,DefaultWeightedEdge>
3. I wrote the following method:

public <T extends Vertex> Set<T> getNeighbors(Vertex v, Class<T> vType){
  if(!this.containsVertex(v))
    return Collections.emptySet();
  else{
    Set<DefaultWeightedEdge> incidentEdges=this.edgesOf(v);
    Set<T> neighbors=new HashSet<T>();
    for(DefaultWeightedEdge e: incidentEdges){
      Vertex neighbor=(this.getEdgeTarget(e)!=v ?
this.getEdgeTarget(e) : this.getEdgeSource(e));
      if(neighbor.getClass() == vType)
        neighbors.add(vType.cast(neighbor));
      }
        return neighbors;
    }
}

This method allows me to query neighbors of a given type. Let's say
that I want to find all neighbors of the type Student for a given
vertex v in the graph, then I would invoke:
graph.getNeighbors(v,Student.class). The result would be an
ArrayList<Student>.
Obviously, if you just want to query the list of vertices of a given
type, the easiest thing is to extend the addVertex() method in the
graph and maintain lists of vertices of a specific type.

br,

Joris


On Wed, Oct 17, 2012 at 4:03 AM, Alex Moir
<am...@di...> wrote:
> I am new to jgrapht.  If I create a custom Vertex class that is abstract and
> it has two sub classes, is there an easy way to get all the vertices of only
> one of the subclass types?
>
>
>
> For example, if my custom vertex type is MyGenericVertex, and one subclass
> is HumanVertex and the other is ComputerVertex.  Is there a built in way to
> efficiently get all the HumanVertex objects?
>
>
>
> I tried searching the archives for an answer to this and didn’t see one .
> The closest thing I found was this topic:
>
> http://sourceforge.net/mailarchive/message.php?msg_id=22046693
>
>
>
> Do I have to maintain my own data structures, one for HumanVertex and one
> for ComputerVertex?
>
>
>
> Thanks,
>
> Alex
>
>
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_sfd2d_oct
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] get all vertices of a certain type

[<hnr...@gr...>]

Hi Alex,

yes, you'll have to maintain your own data structure(s).

Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org

----- Reply message -----
From: "Alex Moir" <am...@di...>
To: <jgr...@li...>
Subject: [jgrapht-users] get all vertices of a certain type
Date: Wed, Oct 17, 2012 04:03
I am new to jgrapht.  If I create a custom Vertex class that is abstract and it has two sub classes, is there an easy way to get all the vertices of only one of the subclass types? For example, if my custom vertex type is MyGenericVertex, and one subclass is HumanVertex and the other is ComputerVertex.  Is there a built in way to efficiently get all the HumanVertex objects? I tried searching the archives for an answer to this and didn’t see one ..  The closest thing I found was this topic:http://sourceforge.net/mailarchive/message.php?msg_id=22046693 Do I have to maintain my own data structures, one for HumanVertex and one for ComputerVertex? Thanks,Alex

[jgrapht-users] get all vertices of a certain type

[Alex M. <am...@di...>]

I am new to jgrapht.  If I create a custom Vertex class that is abstract and
it has two sub classes, is there an easy way to get all the vertices of only
one of the subclass types?

 

For example, if my custom vertex type is MyGenericVertex, and one subclass
is HumanVertex and the other is ComputerVertex.  Is there a built in way to
efficiently get all the HumanVertex objects?

 

I tried searching the archives for an answer to this and didn't see one .
The closest thing I found was this topic:

http://sourceforge.net/mailarchive/message.php?msg_id=22046693

 

Do I have to maintain my own data structures, one for HumanVertex and one
for ComputerVertex?

 

Thanks,

Alex

Re: [jgrapht-users] JGraphT Enquiry: KShortestPaths Bug?

[martin85 <vic...@gm...>]

I had exactly the same problem with my graph using kshort alg, error message
saying : "graph must contain the start vertex".
CrossComponentIterator:170 -> constructor CrossComponentIterator(Graph<V, E>
g, V startVertex) 

My graph is huge so i dont know how to write small junit test for you guys -
i will propably try to generate some small random graphs and i hope it will
trigger that bug.

As a workaround i commented that illegalarg exception and algorithm "works
fine" but obviously it`s tricky.

Before bug will be pointed out and hopefully fixed, are there any alernative
java libraries which implements k-shortest-path algoritm ? 

Thanks





--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Re-JGraphT-Enquiry-KShortestPaths-Bug-tp4024711p4024733.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] edge weight as a function depending on previous edge

[Martin V. <vic...@gm...>]

Hi,

i wonder if it is possible to implement weight in path searching algorithm
(e.g. k-shortest paths) in the way that
weight of actual edge would depend on the attribute of previous edge when
algorithm is constructing path.
More specifically : I am implementing bus routing.

I putted all locations,connections,timetables together and i created graph
and shortest and k-shortest paths are
searched fine BUT thing about what happens when you change bus in some
location - you usually wait for some
time for connecting bus and amount(weight) of this time depends on previous
bus connection and on connecting
bus line -> that`s what concerns me.

For sure i can use unweighted graph, algorithm will tell me what`s best way
in given topology and in some "post-process" i will compute precise timings
for shortest and k-shortest bus paths, BUT this is not so elegant solution.

Any ideas / hints ?
Thank you

Martin85

Re: [jgrapht-users] A question to cycle detection using DefaultDirectedGraph

[<hnr...@gr...>]

Hi Ray,

this makes me suspect you're running into
https://github.com/jgrapht/jgrapht/wiki/EqualsAndHashCode

Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org

----- Reply message -----
From: "Rui Chang" <cha...@ho...>
To: <hnr...@gr...>, <jgr...@li...>
Subject: [jgrapht-users] A question to cycle detection using DefaultDirectedGraph
Date: Wed, Oct 3, 2012 00:21
Hi Ernst, Thanks for your reply. Glad to know at least that create a new CycleDetector object should work by definition.
Regarding to a bug in my code or with JGrapht, I am not sure...but I do noticed some weird behavior of this DefaultDirectedGraph, that if I add edge as graph.addEdge("parent","child"), then the resulting graph contains always the last edge added to the graph (some overwritting is going on), if I use graph.addEdge("parent","child","ei") (i=iteration index), then all edges are corrected added...
I don't know if this is propagating into the CycleDetector bug because I modify the graph in a loop and if the graph does not add the edge correct, it may result in a bug seemingly at the CycleDetector's end.
Ray

To: cha...@ho...; jgr...@li...
From: hnr...@gr...
Subject: Re: [jgrapht-users] A question to cycle detection using DefaultDirectedGraph
Date: Tue, 2 Oct 2012 21:54:13 +0200




Hello Ray,

this phrase means that you cannot modify the graph specified when creating the CycleDetector and expect the CycleDetector to work correctly. Instead, you should create a new CycleDetector after every modification to the graph, and use this new CycleDetector.

Since this is what you say you do, I guess there is a bug in your code, or a bug in CycleDetector or a mistake is made when manually checking for cycles. Try to find a minimal example of the problem.

Regards,
Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org

----- Reply message -----
From: "Rui Chang" <cha...@ho...>
To: <jgr...@li...>
Subject: [jgrapht-users] A question to cycle detection using DefaultDirectedGraph
Date: Sun, Sep 30, 2012 19:07



Hi All, I am new to JGraphT. I want to use CycleDetector to detect cycles in a DefaultDirectedGraph. In my code, the graph is initialized/constructed at the beginning of the program, then I have a loop, in each of which, the graph is modified by calling addEdge and/or removeEdge randomly. But the total vertex set stay the same. In each loop, after modification on graph, I initiate a new CycleDetector class to detect cycles in the modified graph, but sometimes, I see obviously there are cycles in the modified graph, which is not captured by CycleDetector!
I wonder is it some bug or is it my mistake to use CycleDetector in this way as I recall the javadoc of CycleDetector class says something like: "The inspected graph is specified at construction time and cannot be modified"...
But I don't know if I really understand what it means...
Thanks for any thought!Best,Ray

Re: [jgrapht-users] A question to cycle detection using DefaultDirectedGraph

[Rui C. <cha...@ho...>]

Hi Ernst, Thanks for your reply. Glad to know at least that create a new CycleDetector object should work by definition.
 Regarding to a bug in my code or with JGrapht, I am not sure...but I do noticed some weird behavior of this DefaultDirectedGraph, that if I add edge as graph.addEdge("parent","child"), then the resulting graph contains always the last edge added to the graph (some overwritting is going on), if I use graph.addEdge("parent","child","ei") (i=iteration index), then all edges are corrected added...
 I don't know if this is propagating into the CycleDetector bug because I modify the graph in a loop and if the graph does not add the edge correct, it may result in a bug seemingly at the CycleDetector's end.
Ray

To: cha...@ho...; jgr...@li...
From: hnr...@gr...
Subject: Re: [jgrapht-users] A question to cycle detection using	DefaultDirectedGraph
Date: Tue, 2 Oct 2012 21:54:13 +0200




Hello Ray,

this phrase means that you cannot modify the graph specified when creating the CycleDetector and expect the CycleDetector to work correctly. Instead, you should create a new CycleDetector after every modification to the graph, and use this new CycleDetector.

Since this is what you say you do, I guess there is a bug in your code, or a bug in CycleDetector or a mistake is made when manually checking for cycles. Try to find a minimal example of the problem.

Regards,
   Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org

----- Reply message -----
From: "Rui Chang" <cha...@ho...>
To: <jgr...@li...>
Subject: [jgrapht-users] A question to cycle detection using	DefaultDirectedGraph
Date: Sun, Sep 30, 2012 19:07



Hi All, I am new to JGraphT. I want to use CycleDetector to detect cycles in a DefaultDirectedGraph. In my code, the graph is initialized/constructed at the beginning of the program, then I have a loop, in each of which, the graph is modified by calling addEdge and/or removeEdge randomly. But the total vertex set stay the same. In each loop, after modification on graph, I initiate a new CycleDetector class to detect cycles in the modified graph, but sometimes, I see obviously there are cycles in the modified graph, which is not captured by CycleDetector!
 I wonder is it some bug or is it my mistake to use CycleDetector in this way as I recall the javadoc of CycleDetector class says something like: "The inspected graph is specified at construction time and cannot be modified"...
 But I don't know if I really understand what it means...
Thanks for any thought!Best,Ray 		 	   		   		 	   		  

Re: [jgrapht-users] A question to cycle detection using DefaultDirectedGraph

[<hnr...@gr...>]

Hello Ray,

this phrase means that you cannot modify the graph specified when creating the CycleDetector and expect the CycleDetector to work correctly. Instead, you should create a new CycleDetector after every modification to the graph, and use this new CycleDetector.

Since this is what you say you do, I guess there is a bug in your code, or a bug in CycleDetector or a mistake is made when manually checking for cycles. Try to find a minimal example of the problem.

Regards,
   Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org

----- Reply message -----
From: "Rui Chang" <cha...@ho...>
To: <jgr...@li...>
Subject: [jgrapht-users] A question to cycle detection using DefaultDirectedGraph
Date: Sun, Sep 30, 2012 19:07
Hi All, I am new to JGraphT. I want to use CycleDetector to detect cycles in a DefaultDirectedGraph. In my code, the graph is initialized/constructed at the beginning of the program, then I have a loop, in each of which, the graph is modified by calling addEdge and/or removeEdge randomly. But the total vertex set stay the same. In each loop, after modification on graph, I initiate a new CycleDetector class to detect cycles in the modified graph, but sometimes, I see obviously there are cycles in the modified graph, which is not captured by CycleDetector!
I wonder is it some bug or is it my mistake to use CycleDetector in this way as I recall the javadoc of CycleDetector class says something like: "The inspected graph is specified at construction time and cannot be modified"...
But I don't know if I really understand what it means...
Thanks for any thought!Best,Ray