Given the following graph of possible flights between seven US cities: (graph ta

Question

Given the following graph of possible flights between seven US cities:

(graph taken from the web site of the American Mathematical Society, http://www.ams.org)

Define a predicate route/3 that takes two cities as arguments and finds the routes to get from city A to a city B. Your predicate should have the signature route(cityA, cityB, Route). Examples:

?- route(seattle, boston, X).

X = [seattle, omaha, atlanta, boston] ;

false.

?- route(fresno, atlanta, X).

X = [fresno, seattle, omaha, atlanta] ;

X = [fresno, albany, seattle, omaha, atlanta] ;

X = [fresno, albany, dallas, seattle, omaha, atlanta] ;

false.

?- route(albany, atlanta, X).

X = [albany, seattle, omaha, atlanta] ;

X = [albany, dallas, seattle, omaha, atlanta] ;

false.

?- route(boston, atlanta, X).

false.

Explanation / Answer

# program to check if there is exist a path between two vertices

# of a graph

from collections import defaultdict

#This class represents a directed graph using adjacency list representation

class Graph:

def __init__(self,vertices):

        self.V= vertices #No. of vertices

        self.graph = defaultdict(list) # default dictionary to store graph

    # function to add an edge to graph

    def addEdge(self,u,v):

        self.graph[u].append(v)

     # Use BFS to check path between s and d

    def isReachable(self, s, d):

        # Mark all the vertices as not visited

        visited =[False]*(self.V)

        # Create a queue for BFS

        queue=[]

        # Mark the source node as visited and enqueue it

        queue.append(s)

        visited[s] = True

        while queue:

            #Dequeue a vertex from queue

            n = queue.pop(0)

            # If this adjacent node is the destination node,

            # then return true

             if n == d:

                 return True

            # Else, continue to do BFS

            for i in self.graph[n]:

                if visited[i] == False:

                    queue.append(i)

                    visited[i] = True

         # If BFS is complete without visited d

         return False

# Create a graph given in the above diagram

g = Graph(4)

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

u =1; v = 3

if g.isReachable(u, v):

    print("There is a path from %d to %d" % (u,v))

else :

    print("There is no path from %d to %d" % (u,v))

u = 3; v = 1

if g.isReachable(u, v) :

    print("There is a path from %d to %d" % (u,v))

else :

    print("There is no path from %d to %d" % (u,v))

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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