jgrapht-users — JGraphT user list.

[jgrapht-users] JGraphT vs. JUNG

[Rob P. <rob...@gm...>]

Hi All,

I was wondering if anyone might be able to provide me with a short
comparison between JGraphT and JUNG.
What are the primary differences between these two libraries?  How do they
compare in terms of features and performance?
How do they compare in terms of API and ease-of-use?

Thanks,
Rob

Re: [jgrapht-users] Bug in the induced subgraphs? (+Patch and JUnit test)

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

+jgrapht-users

Thanks a lot for the clear explanation and unit test; I'm going to
commit your fix to svn.  It turned out not to be necessary to add the
parentSubgraph data member because BaseGraphListener is already a
non-static inner class.

JVS

On Wed, Sep 29, 2010 at 12:13 PM, Michele Mancioppi
<mic...@gm...> wrote:
> Dear John,
>
> I think I have stepped into a bug affecting induced subgraphs in jGraphT.
>
> The problem is the following: I create a listenable graph, and then an induced subgraph based on it (by passing a set of vertexes and null set of edges to the subgraph's constructor). If I add an edge to the base graph and not both its vertexes also in the subgraph, the BaseListenerGraph of attached by the subgraph to the base graph generates an IllegalArgumentException because of the failures in one of the invocations of 'assertVertexExists' in the method .
>
> I believe it is a bug. An induced subgraph should always contain all and only the edges of the base graph whose source and target are both in the subgraph. Attached you find a patch that solves the problem and a JUnit test case for regression testing. Unfortunately I did not have the opportunity of running the JUnit tests, but it is a pretty straightforward modification. I did not change the serialVersionUID of the class Subgraph as I don't know what is your policy about it.
>
> Of course, the code submitted in the attached patch and the JUnit test case are licensed under the LGPL, so feel free to apply it to the the jGraphT codebase :-)
>
> Cheers,
> Michele Mancioppi
>

[jgrapht-users] Memory on Centrality

[Jeff G <jef...@gm...>]

I ran into a memory issue when trying to calculate betweenness centrality on
my graphs.  I'm using a simple graph - is there a better way for efficient
memory usage?  I was using JUNG and it worked fine for computing centrality,
using an UndirectedSparseGraph().  Is there an equivalent in jGraphT that I
should be using so I don't run out of memory?

Thanks,
Jeff

Re: [jgrapht-users] Official model representing the JGraphT structure?

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

Hi,

I join in "from.pampas" to ask if there is an official UML model for JgraphT
?

Thanks

Éric
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Official-model-representing-the-JGraphT-structure-tp994048p1395271.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Count Bridges

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

Hi,

finding the bridges in a graph is quite simple:

- variable a = finding the number of connected sets in the initial graph
- clone the graph

for all edges
 remove edge in the clone
 variable b = finding the number of connected sets in the modifed cloned
graph
 if the number of connected sets is b == a+1
  this edge is a bridge

Time complexity for this algorithm is O(V+E) for the connectivity inspector
and the loop aboce in O(E).
If V <<< E, the total time complexity is : O(E²).

Hope it help,
Regards,

Éric
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Count-Bridges-tp1309515p1395252.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Count Bridges

[ahmed a. <alg...@gm...>]

Hi,

 I need to know if there is a JGraphT algorithm for finding the number of
bridges (cut-edges) of a graph.

Thanks!

--
Ahmed

Re: [jgrapht-users] Max limit of vertices

[Lmhelp <lea...@ig...>]

Hi,

I have been working with Eric and we are sorry but the problem
("StringIndexOutOfBoundsException") wasn't coming from "JGraphT", 
we were trying to extract a sub-string from a string using bad indexes
(like -1...)

We are still trying to build our *huge* graph, we may come back soon :).

See you and, again, we are sorry for the disturbance.

All the best,
--
Léa and Eric



-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Max-limit-of-vertices-tp1194057p1208448.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Max limit of vertices

[Eric M. <eri...@gm...>]

Hi,

We have created a graph which vertices are "String"s
and edges are (String, String) couples.
When we observe the "LinkedHashMap" the keys
are the strings above.

The graph we want to create from a XML file

contains approximately 2,000,000 vertices
and 44,000,000 edges.

When we execute our program, we get the following exception:
--------------------------------------------------------------------------------------------------------------------------------

java.lang.StringIndexOutOfBoundsException: String index out of range: -13
--------------------------------------------------------------------------------------------------------------------------------
after creating  1,034,982  vertices and 2,344,767 edges.

We are wondering if there is a limit in the number of vertices and edges
"JGraphT" can support...
or maybe... the keys in the "LinkedHashMap" cannot be larger than a certain
limit.


Can you help?

Sincerely,

Éric

[jgrapht-users] Max limit of vertices

[Eric M. <eri...@ig...>]

Hi,

