Problem making a C# script run as component

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)

update: script inside the c# component has been edited

Script to component.gh (6.6 KB)

Basically the problem remains the same: the function hamCycle() (see below) doesn’t return anything and simply prints the different results (arrays of integers) in the console. Instead I would like to change it so as it returns a list of lists (one array containing the different arrays) or a tree with different branches.

public static void hamCycle(int[,] graph)
    {
      // Initially value of boolean
      // flag is false
      hasCycle = false;

      // Store the resultant path
      List<int> path = new List<int>();
      path.Add(0);

      // Keeps the track of the
      // visited vertices
      bool[] visited = new bool[graph.GetLength(0)];

      for (int i = 0; i < visited.Length; i++)
        visited[i] = false;

      visited[0] = true;

      // Function call to find all
      // hamiltonian cycles
      FindHamCycle(graph, 1, path, visited);

    }

    // Recursive function to find all
    // hamiltonian cycles
    public static void FindHamCycle(int[,] graph, int pos, List<int> path, bool[] visited)
    {
      // If all vertices are included
      // in Hamiltonian Cycle
      if (pos == graph.GetLength(0)) {

        // If there is an edge
        // from the last vertex to
        // the source vertex
        if (graph[path[path.Count - 1], path[0]] != 0) {

          // Include source vertex
          // into the path and
          path.Add(0);

          // print the path
          for (int i = 0; i < path.Count; i++) {
            Console.Write(path[i] + " ");
          }
          Console.WriteLine();

          // Remove the source
          // vertex added
          path.RemoveAt(path.Count - 1);

          // Update the hasCycle
          // as true
          hasCycle = true;
        }

        return;

      }

      // Try different vertices
      // as the next vertex
      for (int v = 0; v < graph.GetLength(0); v++) {

        // Check if this vertex can
        // be added to Cycle
        if (isSafe(v, graph, path, pos) && !visited[v]) {

          path.Add(v);
          visited[v] = true;

          // Recur to construct
          // rest of the path
          FindHamCycle(graph, pos + 1, path, visited);

          // Remove current vertex
          // from path and process
          // other vertices
          visited[v] = false;
          path.RemoveAt(path.Count - 1);
        }
      }
    }

Well … unless you have very small graphs for kids (But if so : why bother?) and/or you are OK for waiting until the end of days (that’s optimistic) this is NOT the way to solve a Ham path. That said this is one of the most challenging tasks - time wise - known to man. I would strongly advise to pick some other topic to sharpen your C# skills.


Other than that later on I’ll look on your C#. You’ll need to accept someting rational as input as well (a Graph and his Node Connectivity [the Adj Matrix, that is]). For Graph think a classic Graph or a Mesh as Graph (like the examples shown).

PS: What about Plan B? Say, some A-Star routing or a PMST (Min Span Tree) like this one?

So … get that thing of yours (using a Mesh as Graph - see Method for the VV Tree and the equivalent Matrix used). Elapsed time is O(N!) … out of question even for the simple test mesh [the last one] used … thus the 100K milliseconds - Mama Mia. See small C# for what means the factorial part of that ultra stupid algo. That said many things published on Internet are crap (especially for tricky problems like a Ham path).

Graphs_Hamiltonian_V1A.gh (128.4 KB)

See what elapsed to expect if the algo is the proper one (using a Graph and a Mesh as Graph). All that in a very slow/ancient I5 (always use your slowest CPU for testing code):


NOTE: In fact … using a Mesh requires finding the disjoined pieces. Using a Graph requires finding islands (that’s done solely via the VV connectivity and Recursion).

NOTE: Avoid wasting your time with any of these (any Harley is faster):

TIP: Forget Ham paths. As a medium level challenge go for some MST fast algo (most related stuff published on Internet are 100% crap) that can cut the mustard in resonable time … say like: