Vitaly Pechenkin, Professor, Ph,
pechenkinvv@grin-software.net
Yuri Gagarin Saratov State Technical University
GRaph INterface
On this website you can download Grin (GRaph INterface) software for MS Windows (NT . . 10), which allows you to better understand graph and network theory problems, see the solution for these problems directly on the graph. Working with the software, you can take a virtual journey through interesting sections of discrete mathematics. The results of work of many algorithms can be seen at once, which allows to estimate the obtained solution, to understand the essence of the problem.
Grin is a useful computer software for university students and teachers, which can be used not only by mathematicians (discrete mathematics, graph theory, operations research), but also by economists (mathematical models in economics), sociologists (social network analysis) and all those who are interested in discrete models. The software is easy to learn, and if the user has computer skills, it will not be difficult to use.
With the Grin program you can create, interactively edit and explore graphs. The graphs are saved to disk and can be easily downloaded. The help system (in hlp format, requires installation and use of WinHlp32.exe) contains information not only on the program itself, but also detailed help on graph theory and optimization problems of Grin theory. For teachers will be useful methodical materials, which contain special tasks for students to work with Grin in practical classes on the course "Applied aspects of graph theory"
Editing graph commands
- Add graph elements (vertices and edges)
- Delete graph elements (vertices, edges, connectivity components, the whole graph)
- Move graph elements (vertices, connectivity components and the whole graph)
- Change the size of the whole graph or its selected parts: increase, decrease, autofill visible window space)
- Edit the attributes of the elements in the graph (name, colour, weight and some others)
- Change graph type (Directed or Undirected)
- The programme supports standard clipboard operations (copy, paste, cut, delete, select). The clipboard is supported at application level. You can copy and paste graphs to and from the clipboard as a whole or in parts. Besides, the program allows to copy graph image to MS Windows clipboard in raster (bmp) or vector (wmf) format. This feature allows graph images to be copied directly into the office application
- You can decompose the model (graph arcs). This is useful when building complex multi-level project models when solving the critical path problem. Any arc (work) of a project can be treated as an independent project. In this case, when solving the problem for the current model, recursive calculation of critical paths for all its constituent activities with decomposition will be performed
Problem-solving algorithms
- Metric characteristics of the graph (radius, diameter, density, non-density, smallest vertex coverage and some others)
- Paths and cycles (Eulerian and Hamiltonian)
- Bridges and cutpoints
- Vertex colouring (minimal vertex colouring and heuristic colouring algorithms)
- Automorphism Group
- Minimal spanning tree
- Shortest Paths
- Maximum capacity path
- K shortest paths
- The traveling salesman's problem (classical formulation and its generalisation to several traveling salesmen)
- The maximum flow problem
- Critical path problem (with calculation of time reserves for project events and activities represented by an oriented network)
- Building a Dominance Hierarchy in a Social Network (Linton Freeman's Dominance Hierarchy Algorithm)
- Algorithms for calculating centrality characteristics for social networks
- Stochastic modelling of the operation of Petri nets. The process randomly selects a live transition according to given priorities. The simulation is run as long as at least one transition is alive.
The user can save the information from the results window in a graph report file. This file can also be viewed by calling a single command. An alternative way to store information about a graph is in the description of the graph itself, which is saved to the file along with it and is available at any time on the Description tab of the graph window.
The software supports several formats for saving and loading graph information. For export and import operations, MS Excel can be used, which is installed on the user's machine. It is also possible to convert the graph description into plain text (KrackPlot graph representation format), which can be viewed and edited in a conventional text editor.
The standard software file in which the graph information is stored is an XML file, the structure of which is described by the original author's tags. The structure of the file is quite simple and can be viewed and understood in notepad. The user can simply edit the file in a text editor (with some care).
A graph can be saved in some standard graphical formats (bmp or wmf). To do so, use the command "Save as..." and select the appropriate format. When pasting the image in a text editor, it is better to use the command to copy the image in the appropriate format to the clipboard.