Click here to Skip to main content
15,562,223 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
Hello Could someone Help me to find the solution for find all cycles in nondirected graph.

I am working with C# VS 2017, ASP.Net 5.2.60618.0

Tanks so much for Your Help.

LEG.

What I have tried:

I searched in Google and find a solution proposal but theare many error in my VS C# IDE. here a Copy. I am don't know how to correct the errors.

Thanks again.

namespace akCyclesInUndirectedGraphs
{
class Program
{
// Graph modelled as list of edges
static int[,] graph =
{
{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}
};

static List<int[]> cycles = new List<int[]>();

// static void Main(string[] args)
// {
for (int i = 0; i < graph.GetLength(0); i++)
for (int j = 0; j < graph.GetLength(1); j++)
{
findNewCycles(new int[] {graph[i, j]});
}

foreach (int[] cy in cycles)
{
string s = "" + cy[0];

for (int i = 1; i < cy.Length; i++)
s += "," + cy[i];

Console.WriteLine(s);
}
// }

static void findNewCycles(int[] path)
{
int n = path[0];
int x;
int[] sub = new int[path.Length + 1];

for (int i = 0; i < graph.GetLength(0); i++)
for (int y = 0; y <= 1; y++)
if (graph[i, y] == n)
// edge referes to our current node
{
x = graph[i, (y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
Array.Copy(path, 0, sub, 1, path.Length);
// explore extended path
findNewCycles(sub);
}
else if ((path.Length > 2) && (x == path[path.Length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
cycles.Add(p);
}
}
}

static bool equals(int[] a, int[] b)
{
bool ret = (a[0] == b[0]) && (a.Length == b.Length);

for (int i = 1; ret && (i < a.Length); i++)
if (a[i] != b[i])
{
ret = false;
}

return ret;
}

static int[] invert(int[] path)
{
int[] p = new int[path.Length];

for (int i = 0; i < path.Length; i++)
p[i] = path[path.Length - 1 - i];

return normalize(p);
}

// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.Length];
int x = smallest(path);
int n;

Array.Copy(path, 0, p, 0, path.Length);

while (p[0] != x)
{
n = p[0];
Array.Copy(p, 1, p, 0, p.Length - 1);
p[p.Length - 1] = n;
}

return p;
}

static bool isNew(int[] path)
{
bool ret = true;

foreach(int[] p in cycles)
if (equals(p, path))
{
ret = false;
break;
}

return ret;
}

static int smallest(int[] path)
{
int min = path[0];

foreach (int p in path)
if (p < min)
min = p;

return min;
}

static bool visited(int n, int[] path)
{
bool ret = false;

foreach (int p in path)
if (p == n)
{
ret = true;
break;
}

return ret;
}
}
}

//
//The cycles for the demo graph:
//
//
//1,3,2
//1,4,3,2
//1,4,6,2
//1,3,4,6,2
//1,4,6,2,3
//1,4,3
//2,6,4,3
//7,9,8
Posted
Updated 25-Aug-19 3:13am
Comments
Member 14053198 21-Aug-19 22:03pm    
The ( // ) in // static void Main(string[] args) and ( // } in Main () close is only for test...
Patrice T 21-Aug-19 22:39pm    
Use Improve question to update your question.
So that everyone can pay attention to this information.
Member 14053198 24-Aug-19 21:27pm    
Thanks so much to Patrice.

Fortunately I found the error. I forget to copy "using SystemCollections.Generic;" I copy that and all errors go missing. erroneously I supouse my C# VS 2017 take care about.
Today all is working fine.

Thanks for Your Time.

Best Regarads

LEG
Patrice T 24-Aug-19 21:44pm    
Post this as a solution and accept it, just to say the question is solved and to close it.
Patrice T 21-Aug-19 22:39pm    
Try to list error messages and positions.

1 solution

I suggest you study the discussion and the several code examples on this thread: "Finding all cycles in undirected graphs:" [^]
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900