Lab 4

Starting from this week...:

• Use appropriate collections in order to represent data (otherwise: -0.5 points)
• Use Java Stream API in order to perform aggregate operations on data.

A city hall wants to install surveillance cameras at all intersections in a city.
To do this, it must connect all intersections with data cables, along the streets between them, such that the resulting network is connected.
We assume that the lengths of the streets between all the intersections of the city are known and the costs of installing the cables is proportional with the street lengths.
The problem is to determine how to install the data cables (on which streets) such as the total cost is minimum.

The main specifications of the application are:

Compulsory (1p)

• Create a Maven project.
• Create an object-oriented model of the problem. Streets have names and lengths, intersections have names. A street joins two intersections.
• Create a simple example of the problem with 10 intersections. Use streams in order to easily create the intersections.
• Create a list of streets, using LinkedList implementation and sort it by the length, using a comparator expressed as a lambda-expression or method reference. Make sure all the objects are comparable.
• Create a set of intersections, using a HashSet implementation. Verify the property that a Set does not contain duplicates.

Homework (2p)

• Create a class that describes the city.
• Using Java Stream API, write a query that display all the streets that are longer than a specified value and join at least 3 streets.
• Use a third-party library in order to generate random fake names for intersections and streets.
• Write an algorithm that returns not only the minimum cost solution, but a list of possible solutions, of a given size, ordered by their cost.
  You may use a library containing graph algorithm implementations, such as:
  • Graph4J (check the org.graph4j.spanning package).
  • JGraphT
• 
  

Advanced (2p)

• The city hall wants to regularly inspect the surveillance cameras, sending a maintenance car to go through it all.
• Implement an algorithm that determines the route of the maintenance car, in order to minimize the total length. The algorithm must run fast and should not find a solution that is twice as bad than the optimum route.
  
• Create a random problem generator, making sure that the lengths between intersections satisfy the triangle inequality.

Resources

• Slides
• Aggregate Operations
• The Java Tutorials: Collections ( Know Thy Complexities! )
• Setting the class path
• Creating, Importing, and Configuring Java Projects in Netbeans
• Packaging Programs in JAR Files

Objectives

• Use various collections and polymorphic algorithms.
• Use Java Stream API.
• Use Optional class and var keyword.
• Understand the notion of CLASSPATH.
• Use external JAR libraries.
• Create a Maven Project.
• Package all project classes as an executable JAR file.