Skip to content

Instantly share code, notes, and snippets.

@mastoj
Created December 21, 2010 15:04
Show Gist options
  • Save mastoj/750015 to your computer and use it in GitHub Desktop.
Save mastoj/750015 to your computer and use it in GitHub Desktop.
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);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment