Package ghidra.util.graph
Class DirectedGraph
- java.lang.Object
-
- ghidra.util.graph.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 Summary
Constructors Constructor Description DirectedGraph()
Default constructorDirectedGraph(int vertexCapacity, int edgeCapacity)
Creates an empty DirectedGraph with room for vertexCapacity vertices and edgeCapacity edges.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(Edge e)
Adds the specified edge to the graph.boolean
add(Vertex v)
Adds the specified vertex to the graph.boolean
areRelatedAs(Vertex parent, Vertex child)
Returns true iff the graph contains and edge from the parent vertex to the child vertex.java.util.Set<Vertex>[]
assignVerticesToStrongComponents()
Returns an array of Sets (HashSet).void
clear()
Removes all vertices and edges from the graph without changing the space allocated.IntegerAttribute<Vertex>
complexityDepth()
Assigns levels to the graph in a bottom up fashion.boolean
contains(Edge e)
Returns true iff the graph contains the edge e.boolean
contains(Vertex v)
Returns true iff the vertex is in the graph.boolean
containsAsSubgraph(DirectedGraph g)
Returns true iff all nodes and edges of the given graph are in the current graphDirectedGraph
copy()
protected void
copyAll(DirectedGraph copy)
Copies all attributes from the indicated directed graph to this one.protected void
copyEdge(Edge e, DirectedGraph other)
This method copies an edge and all object attributes from graph 'other' into this graph.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'protected void
copyVertex(Vertex node, DirectedGraph other)
This method copies a vertex and all object attributes from graph 'other' into this graph.protected void
copyVertexAttributeValues(Vertex vert, DirectedGraph other)
This method copies vertex attributes for vertex 'vert' from graph 'other' to this graph.double
degree(Vertex v)
Returns valence as a double.DirectedGraph
descendantsGraph(Vertex[] seeds)
Get the graph induced by the seed vertices and their descendantsAttributeManager<Edge>
edgeAttributes()
Returns the AttributeManager for the edges of this graph.GraphIterator<Edge>
edgeIterator()
Returns an iterator for the EdgeSet of this graph.ghidra.util.graph.EdgeSet
edges()
Returns the EdgeSet of this graph.java.util.Set<Vertex>
getAncestors(Vertex v)
Returns a set of all the vertices which are ancestors of the given vertex.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.java.util.Set<Vertex>
getChildren(java.util.Set<Vertex> vs)
Returns all children of the vertices in the given set.DirectedGraph
getComponentContaining(Vertex v)
Returns the subgraph of this graph which is the component containing v.DirectedGraph[]
getComponents()
Returns an array of directed graphs.java.util.Set<Vertex>
getDescendants(Vertex v)
Returns a Set (HashSet) containing all descendants of the given vertex.java.util.Set<Vertex>
getDescendants(Vertex[] seedVertices)
Returns a Set (HashSet) of all vertices descended from a vertex in the given array.Edge[]
getEdgeArray()
returns an array containing the edges in the graphprotected ObjectAttribute<Edge>
getEdgeAttribute(java.lang.String attribName)
This method gets and ObjectAttribute method give an attribute name.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.java.util.Set<Edge>
getEdges()
returns a java.util.Set containing the edges in this graph.Edge[]
getEdges(Vertex from, Vertex to)
Returns all edges joing the from and to vertices.Edge
getEdgeWithKey(long key)
java.util.Vector<Vertex>
getEntryPoints()
Returns a vector containing the entry points to a directed graph.java.util.Set<Edge>
getIncomingEdges(Vertex v)
Returns a Set containing all of the edges to the given vertex.IntegerAttribute<Vertex>
getLevels()
This method assigns levels in a top-down manner.java.util.Set<Vertex>
getNeighborhood(Vertex v)
Returns a java.util.Set containing the vertex v and its neighbors.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.java.util.Set<Edge>
getOutgoingEdges(Vertex v)
Returns the outgoing edges from the given vertex.java.util.Set<Vertex>
getParents(Vertex v)
Returns a Set containg all of the vertices from which an edge comes into the given vertex.java.util.Set<Vertex>
getParents(java.util.Set<Vertex> vs)
Returns all parents of the vertices in the given set.java.lang.Object
getReferent(Vertex v)
Returns the referent of the object used to create v if it exists.Vertex[]
getSinks()
Returns a Vertex[] containing the sinks.Vertex[]
getSources()
Returns a Vertex[] containing the sources.Vertex[]
getVertexArray()
returns an array containing the vertices in the graphprotected ObjectAttribute<Vertex>
getVertexAttribute(java.lang.String attribName)
This method gets and ObjectAttribute method give an attribute name.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.Vertex
getVertexWithKey(long key)
java.util.Set<Vertex>
getVertices()
returns a java.util.Set containing the vertices in this graph.Vertex[]
getVerticesHavingReferent(java.lang.Object o)
Returns Vertex[] containing all vertices having the given object as a referent.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.Edge[]
incomingEdges(Vertex v)
Returns an array of all incoming edges.double
inDegree(Vertex v)
Returns inValence as a double.DirectedGraph
inducedSubgraph(Vertex[] vertexSet)
Returns the directed graph which is subgraph induced by the given set of vertices.void
intersectionWith(DirectedGraph otherGraph)
Creates intersection of graphs in place by adding all vertices and edges of other graph to this graph.int
inValence(Vertex v)
The number of edges having v as their terminal or "to" vertex.DirectedGraph
join(DirectedGraph other)
This method joins nodes from a directed graph into this.double
loopDegree(Vertex v)
Returns numLoops as a double.int
numEdges()
Returns the number of edges in the graphint
numLoops(Vertex v)
The number of edges having v as both their terminal and terminal vertex.int
numSinks()
returns the number of vertices with outValence zero.int
numSources()
returns the number of vertices with inValence zero.int
numVertices()
Returns the number of vertices in the graphdouble
outDegree(Vertex v)
Returns outValence as a double.Edge[]
outgoingEdges(Vertex v)
Returns an array of all outgoing edges.int
outValence(Vertex v)
The number of edges having v as their initial or "from" vertex.boolean
remove(Edge e)
Removes Edge e from the graph.boolean
remove(Vertex v)
Removes the vertex v from the graph.Edge[]
selfEdges(Vertex v)
Returns an array of all edges with the given vertex as both the from and to.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.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.void
unionWith(DirectedGraph otherGraph)
Creates union of graphs in place by adding all vertices and edges of other graph to this graph.int
valence(Vertex v)
The number of edges incident with v.AttributeManager<Vertex>
vertexAttributes()
Returns the AttributeManager for the vertices of this graph.GraphIterator<Vertex>
vertexIterator()
Returns an iterator for the VertexSet of this graph.ghidra.util.graph.VertexSet
vertices()
Returns the VertexSet of this graph.Vertex[]
verticesUnreachableFromSources()
Returns array of all vertices unreachable from a source.static java.util.Set<?>
verts2referentSet(java.util.Collection<Vertex> verts)
This method converts a collection of verticies into a set of its referent objects.
-
-
-
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.
-
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 namee
- 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 namev
- the vertexprop
- 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 namev
- 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
-
-