jgrapht-users — JGraphT user list.

Re: [jgrapht-users] Connectivity of Directed Graphs

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

Hi Ulrich,

can't you use the BreadthFirstIterator or the DepthFirstIterator? I'd think either should do what you want.

Regards,
   Ernst

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

----- Reply message -----
From: "Wielant, Ulrich" <U.W...@ge...>
To: "'jgr...@li...'" <jgr...@li...>
Subject: [jgrapht-users] Connectivity of Directed Graphs
Date: Tue, Aug 30, 2011 11:11


Hello everyone,

first of all a big congratulation for maintaining this great framework. I am using it since 4 years and I am still happy with it :-)

Now my question:

I am using a DirectedGraph and I want to get a list of vertices that are reachable from a given vertex with respect to the directions. The ConnectivityInspector does not care about the edge directions whereas the StrongConnectivityInspector only uses strong (so double directed) connections.
Any hints how I can achieve the list of reachable nodes?

Example:

  A <--> B <-- C

reachable(A) => [B]
reachable(B) => [A]
reachable(C) => [A,B]

Thanks!
Uli

www.gematronik.com
www.selex-si.de

Selex Systems Integration GmbH
Sitz der Gesellschaft / Registered Office: Neuss
Registergericht / Register Court: Neuss HR B 1242
Gesch?ftsf?hrer / Managing Director: Ulrich Nellen

------------------------------------------------------------------------------
Special Offer -- Download ArcSight Logger for FREE!
Finally, a world-class log management solution at an even better 
price-free! And you'll get a free "Love Thy Logs" t-shirt when you
download Logger. Secure your free ArcSight Logger TODAY!
http://p.sf.net/sfu/arcsisghtdev2dev
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Connectivity of Directed Graphs

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

Is the function neighborListOf(Graph<V,E> g, V vertex) defined in the
class Graphs the thing you are looking for?

br,

Joris

On Tue, Aug 30, 2011 at 11:11 AM, Wielant, Ulrich
<U.W...@ge...> wrote:
> Hello everyone,
>
> first of all a big congratulation for maintaining this great framework. I am using it since 4 years and I am still happy with it :-)
>
> Now my question:
>
> I am using a DirectedGraph and I want to get a list of vertices that are reachable from a given vertex with respect to the directions. The ConnectivityInspector does not care about the edge directions whereas the StrongConnectivityInspector only uses strong (so double directed) connections.
> Any hints how I can achieve the list of reachable nodes?
>
> Example:
>
>  A <--> B <-- C
>
> reachable(A) => [B]
> reachable(B) => [A]
> reachable(C) => [A,B]
>
> Thanks!
> Uli
>
> www.gematronik.com
> www.selex-si.de
>
> Selex Systems Integration GmbH
> Sitz der Gesellschaft / Registered Office: Neuss
> Registergericht / Register Court: Neuss HR B 1242
> Gesch?ftsf?hrer / Managing Director: Ulrich Nellen
>
> ------------------------------------------------------------------------------
> Special Offer -- Download ArcSight Logger for FREE!
> Finally, a world-class log management solution at an even better
> price-free! And you'll get a free "Love Thy Logs" t-shirt when you
> download Logger. Secure your free ArcSight Logger TODAY!
> http://p.sf.net/sfu/arcsisghtdev2dev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Connectivity of Directed Graphs

[Wielant, U. <U.W...@ge...>]

Hello everyone,

first of all a big congratulation for maintaining this great framework. I am using it since 4 years and I am still happy with it :-)

Now my question:

I am using a DirectedGraph and I want to get a list of vertices that are reachable from a given vertex with respect to the directions. The ConnectivityInspector does not care about the edge directions whereas the StrongConnectivityInspector only uses strong (so double directed) connections.
Any hints how I can achieve the list of reachable nodes?

Example:

  A <--> B <-- C

reachable(A) => [B]
reachable(B) => [A]
reachable(C) => [A,B]

Thanks!
Uli

www.gematronik.com
www.selex-si.de

Selex Systems Integration GmbH
Sitz der Gesellschaft / Registered Office: Neuss
Registergericht / Register Court: Neuss HR B 1242
Gesch?ftsf?hrer / Managing Director: Ulrich Nellen

Re: [jgrapht-users] shortest path - getting all vertices, not just edges

[Sophia <sop...@ya...>]

Thank you very much! This is precisely a function I've been looking for.

Kind regards,
Sophia

--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/shortest-path-getting-all-vertices-not-just-edges-tp3278241p3280521.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] shortest path - getting all vertices, not just edges

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

Dear Sophia,

I'm not absolutely certain I understood your problem, but I think you're having problems with g.getEdgeTarget(e3) returning c, whereas you would like to receive b, is that correct?

In that case Graphs.getOppositeVertex(g, e3, c) might be what you're looking for. It can be used to conveniently cycle through a path:

src = c;
for (E e : edgelist_starting_at_c) {
   println(src); 
   println(e);
   src = Graphs.getOppositeVertex(g, e, src) ;
}

