Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
AlbertoEAF opened this issue Mar 22, 2023 · 1 comment
Open
Assignees
Labels
bug Something isn't working

Comments

@AlbertoEAF
Copy link

AlbertoEAF commented Mar 22, 2023

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.

@AlbertoEAF AlbertoEAF added the bug Something isn't working label Mar 22, 2023
@AlbertoEAF AlbertoEAF changed the title Need help with finding cycles -- not sure I'm seeing a bug or misusing the API Need help running Depth First Search -- doesn't seem to be working Mar 22, 2023
@AlbertoEAF AlbertoEAF changed the title Need help running Depth First Search -- doesn't seem to be working [Question] running Depth First Search -- doesn't seem to be working Mar 22, 2023
@chucklu
Copy link

chucklu commented Apr 12, 2023

@AlbertoEAF if you want to detect cycles, try IsDirectedAcyclicGraph

public static bool IsDirectedAcyclicGraph<TVertex, TEdge>(

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

3 participants