jgrapht-users — JGraphT user list.

Re: [jgrapht-users] Error - declared package does not match the expected package

[Rushang K. <rus...@ho...>]

------------------------------------------------------------------------------

Re: [jgrapht-users] Error - declared package does not match the expected package

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

I think you have to manually tell Eclipse which folder is your source
folder and which folder should be on the build path.
Since this question is not about JgraphT, I advise you to look at similar
questions asked on stackoverflow[1] or just use Maven.

[1]
https://stackoverflow.com/questions/7628686/eclipse-the-declared-package-does-not-match-the-expected-package

Üdvözlettel,

Besenyei Szabolcs

2015-12-10 5:15 GMT+01:00 Rashmi Raghava <ras...@gm...>:

> hi,
>
> I am getting the below error on importing the jgrapht into eclipse.
>
> The declared package "org.jgrapht" does not match the expected package
>  "source.jgrapht-core.src.main.java.org.jgrapht"
>
> How do I go about solving this?
>
> --
> Thanks and Regards,
> Rashmi
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Error - declared package does not match the expected package

[Rashmi R. <ras...@gm...>]

hi,

I am getting the below error on importing the jgrapht into eclipse.

The declared package "org.jgrapht" does not match the expected package
 "source.jgrapht-core.src.main.java.org.jgrapht"

How do I go about solving this?

-- 
Thanks and Regards,
Rashmi

Re: [jgrapht-users] jgrapht - Find all the nodes that are at most x units away from a particular node

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

A possible one-liner off the top of my head:

FloydWarshallShortestPaths fwsp = new FloydWarshallShortestPaths(graph);

fwsp.getShortestPath(sourceVertex).stream().filter(path ->
path.getWeight() <= MAX_DISTANCE).collect(Collectors.toList());


Üdvözlettel,

Besenyei Szabolcs

2015-12-05 17:50 GMT+01:00 Sandeep Sas <san...@gm...>:

> Hi,
>
> I am pretty new to jgrapht.
>
> I am looking for a solution to find all nodes, which are less than x units
> away from a particular graph node. I am using jgrapht's
> DefaultDirectedWeightedGraph.
>
> Is there any easy way to perform this using jgrapht library?
>
> Thank you
> Sandeep
>
> DefaultDirectedWeightedGraph <GraphNode,DefaultWeightedEdge> graph = new
>             DefaultDirectedWeightedGraph <GraphNode,DefaultWeightedEdge>(DefaultWeightedEdge.class);
>
>
>
> ------------------------------------------------------------------------------
> Go from Idea to Many App Stores Faster with Intel(R) XDK
> Give your users amazing mobile app experiences with Intel(R) XDK.
> Use one codebase in this all-in-one HTML5 development environment.
> Design, debug & build mobile apps & 2D/3D high-impact games for multiple
> OSs.
> http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] jgrapht - Find all the nodes that are at most x units away from a particular node

[Sandeep S. <san...@gm...>]

Hi,

I am pretty new to jgrapht.

I am looking for a solution to find all nodes, which are less than x units
away from a particular graph node. I am using jgrapht's
DefaultDirectedWeightedGraph.

Is there any easy way to perform this using jgrapht library?

Thank you
Sandeep

DefaultDirectedWeightedGraph <GraphNode,DefaultWeightedEdge> graph = new
            DefaultDirectedWeightedGraph
<GraphNode,DefaultWeightedEdge>(DefaultWeightedEdge.class);

Re: [jgrapht-users] Question on JGraphT

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

