Package edu.princeton.cs.algs4

Class EdgeWeightedGraph

  • public class EdgeWeightedGraph
extends Object
    The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V – 1, where each undirected edge is of type Edge and has a real-valued weight. It supports the following two primary operations: add an edge to the graph, iterate over all of the edges incident with a vertex. It also provides methods for returning the degree of a vertex, the number of vertices V in the graph, and the number of edges E in the graph. Parallel edges and self-loops are permitted. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v.

    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 degree of the vertex.) Constructing an empty edge-weighted graph with V vertices takes Θ(V) time; constructing an edge-weighted graph with E edges and V vertices takes Θ(E + V) time.

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

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • EdgeWeightedGraph

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

      • EdgeWeightedGraph

        public EdgeWeightedGraph​(int V,
                         int E)
        Initializes a random edge-weighted graph 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

      • EdgeWeightedGraph

        public EdgeWeightedGraph​(In in)
        Initializes an edge-weighted graph from an 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

      • EdgeWeightedGraph

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

    • Method Detail

      • V

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

      • E

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

      • addEdge

        public void addEdge​(Edge e)
        Adds the undirected edge e to this edge-weighted graph.
        Parameters:
        e - the edge
        Throws:
        IllegalArgumentException - unless both endpoints are between 0 and V-1

      • adj

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

      • degree

        public int degree​(int v)
        Returns the degree of vertex v.
        Parameters:
        v - the vertex
        Returns:
        the degree of vertex v
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • edges

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

      • toString

        public String toString()
        Returns a string representation of the edge-weighted graph. This method takes time proportional to E + V.
        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 graph 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 graph 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 graph in DOT format

      • main

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