McGraph is a GUI program for editing and solving common graph-theory problems. It can find shortest distance paths, and perform graph coloring. All graphs without self-looping edges are supported.
This program was made for a 1-month assignment in Object Oriented Programming, so it was a collaborative project with my lab partner. The requirements for the assignment were quite simple and basic to implement, so we added a lot of extensions such as animations, the graph solver functionality, UI customization, etc. which actually turned this into a usable program.
McGraph supports both directed and undirected edges. The graph solver will also work for both types of edges.
You can toggle an edges direction by selecting it and then pressing the direction toggle button on the node tool bar.
McGraph supports arbitrary numeric edge weights. This includes negative weights, as well as fractional weights. The graph solver will work for any edge weight. Non-numeric edge weights are not supported.
The edge weights can be entered into the edge weight field and will set the edge weight of all selected edges. This field can be found on the edge tool bar when an edge is selected.
McGraphs fully supports graphs with cycles, negative weights, and parallel edges. This means that all solver operations will work on these graphs. The only kinds of graphs that are not supported are graphs containing self looping edges.
Graphs can be saved and loaded from a custom file format (.graph). This format is completely lossless meaning graphs can be saved and loaded exactly as they are without any loss of information. Graphs can also be loaded from a "legacy" limited file format that is only supported because the assignment required it. However, this legacy format is lossy, visual customization of nodes and edges, as well as directionality of the edges cannot be saved.
Graphs can be saved and loaded from the file menu in the menu bar.
The graph solver can be used for many useful operations on graphs, including the classic task of finding the shortest path between any two nodes on the graph. This is also done using the Bellman-Ford algorithm, which can deal with edges with negative weights.
To use this feature, you must first mark the start and goal nodes of the graph by pressing Right-click on the respective nodes and clicking the Mark Start and Mark Goal buttons. Then, Right-click anywhere on the graph and select the Find Shortest Path button from the pop-up menu. All nodes and edges along the shortest path will be highlighted.
The graph solver can also find the distance of one node to all other nodes in a graph. This is also done using the Bellman-Ford algorithm.
To use this feature, you must first mark the start node for this operation by pressing Right-click on the desired node and clicking the Mark Start button in the pop-up menu. Then, Right-click and select Explore Graph from the pop-up menu. All nodes and edges reachable from the start node will be highlighted and marked with their distance to the start node in parenthesis.
Another useful feature of the graph solver is to perform graph coloring. This will color all nodes in the graph such that no nodes that are connected by an edge share the same color. McGraph uses a greedy graph coloring algorithm and uses heuristics to come up with a good node order. This means that graphs will usually be colored with the smallest possible number of different colors, however, this is not always the case. Even when the graph coloring isn't completely optimal, it usually comes pretty close.
To use this feature, Right-click anywhere on the graph and select Color Graph from the pop-up menu.
Most visual aspects of nodes and edges can be customized. This includes the fill color, border color, and text color of nodes, the color of edges, the sizes and positions of nodes and edges, as well as the styles of nodes and edges.
The supported node styles include rectangular, rounded, elliptic, and the diamond nodes.
The supported edge styles include line (1), curve (2), spline (3), and elbow joint (4) edges.
McGraph's GUI is mostly animated and responsive to user input, making it pretty intuitive. For example, when you select a node it will quickly blink to indicate that it is selected. When you hover over the button that changes the fill color of a node, that node's fill color will begin to flash to indicate what the button does.
Multiple nodes and edges can be selected with CTRL/⌘+Click. A selection rectangle can be created with CTRL/⌘+Click-drag.
McGraph does not support self looping edges. There is no way to create such edges.
Since performance wasn't a major concern during the development of this student project, McGraph does not perform very well on large (1000+ nodes and edges) graphs. One of the limitations of this assignment was that we could not multi-thread our program. This means that animations must also run on the main thread with the UI, which causes a lot of performance problems due to how we implemented the drawing.
Because we had to use MVC and the observer pattern, an animation playing on 1000 nodes will trigger the panel to redraw 60 × 1000 times per second. Even though the swing framework tries to coallesce duplicate draw requests, this still seems to be too much to handle.
The solver is still responsive and fully functional with 1000+ nodes, taking less than a second to execute.
Java version 1.8 or higher.
Download mcgraph.jar then run:
$ java -jar mcgraph.jarTo start the program with a particular graph run:
$ java -jar mcgraph.jar "dir/file.graph"This program and all of its source code are in the public domain, you can use them for anything you want. Enjoy :)