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

[Nikolay]

LICEcap, attached diagram and the code below. The random graph was generated using https://gist.github.com/erkal/9746513 (some script I have found on Google and adopted a bit).
There is a delay added specifically for filming (500ms) for each step

After reading a bit, now it's clear that BFS (breadth-first-search) should be used instead of DFS (depth-first-search), it should always find the shortest path, actually (given all edges have equal "weight"). The code below finds just SOME path
It's not that big change to the code below, maybe somebody will do it 

Code Select Expand


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

namespace ConsoleApp1
{
    internal class Program
    {
        const string GREEN = "RGB(0,255,0)";
        const string RED = "RGB(255,0,0)";

        static void Main(string[] args)
        {
            var app = new Visio.Application();
            var doc = app.Documents.Open(@"C:\Projects\test\random-graph\demo-drawing.vsdx");

            var page = doc.Pages[1];
            var shapes = page.Shapes;

            var startShape = shapes.Cast<Visio.Shape>().First(s => s.Text == "3");
            var endShape = shapes.Cast<Visio.Shape>().First(s => s.Text == "17");

            var connects = page.Connects.Cast<Visio.Connect>();

            Stack<int> DFS(int srcId, int dstId, Func<int, Array> getChildIds)
            {
                var trail = new Stack<int>();
                var visited = new HashSet<int>();

                bool FindFrom(int shpId)
                {
                    visited.Add(shpId);
                    trail.Push(shpId);

                    foreach (int childId in getChildIds(shpId))
                    {
                        var connectors = connects.Where(a => a.ToSheet.ID == shpId).Select(b => b.FromSheet.ID);
                        var connect = connects.Where(a => a.ToSheet.ID == childId).First(b => connectors.Contains(b.FromSheet.ID));

                        connect.FromSheet.CellsU["LineColor"].FormulaU = GREEN;
                        Thread.Sleep(500);

                        if (!visited.Contains(childId))
                        {
                            shapes.ItemFromID[childId].CellsU["FillForegnd"].FormulaU = GREEN;
                            if (childId == dstId || FindFrom(childId))
                            {
                                return true;
                            }
                        }
                        connect.FromSheet.CellsU["LineColor"].FormulaU = RED;
                        shapes.ItemFromID[childId].CellsU["FillForegnd"].FormulaU = RED;
                    }
                   
                    trail.Pop();
                    shapes.ItemFromID[shpId].CellsU["FillForegnd"].FormulaU = RED;
                    return false;
                }

                FindFrom(srcId);

                return trail;
            }

            var path = DFS(startShape.ID, endShape.ID, shpId =>
                shapes.ItemFromID[shpId].ConnectedShapes(Visio.VisConnectedShapesFlags.visConnectedShapesOutgoingNodes, "")
            );

            foreach (var id in path)
            {
                shapes.ItemFromID[id].CellsU["FillForegnd"].FormulaU = "RGB(0,0,255)";
            }

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

            doc.Saved = true;
            app.Quit();
        }
    }
}


[Surrogate]

Thank you!