Package sc.fiji.snt.analysis.graph

Class SparseDirectedWeightedGraph

java.lang.Object

org.jgrapht.graph.AbstractGraph<SWCPoint,SWCWeightedEdge>

org.jgrapht.graph.AbstractBaseGraph<SWCPoint,SWCWeightedEdge>

sc.fiji.snt.analysis.graph.SNTGraph<SWCPoint,SWCWeightedEdge>

sc.fiji.snt.analysis.graph.DirectedWeightedGraph

sc.fiji.snt.analysis.graph.SparseDirectedWeightedGraph

All Implemented Interfaces:

Serializable, Cloneable, org.jgrapht.Graph<SWCPoint,SWCWeightedEdge>

public class SparseDirectedWeightedGraph
extends DirectedWeightedGraph

Memory-efficient variant of DirectedWeightedGraph backed by a compressed sparse-row (CSR) adjacency representation (CsrDirectedSpecifics). Public surface is identical to DirectedWeightedGraph

Intended for the post-Fast-Marching forest produced by the disk-backed GWDT tracer, where the dense object-based specifics jgrapht uses by default can run to multi-gigabyte heaps for 10⁷+-vertex graphs. Per-vertex overhead with this class is on the order of 30 bytes vs ≈400 bytes for the efault FastLookupDirectedSpecifics.

Trade-off: getEdge(v1, v2) degrades from O(1) to O(out-degree of v1) because the per-pair edge index is gone.

Author:

Tiago Ferreira

See Also:

• CsrDirectedSpecifics
• CsrGraphSpecificsStrategy
• Serialized Form

Field Summary

Fields inherited from interface org.jgrapht.Graph

DEFAULT_EDGE_WEIGHT

Constructor Summary

Constructors

Constructor	Description
SparseDirectedWeightedGraph()	Creates an empty sparse directed-weighted graph.
SparseDirectedWeightedGraph(Collection<SWCPoint> nodes, boolean assignDistancesToWeight)	Builds a CSR-backed graph from a collection of SWC nodes.
SparseDirectedWeightedGraph(Tree tree)	Builds a CSR-backed graph from a Tree.
SparseDirectedWeightedGraph(Tree tree, boolean assignDistancesToWeight)	Builds a CSR-backed graph from a Tree, with an option to skip Euclidean edge-weight assignment.

Method Summary

Methods inherited from class sc.fiji.snt.analysis.graph.DirectedWeightedGraph

addVertex, assignEdgeWeightsEuclidean, getBPs, getBreadthFirstIterator, getBreadthFirstIterator, getComponents, getDepthFirstIterator, getDepthFirstIterator, getLongestPath, getLongestPathVertices, getNodesFromLeavesToRoot, getNodesFromRootToLeaves, getNodeStatistics, getNodeStatistics, getRoot, getShortestPath, getShortestPathVertices, getSimplifiedGraph, getSubgraph, getTips, getTopologicalOrderIterator, getTree, getTree, getTrees, getTreeWithSamePathStructure, init, scale, setRoot, show, sumEdgeWeights, updateVertexProperties, vertexSet

Methods inherited from class sc.fiji.snt.analysis.graph.SNTGraph

applyEdges, applyVertices, filterEdges, filterVertices, getEdgeColor, getEdgeColorRGBMap, getVertexColor, getVertexColorRGBMap, getVertexValue, getVertexValueMap, setEdgeColor, setVertexColor, setVertexValue

Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

addEdge, addEdge, addVertex, addVertex, clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeSource, getEdgeSupplier, getEdgeTarget, getEdgeWeight, getType, getVertexSupplier, incomingEdgesOf, inDegreeOf, iterables, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeSupplier, setEdgeWeight, setVertexSupplier, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph

assertVertexExist, containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.Graph

containsEdge, removeAllEdges, removeAllEdges, removeAllVertices, setEdgeWeight

Constructor Details

SparseDirectedWeightedGraph

public SparseDirectedWeightedGraph()

Creates an empty sparse directed-weighted graph. Edges are unweighted until AbstractBaseGraph.setEdgeWeight(E, double) or DirectedWeightedGraph.assignEdgeWeightsEuclidean() is called, matching DirectedWeightedGraph's default behavior.

SparseDirectedWeightedGraph

public SparseDirectedWeightedGraph(Tree tree)

Builds a CSR-backed graph from a Tree. Edge weights are set to inter-node Euclidean distances. Mirrors DirectedWeightedGraph(Tree) but uses ~20x less per-vertex memory. Useful when batching many StrahlerAnalyzer / TreeStatistics instances against large neuron collections.

Parameters:

tree - the source tree

Throws:

IllegalArgumentException - if tree contains multiple roots

SparseDirectedWeightedGraph

public SparseDirectedWeightedGraph(Tree tree,
 boolean assignDistancesToWeight)

Builds a CSR-backed graph from a Tree, with an option to skip Euclidean edge-weight assignment.

Parameters:

tree - the source tree

assignDistancesToWeight - if true, edge weights are set to inter-node Euclidean distances

Throws:

IllegalArgumentException - if tree contains multiple roots

SparseDirectedWeightedGraph

public SparseDirectedWeightedGraph(Collection<SWCPoint> nodes,
 boolean assignDistancesToWeight)

Builds a CSR-backed graph from a collection of SWC nodes. Mirrors DirectedWeightedGraph(Collection, boolean).

Parameters:

nodes - the SWC nodes

assignDistancesToWeight - if true, edge weights are set to inter-node Euclidean distances