C++ Directed Graph Question Consider the above directed weighted graph and repre
ID: 3693381 • Letter: C
Question
C++ Directed Graph Question
Consider the above directed weighted graph and represent the graph using an adjacency matrix. While creating the adjacency matrix, use the state names in alphabetical orders. Instead of using the whole names (e.g. New York), use the first letters (e.g. N) of the states to identify them. Format of adjacency matrix will be (the first row is done for you): Create a menu driven application which will provide the following options to the users: This option will allow users to add an edge to the existing graph model. To add an edge, take two vertices (the edge is from first to second) and the edge weight as input from the user, update the adjacency matrix using that two vertices as index. If an edge already exists, notify the user by saying ''edge already exists!" This option will allow users to delete an edge to the existing graph model. To delete an edge, take two vertices as input from the user, update the adjacency matrix using that two vertices as index. If there is no existing edge, notify the user by saying "no edge available!" Show total number of edges: Show total number of edges using the adjacency matrix. Show the matrix: Show the updated adjacency matrix in the console. ExitExplanation / Answer
/** A directed acyclic graph (DAG). Copyright (c) 1997-2010 The Regents of the University of California. All rights reserved. Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software. IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. PT_COPYRIGHT_VERSION_2 COPYRIGHTENDKEY */ package ptolemy.graph; import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; import java.util.ListIterator; import ptolemy.graph.analysis.TransitiveClosureAnalysis; import ptolemy.graph.analysis.strategy.CachedStrategy; /////////////////////////////////////////////////////////////////// //// DirectedAcyclicGraph.java /** A directed acyclic graph (DAG). The graphs constructed by this class cannot have cycles. For performance reasons, this requirement is not checked (except for self-loops) during the construction of the graph (calls toadd and addEdge), but is checked when any of the other methods is called for the first time after the addition of nodes or edges. If the graph is cyclic, a GraphTopologyException is thrown. The check for cycles is done by computing the transitive closure, so the first operation after a graph change is slower. This class implements the CPO interface since the Hasse diagram of a CPO can be viewed as a DAG. Therefore, this class can be viewed as both a DAG and a finite CPO. In the case of CPO, the node weights are the CPO elements. The CPO does not require the bottom element to exist. The call to bottom returns null if the bottom element does not exist. NOTE: This class is a starting point for implementing graph algorithms, more methods will be added. @author Yuhong Xiong, Shuvra S. Bhattacharyya @version $Id: DirectedAcyclicGraph.java 57040 2010-01-27 20:52:32Z cxh $ @since Ptolemy II 0.2 @Pt.ProposedRating Green (yuhong) @Pt.AcceptedRating Green (kienhuis) */ // The methods greatestLowerBound, downSet, greatestElement share the // same code with their duals, leastUpperBound, upSet, leastElement. // The only thing different is the use of the transposition of the // transitive closure instead of the original transitive closure. // In another word, the computation of greatestLowerBound, downSet, // greatestElement is converted to their dual operation by reversing // the order relation in this CPO. public class DirectedAcyclicGraph extends DirectedGraph implements CPO { /** Construct an empty DAG. */ public DirectedAcyclicGraph() { super(); } /** Construct an empty DAG with enough storage allocated * for the specified number of elements. Memory management is more * efficient with this constructor if the number of elements is * known. * @param nodeCount The number of elements. */ public DirectedAcyclicGraph(int nodeCount) { super(nodeCount); } /////////////////////////////////////////////////////////////////// //// public methods //// /** Return the bottom element of this CPO. * @return An Object representing the bottom element, or * null if the bottom does not exist. */ public Object bottom() { _validate(); return _bottom; } /** Compare two elements in this CPO. * @param e1 An Object representing a CPO element. * @param e2 An Object representing a CPO element. * @return One of CPO.LOWER, CPO.SAME, * CPO.HIGHER, CPO.INCOMPARABLE. * @exception IllegalArgumentException If at least one of the * specified Objects is not an element of this CPO. */ public int compare(Object e1, Object e2) { _validate(); int i1 = nodeLabel(e1); int i2 = nodeLabel(e2); return _compareNodeId(i1, i2); } /** Compute the down-set of an element in this CPO. * @param e An Object representing an element in this CPO. * @return An array of of Objects representing the elements in the * down-set of the specified element. * @exception IllegalArgumentException If the specified Object is not * an element in this CPO. */ public Object[] downSet(Object e) { _validateDual(); return _upSetShared(e); } /** Compute the greatest element of a subset. * @param subset An array of Objects representing the subset. * @return An Object representing the greatest element of the subset, * or null if the greatest element does not exist. * @exception IllegalArgumentException If at least one Object in the * specified array is not an element of this CPO. */ public Object greatestElement(Object[] subset) { _validateDual(); return _leastElementShared(subset); } /** Compute the greatest lower bound (GLB) of two elements. * @param e1 An Object representing an element in this CPO. * @param e2 An Object representing an element in this CPO. * @return An Object representing the GLB of the two specified * elements, or null if the GLB does not exist. * @exception IllegalArgumentException If at least one of the * specified Objects is not an element of this CPO. */ public Object greatestLowerBound(Object e1, Object e2) { _validateDual(); return _lubShared(e1, e2); } /** Compute the greatest lower bound (GLB) of a subset. * If the specified array representing the subset has size 0, * the subset is considered empty, in which case the top element * of this CPO is returned, if it exists. If the subset is empty * and the top does not exist, null is returned. * @param subset An array of Objects representing the subset. * @return An Object representing the GLB of the subset, or * null if the GLB does not exist. * @exception IllegalArgumentException If at least one Object * in the specified array is not an element of this CPO. */ public Object greatestLowerBound(Object[] subset) { _validateDual(); return _lubShared(subset); } /** Test if this CPO is a lattice. * By a theorem in Davey and Priestley, only the LUB or the GLB * need to be checked, but not both. The implementation tests the * existence of the LUB of any pair of elements, as well as the * existence of the bottom and top elements. The complexity is * O(|N|*|N|) where N for elements, and an individual computation * is the LUB of two elements. * @return True if this CPO is a lattice; * false otherwise. */ public boolean isLattice() { _validate(); if ((bottom() == null) || (top() == null)) { return false; } Object[] nodes = weightArray(nodes()); for (int i = 0; i < (nodes.length - 1); i++) { for (int j = i + 1; j
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.