Hope this helps,
   Ernst de Ridder

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

----- Reply message -----
From: "Sophia Katrenko" <sop...@ya...>
To: <jgr...@li...>
Subject: [jgrapht-users] shortest path - getting all vertices, not just edges
Date: Tue, Aug 23, 2011 16:55
In short, I have an undirected graph and use the Dijsktra method to find the shortest path between two vertices. I'd like to output not only edges, but also traverse all the vertices on the way. Since I only get edges by using both DijkstraShortestPath.findPathBetween() and DijkstraShortestPath.getPath(), I do iterate over all edges in the path and, for each edge 'e', I output vertices using the getEdgeTarget(e). It does work well, however in the cases like below, it doesn't work even though a graph is undirected:
e1(a, d)e2(a, b)e3(b, c)
path between
'c' and 'd' is [e3, e2, e1] or [e3, b, e2, a, e1, d]
However, I cannot get the last solution because I use getEdgeTarget, so I have to do some extra checks in the code to arrive at this path.

[jgrapht-users] shortest path - getting all vertices, not just edges

[Sophia K. <sop...@ya...>]

Dear All,
It's a totally newbie question, and I must have overlooked something (so I apologize in advance). I couldn't find an elegant solution and had to implement it in an ugly way which I would like to change.
In short, I have an undirected graph and use the Dijsktra method to find the shortest path between two vertices. I'd like to output not only edges, but also traverse all the vertices on the way. Since I only get edges by using both DijkstraShortestPath.findPathBetween() and DijkstraShortestPath.getPath(), I do iterate over all edges in the path and, for each edge 'e', I output vertices using the getEdgeTarget(e). It does work well, however in the cases like below, it doesn't work even though a graph is undirected:
e1(a, d)e2(a, b)e3(b, c)
path between 'c' and 'd' is [e3, e2, e1] or [e3, b, e2, a, e1, d]
However, I cannot get the last solution because I use getEdgeTarget, so I have to do some extra checks in the code to arrive at this path. 
Could you please suggest a better solution for this? I would really prefer to do it right away using the instance of DijkstraShortestPath.
Thanks in advance!
Best,Sophia
 

Re: [jgrapht-users] bug in graph?

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

http://pub.eigenbase.org/wiki/JGraphT:EqualsAndHashCode

On Thu, Aug 11, 2011 at 2:22 PM, Bagwell, Allen F <af...@sa...> wrote:
> I believe I’ve found a bug. I get the IllegalArgumentException whether I
> invoke outgoingEdgesOf(vertex) or incomingEdgesOf(vertex). And this only
> happens after I modify a simple field in my vertex object.
>
> If rn == TESTNODE evaluates to true after modifying the node’s string field,
> then the offending method should not be throwing an exception saying the
> vertex isn’t in the graph.
>
> -Allen
>
>
> SimpleDirectedWeightedGraph<RiskNode, DefaultWeightedEdge> graph = new
> SimpleDirectedWeightedGraph<RiskNode,
> DefaultWeightedEdge>(DefaultWeightedEdge.class);
> RiskNode TESTNODE = new RiskNode("TEST","");
> if (!graph.addVertex(TESTNODE))
> fail("Didn't add TEST node.");
>
> for (RiskNode rn : graph.vertexSet()) {
> if (rn.equals(TESTNODE))
> System.out.println("#1: found it");
> if (rn == TESTNODE)
> System.out.println("#1: they are the same object");
> else
> System.out.println("#1: they are different objects");
> }
>
> System.out.println("Number of outgoing edges = " +
> graph.outgoingEdgesOf(TESTNODE).size());
>
> TESTNODE.setDescription("adding a description...");
>
> for (RiskNode rn : graph.vertexSet()) {
> if (rn.equals(TESTNODE))
> System.out.println("#2: found it");
> if (rn == TESTNODE)
> System.out.println("#2: they are the same object");
> else
> System.out.println("#2: they are different objects");
> }
>
> System.out.println("Number of outgoing edges = " +
> graph.outgoingEdgesOf(TESTNODE).size());
>
> ----- Output from running code:
>
> #1: found it
> #1: they are the same object
> Number of outgoing edges = 0
> #2: found it
> #2: they are the same object
>
> java.lang.IllegalArgumentException: no such vertex in graph
>         at org.jgrapht.graph.AbstractGraph.assertVertexExist(Unknown Source)
>         at
> org.jgrapht.graph.AbstractBaseGraph$DirectedSpecifics.getEdgeContainer(Unknown
> Source)
>         at
> org.jgrapht.graph.AbstractBaseGraph$DirectedSpecifics.outgoingEdgesOf(Unknown
> Source)
>         at org.jgrapht.graph.AbstractBaseGraph.outgoingEdgesOf(Unknown
> Source)
>         at
> gov.sandia.analysis.TestRiskAnalysis.testChangeVertex(TestRiskAnalysis.java:385)
>         at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
>         at
> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>         at
> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>         at java.lang.reflect.Method.invoke(Method.java:597)
>         at
> org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:44)
>         at
> org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:15)
>         at
> org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:41)
>         at
> org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:20)
>         at
> org.junit.runners.BlockJUnit4ClassRunner.runNotIgnored(BlockJUnit4ClassRunner.java:79)
>         at
> org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:71)
>         at
> org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:49)
>         at org.junit.runners.ParentRunner$3.run(ParentRunner.java:193)
>         at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:52)
>         at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:191)
>         at org.junit.runners.ParentRunner.access$000(ParentRunner.java:42)
>         at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:184)
>         at
> org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:28)
>         at org.junit.runners.ParentRunner.run(ParentRunner.java:236)
>         at
> org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:46)
>         at
> org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
>         at
> org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467)
>         at
> org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683)
>         at
> org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390)
>         at
> org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)
>
>
> -------------------------------------------------------
> Allen F. Bagwell
> Sandia National Laboratories - CA
> Systems Modeling & Software Engineering, Org. 8116
> af...@sa...
> TEL: (925) 294.4756
> FAX: (925) 294.3870
>
>
>
> ------------------------------------------------------------------------------
> Get a FREE DOWNLOAD! and learn more about uberSVN rich system,
> user administration capabilities and model configuration. Take
> the hassle out of deploying and managing Subversion and the
> tools developers use with it.
> http://p.sf.net/sfu/wandisco-dev2dev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] bug in graph?