Hi,In a mood of making a clean-up of my unused email addresses, I came across your e-mail.It might be useful that I answer you before I give up for good to visit my Yahoo mailbox :)
I will not answer exactly to your question (you may consider to attach a JUnit test case for the members willing to look at the bug you mentioned), on the hand I want to clarify the poor performance of the algorithm to warn new JGraphT users.
Initially I designed the algorithm (a long time ago...) mainly for the purpose of complete graphs with possibly negative weight cycles. However, as the name of the class 'KShortestPaths' does not refer to this specific property (of possible negative cycles), it might be misleading for the majority of users whose graphs are only with non-negative edge weights.
Indeed, what is 100% true is that it is far far too slow compared to other algorithms for non-negative edge weights :(Unfortunately everybody seems to perform the 'KShortestPaths' algorithm with non-negative edge weights... 
In order not to mislead users, it might be worth to rename the class or to remove the class completely (I will feel hurt) and replace it with a best-in-class algorithm. You may think of the REA algorithm (Recursive Enumeration Algorithm) by Jimenez and Marzal (see http://www.springerlink.com/content/pl0054nt2d0d2u3t/ ) or to the Yen's algorithm (as already pointed by somebody at http://stackoverflow.com/questions/12773525/k-shortest-alternative-path-algorithm-java-implementations ).
I definitely submitted to JGraphT a not satisfying implementation for the 'KShortestPaths' class. Sorry for that.


    Le Mercredi 29 juillet 2015 14h05, SSovine <so...@gm...> a écrit :
 

 I see that this is a fairly old post, but hopefully this will be useful
anyway. 

I have experimented with this same algorithm, and unfortunately I think it
may not always correctly produce the K shortest paths.

Consider a graph with the following edges (posted as .dot file for
graphviz), where we are searching for the 3-shortest paths from S to U:

graph G {
autosize=false;
size="20,12!";
rankdir=LR;

S -- U [label="1"];
S -- a1 [label="1"];
a1 -- a2 [label="1"];
a2 -- a3 [label="1"];
a3 -- a4 [label="1"];
a4 -- V [label="1"];
S -- b1 [label="3"];
b1 -- b2 [label="1"];
b2 -- b3 [label="1"];
b3 -- b4 [label="1"];
b4 -- b5 [label="1"];
b5 -- U [label="1"];
S -- c1 [label="2"];
c1 -- b2 [label="1"];

V -- U [label="1"];
V -- d1 [label="1"];
d1 -- U [label="1"];
V -- e1 [label="1"];
e1 -- e2 [label="1"];
e2 -- U [label="1"];
}

The path (S, a1, a2, a3, a4, V, U) should be one of the 3-shortest paths
from S to U. However, after four iterations, the three shortest paths stored
for V will be {(S, U, V), (S, U, d1, V), (S, U, e2, e1, V)}. This will
prevent the path {(S, a1, a2, a3, a4, V)} from being stored for V at the
fifth iteration, which will prevent it from being passed on to U at the
sixth iteration.

The problem comes from the fact that we only store simple paths for each
vertex at each iteration. If we allow paths to have loops, then we can prove
correctness for the algorithm using essentially the same method that is used
to prove correctness for Bellman-Ford.

SRS



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Re-Question-on-JGraphT-tp107942p4025031.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

------------------------------------------------------------------------------
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


  

Re: [jgrapht-users] jgrpht-Floyd Warshall's Algorithm

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

You do realize that you are trying to calculate something in the order of
100000^2=10.000.000.000 shortest paths right? Let's assume for the sake of
argument that each path can be stored in a single byte (8 bits). This is
obviously not realistic since a single integer in java already takes up 4
bytes. Nevertheless, let's assume that you need 1 byte per path. There are
2^30 bytes in a single gigabyte. That means that you would need
100000^2 /2^30=9.31 Gb. There's no way that your computer with merely 16GB
of RAM will be able to keep all paths in memory.

There are a few things you can try however. Create a new Floyd Warshall
(FW) instance from your graph and invoke shortestDistance(a,b) for a pair
of vertices a,b. If you don't get a cost due to an out-of-memory or simply
because it takes too long, you are out of luck. My guess is that this will
be the case, as FW runs in cubic time if I recall correctly, which means
that you need 100000^3 iterations to actually calculate the distance
matrix. If your computer does let's say 10^7 or so iterations per second,
that may still take a very long time.

The way FW is implemented in jgrapht is as follows:
1. If you invoke any of the functions in the FW class, it will calculate a
next-hop matrix which for any pair of nodes a,b gives you the next node on
the shortest path from a to b. This is the core of any FW implementation
(see https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm). As an
added bonus, you get the distance matrix for free.
2. if you would invoke any other function except shortestDistance(a,b) in
the FW class, it will start calculating *every* shortest path between every
pair of nodes. This is nice for efficiency since next time you invoke the
getShortestPath(a,b) function you'll get the path in constant time, since
all the paths are precomputed. The disadvantage ofc is that precomputing
all paths is super expensive in terms of memory.

When you invoke shortestDistance(a,b), the FW class only calculates the
next0hop matrix, but will not precompute all paths. If this works for you,
you can easily write a new function which calculates the shortest path from
a to b based on the next-hop matrix. Example code for this is already in
the FW class.

Running Dijksta's shortest path alg for every pair of nodes is a bad idea:
this is way slower and more memory intensive than FW.

Joris


On Sun, Nov 22, 2015 at 2:02 PM, Sandeep Sas <san...@gm...>
wrote:

> Hi,
>
> I am pretty new to jgrapht.
>
> I am trying to run all-pairs shortest path Algorithm for the city of
> Chicago. The data source is OpenStreetMaps and has 100k nodes. I used
> jgrapht library for creating the graph.  But when I tried to run the
> Floyd Warshall's Algorithm on the graph, the program existed with error:
> Insufficient Java heap memory. I ran Dijktra's shorted path on this graph
> and was successful. I already tried increasing the heap size in the
> Eclipse IDE.
>
> How do I deal with this issue?
>
> System Config: 64 bit, 16 GB RAM (Eclipse on Windows)
>
> I really appreciate your reply
>
> Thank you
>
> Sandeep
>
>
> ------------------------------------------------------------------------------
> Go from Idea to Many App Stores Faster with Intel(R) XDK
> Give your users amazing mobile app experiences with Intel(R) XDK.
> Use one codebase in this all-in-one HTML5 development environment.
> Design, debug & build mobile apps & 2D/3D high-impact games for multiple
> OSs.
> http://pubads.g.doubleclick.net/gampad/clk?id=254741551&iu=/4140
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] jgrpht-Floyd Warshall's Algorithm

[Sandeep S. <san...@gm...>]

Hi,

I am pretty new to jgrapht.

I am trying to run all-pairs shortest path Algorithm for the city of
Chicago. The data source is OpenStreetMaps and has 100k nodes. I used
jgrapht library for creating the graph.  But when I tried to run the Floyd
Warshall's Algorithm on the graph, the program existed with error:
Insufficient Java heap memory. I ran Dijktra's shorted path on this graph
and was successful. I already tried increasing the heap size in the Eclipse
IDE.

How do I deal with this issue?

System Config: 64 bit, 16 GB RAM (Eclipse on Windows)

I really appreciate your reply

Thank you

Sandeep

Re: [jgrapht-users] GraphReader - Is there any corresponding writer /exporter

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

Perhaps this will answer your question:
http://stackoverflow.com/questions/27637791/how-to-import-a-graphml-to-jgrapht

IIRC, the current version of JgraphT has a graphml exporter only. We
obviously welcome a nice import class.
Judging from the code:
https://bitbucket.org/sorend/jgrapht-sna/src/cc8a3d6fbef2472cb5963a7ba84b393812154d4a/src/main/java/dk/aaue/sna/ext/graphml/GraphMLImporter.java?at=default

it would not be very hard to include this into JgraphT.

br,

Joris

On Wed, Nov 18, 2015 at 4:57 AM, L W <abt...@ms...> wrote:

> Hello,
>
> I'm trying to read a stored graph via GraphReader. It is not working,
> becaue at the moment I am using
> .graphml which uses <edge> and <vertex>. GraphReader seems to expect "p"
> and "e" as names for vertices and edges correspondingly (if
> (cols[0].equals("p")) {).
> Is there any exporter or writer satisfying the format required by
> GraphReader?
> Beside using serializables instead of e.g., .graphml is there any way of
> writing and reading with jgrapht?
> In advance thank you very much for your answer
>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] GraphReader - Is there any corresponding writer /exporter

[L W <abt...@ms...>]

Hello,

I'm trying to read a stored graph via GraphReader. It is not working, becaue at the moment I am using 
.graphml which uses <edge> and <vertex>. GraphReader seems to expect "p" and "e" as names for vertices and edges correspondingly (if (cols[0].equals("p")) {).
Is there any exporter or writer satisfying the format required by GraphReader? 
Beside using serializables instead of e.g., .graphml is there any way of writing and reading with jgrapht?
In advance thank you very much for your answer

 		 	   		  

Re: [jgrapht-users] Searching a node based on some attributes

[Atreyee M. <atr...@gm...>]

Thanks for your reply. However, my in-memory graph is large. I don't want
to incur the cost of traversing the entire graph. Instead if there is some
indexing mechanism or id to quickly fetch some node, that is what I am
looking for. Is there any way to do this in jgrapht explicitly?

Regards,
Atreyee

On Sun, Nov 15, 2015 at 2:48 PM, Szabolcs Besenyei <bes...@gm...>
wrote:

> ​If I understand your question correctly, you simply want to filter the
> vertex set of your graph by a certain attribute.
> Let's say we have a relationship graph between people:
> UndirectedGraph<Person, DefaultEdge> graph = createRealtionshipGraph();​
> You can filter the vertex set simply by:
> Set<Person> filteredVertices = new HashSet<>();
> filteredVertices.addAll(graph.vertexSet().stream().filter(p -> p.height()
> > 180));
> ​(The *Person​* class could hold different attributes age, height, sex,
> etc.)
> From here you can create a new graph based on your result or just do
> something with these vertices.​
> ​
> I hope I could help.
>
> ​Regards,
>
> Besenyei Szabolcs
>
> 2015-11-15 8:08 GMT+01:00 Atreyee Maiti <atr...@gm...>:
>
>> Hi,
>>
>> I was wondering if there is a way to find a node given certain attributes
>> in a graph using Jgrapht. I understand that I could always construct a
>> similar node and as long as the equals method is correctly implemented, I
>> would be able to verify if the node exists in the graph but what if I know
>> only 1 specific attribute of the node that I want to search by?
>>
>> Essentially I am looking for a search filter kind of querying mechanism.
>>
>> Regards,
>> Atreyee
>>
>>
>> ------------------------------------------------------------------------------
>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>

Re: [jgrapht-users] Searching a node based on some attributes

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

​If I understand your question correctly, you simply want to filter the
vertex set of your graph by a certain attribute.
Let's say we have a relationship graph between people:
UndirectedGraph<Person, DefaultEdge> graph = createRealtionshipGraph();​
You can filter the vertex set simply by:
Set<Person> filteredVertices = new HashSet<>();
filteredVertices.addAll(graph.vertexSet().stream().filter(p -> p.height() >
180));
​(The *Person​* class could hold different attributes age, height, sex,
etc.)
>From here you can create a new graph based on your result or just do
something with these vertices.​
​
I hope I could help.

​Regards,

Besenyei Szabolcs

2015-11-15 8:08 GMT+01:00 Atreyee Maiti <atr...@gm...>:

> Hi,
>
> I was wondering if there is a way to find a node given certain attributes
> in a graph using Jgrapht. I understand that I could always construct a
> similar node and as long as the equals method is correctly implemented, I
> would be able to verify if the node exists in the graph but what if I know
> only 1 specific attribute of the node that I want to search by?
>
> Essentially I am looking for a search filter kind of querying mechanism.
>
> Regards,
> Atreyee
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Searching a node based on some attributes

[Atreyee M. <atr...@gm...>]

Hi,

I was wondering if there is a way to find a node given certain attributes
in a graph using Jgrapht. I understand that I could always construct a
similar node and as long as the equals method is correctly implemented, I
would be able to verify if the node exists in the graph but what if I know
only 1 specific attribute of the node that I want to search by?

Essentially I am looking for a search filter kind of querying mechanism.

Regards,
Atreyee

Re: [jgrapht-users] Unexpected behavior for addVertex

[Ajay L <aja...@gm...>]

Thx for your quick reply, Besenyei. I had overridden equals() but had
missed doing hashCode(). Did that and it works fine now. thx

On Thu, Oct 22, 2015 at 1:01 PM, Szabolcs Besenyei <bes...@gm...>
wrote:

> Hi Ajay,
>
> Did you override the equals and hashCode methods in your costum node and
> edge classes?
>
> Üdvözlettel,
>
> Besenyei Szabolcs
>
> 2015-10-22 19:05 GMT+02:00 Ajay L <aja...@gm...>:
>
>> Hi all,
>>
>> Please refer to code snippet below.
>>
>> SimpleDirectedWeightedGraph<CustomNode, CustomWeightedEdge> graph = new
>> SimpleDirectedWeightedGraph<CustomNode, CustomWeightedEdge>(
>> CustomWeightedEdge.class);
>>
>> CustomNode node1 = new CustomNode("node1");
>> graph.addVertex(node1);
>> CustomNode node1Copy = new CustomNode("node1");
>> System.out.println(node1.equals(node1Copy));
>> System.out.println(graph.addVertex(node1));
>> System.out.println(graph.addVertex(node1Copy));
>>
>> When run, this produces true, false, true
>>
>> As per addVertex documentation - "Adds the specified vertex to this
>> graph if not already present. More formally, adds the specified vertex, v,
>> to this graph if this graph contains no vertex u such that u.equals(v).
>> If this graph already contains such vertex, the call leaves this graph
>> unchanged and returns false. In combination with the restriction on
>> constructors, this ensures that graphs never contain duplicate vertices"
>>
>> So why is addVertex call on node1Copy returning true. What am I missing?
>>
>> Using latest jgrapht release 0.9.1
>>
>> Thanks
>> Ajay
>>
>>
>> ------------------------------------------------------------------------------
>>
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>

Re: [jgrapht-users] Unexpected behavior for addVertex

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

Hi Ajay,

Did you override the equals and hashCode methods in your costum node and
edge classes?

Üdvözlettel,

Besenyei Szabolcs

2015-10-22 19:05 GMT+02:00 Ajay L <aja...@gm...>:

> Hi all,
>
> Please refer to code snippet below.
>
> SimpleDirectedWeightedGraph<CustomNode, CustomWeightedEdge> graph = new
> SimpleDirectedWeightedGraph<CustomNode, CustomWeightedEdge>(
> CustomWeightedEdge.class);
>
> CustomNode node1 = new CustomNode("node1");
> graph.addVertex(node1);
> CustomNode node1Copy = new CustomNode("node1");
> System.out.println(node1.equals(node1Copy));
> System.out.println(graph.addVertex(node1));
> System.out.println(graph.addVertex(node1Copy));
>
> When run, this produces true, false, true
>
> As per addVertex documentation - "Adds the specified vertex to this graph
> if not already present. More formally, adds the specified vertex, v, to
> this graph if this graph contains no vertex u such that u.equals(v). If
> this graph already contains such vertex, the call leaves this graph
> unchanged and returns false. In combination with the restriction on
> constructors, this ensures that graphs never contain duplicate vertices"
>
> So why is addVertex call on node1Copy returning true. What am I missing?
>
> Using latest jgrapht release 0.9.1
>
> Thanks
> Ajay
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Unexpected behavior for addVertex

[Ajay L <aja...@gm...>]

Hi all,

Please refer to code snippet below.

SimpleDirectedWeightedGraph<CustomNode, CustomWeightedEdge> graph = new
SimpleDirectedWeightedGraph<CustomNode, CustomWeightedEdge>(
CustomWeightedEdge.class);

CustomNode node1 = new CustomNode("node1");
graph.addVertex(node1);
CustomNode node1Copy = new CustomNode("node1");
System.out.println(node1.equals(node1Copy));
System.out.println(graph.addVertex(node1));
System.out.println(graph.addVertex(node1Copy));

When run, this produces true, false, true

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

So why is addVertex call on node1Copy returning true. What am I missing?

Using latest jgrapht release 0.9.1

Thanks
Ajay

Re: [jgrapht-users] PageRank in JGraphT

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

When I google for "jgrapht pagerank", a number of different code examples
come up, so you can probably adapt one of those.

On Mon, Oct 5, 2015 at 7:17 AM, Nejc Ambrozic <nej...@gm...>
wrote:

> Hello,
>
> I am getting invoved in network analysis and looking for java network
> analysis library. Looking at javadocs I have not been able to find PageRank
> algorithm in JGraphT, which I know I will need in my work. Is there any
> option to use PageRank algorithm with JGraphT or must I use something like
> JUNG to be able to perform this algorithm.
>
> Best regards,
> Nejc
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] PageRank in JGraphT

[Nejc A. <nej...@gm...>]

Hello,

I am getting invoved in network analysis and looking for java network
analysis library. Looking at javadocs I have not been able to find PageRank
algorithm in JGraphT, which I know I will need in my work. Is there any
option to use PageRank algorithm with JGraphT or must I use something like
JUNG to be able to perform this algorithm.

Best regards,
Nejc

Re: [jgrapht-users] Obtaining a path from BreadthFirstIterator

[Traven <mar...@gm...>]

I'm sorry, I tried to simplify the case too much and made it unreadable. My
core in reality looks more like this:


SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph =
                new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>
                        (DefaultWeightedEdge.class);
        graph.addVertex("1");
        graph.addVertex("2");
        graph.addVertex("3");
        graph.addVertex("4");
        graph.addVertex("5");


        DefaultWeightedEdge e1 = graph.addEdge("1", "2");
        graph.setEdgeWeight(e1, 5);
        DefaultWeightedEdge e2 = graph.addEdge("2", "3");
        graph.setEdgeWeight(e2, 10);
        DefaultWeightedEdge e3 = graph.addEdge("2", "4");
        graph.setEdgeWeight(e3, 2);
        DefaultWeightedEdge e4 = graph.addEdge("4", "5");
        graph.setEdgeWeight(e4, 2);
        DefaultWeightedEdge e5 = graph.addEdge("5", "3");
        graph.setEdgeWeight(e5, 2);



        System.out.println("Shortest path from vertex 1 to vertex 5:");
        List shortest_path =   DijkstraShortestPath.findPathBetween(graph,
"1", "3");
        System.out.println(shortest_path);

    }

