Write in the Racket programming language functions: (a) Graph to define a graph.
ID: 2247618 • Letter: W
Question
Write in the Racket programming language functions: (a) Graph to define a graph. A graph is a list of (node list of nodes) (b) neighbors neighbors(node, graph) = list of nodes neighbors: node graph -> list of nodes to compute node’s neighbors in graph. (c) find-route find-route(node, node, graph) = list of nodes or false find-route: node node graph -> list of nodes or false to compute a list of nodes, starting with the origination node and ending with the destination node in a graph. If there is no path, the value of function is false. Test the program for the graph Example G has no neighbors: empty A has the list of neighbors (B E) Hint (define Graph etc. ) (define (neighbors a-node a-graph) etc. ) (define (find-route origination destination graph) etc. ) Test (define Graph '((A (B E)) (B (E F)) (C (D)) (D ()) (E (C F)) (F (D G)) (G ()))) (find-route 'A 'G Graph) -> (list 'A 'B 'E 'F 'G) (find-route 'C 'G Graph) -> #f
Explanation / Answer
First of all the given problem stated as be written as below drawn:
A
/
/
B C
| /|
| / |
D E F
| /
|/
G
(arrows pointing down)
(define mygraph (make-graph
'(a b c d e f g)
(lambda (node)
(cond
[(symbol=? node 'a) '(b)]
[(symbol=? node 'b) '(d e)]
[(symbol=? node 'c) '(e f)]
[(member node '(d e f)) '(g)]
[(symbol=? node 'g) '()])) symbol=?))
A --------> E
/
B->C-->D
assume ((graph-neighbor g) 'A) => '(B E)
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <limits> // for numeric_limits
#include <queue>
#include <utility> // for pair
#include <algorithm>
#include <iterator>
typedef int vertex_t;
typedef double weight_t;
const weight_t max_weight = std::numeric_limits<double>::infinity();
struct neighbor {
vertex_t target;
weight_t weight;
neighbor(vertex_t arg_target, weight_t arg_weight)
: target(arg_target), weight(arg_weight) { }
};
typedef std::vector<std::vector<neighbor> > adjacency_list_t;
typedef std::pair<weight_t, vertex_t> weight_vertex_pair_t;
void DijkstraComputePaths(vertex_t source,
const adjacency_list_t &adjacency_list,
std::vector<weight_t> &min_distance,
std::vector<vertex_t> &previous)
{
int n = adjacency_list.size();
min_distance.clear();
min_distance.resize(n, max_weight);
min_distance[source] = 0;
previous.clear();
previous.resize(n, -1);
// we use greater instead of less to turn max-heap into min-heap
std::priority_queue<weight_vertex_pair_t,
std::vector<weight_vertex_pair_t>,
std::greater<weight_vertex_pair_t> > vertex_queue;
vertex_queue.push(std::make_pair(min_distance[source], source));
while (!vertex_queue.empty())
{
weight_t dist = vertex_queue.top().first;
vertex_t u = vertex_queue.top().second;
vertex_queue.pop();
// Because we leave old copies of the vertex in the priority queue
// (with outdated higher distances), we need to ignore it when we come
// across it again, by checking its distance against the minimum distance
if (dist > min_distance[u])
continue;
// Visit each edge exiting u
const std::vector<neighbor> &neighbors = adjacency_list[u];
for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
neighbor_iter != neighbors.end();
neighbor_iter++)
{
vertex_t v = neighbor_iter->target;
weight_t weight = neighbor_iter->weight;
weight_t distance_through_u = dist + weight;
if (distance_through_u < min_distance[v]) {
min_distance[v] = distance_through_u;
previous[v] = u;
vertex_queue.push(std::make_pair(min_distance[v], v));
}
}
}
}
std::list<vertex_t> DijkstraGetShortestPathTo(
vertex_t vertex, const std::vector<vertex_t> &previous)
{
std::list<vertex_t> path;
for ( ; vertex != -1; vertex = previous[vertex])
path.push_front(vertex);
return path;
}
int main()
{
// remember to insert edges both ways for an undirected graph
adjacency_list_t adjacency_list(6);
// 0 = a
adjacency_list[0].push_back(neighbor(1, 7));
adjacency_list[0].push_back(neighbor(2, 9));
adjacency_list[0].push_back(neighbor(5, 14));
// 1 = b
adjacency_list[1].push_back(neighbor(0, 7));
adjacency_list[1].push_back(neighbor(2, 10));
adjacency_list[1].push_back(neighbor(3, 15));
// 2 = c
adjacency_list[2].push_back(neighbor(0, 9));
adjacency_list[2].push_back(neighbor(1, 10));
adjacency_list[2].push_back(neighbor(3, 11));
adjacency_list[2].push_back(neighbor(5, 2));
// 3 = d
adjacency_list[3].push_back(neighbor(1, 15));
adjacency_list[3].push_back(neighbor(2, 11));
adjacency_list[3].push_back(neighbor(4, 6));
// 4 = e
adjacency_list[4].push_back(neighbor(3, 6));
adjacency_list[4].push_back(neighbor(5, 9));
// 5 = f
adjacency_list[5].push_back(neighbor(0, 14));
adjacency_list[5].push_back(neighbor(2, 2));
adjacency_list[5].push_back(neighbor(4, 9));
std::vector<weight_t> min_distance;
std::vector<vertex_t> previous;
DijkstraComputePaths(0, adjacency_list, min_distance, previous);
std::cout << "Distance from 0 to 4: " << min_distance[4] << std::endl;
std::list<vertex_t> path = DijkstraGetShortestPathTo(4, previous);
std::cout << "Path : ";
std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " "));
std::cout << std::endl;
return 0;}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.