Trace all possible paths & Duration as per the Directed Graph (1 Viewer)

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
i think you need to "group" all A first, all B first.
what i mean is there must be an order first.
you have your data popping out of nowhere.

i am sorting it using macro.
also the map is outdated so you must follow your
chart data.
 

Attachments

  • matrix2.zip
    42.4 KB · Views: 94

Futurz

New member
Local time
Today, 13:06
Joined
Sep 17, 2021
Messages
26
i think you need to "group" all A first, all B first.
what i mean is there must be an order first.
you have your data popping out of nowhere.

i am sorting it using macro.
also the map is outdated so you must follow your
chart data.
Dear arnelgp,
The above attached file is showing Runtime error 438..
However in the earlier file, I sorted all A,B,C... manually by using sort Tool. Almost all paths traced except one path(see attached file)...
Please advice..
 

Attachments

  • matrix4.zip
    102.5 KB · Views: 86

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
use matrix2, i updated its VBA code.
you do not need to sort it manually.
the VBA will sort it before doing the
calculation.
 

Attachments

  • matrix2.zip
    49.6 KB · Views: 88

Futurz

New member
Local time
Today, 13:06
Joined
Sep 17, 2021
Messages
26
use matrix2, i updated its VBA code.
you do not need to sort it manually.
the VBA will sort it before doing the
calculation.
Dear arnelgp,

I am still getting Runtime error 438 with "macro 1"

*** I then Used Macro "do_path", it is working good***

Any new entries Sources, I am sorting manually...
I thank you for your excellent efforts...


Screenshot (1155).png
 

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
Any new entries Sources, I am sorting manually...
I thank you for your excellent efforts...
i just told you not to sort manually.
when you click the blue button, VBA will sort it.
 

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
you can try your 100 rows (with long "source"/"target" name).
 

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
try this one, I complete remove the sorting.
and i think there is no need to for you or the program to sort with
the current code.
 

Attachments

  • matrix2.zip
    49.7 KB · Views: 87

Futurz

New member
Local time
Today, 13:06
Joined
Sep 17, 2021
Messages
26
try this one, I complete remove the sorting.
and i think there is no need to for you or the program to sort with
the current code.
Dear arnelgp,
Yes, its working good...
My query is Resolved...
 

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
Try on bigger dataset.
on your post #27 there is a blank row on 18, make sure you press delete in side the cells
so it will not be included.
 

gemma-the-husky

Super Moderator
Staff member
Local time
Today, 13:06
Joined
Sep 12, 2006
Messages
15,614
You should be able to do this with (recursive) code, but you need a way to store all the the edges (of whatever the technical term is) of the graph.

you need a way to test that the graph does not return to a previously visited node, or the recursion will never end.
you also need a way to ignore paths that don't work. In the above example, if you are tracing routes from a to e, any route reaching z fails (eg A,F,Z) and needs to be ignored.

You could do this in vba, but it would be much easier with a language that has pointer data types, I think.

If I have time today, I will write some code to deal with your graph in post #19. It looks like a bit of fun.
 

MajP

You've got your good things, and you've got mine.
Local time
Today, 09:06
Joined
May 21, 2018
Messages
8,463
@ gemm-the-husky. If you want a 90% working solution to do this I would start here. You will have all the data structures to support this. This includes the interface to build your graph and the code and interface for the output. That will save you lots of tedious form and code building. So all of this is already built, you simply have to modify a version of the algorithm and use the structure. You can do this fine in vba, but I built these custom classes just for this purpose. It just makes writing other graph algorithms very easy.


In that example I do two slightly more complicated algorithms. One is the well knwon Djikstra shortest path to determine the shortest path between two paths. My algorithm is fast in
O(V^2) but if you want to modify you can get this to run O(|V|+|E|) * log |V|) using a priority que.
Also it does handle both directed and undirected graphs.
The next algorithm is the Floyd-Warshall which is the shortest path between all nodes. This is a hard to code algorithm, but still runs in O(V^3).
I will caution you that you would think that you could run a series of individual Dijkstra for each node pair instead of writing the Floyd-Warshal. That is what I did originally and it ran over night vs a few minutes with the Floyd_Warshall.

So if you want this is just a slight modification of the Floyd-warshall.

These algorithms use a form of Breadth First Search (BFS) .

As you can see it is a pretty simple algorithm to code. In my opinion far simpler than the Floyd-Warshall.
So if you want to use what I already built, it should not require much code than that algorithm. All the supporting procedures and data structures for creating and loading the Nodes and Edges exist. In that structure I aready account for visited nodes so you can easily avoid cycling. In all the above code the algorithms will not revisit a traversed edge so you cannot cycle.
 
Last edited:

gemma-the-husky

Super Moderator
Staff member
Local time
Today, 13:06
Joined
Sep 12, 2006
Messages
15,614
Here you go with a simple recursive solution.
(not particularly tedious. There's only a handful of lines in the recursive sub process. Most of the lines are taken up with recording the node details (in sub main).

By the way, I just modified the sub main code to output the results to a text file.


In sub main
1) define all the edges
2) then define the start and end route you want in the line
process from, to, path, length eg process "A","Z","",0
3) then just run main. The path and path length extend themselves with each iteration.