[Bagwell, A. F <af...@sa...>]

I believe I've found a bug. I get the IllegalArgumentException whether I invoke outgoingEdgesOf(vertex) or incomingEdgesOf(vertex). And this only happens after I modify a simple field in my vertex object.

If rn == TESTNODE evaluates to true after modifying the node's string field, then the offending method should not be throwing an exception saying the vertex isn't in the graph.

-Allen


SimpleDirectedWeightedGraph<RiskNode, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<RiskNode, DefaultWeightedEdge>(DefaultWeightedEdge.class);
RiskNode TESTNODE = new RiskNode("TEST","");
if (!graph.addVertex(TESTNODE))
fail("Didn't add TEST node.");

for (RiskNode rn : graph.vertexSet()) {
      if (rn.equals(TESTNODE))
      System.out.println("#1: found it");
      if (rn == TESTNODE)
      System.out.println("#1: they are the same object");
else
      System.out.println("#1: they are different objects");
}

System.out.println("Number of outgoing edges = " + graph.outgoingEdgesOf(TESTNODE).size());

TESTNODE.setDescription("adding a description...");

for (RiskNode rn : graph.vertexSet()) {
if (rn.equals(TESTNODE))
      System.out.println("#2: found it");
if (rn == TESTNODE)
      System.out.println("#2: they are the same object");
else
      System.out.println("#2: they are different objects");
}

System.out.println("Number of outgoing edges = " + graph.outgoingEdgesOf(TESTNODE).size());

----- Output from running code:

#1: found it
#1: they are the same object
Number of outgoing edges = 0
#2: found it
#2: they are the same object

java.lang.IllegalArgumentException: no such vertex in graph
        at org.jgrapht.graph.AbstractGraph.assertVertexExist(Unknown Source)
        at org.jgrapht.graph.AbstractBaseGraph$DirectedSpecifics.getEdgeContainer(Unknown Source)
        at org.jgrapht.graph.AbstractBaseGraph$DirectedSpecifics.outgoingEdgesOf(Unknown Source)
        at org.jgrapht.graph.AbstractBaseGraph.outgoingEdgesOf(Unknown Source)
        at gov.sandia.analysis.TestRiskAnalysis.testChangeVertex(TestRiskAnalysis.java:385)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:44)
        at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:15)
        at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:41)
        at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:20)
        at org.junit.runners.BlockJUnit4ClassRunner.runNotIgnored(BlockJUnit4ClassRunner.java:79)
        at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:71)
        at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:49)
        at org.junit.runners.ParentRunner$3.run(ParentRunner.java:193)
        at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:52)
        at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:191)
        at org.junit.runners.ParentRunner.access$000(ParentRunner.java:42)
        at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:184)
        at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:28)
        at org.junit.runners.ParentRunner.run(ParentRunner.java:236)
        at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:46)
        at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
        at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467)
        at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683)
        at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390)
        at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)


-------------------------------------------------------
Allen F. Bagwell
Sandia National Laboratories - CA
Systems Modeling & Software Engineering, Org. 8116
af...@sa...<mailto:af...@sa...>
TEL: (925) 294.4756
FAX: (925) 294.3870

Re: [jgrapht-users] cycles in an undirected graph

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

Hm, as Ethan pointed out correctly you were asking for *all* cycles in
a graph. I should read more carefully! In that case, the problem is of
a completely different level and you won't be able to solve it with a
simple Depth first search as it is indeed an NP-complete problem. You
might want to check this article http://dx.doi.org/10.1137/0205007
from SIAM (you probably need university credentials to log in to that
website). At least jgraph hasnt any method to find *all*  cycles in a
graph (feel free to add such a method though :) ).

