Graph theory

[Mat]

A graph in this context is a set of objects (called nodes or vertices - this program uses nodes) where some pairs of nodes are linked by arcs (also known as edges). The arcs are weighted, meaning there is a certain cost for traveling over them. This can be in terms of distance, time, cost or anything else. This program does not give units for arc weights though. Not to be confused with bar charts and line graphs you might see in excel.

A graph can represent a lot of problems. For example, you can think of a road map as being a graph, with nodes representing junctions and arcs representing roads. The weight of an arc could be the distance of that road in kilometers. Once as a graph, there are a number of algorithms to solve certain problems. For example Dijkstra's algorithm finds the shortest route from one node to another.

This has already been done to some extent in a few places, Toady did one for a set of squares that would find the shortest path using A* (an extension to dijkstra's algorithm) and hyperzap wrote a proof of concept His GUI was very basic and flickered, as well as being not as easy to use as it could be, so I started this project. Although both of those made me want to write this, I've implemented all the algorithms myself, so any bugs are my fault.

If you look at the source code you'll learn more than just maths as well, the main GUI element is a custom class I wrote entirely in AutoIt, with all the drawing done in GDI+. There are also some nice examples on using WM_NOTIFY with listviews, and making a status bar update when you hover over menu items. You can export the graphs to images, tables (in text and HTML) as well as svg. Open + Save + Undo + redo is also implemented, as well as locking of nodes and arcs to stop them being moved/changed.

https://sourceforge.net/p/graphau3/home/

Download

The exe is completely standalone btw.

Example:

Using this file: Example.grp

Screenshot of program:

Example of Prim's algorithm:

Exported as an image:

Exported as text table (May be a bit wide for your monitor):

|       1 |       2 |       3 |       4 |       5 |       6 |       7 |       8 |       9 |      10 |      11 |      12 |      13 |      14 |      15 |
       1 |       - |     181 |         |         |         |         |     173 |         |         |         |     121 |         |         |         |     180 |
       2 |     181 |       - |     123 |         |         |         |         |         |         |         |     188 |      88 |         |         |         |
       3 |         |     123 |       - |     187 |         |         |         |     149 |     131 |         |         |         |         |         |         |
       4 |         |         |     187 |       - |      76 |         |         |         |     102 |         |         |     257 |         |         |         |
       5 |         |         |         |      76 |       - |         |         |         |     134 |     199 |         |         |     207 |         |         |
       6 |         |         |         |         |         |       - |     182 |     166 |         |      76 |         |         |      98 |     113 |         |
       7 |     173 |         |         |         |         |     182 |       - |         |         |         |         |         |         |     108 |         |
       8 |         |         |     149 |         |         |     166 |         |       - |         |     126 |     106 |         |         |         |         |
       9 |         |         |     131 |     102 |     134 |         |         |         |       - |     149 |         |         |         |         |         |
      10 |         |         |         |         |     199 |      76 |         |     126 |     149 |       - |         |         |         |         |         |
      11 |     121 |     188 |         |         |         |         |         |     106 |         |         |       - |         |         |         |         |
      12 |         |      88 |         |     257 |         |         |         |         |         |         |         |       - |         |         |         |
      13 |         |         |         |         |     207 |      98 |         |         |         |         |         |         |       - |         |         |
      14 |         |         |         |         |         |     113 |     108 |         |         |         |         |         |         |       - |     176 |
      15 |     180 |         |         |         |         |         |         |         |         |         |         |         |         |     176 |       - |

Exported as html:

ExportTable.html

Exported as SVG (will require a modern browser):

ExportSVG.svg

Mat

[twitchyliquid64]

very, very nice. As you say, my node graph was just a proof of concept for building a P2P node routing system.

[Mat]

If you are interested in implementing the algorithm you used then it's easy enough to add another tab... Maybe I'll have to take a look at your code and see what I can find.

[ValeryVal]

It's great, Mat!

May I suggest one demure tip?

The graph nodes could be easily "rounded" by simple replacements:

_GDIPlus_GraphicsDrawRect - > _GDIPlus_GraphicsDrawEllipse

_GDIPlus_GraphicsFillRect -> _GDIPlus_GraphicsFillEllipse

It works for me.

[iShafayet]

Hmm.. works like a charm.

Really well done, mate.

[Mat]

I never considered rounding the nodes... But that would definitely work so thanks I'll add that in and release it with the next version (theres a few other things I've noticed like a bug in the saving function). There are also a few bugs when you add more than 30ish nodes, not to mention some performance issues with some of the algorithms which I've also improved. I've also noticed that I haven't implemented directed outout when exporting as svg... That shouldn't be too hard to implement with paths. I also want to triple buffer the drawing... But that will have to wait.

