Package org.drip.graph.core

Class Forest

java.lang.Object
org.drip.graph.core.Forest
Direct Known Subclasses:
KruskalForest
public class Forest
extends java.lang.Object
Forest holds a Map of Trees indexed by the Starting Vertex Names. The References are:

  • Bollobas, B. (1998): Modern Graph Theory Springer
  • Eppstein, D. (1999): Spanning Trees and Spanners https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf
  • Gross, J. L., and J. Yellen (2005): Graph Theory and its Applications Springer
  • Kocay, W., and D. L. Kreher (2004): Graphs, Algorithms, and Optimizations CRC Press
  • Wikipedia (2020): Spanning Tree https://en.wikipedia.org/wiki/Spanning_tree




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    Forest()
    Forest Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean addTree​(java.lang.String treeName, Tree tree, DirectedGraph graph)
    Add a Named Tree to the Forest
    boolean conditionalMerge​(Edge edge, DirectedGraph graph)
    Conditionally Merge the Specified Source and Destination Trees of the Edge
    Tree containingTree​(java.lang.String vertexName)
    Retrieve the Tree that contains the specified Vertex
    java.util.Map<java.lang.String,​java.lang.String> containingTreeNameMap()
    Retrieve the Map of Containing Tree Names
    boolean containsVertex​(java.lang.String vertexName)
    Indicate if the Vertex is Contained in the Forest
    double length()
    Retrieve the Length of the Forest
    java.util.Map<java.lang.String,​Tree> treeMap()
    Retrieve the Map of Trees in the Forest
    java.util.Set<java.lang.String> treeNameSet()
    Retrieve the Set of the Tree Names
    boolean unitVertexTree​(java.lang.String vertexName, DirectedGraph graph)
    Create and add a Unit Vertex Tree into the Forest
    java.util.Set<java.lang.String> vertexSet()
    Retrieve the Set of Vertexes

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Forest

      public Forest()
      Forest Constructor

  • Method Details

    • treeMap

      public java.util.Map<java.lang.String,​Tree> treeMap()
      Retrieve the Map of Trees in the Forest
      Returns:
      Map of Trees in the Forest

    • containingTreeNameMap

      public java.util.Map<java.lang.String,​java.lang.String> containingTreeNameMap()
      Retrieve the Map of Containing Tree Names
      Returns:
      Map of Containing Tree Names

    • vertexSet

      public java.util.Set<java.lang.String> vertexSet()
      Retrieve the Set of Vertexes
      Returns:
      The Set of Vertexes

    • unitVertexTree

      public boolean unitVertexTree​(java.lang.String vertexName, DirectedGraph graph)
      Create and add a Unit Vertex Tree into the Forest
      Parameters:
      vertexName - Vertex Name
      graph - Parent Graph
      Returns:
      TRUE - The Unit Vertex Tree successfully added into the Forest

    • addTree

      public boolean addTree​(java.lang.String treeName, Tree tree, DirectedGraph graph)
      Add a Named Tree to the Forest
      Parameters:
      treeName - The Tree Name
      tree - The Tree
      graph - The Graph
      Returns:
      TRUE - The Keyed Tree successfully added to the Forest

    • treeNameSet

      public java.util.Set<java.lang.String> treeNameSet()
      Retrieve the Set of the Tree Names
      Returns:
      The Set of the Tree Names

    • containsVertex

      public boolean containsVertex​(java.lang.String vertexName)
      Indicate if the Vertex is Contained in the Forest
      Parameters:
      vertexName - The Vertex Name
      Returns:
      TRUE - The Vertex is Contained in the Forest

    • containingTree

      public Tree containingTree​(java.lang.String vertexName)
      Retrieve the Tree that contains the specified Vertex
      Parameters:
      vertexName - The Vertex Name
      Returns:
      Tree that contains the specified Vertex

    • conditionalMerge

      public boolean conditionalMerge​(Edge edge, DirectedGraph graph)
      Conditionally Merge the Specified Source and Destination Trees of the Edge
      Parameters:
      edge - The Edge
      graph - The Graph
      Returns:
      TRUE - The Source and the Destination Trees successfully conditionally merged

    • length

      public double length()
      Retrieve the Length of the Forest
      Returns:
      Length of the Forest