We have created a graph which vertices are "String"s
and edges are (String, String) couples.
When we observe the "LinkedHashMap" the keys
are the strings above.

The graph we want to create from a XML file
contains approximately 2,000,000 vertices
and 44,000,000 edges.

When we execute our program, we get the following exception:
--------------------------------------------------------------------------------------------------------------------------------
java.lang.StringIndexOutOfBoundsException: String index out of range: -13
--------------------------------------------------------------------------------------------------------------------------------
after creating  1,034,982  vertices and 2,344,767 edges.

We are wondering if there is a limit in the number of vertices and edges
"JGraphT" can support...
or maybe... the keys in the "LinkedHashMap" cannot be larger than a certain
limit.

Can you help?

Sincerely,

[jgrapht-users] ER Graph

[Muhammad J. <mj...@co...>]

Hi,

Can i create a graph like this ER Diagram given below in link

http://www.graphviz.org/Gallery/undirected/ER.html


having ellipse and rectangle shapes.....Rectangle representing* Graph
Nodes*and Ellipse representing
*Attribute Nodes*.


thanks for your help in advance.


-- 
Regards
________________________________________
Muhammad Javed
Centre for Next Generation Localisation (CNGL)
School of Computing,
Dublin City University, Ireland
ph. # : + 353 - 1 700 6912
web: www.computing.dcu.ie/~mjaved

[jgrapht-users] removeEdge null pointer exception (JGraphT w/ JGraph)

[Haoqi Z. <hq...@ee...>]

Hi there,

I am starting to use JGraph (v5) and JGraphT for a graph applet and in particular would like to allow a user 
to click on an edge to remove it. The problem I am encountering is that when I call removeEdge when 
the click event is triggered, it removes the edge, but then throws a null pointer exception in one of the edge listeners. 
This only happens if I am removing the edge that is being clicked on -- if I remove a different edge there is 
no problem. The removeEdge call is wrapped within a SwingUtilities.InvokeLater, but to no avail.

My code looks something like this:

[within the marqueeEvent handler's mouse press event]
...
DefaultEdge e = (DefaultEdge)jgraphAdapter.getValue(cell);
  SwingUtilities.invokeLater(new Runnable(){
   public void run(){
		graph.removeEdge(e);
   }
  });

If you have encountered this issue before, know of a fix, or have ideas on this, please let me know. Thanks!

Best,
Haoqi

[jgrapht-users] New Member

[Muhammad J. <mj...@co...>]

Hi ya,

I am new to this member,
I was just running the demo samples,  I wonder if

1-  I can label the edges.
2-  I can present Attributed Typed Graph with it. i.e adding attributes to
the vertex and edges.

your help will be appreciated.

Regards
________________________________________
Muhammad Javed
Centre for Next Generation Localisation (CNGL)
School of Computing,
Dublin City University, Ireland
ph. # : + 353 - 1 700 6912
web: www.computing.dcu.ie/~mjaved

[jgrapht-users] Colors implementation

[jwala <jwa...@ya...>]

Hi friends,

may i know how to implement different colors to different nodes by using
jgrapht.

Thanks in advance.
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Colors-implementation-tp997893p997893.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] finding all paths from one vertex to another

[DanielAgota <ago...@gm...>]

Hi,

do you need the exact paths?
You could rewrite/extend the BreadhtFirstIterator for instance... take a
look at the encounterVertex/encounterVertexAgain methods.

I have used/extended the methods above to count the number of shortest paths
between one StartVertex and all the others and get their distances from the
start vertex - the length of the shortest path.

You could also use the FloydWarhallShortestPaths (check spelling) class, if
you know the maximal number of paths you are interested in.

Or combine the two, to find the number of shortest paths and list them :)
... it definitely won't scale very good...

Regards, Daniel
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/finding-all-paths-from-one-vertex-to-another-tp108000p995888.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] finding all paths from one vertex to another

[from.pampas <mar...@gm...>]

I've found an interesting paper with a very easy algorithm to explore all
possible paths...
"APAC: An exact algorithm for retrieving cycles and paths in all kind of
graphs by Ricardo Simoes (2009)"
As is very easy to understand, it's easy to adapt as well. 
Hoping to be useful to someone

from.pampas
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/finding-all-paths-from-one-vertex-to-another-tp108000p994056.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] All paths

[from.pampas <mar...@gm...>]

I've found an interesting paper with a very easy algorithm to explore all
possible paths...
"APAC: An exact algorithm for retrieving cycles and paths in all kind of
graphs by Ricardo Simoes (2009)"
As is very easy to understand, it's easy to adapt as well. 
Hoping to be useful to someone

from.pampas
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/All-paths-tp697544p994055.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] all possible paths

[from.pampas <mar...@gm...>]

I've found an interesting paper with a very easy algorithm to explore all
possible paths...
"APAC: An exact algorithm for retrieving cycles and paths in all kind of
graphs by Ricardo Simoes (2009)"
As is very easy to understand, it's easy to adapt as well. 
Hoping to be useful to someone

