Graphstream – a Java Graph API

I stumbled upon Graphstream while looking for a Graph (not to be confused with Chart) API for Java. My use case was simple: mesh network analysis and planning: how nodes in a given network are, who can see each other and how strong is the mesh, or how many paths  there are for a given node.

Such use cases have the “smell” of graphs: the network nodes are your graph Nodes, the network link between the network nodes are the graph Edges, and you can then do a lot of analysis: calculate critical paths and nodes that are central to the mesh network – such nodes are good candidates as routing/gateway points.

Graphstream is very flexible: you create Nodes and Edges using the default implementation or your own factories. Nodes and Edges have attributes and some have special meanings, like “xy” is a double[] that can be used for positioning the nodes when visualizing the graph (and Graphstream has a very good visualization API). But you’re really free to do a whatever with your graph. They also have lots of algorithms for graphs already implemented (which saved me some time!)

The API has lots of methods to iterate over nodes and edges, and this is a boon to use with Java 8 Streams API. But this also shows one of the shortcomings I found in it: the API iterations are not so much thread safe: because it propagates changes (like a new attribute value) using non-synchronized queues, you can’t use parallelStream() – stick to stream().

Another shortcoming that had me scratching my head is how to remove nodes and edges: you can do so using strings (the ID) or passing an object. But using an object actually tries to use an internal number that may not remove what you want… So keep to strings. One thing that I normally do is have a nice Stream going on. For example, removing edges that are not critical to the network (so they have the critical attribute set to false):

merged.getEdgeSet().stream().filter(e -> Boolean.FALSE.equals(e.getAttribute("critical"))).map(Edge::getId).collect(Collectors.toList()).forEach(id -> merged.removeEdge(id));

Ideas I have to expand this framework are to interact with NoSQL Graph Databases (which would allow graphs with millions loads with TBs of RAM…) and also disable (or make it optional) its event propagation system (because normally my graphs are static). More advanced, modify it to be more parallel in its calculations!

Let me know if you’re interested in more Graph examples and I can publish more!

Advertisements

How can I determine whether a 2D Point is within a Polygon?

Need to see if a given point is inside a polygon? This StackOverflow Q&A works pretty fine.

I used the one extracted from PNPOLY – Point Inclusion in Polygon Test by W. Randolph Franklin (WRF) and worked for my use case (converted to Java for my Polygon class in a boolean contains(x, y) method).

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}