Perhaps this discussion is usefull:
http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph

You might want to reconsider whether you really need to find *all*
cycles in a graph for your problem. Perhaps some less heavy approach
would be sufficient? Maybe you could find *a* cycle and remove one
edge such thereby breaking the cycle and repeat until you cannot find
cycles anymore (and possibly end up with a disconnected graph). I
haven't tested this nor seen this so I have no clue how well this
works . It probably will give you a lower bound on the number of
cycles.

br,

Joris

On Wed, Aug 3, 2011 at 11:03 AM, azzam <ma...@cs...> wrote:
> Dear Joris,
> Thanks a lot about your reply
> Actually, I tried Googling how to find all cycles in  graph (undirected),
> but I wondered if the jgraph package includes an implementation for this
> method. I think that there is such method for the directed graph. From your
> answer, I realized that there is no implementation for the undirected
> graph.
> I will read the attached link, and try to implement the method alone. From
> your answer, I think that this is not so difficult. :)
> Azzam
>
>
> On Wed, Aug 3, 2011 at 10:47 AM, Joris Kinable <de...@gm...> wrote:
>>
>> Have you actually tried Googling how to find a cycles in a graph...
>> this usually helps a lot ;).
>>
>> Quick answer: run a depth first search on your node. (A depth first
>> search algorithm is included in the jgraph package). If the depth
>> first search algorithm re-encounters a node, then you know that there
>> is a cycle. Check for example these slides :
>> www.cs.sunysb.edu/~algorith/video-lectures/2007/lecture12.pdf
>>
>> br,
>>
>> Joris
>>
>> On Tue, Aug 2, 2011 at 6:17 PM, zara75 <con...@gm...> wrote:
>> > I need to find all cycles in an undirected graph, and all cycles passing
>> > from
>> > a given node /e/, also in  an
>> > undirected graph.
>> >
>> > I would appreciate any help
>> >
>> >
>> > A.
>> >
>> >
>> > --
>> > View this message in context:
>> > http://jgrapht-users.107614.n3.nabble.com/cycles-in-an-undirected-graph-tp3219434p3219434.html
>> > Sent from the jgrapht-users mailing list archive at Nabble.com.
>> >
>> >
>> > ------------------------------------------------------------------------------
>> > BlackBerry&reg; DevCon Americas, Oct. 18-20, San Francisco, CA
>> > The must-attend event for mobile developers. Connect with experts.
>> > Get tools for creating Super Apps. See the latest technologies.
>> > Sessions, hands-on labs, demos & much more. Register early & save!
>> > http://p.sf.net/sfu/rim-blackberry-1
>> > _______________________________________________
>> > jgrapht-users mailing list
>> > jgr...@li...
>> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>> >
>
>
>
> --
> Azzam Maraee
> Department of Computer Science
> Ben-Gurion University
> ISRAEL
> ma...@cs...
> 972-8-6428044 (o)
>

Re: [jgrapht-users] cycles in an undirected graph

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

Have you actually tried Googling how to find a cycles in a graph...
this usually helps a lot ;).

Quick answer: run a depth first search on your node. (A depth first
search algorithm is included in the jgraph package). If the depth
first search algorithm re-encounters a node, then you know that there
is a cycle. Check for example these slides :
www.cs.sunysb.edu/~algorith/video-lectures/2007/lecture12.pdf

br,

Joris

On Tue, Aug 2, 2011 at 6:17 PM, zara75 <con...@gm...> wrote:
> I need to find all cycles in an undirected graph, and all cycles passing from
> a given node /e/, also in  an
> undirected graph.
>
> I would appreciate any help
>
>
> A.
>
>
> --
> View this message in context: http://jgrapht-users.107614.n3.nabble.com/cycles-in-an-undirected-graph-tp3219434p3219434.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
> ------------------------------------------------------------------------------
> BlackBerry&reg; DevCon Americas, Oct. 18-20, San Francisco, CA
> The must-attend event for mobile developers. Connect with experts.
> Get tools for creating Super Apps. See the latest technologies.
> Sessions, hands-on labs, demos & much more. Register early & save!
> http://p.sf.net/sfu/rim-blackberry-1
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] cycles in an undirected graph

[zara75 <con...@gm...>]

I need to find all cycles in an undirected graph, and all cycles passing from
a given node /e/, also in  an 
undirected graph.

I would appreciate any help


A.


--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/cycles-in-an-undirected-graph-tp3219434p3219434.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

[jgrapht-users] Help compare graph structure

[Syed Z. <zee...@gm...>]

Hi Guys,

 

I want to use jgrapht to compare structure of two graphs ( ignoring labels,
need to compare only structure ),generate similarity score such as edit
distance.

Is this possible using jgrapht? Is there any function which can actually
calculate edit distance.

 

I am doing this as part of a research project to compare two schemas. I need
to compare structure of  tables (relations) represented as graphs.

 

Please help or suggest a more suitable java api.

 

Thanks and Regards,