In this case Dijkstra returns the correct, shortest path: 1->2->4->5->3. My
problem is - for the same graph, I want to obtain the path containing the
fewest number of transfers between vertices (in this case it would be
1->2->3). For this use-case the BFS would be the perfect solution. Is there
a way to somehow use the BreadthFirstIterator from jgrapht API or do I have
to write an algorithm by myself?



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Obtaining-a-path-from-BreadthFirstIterator-tp4025051p4025053.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] Obtaining a path from BreadthFirstIterator

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

If you need a path in a given graph use the relevant method of any of the
shortest path algorithm implementations, such as
DijkstraShortestPath.findPathBetween(graph, source, destination).

Üdvözlettel,

Besenyei Szabolcs

2015-10-04 17:20 GMT+02:00 Traven <mar...@gm...>:

> Here is the code to traverse the graph with BreathFirstIterator:
>
> public class GraphTest {
>
>     public static void main(String[] args) {
>         DirectedGraph<Integer, DefaultEdge> graph =
>             new DefaultDirectedGraph <Integer,
> DefaultEdge>(DefaultEdge.class);
>
>         graph.addVertex(7);
>         graph.addVertex(4);
>         graph.addVertex(9);
>         graph.addVertex(3);
>         graph.addVertex(2);
>         graph.addVertex(5);
>
>
>         graph.addEdge(7, 4);
>         graph.addEdge(7, 9);
>         graph.addEdge(9, 3);
>         graph.addEdge(3, 2);
>         graph.addEdge(3, 5);
>
>         GraphIterator<Integer, DefaultEdge> iterator =
>                 new BreadthFirstIterator<Integer, DefaultEdge>(graph);
>         while (iterator.hasNext()) {
>             System.out.println( iterator.next() );
>         }
>     }
> }
> As expected, the code prints out the list of all visited vertexes:
> 7,4,9,3,2,5. My problem is - I don't know how can I use this API to obtain
> a
> path (with removed backtracks of algorithm, i.e for example for path from 7
> to 2: 7->9->3->2), not just the list of visited vertexes. Stopping it after
> reaching the destination is obviously not enough. Have anyone already
> solved
> this issue?
>
>
>
> --
> View this message in context:
> http://jgrapht-users.107614.n3.nabble.com/Obtaining-a-path-from-BreadthFirstIterator-tp4025051.html
> Sent from the jgrapht-users mailing list archive at Nabble.com.
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

