Added by Rueben Schulz, last edited by Justin Deoliveira on Sep 30, 2007  (view change)

Labels

 
(None)

this is a work in progress

The geotools2 graph package defines the concept of a graph (or network) made up of geotools2 Features. The graph module strives to provide a convient flexable and performant API for graph construction and query.

In additional to generic Graph support, Networks based on LineStrings and Directed Networks have been implementations.

Graphing Terms

The Graph module makes use of concepts and (classes) from the geotools2 core:

  • Feature - atomic unit of geographic information
  • FeatureType - keeps track of what attributes each Feature can hold
  • FeatureID - a unique id associated with each Feature (must start with a non-numeric character)

In addition to the Feature API from core, the graph module makes use of relationships. Usually relationships are based on spatial comparisions between features.

Example Relationships:

  • Graph constructed from LineStrings based on "shared end points"
  • Graph constructed from Polygons based on "touches"

Creating and using a Graph

Graph creation is handled using a Graph Builder. For those familliar with the Builder Pattern (GOF Design Patterns) this will look familliar.

Example of building a Line network:

LineGraphBuilder lgb = new LineGraphBuilder();
FeatureSource fs = (FeatureSource)layers.get(typeName);
FeatureResults fr = fs.getFeatures();
FeatureCollection fc = fr.collection();
FeatureIterator f = fc.features();
while(f.hasNext()){
  Feature ft = f.next();
  if(envelope.contains(ft.getBounds()))
    lgb.add(ft);
}
// lgb is loaded
Graph g = lgb.build();

To make use of your graph we will use a GraphVisitor (this is the usual GOF Visitor pattern):

Example of making use of the network:

class OrphanVisitor implements GraphVisitor{
  private int count = 0;
  public int getCount(){return count;}
  public int visit(GraphComponent element){
    if(element.getAdjacentElements().size()==0)
      count++;
    results.error(element.getFeature(),"Orphaned");
    return GraphTraversal.CONTINUE;
  }
}
OrphanVisitor ov = new OrphanVisitor();
SimpleGraphWalker sgv = new SimpleGraphWalker(ov);
BasicGraphTraversal bgt = new BasicGraphTraversal(g,sgv);
bgt.walkNodes();
if(ov.getCount()==0)
  return true;
else
  return false;

Building Graph from a FeatureCollection

This example can be used if you want to build a graph from a feature collection made up of linear features. This example can
be used in geotools 2.3.x and up.

// get a feature collection somehow
FeatureCollection fCollection = ...
 
//create a linear graph generate
LineStringGraphGenerator lineStringGen = new LineStringGraphGenerator();

//wrap it in a feature graph generator
FeatureGraphGenerator featureGen = new FeatureGraphGenerator( lineStringGen );

//throw all the features into the graph generator
Iterator iter = fCollection.iterator();
while(iter.hasNext()){
     Feature feature = (Feature)iter.next();
     featureGen.add( feature );
}

Graph g = featureGen.getGraph()

Building Graph from Line Segments

This example can be used to build a graph from just a set of line segments.

//we have some line segments 
LineSegment[] lines = ...

//create the graph generator
BasicLineGraphGenerator graphGen = new BasicLineGraphGenerator();

//add the lines to the graph
for ( int i = 0; i < lines.length; i++ ) {
  graphGen.add( lines[i] );
}

Graph graph = graphGen.getGraph()

Building Graph from Jump Layer

This example can be used, if you are Jump user and want to build a graph from jump layer.

BasicLineGraphGenerator graphGen = new BasicLineGraphGenerator();
BasicLineGraphBuilder lineGraphBuilder = new BasicLineGraphBuilder();
graphGen.setGraphBuilder(lineGraphBuilder);


//obtain the feature collection from the line layer
FeatureCollection fCollection  = lyr.getFeatureCollectionWrapper();
Iterator iter = fCollection.iterator();

Feature feature = null;
Geometry geom = null;
Graph graph = null;
Cooordinate[] coords ;
		
while(iter.hasNext()){
	
	feature = (Feature)iter.next();
	geom = (Geometry)feature.getGeometry();
	coords = geom.getCoordinates();
	LineSegment lsg = null;
	Coordinate p0 = null;
	Coordinate p1 = null;
		
	for(int i = 0; i< coords.length; i++){
		p0 = p1;
		p1 = coords[i];
		if(p0 != null){
			lsg = new LineSegment(p0,p1);
			graphGen.add(lsg);
		}
	}
}

graph = graphGen.getGraph();

Building a FeatureCollection from your Graph

Once the graph is built each, edge#getObject() will hold the original feature used to built it.

So you can traverse your graph and build up FeatureCollection as you go.

FeatureCollection features = FeatureCollections.newInstance();

for ( Iterator e = graph.getEdges().iterator(); e.hasNext(); ) {
  Edge edge = (Edge) e.next();
  Feature feature = (Feature) e.getObject();
  
  features.add( feature );
}

Finding the Shortest Path between two Nodes

The org.geotools.graph.path.DijkstraShortestPathFinder class can be used to calculate paths in a graph using Dijkstra's Shortest Path algorithm.

//reference to a graph, already built
Graph graph = ...

//find a source  node
Node source = ..

//create a strategy for weighting edges in the graph
DijkstraIterator.EdgeWeigter weighter = new DijkstraIterator.EdgeWeighter() {
   public double getWeight(Edge e) {
      return 1.0;  //constant
   }
}

//create the path finder
DijkstraShortestPathFinder pf = new DijkstraShortestPathFinder( graph, source, weighter );

//find some destinations to calculate paths to
List/*<Node>*/ destinations = ...

//calculate the paths
for ( Iterator d = destinations.iterator(); d.hasNext(); ) {
  Node destination = (Node) d.next();
  Path path = pf.getPath( destination );

  //do something with the path
}

Comments  (Hide Comments)

calculate() is missed in the last sample:

//create the path finder
DijkstraShortestPathFinder pf = new DijkstraShortestPathFinder( graph, source, weighter );
pf.calculate();

Posted by Oleksandr Chugai at Jul 30, 2008 04:31