Syed Zeeshanuddin

University of Manchester

[jgrapht-users] Re : Cycles in graph

[aravindh r. <coo...@gm...>]

Hello

I am having a Graph That contain cycle Let the graph be simple like

a->b->c->d->e
     b<-m<-d

i.e, b->c->d->m->b is a cycle...
I detected that using CycleDetector and made is as a SubGraph(SG)..

Now when I try to manipulate the graph again,Its showing  only edges as

[(a,b), (m,b), (b,c), (c,d), (d,e), (d,m)]

I want to make it as [(a,SG),(SG,e)]...So that SG becomes like a node of the
graph..

pls let me know if it possible with JGraphT..?
Also

When there are more than one loop I want each of then to be a subGraph.To my
knowledge Cycle detector finds all the cycles as a single list which is
difficult to make two subgraphs..
For example,

a->b->c->d->e->f->g
     b<-m<-d
                   e<-f
The cycles are b->c->d->m->b and e->f->e
The edges Cycle Detector detects is

[{m,b}, {b,c}, {c,d}, {d,e}, {d,m}, {f,e}, {e,f}]

But i want it as
[{m,b}, {b,c}, {c,d}, {d,e}, {d,m}]         [{f,e}, {e,f}]
So that I can make two subgraphs SG1 and SG2 there by making the graph
a->SG1->SG2->g...

 Pls help me by providing a solution to it..

Regards

Aravindh R
Research Intern
TIFR,Mumbai

Re: [jgrapht-users] Impossible to set source and target of DefaultEdge

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

It's a default edge implementation meant as a companion to the
out-of-the-box graph implementations.  It's rare to need to write your
own graph implementation from scratch (rather than extending or
decorating one of the out-of-the-box ones), but if you do, then
providing your own edge implementation is going to be the least of
your concerns.

JVS

On Mon, Jul 11, 2011 at 10:43 AM, Anant Rathi <ar...@21...> wrote:
> Hey Rob,
>
>
>
> Thanks for your response. I understand that EdgeFactories are much preferred
> to constructors and that graphs are used to query source and target, but in
> the case of DefaultEdge, I don’t see how it’s possible for the system to
> work.
>
>
>
> A factory that constructs DefaultEdges cannot set their source and target.
> And calling getEdgeSource() or getEdgeTarget() on a
> Graph<whatever,DefaultEdge> is essentially meaningless since every pair of
> DefaultEdges in the graph are equal().
>
>
>
> I’ve investigated the source code a bit further, and DefaultEdge extends
> IntrusiveEdge, which has the source and target members’ scope as
> package-private. So graph implementations provided by JGraphT itself
> (DefaultDirectedGraph, etc.) can (and do) set the source and target of
> DefaultEdges , and therefore can (and do) correctly implement
> getEdgeSource() and getEdgeTarget(). But for the rest of us, I think it’s
> impossible to guarantee correctness of these two methods when Defaultedge is
> the edge type.
>
>
>
> Anant
>
>
>
> From: Rob Patro [mailto:rob...@gm...]
> Sent: Monday, July 11, 2011 12:07 PM
> To: jgr...@li...
> Subject: Re: [jgrapht-users] Impossible to set source and target of
> DefaultEdge
>
>
>
> Hi Anant,
>
>   JGraphT is a very well designed library, but takes some getting used to at
> first.  Edges are created using the EdgeFactors; raw Edges are not
> constructed.  Then the src and target are queried via the graph in which the
> edge exists.
>
> --Rob
>
> On Jul 11, 2011 11:59 AM, "Anant Rathi" <ar...@21...> wrote:
>> All,
>>
>> org.jgrapht.graph.DefaultEdge has protected getSource() and getTarget()
>> methods, but there aren't setters for source and target or a constructor
>> that sets them. Whether you are instantiating or extending DefaultEdge, the
>> source and target members can't be modified, and they're always null. That
>> doesn't seem right.
>>
>> Am I missing something?
>>
>> Anant Rathi
>> Research Intern
>> 21st Century Technologies, Inc.
>> 6011 W. courtyard Drive
>> Building 5, Suite 300
>> Austin, TX 78730
>>
>> Phone: 512 682 4707
>> Email: ar...@21...
>> URL: http://www.21technologies.com
>>
>> The information in this email and in any attachments is confidential and
>> may be privileged. If you are not the intended recipient, please destroy
>> this message, delete any copies held on your systems and notify the sender
>> immediately. You should not retain, copy or use this email for any purpose,
>> nor disclose all or any part of its content to any other pserson.
>>
>
>
>
> ------------------------------------------------------------------------------
> All of the data generated in your IT infrastructure is seriously valuable.
> Why? It contains a definitive record of application performance, security
> threats, fraudulent activity, and more. Splunk takes this data and makes
> sense of it. IT sense. And common sense.
> http://p.sf.net/sfu/splunk-d2d-c2
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

Re: [jgrapht-users] Impossible to set source and target of DefaultEdge

[Anant R. <ar...@21...>]

