Building graph from shapefile and shortest path

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

Building graph from shapefile and shortest path

WarLord88
Hello everyone,
i'm working with Geotools and shapefiles and i was able to easily build graph using the code below:

    private Graph buildGraph(FeatureCollection fc) {
        LineStringGraphGenerator lineStringGen = new LineStringGraphGenerator();
        FeatureGraphGenerator featureGen = new FeatureGraphGenerator(lineStringGen);
        FeatureIterator iter = fc.features();

        while (iter.hasNext()) {
                        featureGen.add(f);
        }

        iter.close();

        return featureGen.getGraph();
    }

I can search for shortest path between two points using both dijkstra and AStar algorithms:

    private Path dijkstraShortestPath(Node from, Node to) {
        DijkstraShortestPathFinder pf = new DijkstraShortestPathFinder(graph, from, weighter);
        pf.calculate();
        return pf.getPath(to);
    }

    private Path aStarShortestPath(Node from, Node to) {
        if (parameters.get(LENGTH_FIELD_NAME) == null || parameters.get(LENGTH_FIELD_NAME).trim().length() == 0) {
            createAStarFuncEx(to);
        } else {
            createAStarFunc(to);
        }
        AStarShortestPathFinder pf = new AStarShortestPathFinder(graph, from, to, astarfunc);
        pf.calculate();
        Path path = null;
        try {
            path = pf.getPath();
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
        return path;
    }

    private void createEdgeWeighter() {
        this.weighter = new DijkstraIterator.EdgeWeighter() {

            public double getWeight(Edge e) {
                return (Double) ((SimpleFeature) e.getObject()).getAttribute(parameters.get(LENGTH_FIELD_NAME));
            }
        ;
    }

    ;
    }

    private void createEdgeWeighterEx() {
        this.weighter = new DijkstraIterator.EdgeWeighter() {

            public double getWeight(Edge e) {
                return ((Geometry) ((SimpleFeature) e.getObject()).getDefaultGeometry()).getLength();
            }
        ;
    }

    ;
    }

    private void createAStarFunc(Node nodeTo) {

        this.astarfunc = new AStarIterator.AStarFunctions(nodeTo) {

            @Override
            public double cost(AStarNode asnFrom, AStarNode adnTo) {
                return (Double) ((SimpleFeature) (asnFrom.getNode().getEdge(adnTo.getNode())).getObject()).getAttribute(parameters.get(LENGTH_FIELD_NAME));
            }

            @Override
            public double h(Node node) {
                Point p1 = ((Point) node.getObject());
                Point p2 = ((Point) getDest().getObject());
                return 1.18 * Math.sqrt((p1.getX() - p2.getX()) * (p1.getX() - p2.getX()) + (p1.getY() - p2.getY()) * (p1.getY() - p2.getY()));
            }
        };
    }

    private void createAStarFuncEx(Node nodeTo) {

        this.astarfunc = new AStarIterator.AStarFunctions(nodeTo) {

            @Override
            public double cost(AStarNode asnFrom, AStarNode adnTo) {
                return ((Geometry) ((SimpleFeature) (asnFrom.getNode().getEdge(adnTo.getNode())).getObject()).getDefaultGeometry()).getLength();
            }

            @Override
            public double h(Node node) {
                Point p1 = ((Point) node.getObject());
                Point p2 = ((Point) getDest().getObject());
                return 1.18 * Math.sqrt((p1.getX() - p2.getX()) * (p1.getX() - p2.getX()) + (p1.getY() - p2.getY()) * (p1.getY() - p2.getY()));
            }
        };
    }

I have the following questions:

     - The path returned by algorithms is presented in reverse order (from destination to origin), is this correct?
     - How can i take into account directions during path search? (e.g. oneway)
     - I have a shapefile from Teleatlas with ONEWAY, F_JCNTID, T_JCNTID and other useful properties, how can i use them to create a directed graph?

Any help wil be appreciated.
Thanks.
Reply | Threaded
Open this post in threaded view
|

Re: Building graph from shapefile and shortest path

richisonaliya
This post has NOT been accepted by the mailing list yet.
hello ,
    even i am fasing same thing but i want to ask you that how you take a input node (in code node start) cos graph is generated from SimplefeatureSource... and in ShowMap(map) its displaying the SempleFeatureSource in form of MapContext so for taking input for user for start node what should i do ??? means i can select feature from JMapFrame but how to relate it with Graph node ....
i have tested the code by taking manualy start and destination node and it is working fine ...but having trouble for this user input node .....
code for Start and destination node

 Graph graph = featureGen.getGraph();
                       
 DijkstraIterator.EdgeWeighter weighter = new DijkstraIterator.EdgeWeighter()
                {
      public double getWeight(Edge e)
        {
                 SimpleFeature feature = (SimpleFeature) e.getObject();
                         Geometry geometry = (Geometry)feature.getDefaultGeometry();
                                 return geometry.getLength();
                        }
                 };
       
       
                        // -- to do --
             Node start = (Node)graph.getNodes().toArray()[0];
             System.out.println("starting nod = "+start);
             // Create GraphWalker - in this case DijkstraShortestPathFinder
             DijkstraShortestPathFinder pf = new DijkstraShortestPathFinder( graph, start, weighter );
             pf.calculate();
             //find some destinations to calculate paths to
             List<Node> destinations = new ArrayList<Node>();
             destinations.add((Node)graph.getNodes().toArray()[3]);
             // destinations.add((Node)graph.getNodes().toArray()[7]);
             System.out.println("destinations = "+destinations);  
             for ( Iterator d = destinations.iterator(); d.hasNext(); )
            {
              Node destination = (Node) d.next();
                path= pf.getPath( destination );
                System.out.println("path size = "+path.size());
                if(path!=null)
                System.out.println("Path ="+path.toString());
                else
                System.out.println("Path =null");  
                        }
Reply | Threaded
Open this post in threaded view
|

Re: Building graph from shapefile and shortest path

richisonaliya
This post has NOT been accepted by the mailing list yet.
hello again
     we can select the feature from the JMapframe but how to relate it with the generated graph plese help me out for that i am very new to geotools ....
Reply | Threaded
Open this post in threaded view
|

Re: Building graph from shapefile and shortest path

richisonaliya
This post has NOT been accepted by the mailing list yet.
i finally solved it thanks for every thing....