[jgrapht-users] Obtaining a path from BreadthFirstIterator

[Traven <mar...@gm...>]

Here is the code to traverse the graph with BreathFirstIterator:

public class GraphTest {

    public static void main(String[] args) {
        DirectedGraph<Integer, DefaultEdge> graph = 
            new DefaultDirectedGraph <Integer,
DefaultEdge>(DefaultEdge.class);

        graph.addVertex(7);
        graph.addVertex(4);
        graph.addVertex(9);
        graph.addVertex(3);
        graph.addVertex(2);
        graph.addVertex(5);


        graph.addEdge(7, 4);
        graph.addEdge(7, 9);
        graph.addEdge(9, 3);
        graph.addEdge(3, 2);
        graph.addEdge(3, 5);

        GraphIterator<Integer, DefaultEdge> iterator = 
                new BreadthFirstIterator<Integer, DefaultEdge>(graph);
        while (iterator.hasNext()) {
            System.out.println( iterator.next() );
        }
    }
}
As expected, the code prints out the list of all visited vertexes:
7,4,9,3,2,5. My problem is - I don't know how can I use this API to obtain a
path (with removed backtracks of algorithm, i.e for example for path from 7
to 2: 7->9->3->2), not just the list of visited vertexes. Stopping it after
reaching the destination is obviously not enough. Have anyone already solved
this issue?



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Obtaining-a-path-from-BreadthFirstIterator-tp4025051.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] feature request/help: save (huge) graph to image file

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