Hey Rob,

Thanks for your response. I understand that EdgeFactories are much preferred to constructors and that graphs are used to query source and target, but in the case of DefaultEdge, I don't see how it's possible for the system to work.

A factory that constructs DefaultEdges cannot set their source and target. And calling getEdgeSource() or getEdgeTarget() on a Graph<whatever,DefaultEdge> is essentially meaningless since every pair of DefaultEdges in the graph are equal().

I've investigated the source code a bit further, and DefaultEdge extends IntrusiveEdge, which has the source and target members' scope as package-private. So graph implementations provided by JGraphT itself (DefaultDirectedGraph, etc.) can (and do) set the source and target of DefaultEdges , and therefore can (and do) correctly implement getEdgeSource() and getEdgeTarget(). But for the rest of us, I think it's impossible to guarantee correctness of these two methods when Defaultedge is the edge type.

Anant

From: Rob Patro [mailto:rob...@gm...]
Sent: Monday, July 11, 2011 12:07 PM
To: jgr...@li...
Subject: Re: [jgrapht-users] Impossible to set source and target of DefaultEdge


Hi Anant,

  JGraphT is a very well designed library, but takes some getting used to at first.  Edges are created using the EdgeFactors; raw Edges are not constructed.  Then the src and target are queried via the graph in which the edge exists.

--Rob
On Jul 11, 2011 11:59 AM, "Anant Rathi" <ar...@21...<mailto:ar...@21...>> wrote:
> All,
>
> org.jgrapht.graph.DefaultEdge has protected getSource() and getTarget() methods, but there aren't setters for source and target or a constructor that sets them. Whether you are instantiating or extending DefaultEdge, the source and target members can't be modified, and they're always null. That doesn't seem right.
>
> Am I missing something?
>
> Anant Rathi
> Research Intern
> 21st Century Technologies, Inc.
> 6011 W. courtyard Drive
> Building 5, Suite 300
> Austin, TX 78730
>
> Phone: 512 682 4707<tel:512%20682%204707>
> Email: ar...@21...<mailto:ar...@21...>
> URL: http://www.21technologies.com
>
> The information in this email and in any attachments is confidential and may be privileged. If you are not the intended recipient, please destroy this message, delete any copies held on your systems and notify the sender immediately. You should not retain, copy or use this email for any purpose, nor disclose all or any part of its content to any other pserson.
>

Re: [jgrapht-users] Impossible to set source and target of DefaultEdge

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

Hi Anant,

  JGraphT is a very well designed library, but takes some getting used to at
first.  Edges are created using the EdgeFactors; raw Edges are not
constructed.  Then the src and target are queried via the graph in which the
edge exists.

--Rob
On Jul 11, 2011 11:59 AM, "Anant Rathi" <ar...@21...> wrote:
> All,
>
> org.jgrapht.graph.DefaultEdge has protected getSource() and getTarget()
methods, but there aren't setters for source and target or a constructor
that sets them. Whether you are instantiating or extending DefaultEdge, the
source and target members can't be modified, and they're always null. That
doesn't seem right.
>
> Am I missing something?
>
> Anant Rathi
> Research Intern
> 21st Century Technologies, Inc.
> 6011 W. courtyard Drive
> Building 5, Suite 300
> Austin, TX 78730
>
> Phone: 512 682 4707
> Email: ar...@21...
> URL: http://www.21technologies.com
>
> The information in this email and in any attachments is confidential and
may be privileged. If you are not the intended recipient, please destroy
this message, delete any copies held on your systems and notify the sender
immediately. You should not retain, copy or use this email for any purpose,
nor disclose all or any part of its content to any other pserson.
>

[jgrapht-users] Impossible to set source and target of DefaultEdge

[Anant R. <ar...@21...>]

All,

org.jgrapht.graph.DefaultEdge has protected getSource() and getTarget() methods, but there aren't setters for source and target or a constructor that sets them. Whether you are instantiating or extending DefaultEdge, the source and target members can't be modified, and they're always null. That doesn't seem right.

Am I missing something?

Anant Rathi
Research Intern
21st Century Technologies, Inc.
6011 W. courtyard Drive
Building 5, Suite 300
Austin, TX 78730

Phone: 512 682 4707
Email: ar...@21...
URL: http://www.21technologies.com

The information in this email and in any attachments is confidential and may be privileged. If you are not the intended recipient, please destroy this message, delete any copies held on your systems and notify the sender immediately. You should not retain, copy or use this email for any purpose, nor disclose all or any part of its content to any other pserson.

Re: [jgrapht-users] Null Edge

[Mohammad I. <msi...@ua...>]

Hello,

I have found the error. Actually I used similar codes earlier and it gave
correct result so I thought that it may be some problem of libraries. I
figured out that I have included JGraph library which was not there before
and NetBeans imported DefaulEdge from JGraph not JGraphT and that was
causing the problem.

Thanks.

On Wed, Jul 6, 2011 at 2:06 AM, Ismail Marmoush <mar...@gm...>wrote:

