Package edu.princeton.cs.algs4

Class EdgeWeightedDigraph

  • public class EdgeWeightedDigraph
extends Object
    The EdgeWeightedDigraph class represents an edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all edges incident from a given vertex. It also provides methods for returning the indegree or outdegree of a vertex, the number of vertices V in the digraph, and the number of edges E in the digraph. Parallel edges and self-loops are permitted.

    This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. It uses Θ(E + V) space, where E is the number of edges and V is the number of vertices. All instance methods take Θ(1) time. (Though, iterating over the edges returned by adj(int) takes time proportional to the outdegree of the vertex.) Constructing an empty edge-weighted digraph with V vertices takes Θ(V) time; constructing an edge-weighted digraph with E edges and V vertices takes Θ(E + V) time.

    For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • EdgeWeightedDigraph

        public EdgeWeightedDigraph​(int V)
        Initializes an empty edge-weighted digraph with V vertices and 0 edges.
        Parameters:
        V - the number of vertices
        Throws:
        IllegalArgumentException - if V < 0

      • EdgeWeightedDigraph

        public EdgeWeightedDigraph​(int V,
                           int E)
        Initializes a random edge-weighted digraph with V vertices and E edges.
        Parameters:
        V - the number of vertices
        E - the number of edges
        Throws:
        IllegalArgumentException - if V < 0
        IllegalArgumentException - if E < 0

      • EdgeWeightedDigraph

        public EdgeWeightedDigraph​(In in)
        Initializes an edge-weighted digraph from the specified input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices and edge weights, with each entry separated by whitespace.
        Parameters:
        in - the input stream
        Throws:
        IllegalArgumentException - if in is null
        IllegalArgumentException - if the endpoints of any edge are not in prescribed range
        IllegalArgumentException - if the number of vertices or edges is negative

      • EdgeWeightedDigraph

        public EdgeWeightedDigraph​(EdgeWeightedDigraph G)
        Initializes a new edge-weighted digraph that is a deep copy of G.
        Parameters:
        G - the edge-weighted digraph to copy

    • Method Detail

      • V

        public int V()
        Returns the number of vertices in this edge-weighted digraph.
        Returns:
        the number of vertices in this edge-weighted digraph

      • E

        public int E()
        Returns the number of edges in this edge-weighted digraph.
        Returns:
        the number of edges in this edge-weighted digraph

      • addEdge

        public void addEdge​(DirectedEdge e)
        Adds the directed edge e to this edge-weighted digraph.
        Parameters:
        e - the edge
        Throws:
        IllegalArgumentException - unless endpoints of edge are between 0 and V-1

      • adj

        public Iterable<DirectedEdge> adj​(int v)
        Returns the directed edges incident from vertex v.
        Parameters:
        v - the vertex
        Returns:
        the directed edges incident from vertex v as an Iterable
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • outdegree

        public int outdegree​(int v)
        Returns the number of directed edges incident from vertex v. This is known as the outdegree of vertex v.
        Parameters:
        v - the vertex
        Returns:
        the outdegree of vertex v
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • indegree

        public int indegree​(int v)
        Returns the number of directed edges incident to vertex v. This is known as the indegree of vertex v.
        Parameters:
        v - the vertex
        Returns:
        the indegree of vertex v
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • edges

        public Iterable<DirectedEdge> edges()
        Returns all directed edges in this edge-weighted digraph. To iterate over the edges in this edge-weighted digraph, use foreach notation: for (DirectedEdge e : G.edges()).
        Returns:
        all edges in this edge-weighted digraph, as an iterable

      • toString

        public String toString()
        Returns a string representation of this edge-weighted digraph.
        Overrides:
        toString in class Object
        Returns:
        the number of vertices V, followed by the number of edges E, followed by the V adjacency lists of edges

      • toDot

        public String toDot()
        Returns a string representation of this edge-weighted digraph in DOT format, suitable for visualization with Graphviz. To visualize the graph, install Graphviz (e.g., "brew install graphviz"). Then use one of the graph visualization tools - dot (hierarchical or layer drawing) - neato (spring model) - fdp (force-directed placement) - sfdp (scalable force-directed placement) - twopi (radial layout) For example, the following commands will create graph drawings in SVG and PDF formats - dot input.dot -Tsvg -o output.svg - dot input.dot -Tpdf -o output.pdf To change the digraph attributes (e.g., vertex and edge shapes, arrows, colors) in the DOT format, see https://graphviz.org/doc/info/lang.html
        Returns:
        a string representation of this edge-weighted digraph in DOT format

      • main

        public static void main​(String[] args)
        Unit tests the EdgeWeightedDigraph data type.
        Parameters:
        args - the command-line arguments