I'm not behind my computer so it's hard to check any solutions, but here is
something you could do:
export the graph using the DOT exporter. Pretty much any graphical graph
package can read the DOT format. Additionally, I believe there is a CSV
format in one of the pull requests in case DOT isn't supported by the
package. Visualizing large graphs is a very hard, dedicated, research area
on its own.

Btw, the new versions of JGraphT also support exporting to PDF.

I wasn't able to look at your stackoverflow post at the moment, but think
about *how* you want to visualize your graph. If you have >100 vertices,
what would be a good visualization such that the resulting graph is
actually informative? For very large graphs, it is usually better to give
specific statistics about the graph, e.g. degree of connectivity, diameter,
special structures such as planar, etc.

br,

Joris

On Thu, Sep 17, 2015 at 8:11 PM, Ícaro Cavalcante Dourado <ic...@gm...
> wrote:

> Hi there,
>
> I have been using JGraphT in my research project it has been great for me!
> I used to create and manipulate graphs well, so as ploting then using
> JGraphXAdapter API together with java.swing.JFrame. While this works well,
> I currently need to save the graph plots as PNG files.
> I managed how to do it just fine, but I have problems when the graphs get
> too large. The plot seems fine, but the way I perform exporting to png
> failures when the graphs are large.
> I have already asked for this in:
> http://stackoverflow.com/questions/32641766/export-huge-jframe-to-file
>
> Does JGraphT have any built-in solution to save a org.jgrapht.Graph
> directly to image file? Have you guys experienced any problems related to
> that?
>
> Thanks in advance!
> Icaro Cavalcante Dourado
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] feature request/help: save (huge) graph to image file

