DirectedGraph from SimpleFeatureCollection based on attribute

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

DirectedGraph from SimpleFeatureCollection based on attribute

thKous
Hi everybody,

I have a FeatureCollection loaded from a shapefile and create an undirected Graph out of it, using the code provided in:

http://docs.geotools.org/stable/userguide.old/extension/graph/index.html

To investigate if my Graph is connected I use a DijkstraShortestPathFinder as shown in the same link to fetch a path to each other node from a hand-picked start node. At the same time I can confirm that all nodes in my Graph have been visited.

The structure of my data though is so that some features can only be traversed in one direction and for the  DijkstraShortestPathFinder to fetch reasonable results I need to create a directed Graph from my FeatureCollection based on an attribute value in each feature.

Is there any example to provide as help on how to create a directed graph?

Thanks,
Thomas
Reply | Threaded
Open this post in threaded view
|

Re: DirectedGraph from SimpleFeatureCollection based on attribute

thKous
I managed to create a DirectedGraph using the DirectedLineStringGraphGenerator and FeatureGraphGenerator as follows:

public static DirectedGraph getDirectedGraph(SimpleFeatureCollection features) {

        final GeometryOperations geomOps = new GeometryOperations();
        final DirectedLineStringGraphGenerator lineStrGen = new DirectedLineStringGraphGenerator();
               
        SimpleFeatureIterator iterator = merged_features.features();
               
        try {
                while(iterator.hasNext()) {
                        SimpleFeature feature = iterator.next();
                        String bidirectional = feature.getAttribute("TYPE").toString();
                        Coordinate[] featureCoords = ((Geometry)feature.getDefaultGeometry()).getCoordinates();

                        Coordinate[] coords;
                        Geometry directedLineSegment;
                        DirectedEdge e;
                        //build edge based on feature type of segment
                       
                        if (bidirectional == "No") {
                        //create new lineString segment to add as directed edge
                        coords = new Coordinate[]{featureCoords[1], featureCoords[0]};

                        directedLineSegment = geomOps.coordinatesToLineGeometry(coords);
                        e = (DirectedEdge)lineStrGen.add(directedLineSegment);
                        e.setObject(feature);
                        if (!((Geometry)e.getInNode().getObject()).equals(geomOps.coordinateToPointGeometry(coords[0]))
||
!((Geometry)e.getOutNode().getObject()).equals(geomOps.coordinateToPointGeometry(coords[1]))) {
                        System.err.println("Slope segment " + ((SimpleFeature)e.getObject()).getAttribute("r_id") + " was falsely entered in directed graph");
}
                        } else {
                        coords = new Coordinate[]{featureCoords[1], featureCoords[0]};
                        directedLineSegment = geomOps.coordinatesToLineGeometry(coords);
                        e = (DirectedEdge)lineStrGen.add(directedLineSegment);
                        e.setObject((SimpleFeature) feature);
                                                       
                        coords = new Coordinate[]{featureCoords[0], featureCoords[1]};
                        directedLineSegment = geomOps.coordinatesToLineGeometry(coords);
                        e = (DirectedEdge)lineStrGen.add(directedLineSegment);
                        e.setObject((SimpleFeature) feature);
                        }
                catch (Exception e) {
                        Logger.getLogger(Logger.GLOBAL_LOGGER_NAME).log(Level.SEVERE, "Directed graph generation aborted: " + e);
                }
                finally {
                        iterator.close();
                }
               
                DirectedGraph graph = (DirectedGraph)featureGen.getGraph();
                return graph;
}

I realised that using a FeatureGraphGenerator to wrap the DirectedLineStringGraphGenerator and adding the features through the FeatureGraphGenerator like this : featureGen.add(feature)
won't result to directed edges somehow.

After having created the Directed graph I want to query some paths using the Dijkstra algorithm. To force the path finder to use a DirectedDijkstraIterator I realised I had to explicitly instantiate a PathFinder by providing a DirectedDijkstraIterator in the constructor parameters and set the source directly in the iterator object, as such:

                DirectedDijkstraIterator iterator = new DirectedDijkstraIterator(new DijkstraIterator.EdgeWeighter() {
                   public double getWeight(Edge e) {
                      SimpleFeature feature = (SimpleFeature) e.getObject();
                      LineString geometry = (LineString) feature.getDefaultGeometry();
                      return geometry.getLength();
                   }
                   });
                iterator.setSource(start);

                DijkstraShortestPathFinder pf = new DijkstraShortestPathFinder(directedGraph, iterator);
                pf.calculate();

                Path shortestPath = pf.getPath( destination );


Any other alternative I tried failed. This way it seems that the DijkstraShortestPathFinder  is providing the right results.

Please correct, if I have done something wrong.

Regards,
Thomas

thKous wrote
Hi everybody,

I have a FeatureCollection loaded from a shapefile and create an undirected Graph out of it, using the code provided in:

http://docs.geotools.org/stable/userguide.old/extension/graph/index.html

To investigate if my Graph is connected I use a DijkstraShortestPathFinder as shown in the same link to fetch a path to each other node from a hand-picked start node. At the same time I can confirm that all nodes in my Graph have been visited.

The structure of my data though is so that some features can only be traversed in one direction and for the  DijkstraShortestPathFinder to fetch reasonable results I need to create a directed Graph from my FeatureCollection based on an attribute value in each feature.

Is there any example to provide as help on how to create a directed graph?

Thanks,
Thomas