Package ghidra.util.graph

Class DirectedGraph

  • Direct Known Subclasses:
    Dominator, WeightedDigraph
    public class DirectedGraph
extends java.lang.Object
    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 Detail

      • DirectedGraph

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

      • DirectedGraph

        public DirectedGraph()
        Default constructor

    • Method Detail

      • inValence

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

      • outValence

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

      • numLoops

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

      • valence

        public int valence​(Vertex v)
        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()
        Returns the EdgeSet of this graph.

      • getEdgeWithKey

        public Edge getEdgeWithKey​(long key)
        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()
        Returns the VertexSet of this graph.

      • getVertexWithKey

        public Vertex getVertexWithKey​(long key)
        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 java.util.Set<Vertex> getChildren​(Vertex v)
        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 java.util.Set<Edge> getOutgoingEdges​(Vertex v)
        Returns the outgoing edges from the given vertex.

      • getParents

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

      • getIncomingEdges

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

      • getChildren

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

      • getParents

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

      • getDescendants

        public java.util.Set<Vertex> getDescendants​(Vertex v)
        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)
        Returns an array of all incoming edges.

      • outgoingEdges

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

      • selfEdges

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

      • verticesUnreachableFromSources

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

      • getDescendants

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

      • getAncestors

        public java.util.Set<Vertex> getAncestors​(Vertex v)
        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()
        Returns an iterator for the EdgeSet of this graph.

      • vertexIterator

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

      • inDegree

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

      • outDegree

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

      • loopDegree

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

      • degree

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

      • containsAsSubgraph

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

      • assignVerticesToStrongComponents

        public java.util.Set<Vertex>[] assignVerticesToStrongComponents()
        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 java.util.Vector<Vertex> getEntryPoints()
        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 java.util.Set<Vertex> getVertices()
        returns a java.util.Set containing the vertices in this graph.

      • getVertexArray

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

      • getEdges

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

      • getEdgeArray

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

      • numVertices

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

      • numEdges

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

      • add

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

      • add

        public boolean add​(Edge e)
        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)
        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)
        Removes Edge e from the graph. No effect if the edge is not in the graph.

      • contains

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

      • contains

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

      • numSinks

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

      • numSources

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

      • getSources

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

      • getSinks

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

      • getVerticesInContainingComponent

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

      • getComponentContaining

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

      • getComponents

        public DirectedGraph[] getComponents()
        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)
        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)
        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)
        Get the graph induced by the seed vertices and their descendants

      • inducedSubgraph

        public DirectedGraph inducedSubgraph​(Vertex[] vertexSet)
        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 java.util.Set<Vertex> getNeighborhood​(Vertex v)
        Returns a java.util.Set containing the vertex v and its neighbors.

      • getNeighborhood

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

      • getReferent

        public java.lang.Object getReferent​(Vertex v)
        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()
        This method assigns levels in a top-down manner. Sources are on level 0.

      • complexityDepth

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

      • getEdges

        public Edge[] getEdges​(Vertex from,
                       Vertex to)
        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)
        Returns true iff the graph contains and edge from the parent vertex to the child vertex.

      • clear

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

      • vertexAttributes

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

      • edgeAttributes

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

      • getVerticesHavingReferent

        public Vertex[] getVerticesHavingReferent​(java.lang.Object o)
        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()
        Returns:
        A directed graph with the same vertices, edges, and attributes.

      • copyAll

        protected void copyAll​(DirectedGraph copy)
        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)
        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)
        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)
        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)
        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)
        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​(java.lang.String propName,
                               Edge e,
                               java.lang.Object prop)
        This is a helper method that sets a object property named propName to edge e.

      • getEdgeProperty

        protected java.lang.Object getEdgeProperty​(java.lang.String propName,
                                           Edge e)
        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​(java.lang.String propName,
                                 Vertex v,
                                 java.lang.Object prop)
        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 java.lang.Object getVertexProperty​(java.lang.String propName,
                                             Vertex v)
        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​(java.lang.String attribName)
        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​(java.lang.String attribName)
        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 java.util.Set<?> verts2referentSet​(java.util.Collection<Vertex> verts)
        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