मुझे इस प्रश्न के साथ मज़ा आया, धन्यवाद! : पी
मेरे पास सी # में एक समाधान है। चक्र खोजने के लिए एल्गोरिदम बहुत छोटा है (~ 10 लाइनें), लेकिन इसके आस-पास बहुत सारे अव्यवस्थाएं हैं (उदाहरण के लिए कक्षाओं के नोड और एज के कार्यान्वयन)।
मैंने परिवर्तनीय नामकरण सम्मेलन का उपयोग किया है कि पत्र "ई" एक किनारे का प्रतिनिधित्व करता है, अक्षर "ए" नोड जहां किनारे शुरू होता है, और "बी" नोड यह लिंक करता है। उन परंपराओं के साथ, इस एल्गोरिथ्म है:
public static IEnumerable<Cycle> FindAllCycles()
{
HashSet<Node> alreadyVisited = new HashSet<Node>();
alreadyVisited.Add(Node.AllNodes[0]);
return FindAllCycles(alreadyVisited, Node.AllNodes[0]);
}
private static IEnumerable<Cycle> FindAllCycles(HashSet<Node> alreadyVisited, Node a)
{
for (int i = 0; i < a.Edges.Count; i++)
{
Edge e = a.Edges[i];
if (alreadyVisited.Contains(e.B))
{
yield return new Cycle(e);
}
else
{
HashSet<Node> newSet = i == a.Edges.Count - 1 ? alreadyVisited : new HashSet<Node>(alreadyVisited);
newSet.Add(e.B);
foreach (Cycle c in FindAllCycles(newSet, e.B))
{
c.Build(e);
yield return c;
}
}
}
}
यह कुछ Hashsets पुन: उपयोग करने के लिए एक अनुकूलन है, और वह भ्रमित हो सकता है।मैंने निम्न कोड शामिल किया है, जो वास्तव में एक ही परिणाम उत्पन्न करता है, लेकिन यह कार्यान्वयन में अनुकूलन नहीं है, इसलिए आप यह आसानी से समझ सकते हैं कि यह कैसे काम करता है।
private static IEnumerable<Cycle> FindAllCyclesUnoptimized(HashSet<Node> alreadyVisited, Node a)
{
foreach (Edge e in a.Edges)
if (alreadyVisited.Contains(e.B))
yield return new Cycle(e);
else
{
HashSet<Node> newSet = new HashSet<Node>(alreadyVisited);
newSet.Add(e.B);//EDIT: thnx dhsto
foreach (Cycle c in FindAllCyclesUnoptimized(newSet, e.B))
{
c.Build(e);
yield return c;
}
}
}
यह नोड, एज और साइकिल के निम्नलिखित कार्यान्वयन का उपयोग करता है। वे बहुत सरल हैं, हालांकि मैंने सब कुछ अपरिवर्तनीय बनाने और सदस्यों को कम से कम सुलभ बनाने में काफी विचार किया है।
public sealed class Node
{
public static readonly ReadOnlyCollection<Node> AllNodes;
internal static readonly List<Node> allNodes;
static Node()
{
allNodes = new List<Node>();
AllNodes = new ReadOnlyCollection<Node>(allNodes);
}
public static void SetReferences()
{//call this method after all nodes have been created
foreach (Edge e in Edge.AllEdges)
e.A.edge.Add(e);
}
//All edges linking *from* this node, not to it.
//The variablename "Edges" it quite unsatisfactory, but I couldn't come up with anything better.
public ReadOnlyCollection<Edge> Edges { get; private set; }
internal List<Edge> edge;
public int Index { get; private set; }
public Node(params int[] nodesIndicesConnectedTo)
{
this.edge = new List<Edge>(nodesIndicesConnectedTo.Length);
this.Edges = new ReadOnlyCollection<Edge>(edge);
this.Index = allNodes.Count;
allNodes.Add(this);
foreach (int nodeIndex in nodesIndicesConnectedTo)
new Edge(this, nodeIndex);
}
public override string ToString()
{
return this.Index.ToString();
}
}
public sealed class Edge
{
public static readonly ReadOnlyCollection<Edge> AllEdges;
static readonly List<Edge> allEdges;
static Edge()
{
allEdges = new List<Edge>();
AllEdges = new ReadOnlyCollection<Edge>(allEdges);
}
public int Index { get; private set; }
public Node A { get; private set; }
public Node B { get { return Node.allNodes[this.bIndex]; } }
private readonly int bIndex;
internal Edge(Node a, int bIndex)
{
this.Index = allEdges.Count;
this.A = a;
this.bIndex = bIndex;
allEdges.Add(this);
}
public override string ToString()
{
return this.Index.ToString();
}
}
public sealed class Cycle
{
public readonly ReadOnlyCollection<Edge> Members;
private List<Edge> members;
private bool IsComplete;
internal void Build(Edge member)
{
if (!IsComplete)
{
this.IsComplete = member.A == members[0].B;
this.members.Add(member);
}
}
internal Cycle(Edge firstMember)
{
this.members = new List<Edge>();
this.members.Add(firstMember);
this.Members = new ReadOnlyCollection<Edge>(this.members);
}
public override string ToString()
{
StringBuilder result = new StringBuilder();
foreach (var member in this.members)
{
result.Append(member.Index.ToString());
if (member != members[members.Count - 1])
result.Append(", ");
}
return result.ToString();
}
}
तब वर्णन करने के लिए कैसे आप इस छोटे एपीआई का उपयोग हो सकता है, मैं अपने दो उदाहरण लागू किया है। असल में यह नीचे आता है, यह निर्दिष्ट करके सभी नोड्स बनाते हैं कि वे कौन से नोड्स को लिंक करते हैं, फिर SetReferences() को अच्छी तरह से कॉल करें .... कुछ संदर्भ सेट करें। इसके बाद, सार्वजनिक रूप से सुलभ FindAllCycles() को कॉल करना सभी चक्रों को वापस करना चाहिए। मैंने स्थिर सदस्यों को रीसेट करने के लिए किसी भी कोड को बाहर रखा है, लेकिन इसे आसानी से कार्यान्वित किया गया है। यह सिर्फ सभी स्थिर सूचियों को साफ़ करना चाहिए।
static void Main(string[] args)
{
InitializeExampleGraph1();//or: InitializeExampleGraph2();
Node.SetReferences();
var allCycles = FindAllCycles().ToList();
}
static void InitializeExampleGraph1()
{
new Node(1, 2);//says that the first node(node a) links to b and c.
new Node(2);//says that the second node(node b) links to c.
new Node(0, 3);//says that the third node(node c) links to a and d.
new Node(0);//etc
}
static void InitializeExampleGraph2()
{
new Node(1);
new Node(0, 0, 2);
new Node(0);
}
मैं ध्यान दें चाहिए कि इन उदाहरणों में किनारों के सूचकांकों आपकी छवियों में सूचकांक के अनुरूप नहीं है, लेकिन है कि एक साधारण देखने के साथ परिहार्य है। परिणाम: allCycles पहला उदाहरण के लिए है:
{3, 2, 0}
{5, 4, 2, 0}
{3, 1}
{5, 4, 1}
allCycles दूसरे उदाहरण के लिए है:
{1, 0}
{2, 0}
{4, 3, 0}
मुझे आशा है कि आप इस समाधान से संतुष्ट हैं और आप इसका इस्तेमाल करते हैं। मैंने कोड पर शायद ही कभी टिप्पणी की है, इसलिए मुझे पता है कि इसे समझना मुश्किल हो सकता है। उस स्थिति में, कृपया पूछें और मैं इस पर टिप्पणी करूंगा!
दूसरे उदाहरण में समाधान 2-3-1 और 3-1-2 नहीं होगा? –
@msalvadores, कोई संभोग नहीं। एक चक्र नोड्स की एक श्रृंखला है, भले ही क्रमपरिवर्तन। यदि आप कहीं और चक्र शुरू करेंगे, तो वह चक्र को नहीं बदलेगा, है ना? यह कहने जैसा होगा कि क्या आप अपने गिलास को एक तरफ से दूसरी तरफ ले जाएंगे, यह अब भी वही ग्लास नहीं होगा .... – JBSnorro
मुझे लगता है कि यह चर्चा योग्य है। आपके किनारे किनारों के क्रम के आधार पर एक चक्र पर विचार किया जा सकता है। लेकिन यह सब आपके आवेदन की जरूरत के हिसाब से आता है। यदि आपके मामले में 2-3-1 3-1-2 के समान है तो पर्याप्त उचित है। मुझे अपने anwser को फिर से काम करने की आवश्यकता हो सकती है क्योंकि मैं उसी चक्र के सभी क्रमपरिवर्तन वापस देता हूं। –