> Slam Alekom Mohamed,
>
> It compiles and runs fine in my machine
> The output is like this:
> ([v1, v2, v3, v4], [{v1,v2}, {v2,v3}, {v3,v4}, {v4,v1}])
>
> I guess it's something not related to the code it self but to
> (configurations , IDE , compilation etc.. )
>
> On Wed, Jul 6, 2011 at 5:18 AM, Mohammad Islam <msi...@ua...>wrote:
>
>> Hello,
>>
>> Here is the code. It is copied from the HelloJGraphT program.
>>
>> UndirectedGraph<String, DefaultEdge> g =
>>             new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
>>
>>         String v1 = "v1";
>>         String v2 = "v2";
>>         String v3 = "v3";
>>         String v4 = "v4";
>>
>>         // add the vertices
>>         g.addVertex(v1);
>>         g.addVertex(v2);
>>         g.addVertex(v3);
>>         g.addVertex(v4);
>>
>>         // add edges to create a circuit
>>         g.addEdge(v1, v2);
>>         g.addEdge(v2, v3);
>>         g.addEdge(v3, v4);
>>         g.addEdge(v4, v1);
>>
>>         System.out.println(g.toString());
>>
>>
>> On Tue, Jul 5, 2011 at 5:13 PM, Ismail Marmoush <mar...@gm...
>> > wrote:
>>
>>> try to provide some code please
>>>
>>> On Tue, Jul 5, 2011 at 7:28 PM, Mohammad Islam <msi...@ua...>wrote:
>>>
>>>> Hello,
>>>>
>>>> I am a new member of this list and a new user of JGrapht. I was trying
>>>> to build a graph using the provided HelloJGraphT program. The program runs
>>>> well but when I was trying to print the Graph using toString I found that
>>>> all the edges are null. Here is the output
>>>>
>>>> ([v1, v2, v3, v4], [null={v1,v2}, null={v2,v3}, null={v3,v4},
>>>> null={v4,v1}])
>>>>
>>>> Even when I tried to get the set of edges and try to print the
>>>> edges separately I got null edges. So what may be the problem.
>>>>
>>>> --
>>>> Mohammad Saiful Islam
>>>> MSc(Thesis)
>>>> Dept of Computing Science
>>>> University of Alberta
>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> All of the data generated in your IT infrastructure is seriously
>>>> valuable.
>>>> Why? It contains a definitive record of application performance,
>>>> security
>>>> threats, fraudulent activity, and more. Splunk takes this data and makes
>>>> sense of it. IT sense. And common sense.
>>>> http://p.sf.net/sfu/splunk-d2d-c2
>>>> _______________________________________________
>>>> jgrapht-users mailing list
>>>> jgr...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>>
>>>>
>>>
>>
>>
>> --
>> Mohammad Saiful Islam
>> MSc(Thesis)
>> Dept of Computing Science
>> University of Alberta
>>
>>
>


-- 
Mohammad Saiful Islam
MSc(Thesis)
Dept of Computing Science
University of Alberta

Re: [jgrapht-users] Null Edge

[Ismail M. <mar...@gm...>]

Slam Alekom Mohamed,

It compiles and runs fine in my machine
The output is like this:
([v1, v2, v3, v4], [{v1,v2}, {v2,v3}, {v3,v4}, {v4,v1}])

I guess it's something not related to the code it self but to
(configurations , IDE , compilation etc.. )

On Wed, Jul 6, 2011 at 5:18 AM, Mohammad Islam <msi...@ua...> wrote:

> Hello,
>
> Here is the code. It is copied from the HelloJGraphT program.
>
> UndirectedGraph<String, DefaultEdge> g =
>             new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
>
>         String v1 = "v1";
>         String v2 = "v2";
>         String v3 = "v3";
>         String v4 = "v4";
>
>         // add the vertices
>         g.addVertex(v1);
>         g.addVertex(v2);
>         g.addVertex(v3);
>         g.addVertex(v4);
>
>         // add edges to create a circuit
>         g.addEdge(v1, v2);
>         g.addEdge(v2, v3);
>         g.addEdge(v3, v4);
>         g.addEdge(v4, v1);
>
>         System.out.println(g.toString());
>
>
> On Tue, Jul 5, 2011 at 5:13 PM, Ismail Marmoush <mar...@gm...>wrote:
>
>> try to provide some code please
>>
>> On Tue, Jul 5, 2011 at 7:28 PM, Mohammad Islam <msi...@ua...>wrote:
>>
>>> Hello,
>>>
>>> I am a new member of this list and a new user of JGrapht. I was trying to
>>> build a graph using the provided HelloJGraphT program. The program runs well
>>> but when I was trying to print the Graph using toString I found that all the
>>> edges are null. Here is the output
>>>
>>> ([v1, v2, v3, v4], [null={v1,v2}, null={v2,v3}, null={v3,v4},
>>> null={v4,v1}])
>>>
>>> Even when I tried to get the set of edges and try to print the
>>> edges separately I got null edges. So what may be the problem.
>>>
>>> --
>>> Mohammad Saiful Islam
>>> MSc(Thesis)
>>> Dept of Computing Science
>>> University of Alberta
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> All of the data generated in your IT infrastructure is seriously
>>> valuable.
>>> Why? It contains a definitive record of application performance, security
>>> threats, fraudulent activity, and more. Splunk takes this data and makes
>>> sense of it. IT sense. And common sense.
>>> http://p.sf.net/sfu/splunk-d2d-c2
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>>
>>
>
>
> --
> Mohammad Saiful Islam
> MSc(Thesis)
> Dept of Computing Science
> University of Alberta
>
>