from.pampas
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/all-possible-paths-tp690063p994053.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Ecore

[from.pampas <mar...@gm...>]

Is there any ecore file representing the JGraphT model?
Thanks
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Ecore-tp994048p994048.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] EdgeReversedGraph does not modify edgeSet.

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

Luis Pureza wrote:
> Hi,
> 
> I have been using JGraphT for some graph related activities and I love 
> it. Nonetheless, I seem to have found an inconsistency.
> 
> When I create an EdgeReversedGraph, the edgeSet() is not reversed. Is 
> this a bug? Would you like me to cook up a patch?

Do you mean you are expecting that when you iterate edgeSet, the edges 
will be E3 E2 E1 if they were E1 E2 E3 in the original graph?  That's 
not a bug; this class only reverses the direction of the edges (not 
their order in the set).

> Also, while I'm at it... I need to be able to tell if two graphs are 
> equal. Is it enough to compare the vertexSet()s and the edgeSet()s of 
> both graphs? If you'd like, I can submit a patch that implements 
> equals() and hashCode() for graphs.

By equal, do you mean isomorphic?  That is the main comparison of 
interest for graphs, but there is no known polynomial-time algorithm for 
it.  We have a brute-force implementation in the experimental package.

JVS

[jgrapht-users] JGraphModelAdapter - Layuot problem

[Daniel A. <ago...@gm...>]

Dear All,

I'm experimenting with JGrapht and JGraph5 and have issues with the Layout
demos included in the JGraph 5 package.

(com.jgraph.layout.demo.JGraphLayoutDemo)

I replaced the JGraph instance with a preaviosly tested working
JGraphModelAdapter example and get the following Exception:

Exception in thread "AWT-EventQueue-0" java.lang.NoSuchMethodError:
org.jgraph.graph.VertexView.update(Lorg/jgraph/graph/GraphLayoutCache;)V
    at
com.jgraph.layout.demo.JGraphLayoutMorphingManager.setCellBounds(JGraphLayoutMorphingManager.java:272)
    at
com.jgraph.layout.demo.JGraphLayoutMorphingManager.updateCell(JGraphLayoutMorphingManager.java:253)
    at
com.jgraph.layout.demo.JGraphLayoutMorphingManager.actionPerformed(JGraphLayoutMorphingManager.java:200)
    at javax.swing.Timer.fireActionPerformed(Unknown Source)
    at javax.swing.Timer$DoPostEvent.run(Unknown Source)
    at java.awt.event.InvocationEvent.dispatch(Unknown Source)
    at java.awt.EventQueue.dispatchEvent(Unknown Source)
    at java.awt.EventDispatchThread.pumpOneEventForFilters(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForFilter(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.run(Unknown Source)

at the following section of JGraphLayoutMorphing class in the same demo
package:

protected void setCellBounds(Object cell, Rectangle2D bounds) {
        Rectangle2D rect = graph.getCellBounds(cell);
        if (rect != null && bounds != null) {
            rect.setFrame(bounds.getX(), bounds.getY(), bounds.getWidth(),
                    bounds.getHeight());
            CellView view = graph.getGraphLayoutCache().getMapping(cell,
false);
            if (view != null)
                view.update(graph.getGraphLayoutCache());// Exception is
trhrown...
        }
    }

I'm not sure wether this is a JGrapht or JGraph related issue any help
apriciated.

Regards, Daniel

[jgrapht-users] EdgeReversedGraph does not modify edgeSet.

[Luis P. <pu...@gm...>]

Hi,

I have been using JGraphT for some graph related activities and I love it.
Nonetheless, I seem to have found an inconsistency.

When I create an EdgeReversedGraph, the edgeSet() is not reversed. Is this a
bug? Would you like me to cook up a patch?

Also, while I'm at it... I need to be able to tell if two graphs are equal.
Is it enough to compare the vertexSet()s and the edgeSet()s of both graphs?
If you'd like, I can submit a patch that implements equals() and hashCode()
for graphs.

Thanks!

Luís Pureza

Re: [jgrapht-users] all possible paths

[from.pampas <mar...@gm...>]

I would like to know the same.
I am a beginner with JGraphT...
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/all-possible-paths-tp690063p976533.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] All paths

[from.pampas <mar...@gm...>]

I want the same, any advise for that?
thanks
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/All-paths-tp697544p976526.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] All paths

[from.pampas <mar...@gm...>]

I want the same, any advise for that?
thanks
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/All-paths-tp697544p976524.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] finding all paths from one vertex to another

[from.pampas <mar...@gm...>]

Guille, did you find the way? do you have any advise to start with the same
issue that you have?
Thanks
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/finding-all-paths-from-one-vertex-to-another-tp108000p976521.html
Sent from the jgrapht-users mailing list archive at Nabble.com.