Homework Soursethis what we need to do but all im missing is the shortest p
this what we need to do but, all im missing is the shortest path function of a weighted graph
Description: In this assignment you are asked to design and implement a connected, undirected, weighted graph. In the graph class, you must implement the following member functions:
// Add a vertex
// precond: node never appears in the graph before
void addVertex( const std::string& node );
// Add an edge.
// Throw a GraphException if vertices of this edge are not in graph
// pre-cond: the edge between sourceName and targetName does not exist
void addEdge( std::string sourceName, std::string targetName, int weight )
throw (GraphException);
// Remove a vertex and related arcs from graph
// Throw a GraphException if such vertex does not exist
void removeVertex( std::string nodeName )
throw(GraphException);
// Remove an edge
// Throw a GraphException if both vertices are not in graph
// Do nothing if the edge does not exist
void removeEdge( std::string srcName, std::string destName )
throw(GraphException);
// Depth-first traversal: visit ALL vertices once
// During the visit, print edges in the order they are visited
// If graph has no edge, print some information
void DFS( const std::string& source );
// Breadth-first traversal: visit ALL vertices once
// During the visit, print edges in the order they are visited
// If graph has no edge, print some information
void BFS( const std::string& source );
// Find shortest path from the node \"source\", and print all “visited” edges
void shortestPath( const std::string& source );
// print the graph
friend std::ostream& operator << (std::ostream&, const Graph&);
Design: In this design, two classes are needed. One is Menu, which is used to handle the interface between users and programs. This class is defined and implemented by the instructor. You are not required to modify this class. The other one is Graph. The Graph class must provide the above member functions.
In the Graph class, you are recommended to use either map<string, map<string, int> > or hash_map<string, map<string, int> > to represent a graph.
map > the_Graph;
this is my map above and i want to find the shortest path for this function below
void Graph::shortestPath(const std::string & source)
{
}
Solution
public void addVertex(const std::string& node) {
if (!hasVertex(node)) st.put(node, new SET<String>());
}
class GraphException extends RuntimeException
{
public GraphException( String name )
{
super( name );
}
}
class Edge{
string sourceName,targetName,
int weight;
Edge(string sourceName,string targetName,int weight){
sourceName=s;
targetName=d;
weight=w;
}
}
class Node{
ArrayList<Edge> AdjacencyList=new ArrayList<Edge>();
}
class Graph{
private static final Exception GraphException = null;
Node list[];
int vertices;
Graph(int v){
vertices=v;
list=new Node[v];
for(int i=0;i<v;i++)
list[i]=new Node();
}
public void addEdge(int s,int d,int w) throw new GraphException( \" vertices of this edge are not in graph\" );
{
Edge e1=new Edge(s,d,w);
list[s].AdjacenyList.add(e1);// If it were an undirected graph add the edge to source as well as destination node
}
public void bfs(){
bfs(0);
}
private void bfs(int s){
boolean visited[]=new boolean[vertices];
visited[s]=true;
ArrayList<Integer> queue=new ArrayList<Integer>();
while(!queue.isEmpty())
{
int next=queue.remove(0);
System.out.println(\"Visited \"+next+\"node\");
for(int i=0;i<list[next].AdjacencyList.size();i++)
{
Edge e1=list[next].AdjacencyList.get(i);
if(!visited[e1.d])
{
visited[e1.d]=true;
queue.add(e1.d);
}
}
}
}
}
void removeEdge( string srcName, string destName)throw new GraphException( \" remove edge are not in graph\" );{
Edge * e = getEdge(srcName,destName);
if (e != 0){
edges.erase(remove(edges.begin(),edges.end(),e),edges.end());
(*e).getV1()->removeEdge(e);
}
}
void removeVertex(string nodeName)throw new GraphException( \" remove vertices are not in graph\" ){
Vertex * v = getVertexWithLabel(nodeName);
if (v != 0){
vector<Edge *> edges = getVertexWithLabel(l)->getEdges();
for (vector<Edge *>::iterator it = edges.begin(); it != edges.end(); ++it){
string source = (*it)->getV1()->getLabel();
string dest = (*it)->getV2()->getLabel();
removeEdge(source,dest);
}
vertices.erase(nodeName);
}
else {
//handle case where vertex did not exist.
}
}
public void Shortest path( String startName )
{
PriorityQueue<Path> pq = new PriorityQueue<Path>( );
Vertex start = vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( \"Start vertex not found\" );
clearAll( );
pq.add( new Path( start, 0 ) ); start.dist = 0;
int nodesSeen = 0;
while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )
{
Path vrec = pq.remove( );
Vertex v = vrec.dest;
if( v.scratch != 0 ) // already processed v
continue;
v.scratch = 1;
nodesSeen++;
for( Edge e : v.adj )
{
Vertex w = e.dest;
double cvw = e.cost;
if( cvw < 0 )
throw new GraphException( \"Graph has negative edges\" );
if( w.dist > v.dist + cvw )
{
w.dist = v.dist +cvw;
w.prev = v;
pq.add( new Path( w, w.dist ) );
}
}
}
}
public class PreOrderDFSIterator implements Iterator<String> {
private Set<String> visited = new HashSet<String>();
private Deque<Iterator<String>> stack = new LinkedList<Iterator<String>>();
private Graph graph;
private String next;
public PreOrderDFSIterator(Graph g, string & source) {
this.stack.push(g.getNeighbors(source).iterator());
this.graph = g;
this.next = source;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
@Override
public boolean hasNext() {
return this.next != null;
}
@Override
public String next() {
if (this.next == null) {
throw new NoSuchElementException();
}
try {
this.visited.add(this.next);
return this.next;
} finally {
this.advance();
}
}
private void advance() {
Iterator<String> neighbors = this.stack.peek();
do {
while (!neighbors.hasNext()) { // No more nodes -> back out a level
this.stack.pop();
if (this.stack.isEmpty()) { // All done!
this.next = null;
return;
}
neighbors = this.stack.peek();
}
this.next = neighbors.next();
} while (this.visited.contains(this.next));
this.stack.push(this.graph.getNeighbors(this.next).iterator());
}
}
void printGraph(T * t){
map<string,Vertex*> vertices = t->getVertices();
for (map<string, Vertex*>::iterator it = vertices.begin(); it != vertices.end(); ++it){
cout << it->first <<\": \";
vector<Edge *> edges = it->second->getEdges();
for (vector<Edge *>::iterator jit = edges.begin(); jit != edges.end(); ++jit){
string l1 = (*jit)->getV1()->getLabel();
string l2=(*jit)->getV2()->getLabel();
if (l1 != it->first){cout << l1 << \", \";}
if (l2 != it->first){cout << l2 << \", \";}
}
cout << endl;
}
}