I also forgot to mention that there are settings for this, they just aren't advertised at all. Settings go in an ini file in the script (or exe directory):

Note that values shown are defaults, and colours are in ARGB. No error checking is done on these so garbage in = garbage out.

[Graphics]
ArcColor=0xFF000000          ; The default colour for arcs.
ArcWidth=1                   ; The default width of arcs
PathColor=0xFF000090         ; The colour of arcs that lie on the current path
PathWidth=2                  ; The width of arcs on the path
ArcSelectedColor=0xFFDD011C  ; The colour of selected arcs
ArcSelectedWidth=3           ; The width of selected arcs.
NodeColor=0xFF000000         ; The default outline colour of nodes
NodeWidth=1                  ; The default witdth of the outline of nodes
NodeDraggingColor=0xFF999999 ; The colour to fill a node with while it is being dragged
NodeSelectedColor=0xFF000677 ; The node fill colour for when they are selected
StartColor=0xFF067900        ; The colour of the start node
EndColor=0xFFDD011C          ; The colour of the end node
Antialias=1                  ; If 1 then drawing will be antialiased.
NodeSize=10                  ; The width (and height) of a node. Currently they must be square
BkColor=0xFFFFFFFF           ; The cackground colour of the graph.

[General]
Directed=0                   ; If 1 then graphs will be directed by default.

[Export]
Directed=-1                  ; 1 if exports should be directed, 0 if not. -1 will inherit [General]->Directed
Crop=1                       ; If 1 then exported images will be cropped.

Mat

[ValeryVal]

I never considered rounding the nodes...But that would definitely work

Graph would be more explicit (I think!) with simplified func _Canvas_GetArcPos up to:

Func _Canvas_GetArcPos($i)
    Local $aPos[4] = [ _
            $aNodes[$aArcs[$i][0]][0], _
            $aNodes[$aArcs[$i][0]][1], _
            $aNodes[$aArcs[$i][1]][0], _
            $aNodes[$aArcs[$i][1]][1]]

    Return $aPos
EndFunc   ;==>_Canvas_GetArcPos

[Mat]

That's what I had originally, but I didn't like it, so I wrote a more complicated function for it. Maybe that will have to be another setting? Very easy for me to implement (just an if test for the setting then a premature return in that function). I think the logic for the function is slightly out though, It's one of the things on my todo list.

Thanks again for the feedback

[AUTOlTER]

Hi Mat

I have just downloaded to take a look and it's a great job! 

I isolated the code related to graph representation and manipulation along with Dijkstra algorithm to use it for other script.

Since in mi problem all arcs have the same weight I always set the weight to 1. Then started to play with the code (like a lightweight test) and to my surprise I found (what I believe is) a bug. 

Of course the first thing I thought was "probably I missed something during the isolation process", however I was able to reproduce the bug running the .exe from the download.

Here is how to reproduce the bug (how tables are displayed) 

Nodes

1 182 189

2 262 149

3 216 271

 

Arcs

1 2 89

1 3 89

 

Dijkstra (1,3) = arc 2 (ok) 

Dijkstra (3,1) = arc 1 (fail) 

 

Notice that both arcs have the same weight. If I change the weights it works fine.

If I find a solution I'll post it here. 

Thanks!