Mark Heath avatar Mark Heath committed 4a1a0e0

can find longest path

Comments (0)

Files changed (2)

GraphPad.Tests/GraphTests.cs

 
             Assert.AreEqual(1, g.LeafNodes.Count());
             Assert.AreEqual(leaf, g.LeafNodes.First());
+        }
 
+        [Test]
+        public void CanFindLongestPathSimple()
+        {
+            Graph g = CreateGraph(3);
+            var longest = g.FindLongestPath();
+            Assert.AreEqual(3, longest.Count());
+        }
+
+        [Test]
+        public void CanFindLongestPathComplex()
+        {
+            Graph g = CreateGraph(3);
+            g.Nodes.Add(new NodeInfo() { Name = "3" });
+            g.Nodes.Add(new NodeInfo() { Name = "4" });
+            g.Nodes.Add(new NodeInfo() { Name = "5" });
+            g.Nodes[1].AddChild(g.Nodes[3]);
+            g.Nodes[3].AddChild(g.Nodes[4]);
+            g.Nodes[4].AddChild(g.Nodes[5]);
+
+            var longest = g.FindLongestPath();
+            Assert.AreEqual(5, longest.Count());
+        }
+
+        private Graph CreateGraph(int nodes)
+        {
+            Graph g = new Graph();
+            for (int n = 0; n < nodes; n++)
+            {
+                g.Nodes.Add(new NodeInfo() { Name = n.ToString() });
+                if (n > 0)
+                {
+                    g.Nodes[n-1].AddChild(g.Nodes[n]);
+                }
+            }
+            return g;
         }
     }
 }

GraphPad/Logic/Graph.cs

         public IEnumerable<NodeInfo> LeafNodes { get { return nodes.Where(n => n.IsLeafNode()); } }
 
         public IList<NodeInfo> Nodes { get { return nodes; } }
+        
+        public IEnumerable<NodeInfo> FindLongestPath()
+        {
+            return FindLongest(new List<NodeInfo>(), RootNodes);
+        }
+
+        private List<NodeInfo> FindLongest(List<NodeInfo> pathSoFar, IEnumerable<NodeInfo> nodesToTest)
+        {
+            var longest = pathSoFar;
+            foreach (var node in nodesToTest)
+            {
+                var newPath = new List<NodeInfo>();
+                newPath.AddRange(pathSoFar);
+                newPath.Add(node);
+                var testPath = FindLongest(newPath, node.Children);
+                if (testPath.Count > pathSoFar.Count)
+                    longest = testPath;
+            }
+            return longest;
+        }
     }
 }
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.