Hi all,
I’m currently facing issues using the C# script below and make it run as a component inside Grasshopper. It is a simple algorithm that traverse a graph and look for every possible Hamiltonian cycle inside of it.
Script
// From https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/
// C# program for solution of Hamiltonian
// Cycle problem using backtracking
using System;
public class HamiltonianCycle
{
readonly int V = 5;
int []path;
/* A utility function to check
if the vertex v can be added at
index 'pos'in the Hamiltonian Cycle
constructed so far (stored in 'path[]') */
bool isSafe(int v, int [,]graph,
int []path, int pos)
{
/* Check if this vertex is
an adjacent vertex of the
previously added vertex. */
if (graph[path[pos - 1], v] == 0)
return false;
/* Check if the vertex has already
been included. This step can be
optimized by creating an array
of size V */
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
/* A recursive utility function
to solve hamiltonian cycle problem */
bool hamCycleUtil(int [,]graph, int []path, int pos)
{
/* base case: If all vertices
are included in Hamiltonian Cycle */
if (pos == V)
{
// And if there is an edge from the last included
// vertex to the first vertex
if (graph[path[pos - 1],path[0]] == 1)
return true;
else
return false;
}
// Try different vertices as a next candidate in
// Hamiltonian Cycle. We don't try for 0 as we
// included 0 as starting point in hamCycle()
for (int v = 1; v < V; v++)
{
/* Check if this vertex can be
added to Hamiltonian Cycle */
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
/* recur to construct rest of the path */
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
/* If adding vertex v doesn't
lead to a solution, then remove it */
path[pos] = -1;
}
}
/* If no vertex can be added to Hamiltonian Cycle
constructed so far, then return false */
return false;
}
/* This function solves the Hamiltonian
Cycle problem using Backtracking. It
mainly uses hamCycleUtil() to solve the
problem. It returns false if there
is no Hamiltonian Cycle possible,
otherwise return true and prints the path.
Please note that there may be more than
one solutions, this function prints one
of the feasible solutions. */
int hamCycle(int [,]graph)
{
path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
/* Let us put vertex 0 as the first
vertex in the path. If there is a
Hamiltonian Cycle, then the path can be
started from any point of the cycle
as the graph is undirected */
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false)
{
Console.WriteLine("\nSolution does not exist");
return 0;
}
printSolution(path);
return 1;
}
/* A utility function to print solution */
void printSolution(int []path)
{
Console.WriteLine("Solution Exists: Following" +
" is one Hamiltonian Cycle");
for (int i = 0; i < V; i++)
Console.Write(" " + path[i] + " ");
// Let us print the first vertex again
// to show the complete cycle
Console.WriteLine(" " + path[0] + " ");
}
// Driver code
public static void Main(String []args)
{
HamiltonianCycle hamiltonian =
new HamiltonianCycle();
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) */
int [,]graph1= {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
// Print the solution
hamiltonian.hamCycle(graph1);
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) */
int [,]graph2 = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
};
// Print the solution
hamiltonian.hamCycle(graph2);
}
}
// This code contributed by Rajput-Ji
Problem: I’m totally new to this programming language and have a hard time figuring out how to return the output as a list of lists (or a Tree) instead of as a simple Console.WriteLine statement.
Also I’m not sure I’m correctly dealing with the different levels between the class members.
I would really need some help !
Script to component.gh (3.0 KB)
