Triangle Inequality Violation
The triangle inequality theorem states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
Data Set: The Turkish Network file contains the data on the 81 node Turkish network. The file includes travel distances between 81 cities in Turkey.
Generate all possible combination of triangles C(81,3) from the 81 cities of Turkey using the combinatorics library. Travel distances in kilometers will be the sides of the triangle. List all of the triangles that violate the triangle inequality. Your project must be a Maven project (please watch the video to create one) and following commands should be enough to run it.
- mvn clean package
- java -jar target/HW1-1.0.jar
Your project will print out something like:
ESKİŞEHİR GİRESUN ARDAHAN
DİYARBAKIR KIRŞEHİR ZONGULDAK
AĞRI ERZİNCAN MUĞLA
Please click the invitation link and follow the instructions to get started with the submission system.
Example of triangle inequality violation [1]:
[1] Cristian Lumezanu, Randy Baden, Neil Spring, and Bobby Bhattacharjee. 2009. Triangle Inequality and Routing Policy Violations in the Internet. In Proceedings of the 10th International Conference on Passive and Active Network Measurement (PAM '09)