Package ptolemy.graph

Class DirectedGraph

  • All Implemented Interfaces:
    java.lang.Cloneable
    Direct Known Subclasses:
    DirectedAcyclicGraph

    public class DirectedGraph
    extends Graph
    A directed graph. Some methods in this class have two versions, one that operates on graph nodes, and another that operates on node weights. The latter form is called the weights version. More specifically, the weights version of an operation takes individual node weights or arrays of weights as arguments, and, when applicable, returns individual weights or arrays of weights.

    Multiple edges in a graph can be directed between the same pair of nodes. Thus, directed multigraphs are supported.

    Since:
    Ptolemy II 0.2
    Version:
    $Id$
    Author:
    Yuhong Xiong, Jie Liu, Paul Whitaker, Shuvra S. Bhattacharyya, Shahrooz Shahparnia
    Pt.AcceptedRating:
    Yellow (pwhitake)
    Pt.ProposedRating:
    Yellow (pwhitake)
    • Field Detail

      • _transitiveClosureAnalysis

        protected TransitiveClosureAnalysis _transitiveClosureAnalysis
        The graph analysis for computation of transitive closure.
    • Constructor Detail

      • DirectedGraph

        public DirectedGraph()
        Construct an empty directed graph.
      • DirectedGraph

        public DirectedGraph​(int nodeCount)
        Construct an empty directed graph with enough storage allocated for the specified number of nodes. Memory management is more efficient with this constructor if the number of nodes is known.
        Parameters:
        nodeCount - The integer specifying the number of nodes
      • DirectedGraph

        public DirectedGraph​(int nodeCount,
                             int edgeCount)
        Construct an empty directed graph with enough storage allocated for the specified number of edges, and number of nodes. Memory management is more efficient with this constructor if the number of nodes and edges is known.
        Parameters:
        nodeCount - The number of nodes.
        edgeCount - The number of edges.
    • Method Detail

      • backwardReachableNodes

        public java.util.Collection backwardReachableNodes​(Node node)
        Find all the nodes that can be reached backward from the specified node. The reachable nodes do not include the argument unless there is a loop from the specified node back to itself.
        Parameters:
        node - A node in this graph.
        Returns:
        The collection of nodes that is backward-reachable from the specified node; each element is a Node.
        Throws:
        GraphElementException - If the specified node is not a node in this graph.
      • backwardReachableNodes

        public java.lang.Object[] backwardReachableNodes​(java.lang.Object weight)
        Find all the nodes that can be reached backward from the specified node (weights version). If the specified weight is null, find all the nodes that can be reached backward from any node that is unweighted. The reachable nodes do not include the argument unless there is a loop from the specified node back to itself.
        Parameters:
        weight - A node weight in this graph.
        Returns:
        An array of node weights that are backward-reachable from the nodes that have the specified weight; each element is an Object.
        Throws:
        GraphWeightException - If the specified weight is not a node weight in this graph.
      • backwardReachableNodes

        public java.util.Collection backwardReachableNodes​(java.util.Collection nodeCollection)
        Find all the nodes that can be reached backward from the specified collection of nodes. The reachable nodes do not include the specific ones unless there is a loop from the specified node back to itself.
        Parameters:
        nodeCollection - A collection of nodes in this graph; each element is a Node.
        Returns:
        The collection of nodes that are backward-reachable from the specified nodes; each element is a Node.
      • backwardReachableNodes

        public java.lang.Object[] backwardReachableNodes​(java.lang.Object[] weights)
        Find all the nodes that can be reached backward from the specified collection of nodes (weights version). The reachable nodes do not include the weights in the argument unless there is a loop from the specified node back to itself.
        Parameters:
        weights - An array of node weights in this graph; each element is an Object.
        Returns:
        An array of node weights that are backward-reachable from the nodes that have the specified weights; each element is an Object.
        Throws:
        GraphElementException - If the one or more of the specified weights is not a node weight in this graph.
      • cycleNodeCollection

        public java.util.Collection cycleNodeCollection()
        Return the nodes that are in cycles. If there are multiple cycles, the nodes in all the cycles will be returned.
        Returns:
        The collection of nodes that are in cycles; each element is a Node.
      • cycleNodes

        public java.lang.Object[] cycleNodes()
        Return the nodes that are in cycles (weights version). If there are multiple cycles, the nodes in all the cycles will be returned.
        Returns:
        An array of node weights that are in cycles; each element is an Object.
      • edgeExists

        public boolean edgeExists​(Node node1,
                                  Node node2)
        Test if an edge exists from one node to another.
        Parameters:
        node1 - The weight of the first node.
        node2 - The weight of the second node.
        Returns:
        True if the graph includes an edge from the first node to the second node; false otherwise.
      • edgeExists

        public boolean edgeExists​(java.lang.Object weight1,
                                  java.lang.Object weight2)
        Test whether an edge exists from one node weight to another. More specifically, test whether there exists an edge (n1, n2) such that

        (n1.getWeight() == weight1) && (n2.getWeight() == weight2) .

        Parameters:
        weight1 - The first (source) node weight.
        weight2 - The second (sink) node weight.
        Returns:
        True if the graph includes an edge from the first node weight to the second node weight.
      • inputEdgeCount

        public int inputEdgeCount​(Node node)
        Return the number of input edges of a specified node.
        Parameters:
        node - The node.
        Returns:
        The number of input edges.
      • inputEdges

        public java.util.Collection inputEdges​(Node node)
        Return the collection of input edges for a specified node.
        Parameters:
        node - The specified node.
        Returns:
        The collection of input edges; each element is an Edge.
      • isAcyclic

        public boolean isAcyclic()
        Test if this graph is acyclic (is a DAG).
        Returns:
        True if the the graph is acyclic, or empty; false otherwise.
      • outputEdgeCount

        public int outputEdgeCount​(Node node)
        Return the number of output edges of a specified node.
        Parameters:
        node - The node.
        Returns:
        The number of output edges.
      • outputEdges

        public java.util.Collection outputEdges​(Node node)
        Return the collection of output edges for a specified node.
        Parameters:
        node - The specified node.
        Returns:
        The collection of output edges; each element is an Edge.
      • predecessorEdges

        public java.util.Collection predecessorEdges​(Node n1,
                                                     Node n2)
        Return the collection of edges that make a node n2 a predecessor of a node n1. In other words, return the collection of edges directed from n2 to n1. Each element of the collection is an Edge.
        Parameters:
        n1 - The node n1.
        n2 - The node n2.
        Returns:
        The collection of edges that make n2 a predecessor of n1.
        See Also:
        successorEdges(Node, Node), Graph.neighborEdges(Node, Node)
      • predecessors

        public java.util.Collection predecessors​(Node node)
        Return all of the predecessors of a given node in the form of a a collection. Each element of the collection is a Node. A predecessor of a node X is a node that is the source of an edge whose sink is X. All elements in the returned collection are unique nodes.
        Parameters:
        node - The node whose predecessors are to be returned.
        Returns:
        The predecessors of the node.
      • reachableNodes

        public java.util.Collection reachableNodes​(Node node)
        Find all the nodes that can be reached from the specified node. The reachable nodes do not include the specific one unless there is a loop from the specified node back to itself.
        Parameters:
        node - The specified node.
        Returns:
        The collection of nodes reachable from the specified one; each element is a Node.
        Throws:
        GraphElementException - If the specified node is not a node in this graph.
      • reachableNodes

        public java.lang.Object[] reachableNodes​(java.lang.Object weight)
        Find all the nodes that can be reached from any node that has the specified node weight (weights version). If the specified weight is null, find all the nodes that can be reached from any node that is unweighted.
        Parameters:
        weight - The specified node weight.
        Returns:
        An array of node weights reachable from the specified weight; each element is an Object.
        Throws:
        GraphWeightException - If the specified node weight is not a node weight in this graph.
        See Also:
        reachableNodes(Node)
      • reachableNodes

        public java.lang.Object[] reachableNodes​(java.lang.Object[] weights)
        Find all the nodes that can be reached from the specified collection of nodes (weights version). The reachable nodes do not include a specified one unless there is a loop from the specified node back to itself.
        Parameters:
        weights - An array of node weights; each element is an Object.
        Returns:
        The array of nodes that are reachable from the specified one; each element is an Object.
        See Also:
        reachableNodes(Node)
      • reachableNodes

        public java.util.Collection reachableNodes​(java.util.Collection nodeCollection)
        Find all the nodes that can be reached from the specified collection of nodes. The reachable nodes do not include a specified one unless there is a loop from the specified node back to itself.
        Parameters:
        nodeCollection - The specified collection of nodes; each element is a Node.
        Returns:
        The collection of nodes that are reachable from the specified one; each element is a Node.
      • sccDecomposition

        public DirectedGraph[] sccDecomposition()
        Compute the strongly connected component (SCC) decomposition of a graph.
        Returns:
        An array of instances of DirectedGraph that represent the SCCs of the graph in topological order.
      • selfLoopEdgeCount

        public int selfLoopEdgeCount​(Node node)
        Return the number of self loop edges of a specified node. A directed self loop edge (an edge whose source and sink nodes are identical) is both an input edge and an output edge of the incident node, but it is not duplicated in the set of incident edges. Thus, the number of edges incident edges to a node is equal to I + O - S, where I is the number of input edges, O is the number of output edges, and S is the number of self loop edges.
        Overrides:
        selfLoopEdgeCount in class Graph
        Parameters:
        node - The node.
        Returns:
        The number of self loop edges.
      • sinkNodeCount

        public int sinkNodeCount()
        Return the number of sink nodes in this graph. A sink node is a node that has no output edges.
        Returns:
        The number of sink nodes.
      • sinkNodes

        public java.util.Collection sinkNodes()
        Return all the sink nodes in this graph in the form of a collection. Each element in the collection is a Node.
        Returns:
        The sink nodes in this graph.
        See Also:
        sinkNodeCount()
      • sourceNodeCount

        public int sourceNodeCount()
        Return the number of source nodes in this graph. A source node is a node that has no input edges.
        Returns:
        The number of source nodes.
      • sourceNodes

        public java.util.Collection sourceNodes()
        Return all the source nodes in this graph in the form of a collection. Each element in the collection is a Node.
        Returns:
        The source nodes in this graph.
        See Also:
        sourceNodeCount()
      • subgraphs

        public java.util.LinkedList subgraphs()
        Return a list of disconnected subgraphs of this graph.
        Returns:
        A list of disconnected subgraphs.
      • successorEdges

        public java.util.Collection successorEdges​(Node n1,
                                                   Node n2)
        Return the collection of edges that make a node n2 a successor of a node n1. In other words, return the collection of edges directed from n1 to n2. Each element of the collection is an Edge.
        Parameters:
        n1 - The node n1.
        n2 - The node n2.
        Returns:
        The collection of edges that make n2 a successor of n1.
        See Also:
        predecessorEdges(Node, Node), Graph.neighborEdges(Node, Node)
      • successors

        public java.util.Collection successors​(Node node)
        Return all of the successors of a given node in the form of a a collection. Each element of the collection is a Node. A successor of a node X is a node that is the sink of an edge whose source is X. All elements in the returned collection are unique nodes.
        Parameters:
        node - The node whose successors are to be returned.
        Returns:
        The successors of the node.
      • topologicalSort

        public java.util.List topologicalSort​(java.util.Collection nodeCollection)
                                       throws GraphActionException
        Sort a collection of graph nodes in their topological order as long as no two of the given nodes are mutually reachable by each other. This method uses the transitive closure matrix. Since generally the graph is checked for cyclicity before this method is called, the use of the transitive closure matrix should not add any overhead. A bubble sort is used for the internal implementation, so the complexity is O(V^2).
        Parameters:
        nodeCollection - The collection of nodes to be sorted; each element is a Node.
        Returns:
        The nodes in their sorted order in the form of a list; each element is a Node.
        Throws:
        GraphActionException - If any two nodes are strongly connected.
        See Also:
        topologicalSort(Object[])
      • topologicalSort

        public java.lang.Object[] topologicalSort​(java.lang.Object[] weights)
                                           throws GraphActionException
        Sort the given nodes in their topological order as long as no two of the given nodes are mutually reachable by each other (weights version). The set of nodes to sort is taken as the set of nodes whose weights are contained in the specified weight set. The weights of the sorted nodes are returned.
        Parameters:
        weights - The weight set.
        Returns:
        The weights of the sorted nodes.
        Throws:
        GraphActionException - If any two nodes are strongly connected.
        See Also:
        topologicalSort(Collection)
      • transitiveClosure

        public boolean[][] transitiveClosure()
        Return transitive closure for the graph.
        Returns:
        Transitive closure for the graph.
      • _connect

        protected void _connect​(Edge edge,
                                Node node)
        Connect an edge to a node by appropriately modifying the adjacency information associated with the node.
        Overrides:
        _connect in class Graph
        Parameters:
        edge - The edge.
        node - The node.
        Throws:
        GraphConstructionException - If the edge has already been connected to the node.
      • _connectedSubGraph

        protected void _connectedSubGraph​(Node node,
                                          DirectedGraph graph,
                                          java.util.Collection remainingNodes)
        Given a node, get all the edges and nodes that are connected to it directly and/or indirectly. Add them in the given graph. Remove the nodes from the remaining nodes. FIXME: Hidden edges not considered.
        Parameters:
        node - The given node.
        graph - The given graph.
        remainingNodes - Set of nodes that haven't been reached.
      • _disconnect

        protected void _disconnect​(Edge edge,
                                   Node node)
        Description copied from class: Graph
        Disconnect an edge from a node that it is incident to. Specifically, this method removes the edge from the set of edges that are considered incident to the node in this graph. This method does nothing if the given edge is not incident to the given node. This method should be overridden to incorporate additional operations that are required to disconnect an edge from a node (see, for example, DirectedGraph.#_disconnect(Edge, Node)).
        Overrides:
        _disconnect in class Graph
        Parameters:
        edge - The edge.
        node - The node.
      • _initializeAnalyses

        protected void _initializeAnalyses()
        Initialize the list of analyses that are associated with this graph, and initialize the change counter of the graph.
        Overrides:
        _initializeAnalyses in class Graph
        See Also:
        Analysis