↑ Return to Graph Algorithms 2017

Projects

Here you can find currently opened projects for you and your gained scores

General instructions:

Input/Output files are text files. Graphs (both directed and undirected) are represented through list of edges unless stated otherwise in a particular project description. Input files are CSV (Comma Separated Values) tables with one record per row, columns are delimited by TAB symbols and possibly enclosed in quotes. In Java you can use Asser.jar package classes (API) to read (Class CSVParser) and write (Class CSVWriter) CSV files.

An input CSV table contains the following columns: Vertex1, Vertex2, weight, id.

  • Vertex1, Vertex2 –  vertices incident to the edge (in case of directed graph, Vertex1 is the edge’s source/tail and Vertex2 is the edge’s destination/head)
  • weight – the weight of the edge (could be ignored if the particular project task does not require it)
  • id – the edge’s id

Project1:

  • Implement DFSB algorithm that detects all blocks in an undirected graph. From the table below download your graph and produce the list of blocks.
  • Bonus points: 5
  • INPUT: list of undirected edges in CSV table.
  • OUTPUT: text file containing the list of blocks, one block per line. A block is represented through its set of vertices. Note that articulation points will repeat in blocks that they are joining.
  • The benchmark graph is available at: CSV and  PDF. The blocks are the following: (1,2,6,13), (6,14,16,17), (1,3,7,8,15), (4,9), (5,12), (5, 10, 11), (1,4), (1,5), (18,19,20)
  • OPEN DATE: 04.10.2017
  • CLOSING DATE: 03.11.2017
  • Good luck!

Project2:

  • Find shortest paths for all pairs of vertices in a directed graph
  • Bonus points: 5
  • INPUT: list of directed non-negative weighted edges in CSV table.
  • OUTPUT: a CSV table representing matrix of the shortest distances.
    • The first row – vertex labels
    • The first column – vertex labels
    • field at row i column j – an integer representing the shortest distance from vertex vi to vertex vj
  • The benchmark graph is available at: CSV and PDF. The result matrix is available at: Res.
  • OPEN DATE: 04.10.2017
  • CLOSING DATE: 03.11.2017
  • Good luck!

 Project3:

  • Find a minimum spanning tree for every connected component from the graph
  • Bonus points: 5
  • INPUT: list of undirected non-negative weighted edges in CSV table.
  • OUTPUT: a comma-separated list of edge labels forming the spanning tree
  • The benchmark graph is available at: CSV and PDF. The resulting spanning tree is available as list of edge ids in the alphabetical order as TXT. The total weight of the minimal spanning tree is 395. Note that in general a graph may have more than one minimal-weight spanning tree
  • OPEN DATE: 04.10.2017
  • CLOSING DATE: 03.11.2017
  • Good luck!

Project4:

    • TBD

Project5:

  • TBD


Project6:

  • TBD