I think Michael Michaud also used JgraphT for his OpeJUMP Plugin:
http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip but maybe it is already what you meant with JUMP plugin stefan _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Hi,
I have used JGraphT with JTS for a while and I can say it is *very* fast. I use it to find nodes of a linear network, degree* of each node, cycles... When using JTS+JGraphT, I consider linear features as the edges of the graph and first and last coordinates of their geometry as the nodes. It may not fit all needs as the graph has no node where features intersect if intersection point is not already the extremity of those features. I have to admit that I first tried to do this with pure JTS (avoiding to add a 500kb jar), but it appeared much more complex to use. Maybe some convenient methods around PlanarGraph class would have helped me achieve the same goal in pure JTS, but now, I'm no more sure there are much benefits working at the geometry level rather than at the feature level. My two cents Michaël * if you try to use it, note that I just discovered a bug which returns a degree 4 node at the end of a single looping edge (should be degree 2) Stefan Steiniger a écrit : > I think Michael Michaud also used JgraphT for his OpeJUMP Plugin: > > http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar > http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip > > but maybe it is already what you meant with JUMP plugin > > stefan > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > > _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Michael,
I agree with your experience that it's just as reasonable to work at the feature level rather than the geometry level. Graph-based algorithms are pretty much orthogonal to geometric algorithms, so there's not much to be gained from having the graph "know" about the geometry. The one exception is precisely for planar graphs - in this case, the geometry implies an ordering of edges around each node, which is important for various algorithms in JTS. Perhaps this is why you're seeing JGraphT being faster that JTS? There is a cost to computing the edge ordering, of course. Do you have some details of how JGraphT is easier to use than JTS? It would be nice for development if the JTS graph structures were as easy to use as possible. Michaël Michaud wrote: > Hi, > > I have used JGraphT with JTS for a while and I can say it is *very* fast. > I use it to find nodes of a linear network, degree* of each node, > cycles... > When using JTS+JGraphT, I consider linear features as the edges of the > graph and first and last coordinates of their geometry as the nodes. > It may not fit all needs as the graph has no node where features > intersect if intersection point is not already the extremity of those > features. > > I have to admit that I first tried to do this with pure JTS (avoiding > to add a 500kb jar), but it appeared much more complex to use. > Maybe some convenient methods around PlanarGraph class would have > helped me achieve the same goal in pure JTS, but now, I'm no more sure > there are much benefits working at the geometry level rather than at > the feature level. > > My two cents > > Michaël > > * if you try to use it, note that I just discovered a bug which > returns a degree 4 node at the end of a single looping edge (should be > degree 2) > > Stefan Steiniger a écrit : >> I think Michael Michaud also used JgraphT for his OpeJUMP Plugin: >> >> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar >> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip >> >> but maybe it is already what you meant with JUMP plugin >> >> stefan >> _______________________________________________ >> jts-devel mailing list >> [hidden email] >> http://lists.refractions.net/mailman/listinfo/jts-devel >> >> > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Hi Martin,
> I agree with your experience that it's just as reasonable to work at > the feature level rather than the geometry level. Graph-based > algorithms are pretty much orthogonal to geometric algorithms, so > there's not much to be gained from having the graph "know" about the > geometry. The one exception is precisely for planar graphs - in this > case, the geometry implies an ordering of edges around each node, > which is important for various algorithms in JTS. Sure ! I cannot remember if JGraphT has any code to manage an ordered list of incident edges, but It probably lack a lot of code to manage PlanarGraphs as it is needed by a library like JTS. > Perhaps this is why you're seeing JGraphT being faster that JTS? > There is a cost to computing the edge ordering, of course. Indeed, I wrote it is very fast, but I cannot affirm it is faster than JTS as I did not perform the same calculation with JTS. I just saw that computing graphs of large datasets (30000 features) takes only 1 second (I have a very new corei7) and do not need a lot of memory. > > Do you have some details of how JGraphT is easier to use than JTS? It > would be nice for development if the JTS graph structures were as easy > to use as possible. Here after is a small piece of code showing how I build a simple weighted graph from a feature collection. Stefan gave the adresse of the complete source code. After a graph is built, I can use any algorithm of the JGraphT library, then go back from the result (generally a set of nodes or a set of edges) to the underlying features. Michaël private static WeightedGraph<INode,FeatureAsEdge> add(WeightedGraph<INode,FeatureAsEdge> graph, Collection features, boolean dim3) { Coordinate[] cc; for (Iterator it = features.iterator() ; it.hasNext() ; ) { Feature f = (Feature)it.next(); Geometry g = f.getGeometry(); cc = f.getGeometry().getCoordinates(); INode node1 = dim3? new Node3D(cc[0]) : new Node2D(cc[0]); INode node2 = dim3? new Node3D(cc[cc.length-1]) : new Node2D(cc[cc.length-1]); graph.addVertex(node1); graph.addVertex(node2); FeatureAsEdge edge = new FeatureAsEdge(f); graph.addEdge(node1, node2, edge); graph.setEdgeWeight(edge, g.getLength()); } return graph; } > > > Michaël Michaud wrote: >> Hi, >> >> I have used JGraphT with JTS for a while and I can say it is *very* >> fast. >> I use it to find nodes of a linear network, degree* of each node, >> cycles... >> When using JTS+JGraphT, I consider linear features as the edges of >> the graph and first and last coordinates of their geometry as the >> nodes. It may not fit all needs as the graph has no node where >> features intersect if intersection point is not already the extremity >> of those features. >> >> I have to admit that I first tried to do this with pure JTS (avoiding >> to add a 500kb jar), but it appeared much more complex to use. >> Maybe some convenient methods around PlanarGraph class would have >> helped me achieve the same goal in pure JTS, but now, I'm no more >> sure there are much benefits working at the geometry level rather >> than at the feature level. >> >> My two cents >> >> Michaël >> >> * if you try to use it, note that I just discovered a bug which >> returns a degree 4 node at the end of a single looping edge (should >> be degree 2) >> >> Stefan Steiniger a écrit : >>> I think Michael Michaud also used JgraphT for his OpeJUMP Plugin: >>> >>> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar >>> http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip >>> >>> but maybe it is already what you meant with JUMP plugin >>> >>> stefan >>> _______________________________________________ >>> jts-devel mailing list >>> [hidden email] >>> http://lists.refractions.net/mailman/listinfo/jts-devel >>> >>> >> >> _______________________________________________ >> jts-devel mailing list >> [hidden email] >> http://lists.refractions.net/mailman/listinfo/jts-devel >> > _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Thanks, Michael.
I'm not sure there's any easy lesson for JTS here - except maybe that generics are a nice thing to have for graph libraries! Michaël Michaud wrote: > Hi Martin, > >> I agree with your experience that it's just as reasonable to work at >> the feature level rather than the geometry level. Graph-based >> algorithms are pretty much orthogonal to geometric algorithms, so >> there's not much to be gained from having the graph "know" about the >> geometry. The one exception is precisely for planar graphs - in this >> case, the geometry implies an ordering of edges around each node, >> which is important for various algorithms in JTS. > Sure ! I cannot remember if JGraphT has any code to manage an ordered > list of incident edges, but It probably lack a lot of code to manage > PlanarGraphs as it is needed by a library like JTS. >> Perhaps this is why you're seeing JGraphT being faster that JTS? >> There is a cost to computing the edge ordering, of course. > Indeed, I wrote it is very fast, but I cannot affirm it is faster than > JTS as I did not perform the same calculation with JTS. I just saw > that computing graphs of large datasets (30000 features) takes only 1 > second (I have a very new corei7) and do not need a lot of memory. >> >> Do you have some details of how JGraphT is easier to use than JTS? >> It would be nice for development if the JTS graph structures were as >> easy to use as possible. > Here after is a small piece of code showing how I build a simple > weighted graph from a feature collection. > Stefan gave the adresse of the complete source code. > After a graph is built, I can use any algorithm of the JGraphT > library, then go back from the result (generally a set of nodes or a > set of edges) to the underlying features. > > Michaël > > private static WeightedGraph<INode,FeatureAsEdge> > add(WeightedGraph<INode,FeatureAsEdge> graph, Collection > features, boolean dim3) { > Coordinate[] cc; > for (Iterator it = features.iterator() ; it.hasNext() ; ) { > Feature f = (Feature)it.next(); > Geometry g = f.getGeometry(); > cc = f.getGeometry().getCoordinates(); > INode node1 = dim3? new Node3D(cc[0]) : new Node2D(cc[0]); > INode node2 = dim3? new Node3D(cc[cc.length-1]) : new > Node2D(cc[cc.length-1]); > graph.addVertex(node1); > graph.addVertex(node2); > FeatureAsEdge edge = new FeatureAsEdge(f); > graph.addEdge(node1, node2, edge); > graph.setEdgeWeight(edge, g.getLength()); > } > return graph; > } > _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Free forum by Nabble | Edit this page |