KeRNeLith / QuikGraph

Generic Graph Data Structures and Algorithms for .NET
https://kernelith.github.io/QuikGraph/
Microsoft Public License
453 stars 65 forks source link

[Question] running Depth First Search -- doesn't seem to be working #71

Open AlbertoEAF opened 1 year ago

AlbertoEAF commented 1 year ago

Describe the bug I simply want to detect cycles in my graph, and in case I find them, I want to report which are the offending cycles.

I've never used QuikGraph but it seemed like it would be a good fit. I made basic unit tests to start testing it out, but I'm not being able to run DFS.

To Reproduce Self-contained xUnit test code.

using FluentAssertions;
using QuikGraph;
using QuikGraph.Algorithms;
using StateQLTest.helpers;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Xunit.Abstractions;

namespace StateQLTest
{
    public class GraphCyclesTest : BaseTest
    {
        AdjacencyGraph<string, IEdge<string>> graph = new AdjacencyGraph<string, IEdge<string>>();

        string a = "a";
        string b = "b";
        string c = "c";

        public GraphCyclesTest(ITestOutputHelper logger) : base(logger) // Simply assigns logger to a protected member `logger`.
        {
        }

        [Fact]
        public void NoCyclesReturnsFalse()
        {
            graph.AddVertexRange(new List<string> { a, b, c });
            graph.AddEdge(new Edge<string>("a", "b"));
            graph.AddEdge(new Edge<string>("a", "c"));
            graph.AddEdge(new Edge<string>("b", "c"));

            HasCycles(graph).Should().BeFalse();
        }

        [Fact]
        public void WithCyclesReturnsTrue()
        {
            graph.AddVertexRange(new List<string> { a, b, c });
            graph.AddEdge(new Edge<string>("a", "b"));
            graph.AddEdge(new Edge<string>("a", "c"));
            graph.AddEdge(new Edge<string>("b", "c"));
            graph.AddEdge(new Edge<string>("c", "a"));  // Forms a loop.

            HasCycles(graph).Should().BeTrue();
        }

        private bool HasCycles<T>(QuikGraph.AdjacencyGraph<T, IEdge<T>> graph)
        {
            IEnumerable<T>? roots = graph.Roots();
            if (roots == null)
                return false;

            foreach (var root in roots)
            {
               var getPaths = graph.TreeDepthFirstSearch(root);
                if (getPaths == null) continue;

                IEnumerable<IEdge<T>> paths;
                bool success = getPaths(root, out paths);
                if (!success)
                    throw new InvalidProgramException("Couldn't compute quikgraph paths!");
                if (paths == null) return false;

                // TODO: if any path contains a repeated node, store that and return that collection of cycles at the end.

                logger.WriteLine(paths.ToString());
            }

            return false;
        }

    }
}

Expected behavior Both tests should pass, but I get success==false, so I must be doing something wrong.

Screenshots If applicable, add screenshots to help explain your problem.

Additional context Add any other context about the problem here.

chucklu commented 1 year ago

@AlbertoEAF if you want to detect cycles, try IsDirectedAcyclicGraph https://github.com/KeRNeLith/QuikGraph/blob/9cd6b49292e09041258708a37bed99c56177b0ef/src/QuikGraph/Extensions/AlgorithmExtensions.cs#L981