jgrapht-users — JGraphT user list.

[jgrapht-users] saving to database

[Anup J. <arj...@gm...>]

Hello:

I am a newbie to jgrapht ( primarily evaluating it for my purpose).
I would like to know how I can store an in-memory graph representation to a
mysql database and alternatively retrieve it and
re-construct the graph in memory,

Any help would be appreciated.

Re: [jgrapht-users] generating bipartite graph

[gaurav k. <gau...@gm...>]

Hi,
@Luc -Thanks for suggesing it.I will look at it.
I dont want to test the bipartiteness I just want to visualize them so that
I can interpret my data.

Gaurav

On Fri, Nov 18, 2011 at 3:09 AM, Joris Kinable <de...@gm...> wrote:

> Hey,
>
> You question is quite unclear.
>
> What is "testing the validity of a bipartite graph"? Would you like to
> do something like: given a graph description like yours, check, by
> visual inspection, whether the graph is actually a bipartite graph,
> i.e. whether the vertices can be grouped into two partitions without
> any edges running within a single partition? You are better of using
> some mathematical techniques than performing some kind of 'visual'
> inspection. JgrpahT bij the way isn't a graphical package. For that,
> you need JGraphx. See for example:
> http://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness
>
>
> On Fri, Nov 18, 2011 at 9:13 AM, gaurav kejriwal <gau...@gm...>
> wrote:
> > Hi
> >
> > I am working on things related to Graph Theory. Actually I have some data
> > for bipartite graph and I want to test its validity by visualizing in
> graph
> > form.
> >
> > My data is in form like (for triangle):
> >
> > V 0 A
> >
> > V 1 B
> >
> > V 2 C
> >
> > U 0 1 E
> >
> > U 0 2 E
> >
> > U 1 2 E
> >
> > V denotes the vertices and U denotes edges (A, B, C and E are labels).
> Can
> > anyone suggest if  JgraphT will be suited for my purpose.
> >
> > Gaurav
> >
> >
> ------------------------------------------------------------------------------
> > All the data continuously generated in your IT infrastructure
> > contains a definitive record of customers, 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-novd2d
> > _______________________________________________
> > jgrapht-users mailing list
> > jgr...@li...
> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
> >
> >
>

Re: [jgrapht-users] generating bipartite graph

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

Hey,

You question is quite unclear.

What is "testing the validity of a bipartite graph"? Would you like to
do something like: given a graph description like yours, check, by
visual inspection, whether the graph is actually a bipartite graph,
i.e. whether the vertices can be grouped into two partitions without
any edges running within a single partition? You are better of using
some mathematical techniques than performing some kind of 'visual'
inspection. JgrpahT bij the way isn't a graphical package. For that,
you need JGraphx. See for example:
http://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness


On Fri, Nov 18, 2011 at 9:13 AM, gaurav kejriwal <gau...@gm...> wrote:
> Hi
>
> I am working on things related to Graph Theory. Actually I have some data
> for bipartite graph and I want to test its validity by visualizing in graph
> form.
>
> My data is in form like (for triangle):
>
> V 0 A
>
> V 1 B
>
> V 2 C
>
> U 0 1 E
>
> U 0 2 E
>
> U 1 2 E
>
> V denotes the vertices and U denotes edges (A, B, C and E are labels). Can
> anyone suggest if  JgraphT will be suited for my purpose.
>
> Gaurav
>
> ------------------------------------------------------------------------------
> All the data continuously generated in your IT infrastructure
> contains a definitive record of customers, 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-novd2d
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] generating bipartite graph

[gaurav k. <gau...@gm...>]

Hi

I am working on things related to Graph Theory. Actually I have some data
for bipartite graph and I want to test its validity by visualizing in graph
form.

My data is in form like (for triangle):

V 0 A
V 1 B
V 2 C
U 0 1 E

U 0 2 E

U 1 2 E

V denotes the vertices and U denotes edges (A, B, C and E are labels). Can
anyone suggest if  JgraphT will be suited for my purpose.

Gaurav

[jgrapht-users] New graph from breadth-first-search iterator

[Roark F. <roa...@ya...>]

Hi all,

I'm solving a problem almost identical to the example on this page: 
http://code.google.com/p/python-graph/wiki/Example