[Ícaro C. D. <ic...@gm...>]

Hi there,

I have been using JGraphT in my research project it has been great for me!
I used to create and manipulate graphs well, so as ploting then using
JGraphXAdapter API together with java.swing.JFrame. While this works well,
I currently need to save the graph plots as PNG files.
I managed how to do it just fine, but I have problems when the graphs get
too large. The plot seems fine, but the way I perform exporting to png
failures when the graphs are large.
I have already asked for this in:
http://stackoverflow.com/questions/32641766/export-huge-jframe-to-file

Does JGraphT have any built-in solution to save a org.jgrapht.Graph
directly to image file? Have you guys experienced any problems related to
that?

Thanks in advance!
Icaro Cavalcante Dourado

Re: [jgrapht-users] Minimal vertex separator between two nodes in an undirected graph

[Rushang K. <rus...@ho...>]

Have you tried looking at min-cut. There is an implementation of min cut in jgrapht.

NOTE: Min cut is not the same as vertex seperator. There are a few differences!

From: fed...@gm...
Date: Tue, 15 Sep 2015 14:39:37 -0300
To: jgr...@li...
Subject: [jgrapht-users] Minimal vertex separator between two nodes in an	undirected graph

Hi all, is there some implemented function in jgrapht to get a minimal vertex separator set between two non adjacent nodes in an undirected graph? I was searching at the javadoc but I can't find if there exist something like that.
This is the concept: https://en.wikipedia.org/wiki/Vertex_separator#Minimal_separators
I would like to use jgrapht to implement the getMinimalVertexSeparator function in the following example code: 
	public static void main(String[] args) {
		UndirectedGraph g = new UndirectedGraph(6);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(2, 3);
		g.addEdge(3, 4);
		g.addEdge(4, 5);
		g.addEdge(5, 0);
		List<Integer> x = getMinimalVertexSeparator(0, 2, g);
		
	}
​Thanks in advance,​
-- 
​Federico


------------------------------------------------------------------------------
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users 		 	   		  

[jgrapht-users] Minimal vertex separator between two nodes in an undirected graph

[Federico S. <fed...@gm...>]

Hi all, is there some implemented function in jgrapht to get a minimal
vertex separator set between two non adjacent nodes in an undirected graph?
I was searching at the javadoc but I can't find if there exist something
like that.

This is the concept:
https://en.wikipedia.org/wiki/Vertex_separator#Minimal_separators

I would like to use jgrapht to implement the getMinimalVertexSeparator
function in the following example code:

public static void main(String[] args) {
> UndirectedGraph g = new UndirectedGraph(6);
> g.addEdge(0, 1);
> g.addEdge(1, 2);
> g.addEdge(2, 3);
> g.addEdge(3, 4);
> g.addEdge(4, 5);
> g.addEdge(5, 0);
> List<Integer> x = getMinimalVertexSeparator(0, 2, g);
>
> }


​Thanks in advance,​

-- 
​Federico