Package sc.fiji.snt.analysis.graph

Class DirectedWeightedGraph

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
All Implemented Interfaces:
Serializable, Cloneable, org.jgrapht.Graph<SWCPoint,SWCWeightedEdge>
Direct Known Subclasses:
SparseDirectedWeightedGraph
public class DirectedWeightedGraph extends SNTGraph<SWCPoint,SWCWeightedEdge>
Class for accessing a reconstruction as a graph structure.
Author:
Tiago Ferreira, Cameron Arshadi
See Also:

  • Constructor Details

    • DirectedWeightedGraph

      public DirectedWeightedGraph(Tree tree)
      Creates a DirectedWeightedGraph from a Tree with edge weights corresponding to inter-node distances.
      Parameters:
      tree - the Tree to be converted
      Throws:
      IllegalArgumentException - if Tree contains multiple roots

    • DirectedWeightedGraph

      public DirectedWeightedGraph(Tree tree, boolean assignDistancesToWeight)
      Creates a DirectedWeightedGraph from a Tree, with the option to assign edge weights corresponding to inter-node distances.
      Parameters:
      tree - the Tree to be converted
      assignDistancesToWeight - whether to assign inter-node distances between adjacent points as edge weights
      Throws:
      IllegalArgumentException - if Tree contains multiple roots

    • DirectedWeightedGraph

      public DirectedWeightedGraph()
      Creates an empty DirectedWeightedGraph. Edges added to the graph are unweighted until a weight is assigned manually.
      See Also:

    • DirectedWeightedGraph

      protected DirectedWeightedGraph(Supplier<SWCPoint> vertexSupplier, Supplier<SWCWeightedEdge> edgeSupplier, org.jgrapht.GraphType type, org.jgrapht.graph.GraphSpecificsStrategy<SWCPoint,SWCWeightedEdge> specificsStrategy)
      Subclass hook for installing a custom GraphSpecificsStrategy. Not part of the public API — used by SparseDirectedWeightedGraph to swap jgrapht's default FastLookupDirectedSpecifics for a CSR-backed variant without otherwise altering this class's behavior.

    • DirectedWeightedGraph

      public DirectedWeightedGraph(Collection<SWCPoint> nodes, boolean assignDistancesToWeight)
      Creates a DirectedWeightedGraph from a collection of reconstruction nodes.
      Parameters:
      nodes - the collections of SWC nodes
      assignDistancesToWeight - if true, inter-node Euclidean distances are used as edge weights

  • Method Details

    • init

      protected void init(Collection<SWCPoint> nodes, boolean assignDistancesToWeights)

    • getSimplifiedGraph

      public DirectedWeightedGraph getSimplifiedGraph()
      Returns a simplified graph in which slab nodes are removed and the graph is represented only by root, branch nodes and leaves. An edge weight in this graph corresponds to the sum of edge weights along the path between the corresponding vertices in the base graph.
      Returns:
      the simplified graph
      Throws:
      IllegalStateException - if the base graph does not have exactly one root

    • addVertex

      public SWCPoint addVertex(double x, double y, double z)

    • assignEdgeWeightsEuclidean

      public void assignEdgeWeightsEuclidean()
      For all edges, sets the Euclidean distance between the source and target vertex as the weight.

    • scale

      public void scale(double xScale, double yScale, double zScale, boolean updateEdgeWeightsEuclidean)
      Scales the point coordinates of each vertex by the specified factors.
      Parameters:
      xScale - the scaling factor for x coordinates
      yScale - the scaling factor for y coordinates
      zScale - the scaling factor for z coordinates
      updateEdgeWeightsEuclidean - if true, update all edge weights with inter-node Euclidean distances

    • sumEdgeWeights

      public double sumEdgeWeights()
      Gets the sum of all edge weights.
      Returns:
      the sum of all edge weights

    • getDepthFirstIterator

      public org.jgrapht.traverse.DepthFirstIterator<SWCPoint,SWCWeightedEdge> getDepthFirstIterator()
      Gets a DepthFirstIterator, using the graph root as start vertex.
      Returns:
      the DepthFirstIterator
      Throws:
      IllegalStateException - if the graph does not have exactly one root

    • getDepthFirstIterator

      public org.jgrapht.traverse.DepthFirstIterator<SWCPoint,SWCWeightedEdge> getDepthFirstIterator(SWCPoint startVertex)
      Gets a DepthFirstIterator, using the specified start vertex.
      Parameters:
      startVertex - the start vertex
      Returns:
      the DepthFirstIterator

    • getBreadthFirstIterator

      public org.jgrapht.traverse.BreadthFirstIterator<SWCPoint,SWCWeightedEdge> getBreadthFirstIterator()
      Gets a BreadthFirstIterator, using the graph root as start vertex.
      Returns:
      the BreadthFirstIterator
      Throws:
      IllegalStateException - if the graph does not have exactly one root

    • getBreadthFirstIterator

      public org.jgrapht.traverse.BreadthFirstIterator<SWCPoint,SWCWeightedEdge> getBreadthFirstIterator(SWCPoint startVertex)
      Gets a BreadthFirstIterator, using the specified start vertex.
      Parameters:
      startVertex - the start vertex
      Returns:
      the BreadthFirstIterator

    • getTopologicalOrderIterator

      public org.jgrapht.traverse.TopologicalOrderIterator<SWCPoint,SWCWeightedEdge> getTopologicalOrderIterator()
      Gets a TopologicalOrderIterator for this graph.
      Returns:
      the TopologicalOrderIterator

    • getLongestPath

      public Path getLongestPath(boolean useDirected)
      Return the sequence of nodes representing the longest shortest-path in the graph, as a Path.
      Parameters:
      useDirected - whether to treat the graph as directed. If true, the longest shortest-path will always include the root and a terminal node.
      Returns:
      the longest shortest-path
      Throws:
      IllegalStateException - if the graph does not have exactly one root

    • getLongestPathVertices

      public Deque<SWCPoint> getLongestPathVertices(boolean useDirected)
      Return the sequence of nodes representing the longest shortest-path in the graph, as a Deque. This eliminates the computational overhead of converting the vertex sequence to a Path object, if a Path is not desired.
      Parameters:
      useDirected - whether to treat the graph as directed. If true, the longest shortest-path will always include the root and a terminal node.
      Returns:
      the longest shortest-path
      Throws:
      IllegalStateException - if the graph does not have exactly one root

    • getShortestPath

      public Path getShortestPath(SWCPoint v1, SWCPoint v2)
      Gets the shortest path between source and target vertex as a Path object. Since underlying edge direction is ignored, a shortest path will always exist between any two vertices that share a connected component.
      Parameters:
      v1 - the source vertex
      v2 - the target vertex
      Returns:
      the shortest Path between source v1 and target v2, or null if no path exists
      Throws:
      IllegalArgumentException - if the graph does not contain both v1 and v2

    • getShortestPathVertices

      public Deque<SWCPoint> getShortestPathVertices(SWCPoint v1, SWCPoint v2)
      Gets the shortest path between source and target vertex as a Deque of SWCPoint objects. This eliminates the computational overhead of creating a Path object from the vertex sequence, if a Path is not desired. Since underlying edge direction is ignored, a shortest path will always exist between any two vertices that share a connected component.
      Parameters:
      v1 - the source vertex
      v2 - the target vertex
      Returns:
      the shortest path between source v1 and target v2, or null if no path exists
      Throws:
      IllegalArgumentException - if the graph does not contain both v1 and v2

    • updateVertexProperties

      public void updateVertexProperties()
      Re-assigns a unique Integer identifier to each vertex based on visit order during Depth First Search. Also updates the parent and previousPoint fields of each SWCPoint vertex contained in the Graph.
      Throws:
      IllegalStateException - if the graph does not contain exactly one root

    • getBPs

      public List<SWCPoint> getBPs()
      Gets the branch points (junctions) of the graph.
      Returns:
      the list of branch points

    • getTips

      public List<SWCPoint> getTips()
      Gets the end points (tips) of the graph.
      Returns:
      the list of end points

    • getNodeStatistics

      public NodeStatistics<SWCPoint> getNodeStatistics()
      Gets a NodeStatistics instance for the vertex set
      Returns:
      the NodeStatistics instance

    • getNodeStatistics

      public NodeStatistics<SWCPoint> getNodeStatistics(String type)
      Gets a NodeStatistics instance for the nodes in the vertex set of the specified type
      Parameters:
      type - the vertex type (e.g., "tips"/"end-points", "junctions"/"branch points", "all")
      Returns:
      the NodeStatistics instance

    • getRoot

      public SWCPoint getRoot()
      Gets the root of this graph.
      Returns:
      the root node.
      Throws:
      IllegalStateException - if the graph does not contain exactly one root

    • getTree

      public Tree getTree()
      Returns a new tree associated with this graph, using the current state of the graph to build the tree.
      Returns:
      the tree
      Throws:
      IllegalStateException - if the graph does not have exactly one root

    • getTree

      public Tree getTree(boolean createNewTree)
      Returns a tree associated with this graph.
      Parameters:
      createNewTree - If true, reassembles a tree from this graph's data. If false, returns the cached tree if it exists or null if it does not exist
      Returns:
      the tree

    • getTreeWithSamePathStructure

      public Tree getTreeWithSamePathStructure()
      Attempt to build a new Tree with the same Path hierarchy as the source Tree.
      Returns:
      the tree

    • getComponents

      public List<DirectedWeightedGraph> getComponents()
      Return the connected components of this graph as a list of new DirectedWeightedGraphs.
      Returns:
      the list of DirectedWeightedGraph objects

    • getTrees

      public List<Tree> getTrees()
      Return the connected components of this graph as a list of Trees
      Returns:
      the list of Tree objects

    • getSubgraph

      public DirectedWeightedSubgraph getSubgraph(Set<SWCPoint> nodeSubset)
      Returns the subgraph defined by the supplied subset of vertices, including their edges.
      Parameters:
      nodeSubset - a subset of this graph's vertex set
      Returns:
      the subgraph

    • vertexSet

      public Set<SWCPoint> vertexSet(char lr)
      Returns the subset of vertices contained in the given hemisphere
      Parameters:
      lr - the hemisphere (i.e., BrainAnnotation.LEFT_HEMISPHERE, BrainAnnotation.RIGHT_HEMISPHERE ,BrainAnnotation.ANY_HEMISPHERE
      Returns:
      the vertex subset

    • setRoot

      public void setRoot(SWCPoint newRoot)
      Sets the root of the tree. This modifies the edge directions such that all other nodes in the graph have the new root as ancestor.
      Parameters:
      newRoot - the new root of the tree, which must be an existing vertex of the graph
      Throws:
      IllegalArgumentException - if the graph does not contain newRoot

    • getNodesFromRootToLeaves

      public List<SWCPoint> getNodesFromRootToLeaves()

    • getNodesFromLeavesToRoot

      public List<SWCPoint> getNodesFromLeavesToRoot()

    • show

      public Window show()
      Displays this graph in a new instance of SNT's "Dendrogram Viewer".
      Returns:
      a reference to the displayed window.
      Throws:
      IllegalStateException - if the graph does not have exactly one root