Summer School 2016

• Minicourse slides

• Useful links
  • User manual (developer version)
  • Introductory Tutorial
  • Source code repository: http://lemon.cs.elte.hu/hg/lemon-main
  • C++ reference guides
    • ​http://cplusplus.com
    • ​http://cppreference.com
• Road map of Hungary (in LGF format)
  • There are three versions:
    • Undirected version (.lgf.zip) Both one way and two ways road are represented by one single edge
    • Directed version (.lgf.zip) The two way roads are represented by tho oppositely directed arcs.
    • Strongly connected directed version (.lgf.zip) The largest strongly connected component of the previous file. Here is a printable .pdf version: hun-conn.pdf
  • The description of the LGF format can be found here: http://lemon.cs.elte.hu/pub/doc/1.3/a00002.html
  • The file contains the following attributes:
    • in the @nodes section:
      • label: the node label, >= 1 integer numbers
      • lat: the latitude of the node, floating point number
      • lon: the longitude of the node, floating point number
    • in the @arcs section:
      • length: The length of the road, in meter (integer number)
      • maxspeed: The maximum allowed speed , in km/h (integer number)
• Planar graph test examples: planar-graphs.zip
  • The file contains the following attributes:
    • in the @nodes section:
      • cost: cost of the nodes (integer number)
      • label: the node label, >= 0 integer numbers
      • coordinates_x and coordinates_y: the coordinates of the nodes, floating point number
    • in the @arcs section (in *-c.lgf files only)
      • capacity: capacity of the arcs (integer number)
      • cost: cost of the arcs (integer number)

• Homeworks
  • Is there a polynomial algorithm for finding the 1002 long sequence surely opening any three digit door?
    • Or just a short proof that it exists?
  • Find the two places in Hungary that are the farthest away from each other.
  • Find a small cardinality/cost vertex set covering all edges in the above graphs.