This iterates the entire graph.

A,F,Z Length: 6
A,B,F,Z Length: 19
A,B,C,Z Length: 22
A,B,Z Length: 25
A,B,E,Z Length: 16
A,C,Z Length: 15
A,D,Z Length: 26
A,D,E,Z Length: 16

I take the point @MajP just made - for large graphs, you repeat the same stuff over and over. I think you could build it backwards, starting from the end point, work backwards, and then you know the results for any intermediate point without repeating them again. Similar to an improved fibonacci recursion.


Code:
Option Compare Database
Option Explicit


Type TNode
    start As String
    end As String
    size As Long
End Type


Dim point As String
Dim nodes(20) As TNode


Dim results As String


Sub process(frompoint As String, target As String, path As String, length As Long)
Dim x As Long


    If frompoint = target Then
        If Len(results) > 0 Then
            results = results & vbCrLf
        End If
        results = results & path & "," & target & "  Length: " & length
        Exit Sub
    End If
   
    For x = 1 To 20
        If nodes(x).start = frompoint Then
            If path = "" Then
                process nodes(x).end, target, nodes(x).start, length + nodes(x).size
            Else
                process nodes(x).end, target, path & "," & nodes(x).start, length + nodes(x).size
            End If
        End If
    Next


End Sub


Sub main()
Dim x As Long
Dim fno As Long
Dim fname As String

    For x = 1 To 20
        nodes(x).start = ""
        nodes(x).end = ""
        nodes(x).size = 0
    Next

    results = ""
   
    nodes(1).start = "A"
    nodes(1).end = "F"
    nodes(1).size = 2

    nodes(2).start = "A"
    nodes(2).end = "B"
    nodes(2).size = 10

    nodes(3).start = "A"
    nodes(3).end = "C"
    nodes(3).size = 5

    nodes(4).start = "A"
    nodes(4).end = "D"
    nodes(4).size = 12

    nodes(5).start = "B"
    nodes(5).end = "F"
    nodes(5).size = 5

    nodes(6).start = "B"
    nodes(6).end = "C"
    nodes(6).size = 2

    nodes(7).start = "F"
    nodes(7).end = "Z"
    nodes(7).size = 4


    nodes(8).start = "B"
    nodes(8).end = "Z"
    nodes(8).size = 15


    nodes(9).start = "C"
    nodes(9).end = "Z"
    nodes(9).size = 10


    nodes(10).start = "D"
    nodes(10).end = "Z"
    nodes(10).size = 14

    nodes(11).start = "E"
    nodes(11).end = "Z"
    nodes(11).size = 1

    nodes(12).start = "B"
    nodes(12).end = "E"
    nodes(12).size = 5

    nodes(13).start = "D"
    nodes(13).end = "E"
    nodes(13).size = 3


    process "A", "Z", "", 0

    'MsgBox results

    fno = FreeFile
    fname = "d:\graph.txt"
  
    Open fname For Output As #fno
    Print #fno, results
    Close #fno
  
    Application.FollowHyperlink fname

End Sub
 
Last edited:

MajP

You've got your good things, and you've got mine.
Local time
Today, 09:06
Joined
May 21, 2018
Messages
8,463
Actually I see that there are algorithms using both DFS and BFS. I would think the BFS would be much faster. I would be curious to try both once I get some time.
 

Futurz

New member
Local time
Today, 13:06
Joined
Sep 17, 2021
Messages
26
Try on bigger dataset.
on your post #27 there is a blank row on 18, make sure you press delete in side the cells
so it will not be included.
Dear arnelgp,
I tried for a bigger Dataset, it took 6 minutes to display the result(very slow) for upto 80 Rows data.
But beyond 80 rows, it shows its busy....
Please provide a solution
see attached file...
 

Attachments

  • MatrixAllPaths.zip
    66.9 KB · Views: 77

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
it is slow considering it goes on recursively.
somewhat improve by storing "data" in collection/dictionary.
 

Attachments

  • MatrixAllPaths.zip
    96.1 KB · Views: 114

gemma-the-husky

Super Moderator
Staff member
Local time
Today, 13:06
Joined
Sep 12, 2006
Messages
15,614
@Futurz

This example isn't slow.

My recursive version does the network in your last example in a fraction of a second.
It doesn't sort the output, just puts it into a csv file, and opens the csv.
I changed it from my first solution, as you now have durations stored at the points, rather than along the edges.

This example stores the edges in an array as chars (strings), and therefore can only handle up to 26 points. You could allocate numbers to the points, so that instead of edge A,B, you have edge 1,2, and then you wouldn't have problem with a point limit.

Just open module1, and run the sub called "main".
main stores the edges in an array, and stores the values of the nodes in another array.
 

Attachments

  • network.mdb
    132 KB · Views: 80

arnelgp

..forever waiting... waiting for jellybean!
Local time
Today, 21:06
Joined
May 7, 2009
Messages
19,175
Just open module1, and run the sub called "main
it would be realistic if you work on the data provided.
there are 139 source/destination and 107 activity/duration.
duration is "tied" to a particular activity.
 

Users who are viewing this thread

Top Bottom