Find the path through which the shapes on the drawing page are linked

[jigar189]

  Hi,
   I need to find the entire path, through which the shapes are linked on the active drawing page, through code. There is a property called Paths and PathsLocal but I have no idea how to use them or how they behave?
  for e.g. a sample path would be
      Shape1 -> Shape2 -> Shape3

   My language for development is C#.
   Can someone pls help me with the code or suggest an approach?

   

[wapperdude]

Yeah, I know this is old.  But has a lot of looks.  So here are some related links to solve this:
http://visguy.com/vgforum/index.php?topic=6373.msg26266#msg26266
http://visguy.com/vgforum/index.php?topic=5936.15
http://visguy.com/vgforum/index.php?topic=9277.msg41818#msg41818

[Nikolay]

The shapes may be linked using several paths. For example, look at the picture from the linked post:


As you can see, there are multiple paths between "3" and "5".
Which one do you want to get?

Or on your diagram, this may not be the case?

If what you mean is you want to get the connected shapes for a specific one, then you can use shape.ConnectedShapes to get the immediate preceding/following shapes for a specific one.

If you are okay with ANY path (i.e. a "random" one), you can simply use DFS (depth-first-search) algorithm.

[Nikolay]

P.S. Ups. Have not looked at the initial post date ("catch the necroposter")

[wapperdude]

LOL.  Yes old post.  I chose it because  (1) it wasn't answered, and, as indicated, there are multiple answers on the forum, and (2) it's an interesting topic, so gives the forum more presence in Google searches.

A note about the 1st link.  The presented algorithm will find the shortest path out of many, find all paths, or find only paths that lead in, or lead out.  So, it is not a simple code, but tries to give the user many options that would be of interest for network analysis.

[Nikolay]

Right. Anyway. Here is some code that implements the mentioned DFS in C# (as small as I can get it), for Visio (full code, a console app).
It's much easier than Dijkstra, but finds a RANDOM path

Code Select Expand


using Visio= Microsoft.Office.Interop.Visio;
using System.Collections.Generic;
using System;

namespace ConsoleApp1
{
    internal class Program
    {
        public static Stack<int> DFS(int srcId, int dstId, Func<int, Array> getChildIds)
        {
            var trail = new Stack<int>(); // path from src to dst
            var visited = new HashSet<int>(); // visited shapes

            bool FindFrom(int shpId)
            {
                // we've already visited this shape, it's of no use
                if (visited.Contains(shpId))
                    return false;

                // mark this shape as visited
                visited.Add(shpId);

                foreach (int childId in getChildIds(shpId))
                {
                    // if we've found dst or a path to dst, then we're done
                    if (childId == dstId || FindFrom(childId))
                    {
                        trail.Push(childId);
                        return true;
                    }
                }

                return false;
            }

            if (FindFrom(srcId))
                trail.Push(srcId);

            return trail;
        }

        static void Main(string[] args)
        {
            var app = new Visio.Application();
            var doc = app.Documents.Open(@"C:\Users\nbelyh\Documents\connector-test.vsdx");

            var path = DFS(1, 6, shpId =>
                doc.Pages[1].Shapes.ItemFromID[shpId].ConnectedShapes(Visio.VisConnectedShapesFlags.visConnectedShapesOutgoingNodes, "")
            );

            Console.WriteLine($"Path: {string.Join(",", path)}");

            app.Quit();
        }
    }
}


[wapperdude]

Hadn't heard of DFS.  Went to https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/.  Either I'm missing something or this is useless from a connectivity perspective.  That it finds a random path would be an understatement.  It just works its way thru all the nodes without any requirement that adjacent, visited nodes must be connected. 

Am I missing something???

[Nikolay]

Yes, you need to remember the path (i.e. it's a minor "modification" of DFS, where you, additionally to "visiting" shapes, remember the "path").

Check out:
https://brilliant.org/wiki/depth-first-search-dfs/

Or:
https://www.baeldung.com/cs/dfs-vs-bfs-vs-dijkstra

[wapperdude]

Thanx.  Will check those out. 

[Nikolay]

An animation to show how the code above works, just added circle highlight. start = 3, target = 17

[wapperdude]

Seems like nodes 8 and 30 should not be blue.

[Nikolay]

Once again, the DFS provides a RANDOM path. Not the shortest. Not the best. Random.
I.e. the result path may be not an optimal one, but it will lead from start to finish.

In the example above, there is a shorter path that does not include 8 and 30, you are right. But it is not selected. Instead, a longer path is selected that goes through 8 and 30.

There are better algorithms of course. This one may be good in case you know apriori there is just one pagh.

[wapperdude]

I probably made a bad assumption, namely, that the code you posted does shortest path.  In the 2nd link you provided, which compares the 3 sort algorithms, it explains that DFS and BFS can find shortest path, either recursively or iteratively.  And, explains how to do it.

Your nifty demo looked like it was doing that.

Well, there ya go. 
This did generate some interest.

[Nikolay]

You are right, the code above stops when it finds any path, which may be not the shortest one
But can be improved to continue and try to find a better one!

I thought that DFS always finds random, but apparently it can do better than this

[Surrogate]

An animation to show

Great demo!!!!
Nikolay, how you made this?