## geotools-gt2-users

 [Geotools-gt2-users] Use of Graph Traversal From: Pete Ballack - 2009-03-25 15:20:22 ```Hi everybody, first of all, sorry for the unclear subject. Second I'm NOT looking on how to use AStar or Dijkstra – I think the documentation is sufficient here. I build a graph representing a road network – done. Now I have a few LineStrings. I want to find the edges that follow a LineString best. But the LineStrings do NOT match the edges in the graph a 100%. Therefore I want to do some geometrical (distance) and topological (based on the road network) matching to find the best path. I believe the BradthFirstIterator or the BradthFirstTopologicalIterator could solve it. My problem is that I don't really get the idea on how to use the graph-api (how the iterator, traversal, walker and visitor interact with each other). I'm studying the graph-package source code including the unit test to figure it out, but... for more than two days now :-( So far, I can find the starting edge (I select the edge with the closest distance to the first coordinate in the LineString – I know, that it doesn't cover all cases, but it'll do to get started.) How do I traverse the Graph from the starting edge? I need to select all connecting edges and pick the one matching my LineString best... Thanks Pete ```
 Re: [Geotools-gt2-users] Use of Graph Traversal From: Justin Deoliveira - 2009-03-25 19:33:53 ```Hi Pete, Interesting problem. The first thing that comes to mind is to use Disjkstras shortest path, but provide a custom weight function. (see DijkstraIterator.EdgeWeighter). So the basic strategy would be to find the two nodes which are closest to the start and end of the line string. It sounds like you already have this done. Then you create the path finder, and the custom weighter should weight the edges at any particular point on how well they match the line string. The best way to do this is probably to sample along the edge and do an average distance to the line string. That should bias the path found by the dijkstra to the line string you are matching against. Does that make any sense? In terms of the interaction between the iterator, traversal, walker, and visitor (i apologies, the graph module was my first real geotools work at a time in which i felt i necessary to apply every pattern in the book to it :)): Vistor: standard visitor Walker: Visitor on sterioids, basically a bit more functionality which allows the vistior to somewhat control the order in which graph components are visited Iterator: The algorithm which defines the overall order in which components are visited Traversal: Ties together the walker and iterator, a mediator of sorts. -Justin Pete Ballack wrote: > Hi everybody, > > first of all, sorry for the unclear subject. > Second I'm NOT looking on how to use AStar or Dijkstra – I think the > documentation is sufficient here. > > I build a graph representing a road network – done. > > Now I have a few LineStrings. I want to find the edges that follow a > LineString best. But the LineStrings do NOT match the edges in the > graph a 100%. Therefore I want to do some geometrical (distance) and > topological (based on the road network) matching to find the best > path. > > I believe the BradthFirstIterator or the > BradthFirstTopologicalIterator could solve it. My problem is that I > don't really get the idea on how to use the graph-api (how the > iterator, traversal, walker and visitor interact with each other). > > I'm studying the graph-package source code including the unit test to > figure it out, but... for more than two days now :-( > > So far, I can find the starting edge (I select the edge with the > closest distance to the first coordinate in the LineString – I know, > that it doesn't cover all cases, but it'll do to get started.) > > How do I traverse the Graph from the starting edge? I need to select > all connecting edges and pick the one matching my LineString best... > > Thanks > Pete > > ------------------------------------------------------------------------------ > Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are > powering Web 2.0 with engaging, cross-platform capabilities. Quickly and > easily build your RIAs with Flex Builder, the Eclipse(TM)based development > software that enables intelligent coding and step-through debugging. > Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com > _______________________________________________ > Geotools-gt2-users mailing list > Geotools-gt2-users@... > https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users -- Justin Deoliveira OpenGeo - http://opengeo.org Enterprise support for open source geospatial. ```