{"id":5493,"date":"2024-06-20T12:13:27","date_gmt":"2024-06-20T10:13:27","guid":{"rendered":"https:\/\/oopm.org\/?page_id=5493"},"modified":"2024-12-13T11:28:35","modified_gmt":"2024-12-13T10:28:35","slug":"11-3-1-a-graph-representing-cities-and-roads","status":"publish","type":"page","link":"https:\/\/oopm.org\/?page_id=5493","title":{"rendered":"11.3.1 A graph representing cities and roads"},"content":{"rendered":"
\"image_pdf\"<\/a>\"image_print\"<\/a><\/div>\n

Next we describe a graph representing cities and roads between cities. This graph is represented by a class RoadAndCityGraph<\/code>, which is a subclass of Graph<\/code>:<\/p>\n\n\n\n

   class<\/strong> RoadAndCityGraph: Graph \n      class<\/strong> Node::< \n         cityName -> cn: ref<\/strong> String:\n            cn := id\t\n         display::< \n             ...\n      class<\/strong> Edge::<\n         roadLength: var<\/strong> Integer\n         display::\n            ...\n      addCity(nm: var<\/strong> String) -> n: ref<\/strong> Node: \n         :::\n      addRoad(from, to: ref<\/strong> Node, dist: var<\/strong> integer) -> e: ref<\/strong> Edge:\n         :::\t \n      inner(RoadAndCityGraph)<\/code><\/pre>\n\n\n\n
RoadAndCityGraph<\/code> has the following attributes:<\/p>\n\n\n\n
    \n
  • A further binding of the virtual classes extended the descriptions of Node<\/code> and Edge<\/code> from Graph<\/code>. A Node<\/code> represents a city and an Edge<\/code> represents a road.<\/li>\n\n\n\n
  • A method addCity<\/code> and a method addRoad<\/code>.<\/li>\n<\/ul>\n\n\n\n
    The further binding of Node<\/code> adds the following attributes:<\/p>\n\n\n\n
      \n
    • A method cityName<\/code> which returns the id<\/code> of the node – the id<\/code> is used to represent the name of the city. <\/li>\n\n\n\n
    • A further binding of display<\/code>, we which extends the description of display from Node<\/code>.<\/li>\n\n\n\n
    • Note that no further binding of addEdge<\/code> is included here.<\/li>\n<\/ul>\n\n\n\n
      The further binding of Edge<\/code> adds the following attributes:<\/p>\n\n\n\n
        \n
      • A integer variable roadLength<\/code> holding the length of the road.<\/li>\n\n\n\n
      • A further binding of the display<\/code> method.<\/li>\n<\/ul>\n\n\n\n
        Below we show the details of addCity<\/code> and addNode<\/code>:<\/p>\n\n\n\n
              addCity(nm: var<\/strong> String) -> n: ref<\/strong> Node:\n         n := addNode(nm)\n      addRoad(from, to: ref<\/strong> Node, dist: var<\/strong> integer) -> e: ref<\/strong> Edge:\n         e := from.addEdge(to)\n         e.roadLength := dist<\/code><\/pre>\n\n\n\n
          \n
        • AddCity<\/code> has the name, nm<\/code>, of the city as parameter and adds a Node<\/code> with nm<\/code> as argument. The new Node<\/code> is returned as the value of addNode<\/code>.<\/li>\n\n\n\n
        • AddRoad<\/code> has the two cities being connected by the road and the distance between them as parameters: from<\/code>, to<\/code>, and dist<\/code>.<\/li>\n<\/ul>\n\n\n\n
          We may now use class RoadAndCityGraph<\/code> to define a region with some cities and roads. Herre we use Europe and Paris, London and Berlin:<\/p>\n\n\n\n
             Europe: obj<\/strong> RoadAndCityGraph\n      setUp:\n         n1, n2: ref<\/strong> Node\n         e: ref<\/strong> Edge\n         n1 := addCity(\"Paris\")\t \n         n2 := addCity(\"London\")\n         e := addRoad(n1,n2,291) -- 291 miles\n         e := addRoad(n2,n1,291)\n         n2 := addCity(\"Berlin\")\n         e := addRoad(n1,n2,1054) -- 1054 km\n   Europe.setUp<\/code><\/pre>\n\n\n\n
          The example should be self explanatory.<\/p>\n\n\n\n
          Note, however, as a remainder of the importance of being aware of units of quantities, we have deliberately shown the distance from Paris to London in miles and the distance from Paris to Berlin in kilometers. When you use Google Maps (at least at the location of the authors) you get the distance from Paris to London in miles and the one from Paris to Berlin in kilometers. In section