Graph Tutorial 1

Table of Contents

1. Graphing Terms
2. Creating and using a Graph

The GeoTools project strives to support as many geographical data formats and opperations as possible.

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.

1. 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"

2. Creating and using a Graph

Graph creations 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;