Package ghidra.util.graph

Class DirectedGraph

java.lang.Object
ghidra.util.graph.DirectedGraph
Direct Known Subclasses:
Dominator, WeightedDigraph
@Deprecated(since="10.2") public class DirectedGraph extends Object
Deprecated.
Base implementation of a directed graph. A directed graph consists of a set of vertices (implemented as a VertexSet) and a set of edges (implemented as an EdgeSet) joining ordered pairs of vertices in the graph. Both vertices and edges can belong to more than one DirectedGraph. Attributes for both vertices and edges may be defined for a DirectedGraph. Parallel edges (more than one edge with the same from and to vertices) are allowed in DirectedGraph. Loops are also allowed.

  • Constructor Details

    • DirectedGraph

      public DirectedGraph(int vertexCapacity, int edgeCapacity)
      Deprecated.
      Creates an empty DirectedGraph with room for vertexCapacity vertices and edgeCapacity edges.

    • DirectedGraph

      public DirectedGraph()
      Deprecated.
      Default constructor

  • Method Details

    • inValence

      public int inValence(Vertex v)
      Deprecated.
      The number of edges having v as their terminal or "to" vertex.

    • outValence

      public int outValence(Vertex v)
      Deprecated.
      The number of edges having v as their initial or "from" vertex.

    • numLoops

      public int numLoops(Vertex v)
      Deprecated.
      The number of edges having v as both their terminal and terminal vertex.

    • valence

      public int valence(Vertex v)
      Deprecated.
      The number of edges incident with v. For unweighted graphs valence and degree are the same, except valence is an int while degree is a double.

    • edges

      public ghidra.util.graph.EdgeSet edges()
      Deprecated.
      Returns the EdgeSet of this graph.

    • getEdgeWithKey

      public Edge getEdgeWithKey(long key)
      Deprecated.
      Parameters:
      key -
      Returns:
      the edge in the graph with the specified key or null if the graph does not contain an edge with the key.

    • vertices

      public ghidra.util.graph.VertexSet vertices()
      Deprecated.
      Returns the VertexSet of this graph.

    • getVertexWithKey

      public Vertex getVertexWithKey(long key)
      Deprecated.
      Parameters:
      key -
      Returns:
      the vertex in the graph with the specified key or null if the graph does not contain an vertex with the key.

    • getChildren

      public Set<Vertex> getChildren(Vertex v)
      Deprecated.
      Returns a Set (HashSet) containing all vertices that are the tos of outgoing edges of the given vertex. Note in the case of multiple edges, the number of children and outvalence need not be the same.

    • getOutgoingEdges

      public Set<Edge> getOutgoingEdges(Vertex v)
      Deprecated.
      Returns the outgoing edges from the given vertex.

    • getParents

      public Set<Vertex> getParents(Vertex v)
      Deprecated.
      Returns a Set containg all of the vertices from which an edge comes into the given vertex.

    • getIncomingEdges

      public Set<Edge> getIncomingEdges(Vertex v)
      Deprecated.
      Returns a Set containing all of the edges to the given vertex.

    • getChildren

      public Set<Vertex> getChildren(Set<Vertex> vs)
      Deprecated.
      Returns all children of the vertices in the given set.

    • getParents

      public Set<Vertex> getParents(Set<Vertex> vs)
      Deprecated.
      Returns all parents of the vertices in the given set.

    • getDescendants

      public Set<Vertex> getDescendants(Vertex v)
      Deprecated.
      Returns a Set (HashSet) containing all descendants of the given vertex. Note: The vertex is defined to be a descendant of itself.

    • incomingEdges

      public Edge[] incomingEdges(Vertex v)
      Deprecated.
      Returns an array of all incoming edges.

    • outgoingEdges

      public Edge[] outgoingEdges(Vertex v)
      Deprecated.
      Returns an array of all outgoing edges.

    • selfEdges

      public Edge[] selfEdges(Vertex v)
      Deprecated.
      Returns an array of all edges with the given vertex as both the from and to.

    • verticesUnreachableFromSources

      public Vertex[] verticesUnreachableFromSources()
      Deprecated.
      Returns array of all vertices unreachable from a source. These are the vertices descending only from a non-trivial strongly connected component.

    • getDescendants

      public Set<Vertex> getDescendants(Vertex[] seedVertices)
      Deprecated.
      Returns a Set (HashSet) of all vertices descended from a vertex in the given array.

    • getAncestors

      public Set<Vertex> getAncestors(Vertex v)
      Deprecated.
      Returns a set of all the vertices which are ancestors of the given vertex. Note: By definition a vertex is one of its own ancestors.

    • edgeIterator

      public GraphIterator<Edge> edgeIterator()
      Deprecated.
      Returns an iterator for the EdgeSet of this graph.

    • vertexIterator

      public GraphIterator<Vertex> vertexIterator()
      Deprecated.
      Returns an iterator for the VertexSet of this graph.

    • inDegree

      public double inDegree(Vertex v)
      Deprecated.
      Returns inValence as a double. Should be overridden extending classes.

    • outDegree

      public double outDegree(Vertex v)
      Deprecated.
      Returns outValence as a double. Should be overridden extending classes.

    • loopDegree

      public double loopDegree(Vertex v)
      Deprecated.
      Returns numLoops as a double. Should be overridden extending classes.

    • degree

      public double degree(Vertex v)
      Deprecated.
      Returns valence as a double. Should be overridden extending classes.

    • containsAsSubgraph

      public boolean containsAsSubgraph(DirectedGraph g)
      Deprecated.
      Returns true iff all nodes and edges of the given graph are in the current graph

    • assignVerticesToStrongComponents

      public Set<Vertex>[] assignVerticesToStrongComponents()
      Deprecated.
      Returns an array of Sets (HashSet). Each set contains the vertices within a single strongly connected component of the DirectedGraph. A strongly connected component of a directed graph is a subgraph in which it is possible to find a directed path from any vertex to any other vertex in the graph. A cycle is a simple example of strongly connected graph.

    • getEntryPoints

      public Vector<Vertex> getEntryPoints()
      Deprecated.
      Returns a vector containing the entry points to a directed graph. An entry point is either a source (in valence zero) or the least vertex in a strongly connected component unreachable from any vertex outside the strongly connected component. Least is defined here to be the vertex with the smallest key.

    • getVertices

      public Set<Vertex> getVertices()
      Deprecated.
      returns a java.util.Set containing the vertices in this graph.

    • getVertexArray

      public Vertex[] getVertexArray()
      Deprecated.
      returns an array containing the vertices in the graph

    • getEdges

      public Set<Edge> getEdges()
      Deprecated.
      returns a java.util.Set containing the edges in this graph.

    • getEdgeArray

      public Edge[] getEdgeArray()
      Deprecated.
      returns an array containing the edges in the graph

    • numVertices

      public int numVertices()
      Deprecated.
      Returns the number of vertices in the graph

    • numEdges

      public int numEdges()
      Deprecated.
      Returns the number of edges in the graph

    • add

      public boolean add(Vertex v)
      Deprecated.
      Adds the specified vertex to the graph.

    • add

      public boolean add(Edge e)
      Deprecated.
      Adds the specified edge to the graph. If either endpoint of the edge is not in the graph that vertex is also added to the graph.

    • remove

      public boolean remove(Vertex v)
      Deprecated.
      Removes the vertex v from the graph. Also removes all edges incident with v. Does nothing if the vertex is not in the graph.

    • remove

      public boolean remove(Edge e)
      Deprecated.
      Removes Edge e from the graph. No effect if the edge is not in the graph.

    • contains

      public boolean contains(Vertex v)
      Deprecated.
      Returns true iff the vertex is in the graph.

    • contains

      public boolean contains(Edge e)
      Deprecated.
      Returns true iff the graph contains the edge e.

    • numSinks

      public int numSinks()
      Deprecated.
      returns the number of vertices with outValence zero.

    • numSources

      public int numSources()
      Deprecated.
      returns the number of vertices with inValence zero.

    • getSources

      public Vertex[] getSources()
      Deprecated.
      Returns a Vertex[] containing the sources. A vertex is a source if it has no incoming edges.

    • getSinks

      public Vertex[] getSinks()
      Deprecated.
      Returns a Vertex[] containing the sinks. A vertex is a sink if it has no outgoing edges.

    • getVerticesInContainingComponent

      public Set<Vertex> getVerticesInContainingComponent(Vertex v)
      Deprecated.
      Returns a java.util.Set containing all of the vertices within the same component a the given vertex.

    • getComponentContaining

      public DirectedGraph getComponentContaining(Vertex v)
      Deprecated.
      Returns the subgraph of this graph which is the component containing v.

    • getComponents

      public DirectedGraph[] getComponents()
      Deprecated.
      Returns an array of directed graphs. Each array element is a DirectedGraph consisting of a single connected component of this graph.

    • intersectionWith

      public void intersectionWith(DirectedGraph otherGraph)
      Deprecated.
      Creates intersection of graphs in place by adding all vertices and edges of other graph to this graph. This method used to return a different graph as the intersection but now does not.

    • unionWith

      public void unionWith(DirectedGraph otherGraph)
      Deprecated.
      Creates union of graphs in place by adding all vertices and edges of other graph to this graph. This method used to return a different graph as the union but now does not.

    • descendantsGraph

      public DirectedGraph descendantsGraph(Vertex[] seeds)
      Deprecated.
      Get the graph induced by the seed vertices and their descendants

    • inducedSubgraph

      public DirectedGraph inducedSubgraph(Vertex[] vertexSet)
      Deprecated.
      Returns the directed graph which is subgraph induced by the given set of vertices. The vertex set of the returned graph contains the given vertices which belong to this graph. An edge of this graph is in the returned graph iff both endpoints belong to the given vertices.

    • getNeighborhood

      public Set<Vertex> getNeighborhood(Vertex v)
      Deprecated.
      Returns a java.util.Set containing the vertex v and its neighbors.

    • getNeighborhood

      public Set<Vertex> getNeighborhood(Set<Vertex> vs)
      Deprecated.
      Returns a java.util.Set containing the vertices in the given Set and their neighbors.

    • getReferent

      public Object getReferent(Vertex v)
      Deprecated.
      Returns the referent of the object used to create v if it exists. If the vertex was created with a null referent this method returns null.

    • getLevels

      public IntegerAttribute<Vertex> getLevels()
      Deprecated.
      This method assigns levels in a top-down manner. Sources are on level 0.

    • complexityDepth

      public IntegerAttribute<Vertex> complexityDepth()
      Deprecated.
      Assigns levels to the graph in a bottom up fashion. All sinks have the same level.

    • getEdges

      public Edge[] getEdges(Vertex from, Vertex to)
      Deprecated.
      Returns all edges joing the from and to vertices. Recall DirectedGraph uses a multigraph model where parallel edges are allowed.

    • areRelatedAs

      public boolean areRelatedAs(Vertex parent, Vertex child)
      Deprecated.
      Returns true iff the graph contains and edge from the parent vertex to the child vertex.

    • clear

      public void clear()
      Deprecated.
      Removes all vertices and edges from the graph without changing the space allocated.

    • vertexAttributes

      public AttributeManager<Vertex> vertexAttributes()
      Deprecated.
      Returns the AttributeManager for the vertices of this graph.

    • edgeAttributes

      public AttributeManager<Edge> edgeAttributes()
      Deprecated.
      Returns the AttributeManager for the edges of this graph.

    • getVerticesHavingReferent

      public Vertex[] getVerticesHavingReferent(Object o)
      Deprecated.
      Returns Vertex[] containing all vertices having the given object as a referent. Any number of vertices in the graph may refer back to the same object.

    • copy

      public DirectedGraph copy()
      Deprecated.
      Returns:
      A directed graph with the same vertices, edges, and attributes.

    • copyAll

      protected void copyAll(DirectedGraph copy)
      Deprecated.
      Copies all attributes from the indicated directed graph to this one.
      Parameters:
      copy - the directed graph to copy from.

    • copyVertex

      protected void copyVertex(Vertex node, DirectedGraph other)
      Deprecated.
      This method copies a vertex and all object attributes from graph 'other' into this graph.
      Parameters:
      node -
      other -

    • copyEdge

      protected void copyEdge(Edge e, DirectedGraph other)
      Deprecated.
      This method copies an edge and all object attributes from graph 'other' into this graph. Any implicictly created Verticies do not get their attribute values copied -- you must use copyVertex.
      Parameters:
      e -
      other -

    • copyEdgeAttributeValues

      protected void copyEdgeAttributeValues(Edge newe, Edge e, DirectedGraph other)
      Deprecated.
      This method copies the attributes from an edge 'e' from DirectedGraph 'other' into this graph associated with edge 'newe'
      Parameters:
      newe -
      e -
      other -

    • join

      public DirectedGraph join(DirectedGraph other)
      Deprecated.
      This method joins nodes from a directed graph into this. This allows DirectedGraph subclasses to copy nodes and attributes, a shortcomings with the unionWith method.
      Parameters:
      other - the other directed graph that is to be joined into this one.
      Returns:
      this directed graph

    • copyVertexAttributeValues

      protected void copyVertexAttributeValues(Vertex vert, DirectedGraph other)
      Deprecated.
      This method copies vertex attributes for vertex 'vert' from graph 'other' to this graph.
      Parameters:
      vert - the vertex whose attributes should be copied.
      other - the other graph to copy vertex attributes from

    • setEdgeProperty

      protected void setEdgeProperty(String propName, Edge e, Object prop)
      Deprecated.
      This is a helper method that sets a object property named propName to edge e.

    • getEdgeProperty

      protected Object getEdgeProperty(String propName, Edge e)
      Deprecated.
      This is a helper method that gets a property named propName to from edge e.
      Parameters:
      propName - the property name
      e - the edge
      Returns:
      the attribute for the indicated edge

    • setVertexProperty

      protected void setVertexProperty(String propName, Vertex v, Object prop)
      Deprecated.
      This is a helper method that sets an object property named propName for Vertex v.
      Parameters:
      propName - the property name
      v - the vertex
      prop - the property value

    • getVertexProperty

      protected Object getVertexProperty(String propName, Vertex v)
      Deprecated.
      This is a helper method that gets a property named propName for vertex v.
      Parameters:
      propName - the property name
      v - the vertex
      Returns:
      the property value

    • getEdgeAttribute

      protected ObjectAttribute<Edge> getEdgeAttribute(String attribName)
      Deprecated.
      This method gets and ObjectAttribute method give an attribute name. If it is not found in the attribute manager, the attribute is created automatically.
      Parameters:
      attribName - the name of the attribute
      Returns:
      the attribute

    • getVertexAttribute

      protected ObjectAttribute<Vertex> getVertexAttribute(String attribName)
      Deprecated.
      This method gets and ObjectAttribute method give an attribute name. If it is not found in the attribute manager, the attribute is created automatically.
      Parameters:
      attribName - the attribute name
      Returns:
      the attribute

    • verts2referentSet

      public static Set<?> verts2referentSet(Collection<Vertex> verts)
      Deprecated.
      This method converts a collection of verticies into a set of its referent objects. It is up to the methods using the created set to properly type cast the set's elements.
      Parameters:
      verts - the vertices
      Returns:
      the set of referent objects