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 nonnegative 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 nonnegative weighted edges in CSV table.
 OUTPUT: a commaseparated 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 minimalweight 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 nonnegative edges in CSV table.
 OUTPUT: 2 CSV tables:
 vertexcoloring (columns: vertexid,vertexcolor);
 edgecoloring (columns: edgeid, edgecolor)
 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 edgecoloring, (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 maximumcardinality 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 commaseparated list of edge ids that form a maximumcardinality edge matching
 The benchmark graph: Given the benchmark graph for Project 4, available at: CSV and PDF, one maxcard 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 maxflow 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!