specifically:1 - Build a connected graph of say 20 nodes (in mine, the edges are directed, though the example above are not)
2 - Pick a node of interest and do a breadth-first-search
3 - Build a graph of the result of the BFS

I did it first in Python using the above library and it works great.
I'm doing the same with jgrapht and though steps 1 and 2 are great, step 3 is a problem.

The BFS iterator is:

    BreadthFirstIterator<Table, Edge> dfs = new BreadthFirstIterator<Table, Edge>(fullGraph, rootNode);

I can add vertices to a new graph with:

                while (bfs.hasNext()) {
                    Table table=bfs.next();
                    newGraph.addVertex(table);

But I can't see how to add the edges to the newGraph.

I can get just the edge objects with:

                    Set<Edge> edges = fullGraph.incomingEdgesOf(table);

But my Edge class doesn't have the from/to vertices in it.

What is the best way to do this with jgrapht?

My ideal is something like:

  DirectedMultigraph<Table, Edge> newGraph=new DirectedMultigraph<..>(dfs)

or similar.

Thoughts?
Thanks!
RF

[jgrapht-users] JgraphT - Matgraph - Matlab

[Akli B. <akl...@gm...>]

Hi,

I am trying to use a function which is  a wrapper around the JGraphT
library, allowing it to be called from within Matlab on Matgraph graph
objects posted in this
link<http://www.mathworks.com/matlabcentral/fileexchange/27074-maximal-independent-sets-using-jgraphtwww.mathworks.com/matlabcentral/fileexchange/27074-maximal-independent-sets-using-jgrapht>
.
The instructions posted on the previous do not work in my computer. I have
tried in Windows and Linux, tried 2 different versions of JgraphT, added all
the java paths and it doesn't work.

Can anyone help me with this?

Cheers

-- 
Akli Benali

Re: [jgrapht-users] Edge based graph

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

On Sat, October 22, 2011 11:48 pm, Mati Szaingurten wrote:

Hi
Mati,

> That sounds like a good idea... The thing though is
that if you check how
> DijkstraShortestPath is implemented, it's
clearly all about how the
> ClosestFirstIterator is implemented...
The thing is that I don't
> understand
> how (and why) it
works, so I wouldn't know how to correctly delegate the
>
functions to make the ClosestFirstIterator behave as if it was working
on
> an
> edge based graph...

you don't need to
know how the ClosestFirstIterator works. What you do is write the methods
in GraphDelegator according to the definition of the edge based graph in
the article, regardless whether the iterator needs them or not. For the
ones that modify the graph, I'd say just throw an
UnsupportedOperationException. (If you're lazy or in lack of time, you can
throw the same exception for the ones that are difficult. When running the
program, you'll notice if the iterator needs them:-)

The
article says the only thing that should be changed (when choosing the
iterator way) is getting the outedges of a vertex. This is done by
CrossComponentIterator.Specifics.edgesOf(). The appropriate Specifics is
created by a static method CrossComponentIterator.createGraphSpecifics and
unfortunately stored in a private variable. So if you go the iterator way,
you'd have to copy CrossComponentIterator, ClosestFirstIterator and
DijkstraShortestPath and create your own specifics in
CrossComponentIterator.

Regards,
   Ernst

Re: [jgrapht-users] Edge based graph

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

Hi Mati,

can't you write an EdgeGraph class akin to org.jgrapht.graph.GraphDelegator? That's probably easier than messing around with special purpose  iterators and more generally useful as well.

Regards,
Ernst

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

[jgrapht-users] Edge based graph

[Mati S. <mat...@gm...>]

Hello, I am using the jgrapht package and I want to convert my graph into an
EDGE BASED GRAPH, to be able to account for turn costs, as described in this
article http://algo2.iti.kit.edu/documents/routeplanning/volker_sa.pdf.

The article describes two ways of converting node based graphs (regular
graphs) into edge based graphs to use pathfinding algorithms (such as
dijkstra):

* offline conversion which creates an entire new graph, with edges as nodes
(and the edges connecting edges are turns)

* online conversion which is much more time and memory efficient and just
demands a slight modification to the dijkstra algorithm (which is final in
the jgrapht package)

I have managed to implement the offline conversion using the jgrapht
package, but I'm having a really hard time with the online conversion.

It seems that in order to implement it, I would have to override the graph
iterators someway. I have gone lost browsing trough the jgrapht code, trying
to find the right place and way to do it, with no luck.

I would really appreciate the help!

Mati

[jgrapht-users] How to actually change the contents of a Vertex in a Graph

[Matias A. G. <mat...@gm...>]

Hi,

I am new to this API, so I may have overlooked something. I am coding
some graph traversals and need to mark vertices as "visited". For this
sake, I coded my own TrackedVertex class which adds the visited status
to a String name. When doing my traversal, I can use the Graphs
utility class to get opposite vertices and analyze those, which I can
mark as visited since getOppositeVertex returns a vertex which is
backed by the Graph.

However, for the starting vertex (or for that sake, for any vertex I
want to alter for some reason), I am finding no method to get the
actual vertex and change it in the Graph. I can access the vertexSet
but this is just an unmodifiable copy. I do not want to remove the
vertex and add it again because I would lose the edges (or be in the
need to recreate them).

Eventually I coded this very ugly (but useful) method which takes
advantage of getOppositeVertex returning the actual vertex in the
Graph and assumes there is at least one edge containing the vertex I
want. It basically grabs the first edge it finds, and gets the
opposite vertex twice, effectively returning the one I want.

	private TrackedVertex<String> getChangeableVertex(Graph graph, String vertex) {
		TrackedVertex<String> v = new TrackedVertex<String>(vertex);
		Set<? extends DefaultEdge> edges = graph.edgesOf(v);
		
		DefaultEdge edge = edges.iterator().next();
		return (TrackedVertex<String>) Graphs.getOppositeVertex(graph, edge,
Graphs.getOppositeVertex(graph, edge, v));
		
	}

Is there any way to get a reference to a vertex by its equality
criteria (in this case, a String), so that I can modify it and it gets
reflected in the Graph?

Thanks,

Matias

Re: [jgrapht-users] Vertices that validate attempts to add an edge

[Ben J. <bjo...@gm...>]

Thank John, I'll give that a go.  I got the behaviour I wanted by 
subclassing DirectedAcyclicGraph but I think using a GraphDelegator as 
you suggest might be a better approach.

On 2/10/2011 5:17 PM, John Sichi wrote:
> You can do this by wrapping a graph (that's how UnmodifiableGraph is used).
>
> JVS
>
> On Thu, Sep 22, 2011 at 5:48 AM, Ben Johnson
> <bjo...@gm...>  wrote:
>> Hi
>>
>> I'm just experimenting with your library and liking it so far, thanks!
>>
>> I was wondering if anyone had implemented what I would call 'validating
>> edges', where a vertex could prevent an edge from being added if the
>> other vertex did not meet certain criteria.  For example, if I was
>> modeling a directory structure and wanted certain directories to only
>> contain certain types of files, so that any attempt to add an 'invalid'
>> file type would throw an exception.
>>
>> I assume I can do this by subclassing DirectedAcyclicGraph and
>> overriding the addEdge() methods so that it invokes a 'validate' method
>> on each of the two vertices (as a generic solution - in my case I just
>> need the directory vertex to validate the file vertex; the file vertex
>> doesn't care about the directory vertex), but I was wondering if anyone
>> had encountered this problem before and approached it differently.
>>
>> The idea is something like:
>>
>> addEdge(V vertex1, V vertex2) {
>> ...
>>      // TODO: Check if vertices support 'validate' methods
>>      ...
>>      if ( !(vertex1.validate(vertex2) || vertex2.validate(vertex1))) {
>>           throw new IllegalArgumentException("...");
>> ...
>> }
>>
>> Thanks very much
>> Ben
>>
>>
>>
>> ------------------------------------------------------------------------------
>> All the data continuously generated in your IT infrastructure contains a
>> definitive record of customers, application performance, security
>> threats, fraudulent activity and more. Splunk takes this data and makes
>> sense of it. Business sense. IT sense. Common sense.
>> http://p.sf.net/sfu/splunk-d2dcopy1
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>

Re: [jgrapht-users] Vertices that validate attempts to add an edge

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

You can do this by wrapping a graph (that's how UnmodifiableGraph is used).

JVS

On Thu, Sep 22, 2011 at 5:48 AM, Ben Johnson
<bjo...@gm...> wrote:
> Hi
>
> I'm just experimenting with your library and liking it so far, thanks!
>
> I was wondering if anyone had implemented what I would call 'validating
> edges', where a vertex could prevent an edge from being added if the
> other vertex did not meet certain criteria.  For example, if I was
> modeling a directory structure and wanted certain directories to only
> contain certain types of files, so that any attempt to add an 'invalid'
> file type would throw an exception.
>
> I assume I can do this by subclassing DirectedAcyclicGraph and
> overriding the addEdge() methods so that it invokes a 'validate' method
> on each of the two vertices (as a generic solution - in my case I just
> need the directory vertex to validate the file vertex; the file vertex
> doesn't care about the directory vertex), but I was wondering if anyone
> had encountered this problem before and approached it differently.
>
> The idea is something like:
>
> addEdge(V vertex1, V vertex2) {
> ...
>     // TODO: Check if vertices support 'validate' methods
>     ...
>     if ( !(vertex1.validate(vertex2) || vertex2.validate(vertex1))) {
>          throw new IllegalArgumentException("...");
> ...
> }
>
> Thanks very much
> Ben
>
>
>
> ------------------------------------------------------------------------------
> All the data continuously generated in your IT infrastructure contains a
> definitive record of customers, application performance, security
> threats, fraudulent activity and more. Splunk takes this data and makes
> sense of it. Business sense. IT sense. Common sense.
> http://p.sf.net/sfu/splunk-d2dcopy1
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

Re: [jgrapht-users] Question

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

testsrc/org/jgrapht/alg/DijkstraShortestPathTest.java

A*:  no plans, but we always welcome contributions.

Regarding the Fibonacci heap:  I think you can figure that one out by
browsing the code for a few minutes.

JVS

On Mon, Sep 26, 2011 at 1:39 PM, Mati Szaingurten <mat...@gm...> wrote:
>
> Hello JGraphT team!
> I have a couple of questions... First of all, I would very much like to get
> access to an example of the usage of SimpleDirectedWeightedGraph.
> I am writing a program where I need to solve a graph with the Dijkstra
> algorithm and even though I have implemented both the data structure and the
> algorithm by myself, I would much rather use an open source code (yours!).
> Nevertheless, the classes are quite complex so if i could see an example of
> how to create a simple directed weighted graph and run the dijkstra
> algorithm on it, that would be great. I have tried the web, but didnt find a
> suiting example.
> Is the queue used in the dijkstra algorithm a fibonacci heap? I've read
> that's the only way of achieving maximal efficiency for the algorithm.
> For my last question, are you planning on implementing some other shortest
> path algorithms like A* or some others? That would be great.
>
> Thanks!
> Mati
> ------------------------------------------------------------------------------
> All the data continuously generated in your IT infrastructure contains a
> definitive record of customers, application performance, security
> threats, fraudulent activity and more. Splunk takes this data and makes
> sense of it. Business sense. IT sense. Common sense.
> http://p.sf.net/sfu/splunk-d2dcopy1
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Question

[Mati S. <mat...@gm...>]

Hello JGraphT team!

I have a couple of questions... First of all, I would very much like to get
access to an example of the usage of SimpleDirectedWeightedGraph.

I am writing a program where I need to solve a graph with the Dijkstra
algorithm and even though I have implemented both the data structure and the
algorithm by myself, I would much rather use an open source code (yours!).

Nevertheless, the classes are quite complex so if i could see an example of
how to create a simple directed weighted graph and run the dijkstra
algorithm on it, that would be great. I have tried the web, but didnt find a
suiting example.

Is the queue used in the dijkstra algorithm a fibonacci heap? I've read
that's the only way of achieving maximal efficiency for the algorithm.

For my last question, are you planning on implementing some other shortest
path algorithms like A* or some others? That would be great.


Thanks!

Mati

[jgrapht-users] Vertices that validate attempts to add an edge

[Ben J. <bjo...@gm...>]

Hi

I'm just experimenting with your library and liking it so far, thanks!

I was wondering if anyone had implemented what I would call 'validating 
edges', where a vertex could prevent an edge from being added if the 
other vertex did not meet certain criteria.  For example, if I was 
modeling a directory structure and wanted certain directories to only 
contain certain types of files, so that any attempt to add an 'invalid' 
file type would throw an exception.

I assume I can do this by subclassing DirectedAcyclicGraph and 
overriding the addEdge() methods so that it invokes a 'validate' method 
on each of the two vertices (as a generic solution - in my case I just 
need the directory vertex to validate the file vertex; the file vertex 
doesn't care about the directory vertex), but I was wondering if anyone 
had encountered this problem before and approached it differently.

The idea is something like:

addEdge(V vertex1, V vertex2) {
...
     // TODO: Check if vertices support 'validate' methods
     ...
     if ( !(vertex1.validate(vertex2) || vertex2.validate(vertex1))) {
          throw new IllegalArgumentException("...");
...
}

Thanks very much
Ben

Re: [jgrapht-users] JGrapht quick remark

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

I wrote up a wiki page about this a long time ago:

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

I'll see about linking it from some of the JGraphT class Javadoc, but
I think the java.lang.Object Javadoc already says it pretty clearly:
"Note that it is generally necessary to override the hashCode method
whenever this method is overridden, so as to maintain the general
contract for the hashCode method, which states that equal objects must
have equal hash codes."

JVS

On Thu, Sep 15, 2011 at 1:48 PM, Fabian Menges <fm...@ny...> wrote:
> Hi jgrapht team,
>
> I just tried to implement something that uses a custom vertices class.
> It would be great if you could mention in the documentation or in an
> example that in order for this to work correctly you need to override
> not only the equals() but more importantly the hashCode() methods.
>
> I had to look at your source code to see that you were using a
> (linked)Hashmap to store the vertices which does not use equals() or a
> comparator but the hashCode() method.
>
> Thanks your for great work,
>
> Fabian
>

Re: [jgrapht-users] KShortestPaths performance

[Charles G. <cg...@lh...>]

It looks like I'm going to have to do some research as it's the hardest case I am after!

My initial plan was to do the shortest route, then remove one or more key edges and re-route which would be nice and easy, but the trick is to intelligently pick those :)

Thanks for the advice and pointers,
charles

On Sep 14, 2011, at 3:33 PM, hnr...@gr... wrote:

> 
> 
> Hi Charles, So you're looking at k shortest paths between two given vertices. If you google for 'k shortest path' you'll get many results, one of the first a nice article by David Eppstein, which has many pointers to other articles on varieties of the problem. Much depends on the requirements on the paths. Should they be simple or not? Vertex-disjoint? Edge-disjoint? Some varieties can be formulated as a max-flow problem. Or if you need e.g. edge-disjoint simple paths, then I would find the shortest path, remove its edges from the graph, find the second shortest path, and so on. Not elegant, but easy to implement. The hardest case seems to be simple paths that differ in at least one edge, but do not need to be vertex/edge disjoint. I'm afraid you can't get by without implementing an algorithm yourself. The good news is that the problem is well-studied and efficient algorithms do exist. Ernst -- Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org

Re: [jgrapht-users] KShortestPaths performance

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

Hi Charles,

So you're looking at k shortest paths between two given vertices. If you google for 'k shortest path' you'll get many results, one of the first a nice article by David Eppstein, which has many pointers to other articles on varieties of the problem. Much depends on the requirements on the paths. Should they be simple or not? Vertex-disjoint? Edge-disjoint? Some varieties can be formulated as a max-flow problem. Or if you need e.g. edge-disjoint simple paths, then I would find the shortest path, remove its edges from the graph, find the second shortest path, and so on. Not elegant, but easy to implement. The hardest case seems to be simple paths that differ in at least one edge, but do not need to be vertex/edge disjoint.

I'm afraid you can't get by without implementing an algorithm yourself. The good news is that the problem is well-studied and efficient algorithms do exist.

Ernst

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

Re: [jgrapht-users] KShortestPaths performance

[Charles G. <cg...@lh...>]

I forgot to follow up with my findings.

1. The dijkstra shortest path algorithm works nice and fast - faster than with pgroutng.
2. Building a new graph of out of a smaller area of coverage helps, but not by enough to make it feasible, and the graph build time itself takes about 4 seconds on my test cases, so still 8+ seconds to do the top 3 routes using KShortestPaths

If you have any ideas how I might be able to get better performance with the KShortestPaths algorithm, please let me know.

Thanks,
charles

On Sep 12, 2011, at 8:22 AM, Charles Galpin wrote:

> Hi Ernst
> 
> Good question :)  I am currently using postgresql/postgis/pgrouting and it's Dijkstra routing algorithm for my routing and it works well for a single shortest route from one point to another.  A single route is usually a few hundred milliseconds.  However I now need to generate the n shortest routes between two points so they can be offered as alternatives, where depending on the results I expect to to be anywhere from 3 to 10 (I am unsure the differences in routes will all be useful) and I'd like to keep this under a second as well.
> 
> I don't think I need the negative weight as it is a fully directed graph so each vertex is one-way. Is there a way I can make this faster without that?
> 
> This morning I'll try the other algorithms as a comparison to pgrouting, as well as try build a smaller graph each time I do the routing and see what that does for the speed as well.
> 
> Thanks,
> charles
> 
> On Sep 12, 2011, at 3:26 AM, hnr...@gr... wrote:
> 
>> Dear Charles,
>> 
>> What ARE your needs?
>> 
>> Depending on what they are, I dare say they can be fulfilled faster than the KShortestPaths algorithm does, because
>> 1. This algorithm can handle negative weight cycles. Do you need this?
>> 2. Your graph is very sparse.
>> 
>> Did you try e.g. the Dijkstra or Floyd-Warshall algorithms?
>> 
>> Regards,
>>   Ernst

Re: [jgrapht-users] KShortestPaths performance

[Charles G. <cg...@lh...>]

Hi Ernst

Good question :)  I am currently using postgresql/postgis/pgrouting and it's Dijkstra routing algorithm for my routing and it works well for a single shortest route from one point to another.  A single route is usually a few hundred milliseconds.  However I now need to generate the n shortest routes between two points so they can be offered as alternatives, where depending on the results I expect to to be anywhere from 3 to 10 (I am unsure the differences in routes will all be useful) and I'd like to keep this under a second as well.

I don't think I need the negative weight as it is a fully directed graph so each vertex is one-way. Is there a way I can make this faster without that?

This morning I'll try the other algorithms as a comparison to pgrouting, as well as try build a smaller graph each time I do the routing and see what that does for the speed as well.

Thanks,
charles

On Sep 12, 2011, at 3:26 AM, hnr...@gr... wrote:

> Dear Charles,
> 
> What ARE your needs?
> 
> Depending on what they are, I dare say they can be fulfilled faster than the KShortestPaths algorithm does, because
> 1. This algorithm can handle negative weight cycles. Do you need this?
> 2. Your graph is very sparse.
> 
> Did you try e.g. the Dijkstra or Floyd-Warshall algorithms?
> 
> Regards,
>   Ernst

Re: [jgrapht-users] KShortestPaths performance

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

Dear Charles,

What ARE your needs?

Depending on what they are, I dare say they can be fulfilled faster than the KShortestPaths algorithm does, because
1. This algorithm can handle negative weight cycles. Do you need this?
2. Your graph is very sparse.

Did you try e.g. the Dijkstra or Floyd-Warshall algorithms?

Regards,
   Ernst

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

----- Reply message -----
From: "Charles Galpin" <cg...@lh...>
To: <jgr...@li...>
Subject: [jgrapht-users] KShortestPaths performance
Date: Fri, Sep 9, 2011 22:21


Hi All

I'm new to jgrapht, have just downloaded it today to try out the k-shortest paths algorithm.

I made a simple test program to load up my network graph (happens to be road data) as a SimpleDirectedWeightedGraph which has about 60500 vertices and 97000 edges.

I then ran the KShortestPaths algorithm in a loop with the number of paths ranging from 1 to 10.  It takes 8 or 9 seconds to calculate one path, 24 for 2, 42 for 3, and so on until 10 takes 3.5 to 4 minutes. The paths are roughly 145 - 155 edges in length.

This is way too slow for my needs. Is there any way I can optimize this?  I'm guessing the answer is going to be to reduce my graph size to all that is necessary, and I'll try that next. I'm just afraid that the overhead of creating a new graph for every KShortestPaths is going to be pretty high as well (it takes about 30 seconds to load the whole graph from a database and I'll have to do a query to get the network data inside a bounding box containing the start and end points including some buffer)

TIA,
charles


------------------------------------------------------------------------------
Why Cloud-Based Security and Archiving Make Sense
Osterman Research conducted this study that outlines how and why cloud
computing security and archiving is rapidly being adopted across the IT 
space for its ease of implementation, lower cost, and increased 
reliability. Learn more. http://www.accelacomm.com/jaw/sfnl/114/51425301/
_______________________________________________
jgrapht-users mailing list
jgr...@li...
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

Re: [jgrapht-users] Connectivity of Directed Graphs

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

Dear Ulrich,

by  the common graph-theoretic definition of connectivity, the so-called 'underlying' graph is used, which is to say the edges with their direction removed. If the ConnectivityInspector would do something else, it wouldn't obey the usual definitions anymore.

As a visual example, assume you want to draw a big graph on the pages of a notebook, without any edges crossing pages. You can do this by splitting the graph in its connected components and drawing a connected component on every page.

Note also that connectivity is an equivalence relation: A graph can be partitioned in its connected components and then every vertex is in precisely one component. When you would obey directions, you're studying reachability instead of connectivity and this property doesn't hold anymore: in a->b->c, you'd get {a,b,c}, {b,c}, {c}.

Regards,
Ernst

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

[jgrapht-users] KShortestPaths performance

[Charles G. <cg...@lh...>]

Hi All

I'm new to jgrapht, have just downloaded it today to try out the k-shortest paths algorithm.

I made a simple test program to load up my network graph (happens to be road data) as a SimpleDirectedWeightedGraph which has about 60500 vertices and 97000 edges.

I then ran the KShortestPaths algorithm in a loop with the number of paths ranging from 1 to 10.  It takes 8 or 9 seconds to calculate one path, 24 for 2, 42 for 3, and so on until 10 takes 3.5 to 4 minutes. The paths are roughly 145 - 155 edges in length.

This is way too slow for my needs. Is there any way I can optimize this?  I'm guessing the answer is going to be to reduce my graph size to all that is necessary, and I'll try that next. I'm just afraid that the overhead of creating a new graph for every KShortestPaths is going to be pretty high as well (it takes about 30 seconds to load the whole graph from a database and I'll have to do a query to get the network data inside a bounding box containing the start and end points including some buffer)

TIA,
charles

Re: [jgrapht-users] Connectivity of Directed Graphs

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

This gives a list of neighbours but I want to have all reachable vertices (not only neighbours).
Of course it would be possible to write a simple algorithm that uses this function to create such a list.

Thanks
Uli

-----Ursprüngliche Nachricht-----
Von: Joris Kinable [mailto:de...@gm...]
Gesendet: Mittwoch, 31. August 2011 15:45
An: Wielant, Ulrich
Cc: jgr...@li...
Betreff: Re: [jgrapht-users] Connectivity of Directed Graphs

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
>

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] Connectivity of Directed Graphs

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

Ernst,

you are right! That's exactly what I was looking for.
I didn't think of using these iterators because they are used in the ConnectivityInspector. But the ConnectivityInspector uses an UndirectedGraph even if it is called with a DirectedGraph.

Does that make sense? Wouldn't it be better if the ConnectivityInspector respects the directions in a DirectedGraph?
Maybe one has to implement a new Inspector. The current ConnectivityInspector cannot be inherited for this because the graph field is private and could not be modified. So it seems that it has to be copied and only the constructor has to be changed:
    public ConnectivityInspector(DirectedGraph<V, E> g)
    {
        init();
        // old:
        //  this.graph = new AsUndirectedGraph<V, E>(g);
        // new:
       this.graph = g;
    }

Uli

________________________________
Von: hnr...@gr... [mailto:hnr...@gr...]
Gesendet: Mittwoch, 31. August 2011 16:21
An: Wielant, Ulrich; 'jgr...@li...'
Betreff: Re: [jgrapht-users] Connectivity of Directed Graphs

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

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