sc.fiji.analyzeSkeleton.ita

Class GraphPruning

java.lang.Object

sc.fiji.analyzeSkeleton.ita.GraphPruning

public final class GraphPruning
extends Object

Utility functions for pruning certain kinds of edges (and nodes) from a Graph.

Author:

Richard Domander (Royal Veterinary College, London), Alessandro Felder (Royal Veterinary College, London)

Method Summary

Modifier and Type	Method and Description
static net.imglib2.util.ValuePair<Graph,double[]>	pruneShortEdges(Graph graph, double minDistance, boolean iterate, boolean clustered) Creates a copy of the graph, where short edges have been removed.
static net.imglib2.util.ValuePair<Graph,double[]>	pruneShortEdges(Graph graph, double minDistance, boolean iterate, boolean clustered, double[] voxelSize) Creates a copy of the graph, where short edges have been removed.
static void	removeLoops(Graph graph) Removes all loop edges from the graph.
static void	removeParallelEdges(Graph graph) Removes parallel edges from the graph, leaving at most one connection between each vertex pair.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

pruneShortEdges

public static net.imglib2.util.ValuePair<Graph,double[]> pruneShortEdges(Graph graph,
                                                                         double minDistance,
                                                                         boolean iterate,
                                                                         boolean clustered)

Creates a copy of the graph, where short edges have been removed.

Calls pruneShortEdges(Graph, double, boolean, boolean, double[]) with isotropic voxel size {1.0, 1.0, 1.0}.

Parameters:

graph - a graph from a skeleton.

minDistance - minimum distance between the end points of preserved edges.

iterate - if true then the graph is pruned iteratively until no new short edges are found. This can alter the topology of the graph more dramatically. If false, then the graph is pruned just once. It may still contain short edges that were created by the pruning process.

clustered - if true then the method first finds all the sub-graphs where the vertices are connected to each other by short edges only. Each such sub-graph is then reduced to a single vertex at its center. If false, then each short edge is pruned individually. In this case the end result is affected by the order in which the edges are traversed.

Returns:

a pruned copy of the graph and the following pruning statistics: % loop edges, % dead ends, % parallel edges, % other pruned edges and total number of edges in the original graph. The percentages are in relation to the total edges.

See Also:

pruneShortEdges(Graph, double, boolean, boolean, double[])

pruneShortEdges

public static net.imglib2.util.ValuePair<Graph,double[]> pruneShortEdges(Graph graph,
                                                                         double minDistance,
                                                                         boolean iterate,
                                                                         boolean clustered,
                                                                         double[] voxelSize)

Creates a copy of the graph, where short edges have been removed.

Edges are removed, if the distance between their end points is less than the given limit. NB Edge may be arched, and its length can be greater than this distance. When the method removes an edge, it creates a new Vertex that's at the center of the end points of the Edge. If pruning is clustered (see below) then the vertex is at the the center of all the vertices removed. The new vertex connects to all the vertices the deleted vertices connected to. For example, if an edge between the vertices A & B is removed, and they connected to C & D and E & F respectively, then the new vertex A' connects to C, D, E and F. If one end vertex of a short edge is a "dead end", that is, it connects to no other edges, then it is simply deleted.

The method also removes parallel and loop edges.

Parameters:

graph - a graph from a skeleton.

minDistance - minimum distance between the end points of preserved edges.

iterate - if true then the graph is pruned iteratively until no new short edges are found. This can alter the topology of the graph more dramatically. If false, then the graph is pruned just once. It may still contain short edges that were created by the pruning process.

clustered - if true then the method first finds all the sub-graphs where the vertices are connected to each other by short edges only. Each such sub-graph is then reduced to a single vertex at its center. If false, then each short edge is pruned individually. In this case the end result is affected by the order in which the edges are traversed.

voxelSize - [x, y, z] voxel size in the skeleton image from which the graph was created. Affects the distance calculations between vertices.

Returns:

a pruned copy of the graph and the following pruning statistics: % loop edges, % dead ends, % parallel edges, % other pruned edges and total number of edges in the original graph. The percentages are in relation to the total edges.

See Also:

isLoop(Edge), isDeadEnd(Edge), removeParallelEdges(Graph)

removeLoops

public static void removeLoops(Graph graph)

Removes all loop edges from the graph.

Parameters:

graph - a graph.

See Also:

isLoop(Edge)

removeParallelEdges

public static void removeParallelEdges(Graph graph)

Removes parallel edges from the graph, leaving at most one connection between each vertex pair.

While the input graph might already have parallel edges, creating them is a side effect how the graph is pruned in pruneDeadEnds(Graph, double). Note that the method is already called there, so there's no need for the user to explicitly call it afterwards.

An edge is parallel, if there's another edge between its endpoint vertices.

NB non-deterministic in choosing which of the parallel edges is kept.

Parameters:

graph - A Graph that's assumed undirected