Java Implement an undirected graph using a directed graph as the underlying data

Question

Java

Implement an undirected graph using a directed graph as the underlying data structure.

Make sure you have a good understanding of the DirectedGraph class before you use it to implement UndirectedGraph.

I have provided the UndirectedGraph class with the single instance data variable.

Do not add any additional instance data variables. Do not modify any other classes provided.

In addition to writing the 8 required methods of the interface and the constructor, you will also write methods for the two traversals and an isConnected method.

Hint: Don't over-think the implementation of the traversals. Consider whether the traversal of a directed graph differs from an undirected one.

The isConnected method takes one parameter of type T (which represents a vertex) and returns a boolean (true if connected, false if not). Hint: Think about how you can use the traversals of the DirectedGraph class to implement this method.

Note that I altered some of the files provided from the versions in the book. I used the Java version of Stack, Queue,PriorityQueue, and LinkedBlockingQueue (a class that implements queue) instead of the book's versions. I did this mainly to simplify files you need to run your program. Note that Java's Queue class uses "add" and "remove" instead of "queue" and "dequeue," so this might look a little different than what you are used to.

FIles: https://ufile.io/8616e

Explanation / Answer

import java.util.*; // For HashMap, HashSet

public final class UndirectedGraph1<T> implements Iterable<T> {
    /* A map from node1s in the graph to sets of outgoing edges.  Each
     * set of edges is represented by a map from edges to doubles.
     */
    private final Map<T, Set<T>> mGraph1 = new HashMap<T, Set<T>>();

    /**
     * Adds a new node1 to the graph.  If the node1 already exists, this
     * function is a no-op.
     *
     * @param node1 The node1 to add.
     * @return Whether or not the node1 was added.
     */
    public boolean addNode1(T node1) {
        /* If the node1 already exists, don't do anything. */
        if (mGraph1.containsKey(node1))
            return false;

        /* Otherwise, add the node1 with an empty set of outgoing edges. */
        mGraph1.put(node1, new HashSet<T>());
        return true;
    }

    /**
     * Given a node1, returns whether that node1 exists in the graph.
     *
     * @param The node1 in question.
     * @return Whether that node1 eixsts in the graph.
     */
    public boolean isConnected(T node1) {
        return mGraph1.containsKey(node1);
    }

    /**
     * Given two node1s, adds an arc of that length between those node1s.  If
     * either endpoint does not exist in the graph, throws a
     * NoSuchElementException.
     *
     * @param one The first node1.
     * @param two The second node1.
     * @throws NoSuchElementException If either the start or destination node1s
     *                                do not exist.
     */
    public void addEdge(T one1, T two1) {
        /* Confirm both endpoints exist. */
        if (!mGraph1.containsKey(one1) || !mGraph1.containsKey(two1))
            throw new NoSuchElementException("Both node1s must be in the graph.");

        /* Add the edge in both directions. */
        mGraph1.get(one1).add(two1);
        mGraph1.get(two1).add(one1);
    }

    /**
     * Removes the edge between the indicated endpoints from the graph.  If the
     * edge does not exist, this operation is a no-op.  If either endpoint does
     * not exist, this throws a NoSuchElementException.
     *
     * @param one The start node1.
     * @param two The destination node1.
     * @throws NoSuchElementException If either node1 is not in the graph.
     */
    public void removeEdge(T one1, T two1) {
        /* Confirm both endpoints exist. */
        if (!mGraph1.containsKey(one1) || !mGraph1.containsKey(two1))
            throw new NoSuchElementException("Both node1s must be in the graph.");

        /* Remove the edges from both adjacency lists. */
        mGraph1.get(one1).remove(two1);
        mGraph1.get(two1).remove(one1);
    }

    /**
     * Given two endpoints, returns whether an edge exists between them.  If
     * either endpoint does not exist in the graph, throws a
     * NoSuchElementException.
     *
     * @param one The first endpoint.
     * @param two The second endpoint.
     * @return Whether an edge exists between the endpoints.
     * @throws NoSuchElementException If the endpoints are not node1s in the
     *                                graph.
     */
    public boolean edgeExists(T one1, T two1) {
        /* Confirm both endpoints exist. */
        if (!mGraph1.containsKey(one1) || !mGraph1.containsKey(two1))
            throw new NoSuchElementException("Both node1s must be in the graph.");     
        
        /* Graph is symmetric, so we can just check either endpoint. */
        return mGraph1.get(one1).contain

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.