Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 384. (October 2015)

I. 384. Create an application to create and manipulate simple graphs (that is, graphs without loops or multiple edges). Your program should be able to handle and edit graphs with at most 20 vertices, and the user should be able to save and read these from a text file.

Upon clicking on an empty area in edit mode, a new vertex should be drawn. If the user clicks on two vertices, then the first vertex and the second vertex should become connected with an (undirected) edge if there was no edge between them, or the edge should be removed if there was already one between them.

Right-clicking with the mouse should have an analogous meaning: drawing or deleting a directed edge. The user should be able to move vertices with a drag-and-drop operation. Your program should number the vertices starting from 1. A double-click on a vertex should delete that vertex. If a vertex is removed, then all its edges should also be removed, and the numbers of all larger vertices should be decreased by one. Hence in the graph with \(\displaystyle N\) vertices, the vertex numbers range from 1 to \(\displaystyle N\). Vertices should be displayed as simple disks, with the current vertex numbers inside the disk. Edges should be drawn as line segments, and directed edges should have arrows. Your program can ignore certain graphical issues, for example, it is not considered as a problem if a disk partially covers an edge of a different vertex, or if two disks representing two vertices overlap. We can assume that the user is experienced, and tries to create a nice graph layout. Upon pressing key M, or choosing Save from the menu, your program should save the graph data into a text file graf.txt. The first line of the file should contain the number of vertices \(\displaystyle N\) and edges \(\displaystyle E\), then the width and height of the drawing area, separated by a space. The following \(\displaystyle N\) lines contain the coordinates of the vertices obtained from the graphical input (pairs of integers separated by a space). The next \(\displaystyle E\) lines should contain the edge data (again, pairs of integers separated by a space). Upon pressing key B, or choosing Open from the menu, your program should erase the current working area and open the file graf.txt for further editing.

In your solution you can use any programming language or developer environment that appears on our ``Rules of the contest'' page. We also accept web applications running on the client side.

The source code of your program\(\displaystyle -\)together with a short documentation also describing your solution and specifying the developer environment to compile your code\(\displaystyle -\)should be submitted in a compressed file i384.zip.

(10 pont)

Deadline expired on November 10, 2015.


Statistics:

2 students sent a solution.
10 points:Kazal Soma, Olexó Gergely.

Problems in Information Technology of KöMaL, October 2015