Sign in to follow this  
Followers 0
Mat

Graph theory

8 posts in this topic

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:

Posted Image

Example of Prim's algorithm:

Posted Image

Exported as an image:

Posted 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

Share this post


Link to post
Share on other sites



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


ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

:)


The point of world view

Share this post


Link to post
Share on other sites

Hmm.. works like a charm.

Really well done, mate.


whoa! I can write!

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

The point of world view

Share this post


Link to post
Share on other sites

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 :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0