Package ghidra.util.graph

# Class AbstractDependencyGraph<T>

java.lang.Object
ghidra.util.graph.AbstractDependencyGraph<T>

Type Parameters:
  `T` - the type of value. Some concrete classes might have restrictions on T.

Direct Known Subclasses:
  `DependencyGraph`, `DeterministicDependencyGraph`

public abstract class AbstractDependencyGraph<T> extends Object
Class for managing the visiting (processing) of a set of values where some values depend on other values being process before them. In other words, an acyclic directed graph will be formed where the vertexes are the values and the edges represent dependencies. Values can only be removed if they have no dependencies. Since the graph is acyclic, as values are removed that have no dependencies, other nodes that depend on those nodes will become eligible for processing and removal. If cycles are introduced, they will eventually cause an IllegalState exception to occur when removing and processing values. There is also a hasCycles() method that can be called before processing to find cycle problems up front without wasting time processing values.

See Also:
  - `DependencyGraph`
  - `DeterministicDependencyGraph`

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `protected class`
  `AbstractDependencyGraph.DependencyNode`

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `protected Map<T,AbstractDependencyGraph<T>.DependencyNode>`
  `nodeMap`
  `protected Set<T>`
  `unvisitedIndependentSet`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `AbstractDependencyGraph()`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `addDependency(T value1, T value2)`
  Add a dependency such that value1 depends on value2.
  `void`
  `addValue(T value)`
  Adds the value to this graph.
  `boolean`
  `contains(T value)`
  Returns true if this graph has the given key.
  `abstract AbstractDependencyGraph<T>`
  `copy()`
  Returns a copy of this graph.
  `protected abstract Set<AbstractDependencyGraph<T>.DependencyNode>`
  `createDependencyNodeSet()`
  Creates the Set of `AbstractDependencyGraph<T>.DependencyNode`s appropriate for the implementer.
  `protected abstract Map<T,AbstractDependencyGraph<T>.DependencyNode>`
  `createNodeMap()`
  Creates the Map of Nodes to `AbstractDependencyGraph<T>.DependencyNode`s appropriate for the implementer.
  `protected abstract Set<T>`
  `createNodeSet()`
  Creates the Set of Nodes appropriate for the implementer.
  `Set<T>`
  `getAllIndependentValues()`
  Returns the set of all values that have no dependencies regardless of whether or not they have been "visited" (by the getUnvisitedIndependentValues() method.
  `Set<T>`
  `getDependentValues(T value)`
  Returns a set of values that depend on the given value.
  `Map<T,AbstractDependencyGraph<T>.DependencyNode>`
  `getNodeMap()`
  `abstract Set<T>`
  `getNodeMapValues()`
  Returns the set of values in this graph.
  `Set<T>`
  `getUnvisitedIndependentValues()`
  Returns a set of all values that have no dependencies.
  `Set<T>`
  `getValues()`
  Returns the set of values in this graph.
  `boolean`
  `hasCycles()`
  Checks if this graph has cycles.
  `boolean`
  `hasUnVisitedIndependentValues()`
  Returns true if there are unvisited values ready (no dependencies) for processing.
  `boolean`
  `isEmpty()`
  Returns true if the graph has no values;
  `T`
  `pop()`
  Removes and returns a value that has no dependencies from the graph.
  `void`
  `remove(T value)`
  Removes the value from the graph.
  `int`
  `size()`
  Returns the number of values in this graph.

  ### Methods inherited from class java.lang.Object

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

- ## Field Details

  - ### nodeMap

    protected Map<T,AbstractDependencyGraph<T>.DependencyNode> nodeMap

  - ### unvisitedIndependentSet

    protected Set<T> unvisitedIndependentSet

- ## Constructor Details

  - ### AbstractDependencyGraph

    public AbstractDependencyGraph()

- ## Method Details

  - ### getNodeMap

    public Map<T,AbstractDependencyGraph<T>.DependencyNode> getNodeMap()

  - ### createNodeMap

    protected abstract Map<T,AbstractDependencyGraph<T>.DependencyNode> createNodeMap()
    Creates the Map of Nodes to `AbstractDependencyGraph<T>.DependencyNode`s appropriate for the implementer.
    Returns:
      a new Map of Nodes to `AbstractDependencyGraph<T>.DependencyNode`s.

  - ### createNodeSet

    protected abstract Set<T> createNodeSet()
    Creates the Set of Nodes appropriate for the implementer.
    Returns:
      a new Set of Nodes.

  - ### createDependencyNodeSet

    protected abstract Set<AbstractDependencyGraph<T>.DependencyNode> createDependencyNodeSet()
    Creates the Set of `AbstractDependencyGraph<T>.DependencyNode`s appropriate for the implementer.
    Returns:
      a new Set of `AbstractDependencyGraph<T>.DependencyNode`s.

  - ### copy

    public abstract AbstractDependencyGraph<T> copy()
    Returns a copy of this graph.
    Returns:
      a copy of this graph.

  - ### addValue

    public void addValue(T value)
    Adds the value to this graph.
    Parameters:
      `value` - the value to add

  - ### size

    public int size()
    Returns the number of values in this graph.
    Returns:
      the number of values in this graph.

  - ### isEmpty

    public boolean isEmpty()
    Returns true if the graph has no values;
    Returns:
      true if the graph has no values;

  - ### contains

    public boolean contains(T value)
    Returns true if this graph has the given key.
    Parameters:
      `value` - the value to check if its in this graph
    Returns:
      true if this graph has the given key.

  - ### getValues

    public Set<T> getValues()
    Returns the set of values in this graph.
    Returns:
      the set of values in this graph.

  - ### getNodeMapValues

    public abstract Set<T> getNodeMapValues()
    Returns the set of values in this graph.
    Returns:
      the set of values in this graph.

  - ### addDependency

    public void addDependency(T value1, T value2)
    Add a dependency such that value1 depends on value2. Both value1 and value2 will be added to the graph if they are not already in the graph.
    Parameters:
      `value1` - the value that depends on value2
      `value2` - the value that value1 is depending on

  - ### hasUnVisitedIndependentValues

    public boolean hasUnVisitedIndependentValues()
    Returns true if there are unvisited values ready (no dependencies) for processing.
    Returns:
      true if there are unvisited values ready for processing.
    Throws:
      `IllegalStateException` - is thrown if the graph is not empty and there are no nodes without dependency which indicates there is a cycle in the graph.

  - ### pop

    public T pop()
    Removes and returns a value that has no dependencies from the graph. If the graph is empty or all the nodes without dependencies are currently visited, then null will be returned. NOTE: If the getUnvisitedIndependentValues() method has been called(), this method may return null until all those "visited" nodes are removed from the graph.
    Returns:
      return an arbitrary value that has no dependencies and hasn't been visited or null.

  - ### hasCycles

    public boolean hasCycles()
    Checks if this graph has cycles. Normal processing of this graph will eventually reveal a cycle and throw an exception at the time it is detected. This method allows for a "fail fast" way to detect cycles.
    Returns:
      true if cycles exist in the graph.

  - ### getUnvisitedIndependentValues

    public Set<T> getUnvisitedIndependentValues()
    Returns a set of all values that have no dependencies. As values are removed from the graph, dependencies will be removed and additional values will be eligible to be returned by this method. Once a value has been retrieved using this method, it will be considered "visited" and future calls to this method will not include those values. To continue processing the values in the graph, all values return from this method should eventually be deleted from the graph to "free up" other values. NOTE: values retrieved by this method will no longer be eligible for return by the pop() method.
    Returns:
      the set of values without dependencies that have never been returned by this method before.

  - ### getAllIndependentValues

    public Set<T> getAllIndependentValues()
    Returns the set of all values that have no dependencies regardless of whether or not they have been "visited" (by the getUnvisitedIndependentValues() method.
    Returns:
      return the set of all values that have no dependencies.

  - ### remove

    public void remove(T value)
    Removes the value from the graph. Any dependency from this node to another will be removed, possible allowing nodes that depend on this node to be eligible for processing.
    Parameters:
      `value` - the value to remove from the graph.

  - ### getDependentValues

    public Set<T> getDependentValues(T value)
    Returns a set of values that depend on the given value.
    Parameters:
      `value` - the value that other values may depend on.
    Returns:
      a set of values that depend on the given value.