CycleGraph.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CycleGraph
{
    public class Node
    {
        public int Id { get; set; }
        public IList<Node> ConnectedNodes { get; set; }

        public override string ToString()
        {
            var nodeDesc = new StringBuilder();
            nodeDesc.Append("Node id: " + Id);
            nodeDesc.Append(Environment.NewLine);
            nodeDesc.Append("Connected to: ");
            foreach (var connectedNode in ConnectedNodes.OrderBy(y => y.Id))
            {
                nodeDesc.Append(connectedNode.Id + ", ");
            }
            nodeDesc.Append(Environment.NewLine);
            return nodeDesc.ToString();
        }

        public override bool Equals(object obj)
        {
            return Id == ((Node)obj).Id;
        }

        public override int GetHashCode()
        {
            return Id.GetHashCode();
        }

        private bool _isHandled = false;
        public bool IsHandled { get { return _isHandled; } }
        internal void MarkAsHandled()
        {
            _isHandled = true;
        }
    }

    public class Graph
    {
        public IList<Node> NodesInGraph { get; set; }
        public override string ToString()
        {
            var nodesDesc = new StringBuilder();
            foreach (var node in NodesInGraph.OrderBy(y => y.Id))
            {
                nodesDesc.Append(node.ToString());
            }
            return nodesDesc.ToString();
        }

        public bool IsSuperSetOfGraph(Graph graph)
        {
            var isSuperSet = graph.NodesInGraph != null && graph.NodesInGraph.Count > 0 && graph.NodesInGraph.Count < NodesInGraph.Count;
            foreach (var node in graph.NodesInGraph)
            {
                isSuperSet = isSuperSet && NodesInGraph.Contains(node);
            }
            return isSuperSet;
        }

        public override bool Equals(object obj)
        {
            var equal = true;
            var otherGraph = (Graph)obj;
            if (otherGraph.NodesInGraph.Count != NodesInGraph.Count)
            {
                return false;
            }
            foreach (var node in otherGraph.NodesInGraph)
            {
                equal = equal && NodesInGraph.Contains(node);
            }
            return equal;
        }

        public override int GetHashCode()
        {
            var hash = NodesInGraph.Sum(y => y.GetHashCode());
            return hash;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter graph to use: ");
            var graphNumber = Console.ReadLine();
            
            Graph graph = null;
            switch(graphNumber)
            {
                case "1": graph = BuildGraph(); break;
                case "2": graph = BuildGraph2(); break;
                default: graph = BuildGraph3(); break;
            }
            IList<Graph> cycles = new List<Graph>();
            
            Console.Write(graph.ToString());

            foreach(var node in graph.NodesInGraph)
            {
                ((List<Graph>)cycles).AddRange(FindCycle(node));
                node.MarkAsHandled();
                cycles = cycles.Distinct().ToList();
            }
            cycles = cycles.Distinct().ToList();

            cycles = RemoveSuperSets(cycles);

            Console.WriteLine("=====CYCLES=====");
            foreach (var cycle in cycles.OrderBy(y => y.NodesInGraph.Count))
            {
                Console.Write(cycle.ToString());
                Console.WriteLine("=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=");
            }

            Console.ReadLine();
        }

        private static IList<Graph> RemoveSuperSets(IList<Graph> cycles)
        {
            var superSets = new List<Graph>();
            foreach (var cycle in cycles.OrderByDescending(y => y.NodesInGraph.Count))
            {
                if (IsSuperSet(cycle, cycles))
                {
                    superSets.Add(cycle);
                }
            }
            var notSuperSets = cycles.Where(y => superSets.Contains(y) == false).ToList();
            return notSuperSets;
        }

        private static bool IsSuperSet(Graph cycle, IList<Graph> cycles)
        {
            foreach (var otherCycle in cycles.Where(y => y != cycle))
            {
                if (cycle.IsSuperSetOfGraph(otherCycle))
                {
                    return true;
                }
            }
            return false;
        }

        private static IList<Graph> FindCycle(Node startingNode)
        {
            var cycles = new List<Graph>();
            foreach (var node in startingNode.ConnectedNodes.Where(y => y.IsHandled == false))
            {
                cycles.AddRange(FindCycle(startingNode, node, startingNode, new List<Node>()));
            }
            return cycles;
        }

        private static IList<Graph> FindCycle(Node startingNode, Node currentNode, Node originNode, List<Node> visitedNodes)
        {
            var cycles = new List<Graph>();
            visitedNodes = visitedNodes.Select(y => y).ToList();
            visitedNodes.Add(currentNode);
            var nodesToVisit = currentNode.ConnectedNodes.Where(y => visitedNodes.Contains(y) == false && y.IsHandled == false).OrderBy(y => y.Id).ToList();
            foreach (var node in nodesToVisit)
            {
                if (node.Id == originNode.Id)
                {
                    continue;
                }
                if (node.Id == startingNode.Id)
                {
                    // We have a cycle
                    var cycle = new List<Node>();
                    foreach (var cycleNode in visitedNodes)
                    {
                        cycle.Add(cycleNode);
                    }
                    cycle.Add(startingNode);

                    cycles.Add(new Graph() { NodesInGraph = cycle });
                }
                else
                {
                    // Continue searching
                    cycles.AddRange(FindCycle(startingNode, node, currentNode, visitedNodes));
                }
            }
            return cycles;
        }

        private static Graph BuildGraph()
        {
            var nodes = new List<Node>();
            for (int i = 1; i <= 16; i++)
            {
                nodes.Add(new Node() { Id = i });
            }

            ConnectNodes(nodes[0], nodes[1], nodes[10]);
            ConnectNodes(nodes[1], nodes[10], nodes[9], nodes[2], nodes[0]);
            ConnectNodes(nodes[2], nodes[1], nodes[9], nodes[3]);
            ConnectNodes(nodes[3], nodes[2], nodes[4]);
            ConnectNodes(nodes[4], nodes[3], nodes[5]);
            ConnectNodes(nodes[5], nodes[4], nodes[6]);
            ConnectNodes(nodes[6], nodes[5], nodes[7]);
            ConnectNodes(nodes[7], nodes[6], nodes[8], nodes[13]);
            ConnectNodes(nodes[8], nodes[7], nodes[12], nodes[9]);
            ConnectNodes(nodes[9], nodes[2], nodes[1], nodes[8]);
            ConnectNodes(nodes[10], nodes[0], nodes[1], nodes[11]);
            ConnectNodes(nodes[11], nodes[10], nodes[12]);
            ConnectNodes(nodes[12], nodes[11], nodes[14], nodes[13], nodes[8]);
            ConnectNodes(nodes[13], nodes[15], nodes[12], nodes[7]);
            ConnectNodes(nodes[14], nodes[0], nodes[12], nodes[15]);
            ConnectNodes(nodes[15], nodes[14], nodes[13]);

            var graph = new Graph() { NodesInGraph = nodes };
            return graph;
        }

        private static Graph BuildGraph2()
        {
            var nodes = new List<Node>();
            for (int i = 1; i <= 5; i++)
            {
                nodes.Add(new Node() { Id = i });
            }

            ConnectNodes(nodes[0], nodes[1], nodes[2], nodes[4]);
            ConnectNodes(nodes[1], nodes[0], nodes[3], nodes[4]);
            ConnectNodes(nodes[2], nodes[0], nodes[3], nodes[4]);
            ConnectNodes(nodes[3], nodes[2], nodes[1]);
            ConnectNodes(nodes[4], nodes[0], nodes[1], nodes[2]);

            var graph = new Graph() { NodesInGraph = nodes };
            return graph;
        }

        private static Graph BuildGraph3()
        {
            var nodes = new List<Node>();
            for (int i = 1; i <= 5; i++)
            {
                nodes.Add(new Node() { Id = i });
            }

            ConnectNodes(nodes[0], nodes[1], nodes[4]);
            ConnectNodes(nodes[1], nodes[0], nodes[4]);
            ConnectNodes(nodes[2], nodes[3], nodes[4]);
            ConnectNodes(nodes[3], nodes[2], nodes[4]);
            ConnectNodes(nodes[4], nodes[0], nodes[1], nodes[2], nodes[3]);

            var graph = new Graph() { NodesInGraph = nodes };
            return graph;
        }

        private static void ConnectNodes(Node node, params Node[] nodesToConnectTo)
        {
            if(node.ConnectedNodes == null)
            {
                node.ConnectedNodes = new List<Node>();
            }
            foreach (var connectingNode in nodesToConnectTo)
            {
                if (connectingNode.ConnectedNodes == null)
                {
                    connectingNode.ConnectedNodes = new List<Node>();
                }
                ConnectSingleNodes(node, connectingNode);
                ConnectSingleNodes(connectingNode, node);
            }
        }

        private static void ConnectSingleNodes(Node node, Node connectingNode)
        {
            if (node.ConnectedNodes.Contains(connectingNode) == false)
            {
                node.ConnectedNodes.Add(connectingNode);
            }
        }
    }
}