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:

    • Find a proper edge and vertex coloring for an undirected graph. Colors could be represented as integers.
    • Bonus points: 8
    • INPUT: list of undirected non-negative edges in CSV table.
    • OUTPUT: 2 CSV tables:
      • vertex-coloring (columns: vertex-id,vertex-color);
      • edge-coloring (columns: edge-id, edge-color)
    • The benchmark graph is available at: CSV and PDF. One possible output for vertex coloring, pairs (i,j) represent (node,color): (1,0), (2,1), (3,0), (4,2), (5,1 ), (6,0 ), (7,1 ), (8,2), (9,2), (10,0). And for edge-coloring, (edge, color): (e12,0),(e15,2),(e17,1),(e23,2),(e28,1),(e34,1),(e39,0),(e45,0),(e410,2),(e56,1),(e68,2),(e69,3),(e79,2),(e710,0),(e810,3).
    • OPEN DATE: 
    • CLOSING DATE: 20.01.2017
    • Good luck!

Project5:

  • Find a maximum-cardinality edge matching in a connected undirected graph
  • Bonus points: 8
  • INPUT: list of undirected edges in CSV table.
    • NOTE: the input graph differs from the graph from the previous task!
  • OUTPUT: TXT file with a comma-separated list of edge ids that form a maximum-cardinality edge matching
  • The benchmark graph: Given the benchmark graph for Project 4, available at: CSV  and PDF, one max-card edge matching is the following: e23, e15, e68, e79, e410.
  • OPEN DATE: 
  • CLOSING DATE: 20.01.2017
  • Good luck!


Project6:

  • Find a maximum flow in a given network.
  • Bonus points: 7
  • INPUT: list of directed edges and their capacities in CSV table, the source and the sink vertex. The format of CSV table: Vertex1, Vertex2, capacity, id
  • OUTPUT: CSV table with flow value assigned to each edge and the max-flow value. The format of the CSV table: edge_id, flow_value
  • The benchmark graph is available at: CSV and PDF. The maxflow for the graph is: 12.
  • OPEN DATE: 
  • CLOSING DATE: 20.01.2017
  • Good luck!