[jgrapht-users] Null Edge

[Mohammad I. <msi...@ua...>]

Hello,

I am a new member of this list and a new user of JGrapht. I was trying to
build a graph using the provided HelloJGraphT program. The program runs well
but when I was trying to print the Graph using toString I found that all the
edges are null. Here is the output

([v1, v2, v3, v4], [null={v1,v2}, null={v2,v3}, null={v3,v4}, null={v4,v1}])

Even when I tried to get the set of edges and try to print the
edges separately I got null edges. So what may be the problem.

-- 
Mohammad Saiful Islam
MSc(Thesis)
Dept of Computing Science
University of Alberta

Re: [jgrapht-users] Dependecy Graph on jgrapht

[Randall R S. <rs...@so...>]

On Sunday June 19 2011, arif handoyo wrote:
> I have a directed graph, where the direction of the graph shows the
> dependencies, ega-> b, which means a need b. example for graph
> a-> b
> b-> c
> c-> a
> d-> b
> c-> e
> I want to sort the graph becomes e, a, b, c, d based on the level
> dependecynya, canjgrapht overcome this problem?

You want a topological sort.

http://www.jgrapht.org/javadoc/org/jgrapht/traverse/TopologicalOrderIterator.html


Randall Schulz

[jgrapht-users] Dependecy Graph on jgrapht

[arif h. <ari...@gm...>]

I have a directed graph, where the direction of the graph shows the
dependencies, ega-> b, which means a need b. example for graph
a-> b
b-> c
c-> a
d-> b
c-> e
I want to sort the graph becomes e, a, b, c, d based on the level
dependecynya, canjgrapht overcome this problem?

[jgrapht-users] Query in installation-reg

[aravindh r. <coo...@gm...>]

Hello

I am a student working with programming language ORC whose core input is in
the form of graph.In order to work with graph I downloaded the latest
JGraphT - 0.8.2. Am using jdk 1.6.0_25 and am unable to import the files
that reside in /src and also cannot work with demo  though I have built
JGraphT - 0.8.2 using ANT-1.8.2 .

It will be helpful to me if you provide me the detailed installation
procedure.


Thank you



With Regards

Aravindh R

[jgrapht-users] query in Installation-reg

[aravindh r. <coo...@gm...>]

Hello

I am a student working with programming language ORC whose core input is in
the form of graph.In order to work with graph I downloaded the latest
JGraphT - 0.8.2. Am using jdk 1.6.0_25 and am unable to import the files
that reside in /src and also cannot work with demo  though I have built
JGraphT - 0.8.2 using ANT-1.8.2 .

It will be helpful to me if you provide me the detailed installation
procedure.


Thank you



With Regards

Aravindh R

Re: [jgrapht-users] Graph Partitioning

[Ball, N. S <nic...@im...>]

Nope, unfortunately that's not what I was looking for.

I need a way to partition a complete weighted graph into two parts (not necessarily equal) in the best way so that to minimize the weights that cross between the two partitions. AKA: Graph bisection problem or Graph partitioning problem.

Not sure if you support such a thing as it is quite computationally intensive and not easy development!
There are a number of approximation solutions but none have been implemented in Java :(

Nicholas

________________________________________
From: John Sichi [js...@gm...]
Sent: 03 June 2011 00:01
To: Ball, Nicholas S
Cc: jgr...@li...
Subject: Re: [jgrapht-users] Graph Partitioning

Your requirements aren't clear, but if you mean you'd like to apply a
weight threshold to decide whether an edge should count as a
connection or not, then just create a subgraph view which filters the
edges based on weight, and then run ConnectivityInspector on that.

JVS

On Thu, Jun 2, 2011 at 11:17 AM, Ball, Nicholas S
<nic...@im...> wrote:
> Hello all,
> I see you have a way of generating Bipartite Graphs but do you have anything
> implemented that will split a graph into two graphs/sets based on the
> weighted values on the edges.
> If not, any idea where I can find a java implementation of this!? Been
> looking everywhere!
> Thank you and keep up the good work!
> Nicholas
>
> ------------------------------------------------------------------------------
> Simplify data backup and recovery for your virtual environment with vRanger.
> Installation's a snap, and flexible recovery options mean your data is safe,
> secure and there when you need it. Discover what all the cheering's about.
> Get your free trial download today.
> http://p.sf.net/sfu/quest-dev2dev2
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>