A description is available at http://en.wikipedia.org/wiki/Strahler_number

The unit test functiontestClosenessCentrality2DUndirected is in error.

Double assertion should be checked with a delta value :

assertEquals(0.0055753940798198886,closenessCentralityDriver.
                getFieldValue(0, 1).
                getAsDouble() ,DELTA);

See orbisgis/orbisgis#560. I need to make the description a lot shorter for the following functions:

• ST_Accessibility
• ST_ConnectedComponents
• ST_StronglyConnectedComponents
• ST_Graph
• ST_GraphAnalysis
• ST_ShortestPath
• ST_ShortestPathLength
• ST_ShortestPathTree
• ST_StrahlerStreamOrder

Closeness centrality makes sense only on the strongly connected components of a graph. Add a function to calculate these.

Use JGraphT's StrongConnectivityInspector.

It will be better to use a table function so the user will be able to apply WHERE directly and filter on the result. This is possible since ST_ConnectedComponents returns only one table.

I already did this for AbstractExcecutorFunctions. Now I would like to do the same thing for TableFunctions.

Add an SQL function with the following behavior:

• Inputs:
  • edges

  • = 2 destination nodes

• Output: The nodes table with the id of the closest destination node (and optionally its distance to this node)

Calculation

A naive implementation would use Dijkstra to calculate the distance from each source node to all of the destination nodes and take the min. In practice, this will be too slow.

A better method is the following:

1. Pick a source node and execute Dijkstra until one of the destination nodes is encountered. This is the closest one. Store its id and distance.
2. For each node on the shortest path from the source node to the newly found destination node, store the id of and distance to the destination.
3. Repeat steps 1-2, except that at each step along Dijkstra, check if the node being examined already has a destination node id. If so, then store the same id, and store the distance to the destination of every node along the shortest path back to the source.

Note: This would be rather easy to implement in undirected networks starting from each of the destination nodes (using the calculateShortestPathsFromNode method and an adapted NodeBetweennessInfo). In directed networks, however, we have to start from each of the source nodes.

ST_ConnectedComponents seems to give the same output regardless of the graph orientation. This is using the JGraphT version?

Using DFS, it would be easy to implement my own version.

The current graph creators use only multigraphs, but for some algorithms we may need more general graphs (that allow loops, for example). In JGraphT, this is known as a (Directed)PseudoGraph. The graph creators should be refactored to allow for this; restrictions can be applied later as needed.

(Rethink the underlying JGraphT graph data structure (edge factory, node factory ...; node info).)

Once the graph creators are in place, refactor the old GDMS-Topology code to use them. This will eliminate a lot of code repetition that is currently present and reduce the possibility of introducing bugs. The code will be much easier to maintain.

Redo these functions to use Java Network Analyzer for routing.

Concretely, there will be two overloaded functions ST_ShortestPath (for returning geometries) and ST_ShortestPathLength (for returning distances).

Possible signatures

In every case, the user must either specify the weights column (for weighted graphs) or enter 1 (for unweighted graphs). The orientation is optional; the graph is considered directed if the user omits it.

• One-to-One Calculate the shortest path (or all shortest paths) from node 34 to node 83. (Note here: It would also be interesting to calculate all shortest paths within a given distance tolerance. That is, propose alternate "almost shortest" paths.)

ST_ShortestPath(edges, 34, 83, 'weights_column' OR 1[, orientation])

• One-to-All Calculate all shortest paths from node 34 (and hence produce a shortest path tree, or something like it if multiple shortest paths are allowed):

ST_ShortestPath(edges, 34, 'weights_column' OR 1[, orientation])

• Many-to-Many Calculate all shortest paths from every source to every destination contained in the table source_dest_table. This table must contain two columns, source and destination, containing node ids. (Use a Map<Integer, Set<V>> to keep track of sources and destinations?)

ST_ShortestPath(edges, source_dest_table, 'weights_column' OR 1[, orientation])

@ebocher @gpetit

While I already have unit tests for graph analyzers in JNA that GDMS-Toplogy uses, it would nevertheless be legitimate and useful to put write unit tests for GDMS-Topology's ST_GraphAnalysis (coupled with appropriate data, of course).

The default uses of ST_Graph must used the name of the table as prefix and not a system id.

The St_ShortestPath function must return a geometry set with a curve dimension constraint (equal to 1).
It seems done with the GraphMetadataFactory. createEdgeMetadataShortestPath() in GraphPath.findPathBetween2Nodes but the orbisgis renderer is not able to analyse this constraint and display a linesymbolizer but a point.
We must ensure that this tablefunction will be display like a line and may be relate this pb to SE core ?
@agueganno @agouge

If the optional argument orientation is omitted, we get an ArrayIndexOutOfBounds error.

In the current implementation, ST_Graph uses the order of the geometry coordinates to determine orientation. In addition, undirected edges are currently represented by two directed edges.

It would be nice to have the option of using a user-provided orientation field to determine orientation. That is, the user specifies in an added field whether the edge is to be oriented in the same sense as the order of the geometry coordinates (directed) or in the opposite order (reversed). The user may also specify that a given edge is to be undirected, and this undirected edge should be represented internally as a single undirected edge, not as two separate directed edges.

To simplify the code and increase maintainability, refactor ST_Graph to use the new function helpers.

This function uses a JGraphT Connectivity inspector. I need to write unit tests for both directed and undirected networks.

In OrbisGIS's Plugin Manager, GDMS-Topology doesn't have an icon yet.

ST_GraphAnalysis is currently an executor function, but as it returns only one table, it should be converted to a table function, using the new function helpers.

Given that GDMS is being replaced by H2, we will need to convert gdms-topology to h2-topology.

Given that for each node, we calculate the distance and number of shortest paths to every other node in the network, we should be able to calculate several extra network parameters at little added cost.

See Network Analyzer for ideas.

As of #61, edge betweenness has been implemented. This means that we will need to undo #46 to reverse the solution to #29, making ST_GraphAnalysis an ExecutorFunction again. It should register a nodes-centrality table and an edges-centrality table.

During the last wave of PRs, I had to redo the signatures of several functions (including ST_GraphAnalysis, ST_ShortestPathLength) to parse graph orientations (e.g., 'directed - edge_orientation_column'). I ended up with several methods (called parseStringArguments) doing the same thing. I need to put these all in one place to avoid duplicate code.

Connected components do not depend on edge weight, so we should remove 'weight' from the required parameters.

Write a beanshell script / tutorial on how to use the new ST_StrahlerStreamOrder function and post it to the wiki.