Kushina Kushina - 4 months ago 20
C# Question

How to use prim algorithm to traverse cells in a rectangular array in c#

I need to obtain a path consists of a series of ones starting from a given starting point (cell) in which to be the longest; in a rectangular array. I made a simple search of what are the suitable search algorithms to implement such a task and found that the prime algorithm is the most preferable technique but I have no idea how to implement it to get the target result.

I have no idea how to use Prime to implement my approach to find the longest path in terms of the number of the connected cells with the value of one. Is it actually "Prime Algorithm" or other?

I tried using Recursive and Dijkstra's algorithm but I could not get the correct path.

The following code is for the windows form application, some times it output a correct results and sometimes not:

namespace AUV_Topology
{
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace AUV_Topology
{
/* Class Cell */
/*****************************************************************************************************************************/

public class Cell
{
public int row { get; set; }
public int col { get; set; }
public int value { get; set; }
public Boolean visited { get; set; }
}

/* Class EnumCell */
/*****************************************************************************************************************************/

public class EnumCell : IEnumerator<Cell>
{
public EnumCell() { }

public EnumCell(int startRow, int startCol, List<List<Cell>> graph)
{
this.row = startRow;
this.col = startCol;
this.numberOfRows = graph.Count;
this.numberOfCols = graph[0].Count;
this.graph = graph;
}

public enum XY
{
Y = 0, //row
X = 1 //col
}

public enum LOCATIONS : byte
{
TOP_LEFT = 0,
TOP_MIDDLE,
TOP_RIGHT,
LEFT,
RIGHT,
BOTTOM_LEFT,
BOTTOM_MIDDLE,
BOTTOM_RIGHT,
END,
INVALID
}

public List<List<Cell>> graph { get; set; }
public int row { get; set; }
public int col { get; set; }
public int numberOfRows { get; set; }
public int numberOfCols { get; set; }

//offsets are in same order as enum location as y-offset(row), x-offset (col)
private List<List<int>> offsets = new List<List<int>>() {
new List<int>() { -1, -1 },
new List<int>() { -1, 0 },
new List<int>() { -1, +1 },
new List<int>() { 0, -1 },
new List<int>() { 0, +1 },
new List<int>() { +1, -1 },
new List<int>() { +1, 0 },
new List<int>() { +1, +1 }
};
public LOCATIONS position { get; set; }

public EnumCell GetEnumerator()
{
return new EnumCell(row, col, graph);
}

object IEnumerator.Current
{
get {
return Current;
}
}

/* Class Current Cell */
/*****************************************************************************************************************************/
public Cell Current
{
get {
try {
// move to first valie postion
for (LOCATIONS location = position; location < LOCATIONS.END; location++) {
if ((row + offsets[(byte)location][(int)XY.Y] >= 0) && (row + offsets[(byte)location][(int)XY.Y] < numberOfRows) &&
(col + offsets[(byte)location][(int)XY.X] > 0) && (col + offsets[(byte)location][(int)XY.X] < numberOfCols)) {
position = (LOCATIONS)location;
int newRow = row + offsets[(byte)location][(int)XY.Y];
int newCol = col + offsets[(byte)location][(int)XY.X];
return graph[newRow][newCol];
}
}
throw new InvalidOperationException();
} catch (IndexOutOfRangeException) {
throw new InvalidOperationException();
}
}
}

public Boolean MoveNext()
{
Boolean results = false;
for (LOCATIONS location = ++position; location < LOCATIONS.END; location++) {
int y = offsets[(byte)location][(int)XY.Y];
int x = offsets[(byte)location][(int)XY.X];
if ((row + y >= 0) && (row + y < numberOfRows) &&
(col + x > 0) && (col + x < numberOfCols)) {
if (graph[row + y][col + x].value == 1) {
position = (LOCATIONS)location;
return true;
}
}
}
return results;
}

public void Reset()
{
position = LOCATIONS.TOP_LEFT;
}

public void Dispose()
{
}
}

/* Class Graph */
/*****************************************************************************************************************************/
public class Graph
{
public Graph(int[,] graph)
{
this.graph = new List<List<Cell>>();
for (int row = 0; row < graph.GetLength(0); row++) {
List<Cell> newRow = new List<Cell>();
this.graph.Add(newRow);
for (int col = 0; col < graph.GetLength(1); col++) {
Cell newCell = new Cell();
newRow.Add(newCell);

newCell.row = row;
newCell.col = col;
newCell.value = graph[row, col];
newCell.visited = false;
}
}
}
public List<List<Cell>> graph;
}

/* Class SpanningTree */
/*****************************************************************************************************************************/
class SpanningTree
{
public static Graph graph = null;
public static SpanningTree root = new SpanningTree();

public static int counter = 0;

public int row { get; set; }
public int col { get; set; }
public int length { get; set; }
public List<SpanningTree> children { get; set; }

public SpanningTree() { }
public SpanningTree(int startRow, int startCol, int[,] graph)
{
SpanningTree.graph = new Graph(graph);
RecursiveTree(root, SpanningTree.graph.graph[startRow][startCol]);
}

public int RecursiveTree(SpanningTree parent, Cell currentCell)
{
int length = 0;
int maxLength = 0;
parent.row = currentCell.row;
parent.col = currentCell.col;

graph.graph[currentCell.row][currentCell.col].visited = true;

EnumCell enumCell = new EnumCell(currentCell.row, currentCell.col, graph.graph);
foreach (Cell cell in enumCell) {
if (!cell.visited) {
SpanningTree newBranch = new SpanningTree();
if (parent.children == null) parent.children = new List<SpanningTree>();
parent.children.Add(newBranch);
length = RecursiveTree(newBranch, SpanningTree.graph.graph[cell.row][cell.col]);
if (length > maxLength) maxLength = length;
}
}
graph.graph[currentCell.row][currentCell.col].visited = false;

parent.length = maxLength;
return maxLength + 1;
}

public static void OrderHighLow(SpanningTree parent, int level)
{
if (parent.children != null) {
parent.children = parent.children.OrderByDescending(x => x.length).ToList();
foreach (SpanningTree child in parent.children) {
OrderHighLow(child, level + 1);
}
}
}

public static void Print(SpanningTree parent, int level, int chromosomeNum)
{
FileStream fs = new FileStream("C:/Users/Welcome/Desktop/TreeParser.txt", FileMode.Append, FileAccess.Write);
using (StreamWriter sw = new StreamWriter(fs)) {
sw.WriteLine("------------------- Chromosome : {0} -------------------", chromosomeNum);
Print(parent, level, sw);
sw.WriteLine("---------Longest----------");
PrintLongest(parent, level, sw);
counter = 0;
}
}

private static void Print(SpanningTree parent, int level, StreamWriter sw)
{
//////////////////////////////////////////////////////////////////////
sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, parent.row, parent.col, parent.length);
//////////////////////////////////////////////////////////////////////

if (parent.children != null) {
foreach (SpanningTree child in parent.children) {
Print(child, level + 1, sw);

if (child.length == 0) {
sw.WriteLine("||,,,,,,Branch {0},,,,,,||", counter);
level = 0;
sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, root.row, root.col, root.length);
counter += 1;
}
}
}
}

public static void PrintLongest(SpanningTree parent, int level, StreamWriter sw)
{
//////////////////////////////////////////////////////////////////////
sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, parent.row, parent.col, parent.length);
//////////////////////////////////////////////////////////////////////

if (parent.children != null) {
PrintLongest(parent.children[0], level + 1, sw);
}
}
}
}
}// end name space


I made call in the main form:

int tt = 0;

foreach (int[,] graph in rectArrays)
{
new SpanningTree(indexesX[tt], indexesY[tt], graph);
SpanningTree.OrderHighLow(SpanningTree.root, 0);
SpanningTree.Print(SpanningTree.root, 0,tt);
tt++;
}


Here is the latest results : Debug

Problem 1

I got so many branches for some graphs, sometimes the path not as long as expected i.e. some cases (cells) not included while it should be!, sometimes the path contains cells with value zero, and sometimes it move from a cell to another cell while they are not adjacent to each other!.

Problem 2

When I use a big matrix such as 9 x 9 or above; I got the following:


Exception of type 'System.OutOfMemoryException' was thrown.

Answer Source

In method RecursiveTree replace the condition

if (!cell.visited)

by

if (!cell.visited && cell.value == 1)

This restricts the search to cells with value = 1 as required.


Your algorithm is rather complicated and entangled. Also, the naming makes it difficult to guess what things do. For instance, it is not clear what EnumCell enumerates. The name suggests that it is a kind of universal enumerator; however, MoveNext() returns only positions with value == 1. Why is there a variable results which is always false? Why is the logic split between MoveNext() and Current? Current should only return the value found in MoveNext. If MoveNext works correctly, no other logic should be required in Current. There are a lot of other such oddities in your code.

Try to simplify your code and debug it.

I implemented a backtracking solution that returns all solutions with the maximum path length. Except for setup and printing the result, there is no other logic involved:

Declarations:

private int[,] _world;
private bool[,] _visited;

[DebuggerDisplay("Coord({Row}, {Col})")]
private struct Coord
{
    public Coord(int row, int col)
    {
        this.Row = row;
        this.Col = col;
    }
    public readonly int Row;
    public readonly int Col;
}

Backtracking algorithm (call Find on a valid starting point of a path):

// Returns a list of paths of maximum length consisting of lists of coordinates.
private List<List<Coord>> Find(int row, int col)
{
    _visited[row, col] = true;
    var allResults = new List<List<Coord>>();
    for (int i = Math.Max(0, row - 1); i <= Math.Min(_world.GetLength(0) - 1, row + 1); i++) {
        for (int j = Math.Max(0, col - 1); j <= Math.Min(_world.GetLength(1) - 1, col + 1); j++) {
            if (!_visited[i, j] && _world[i, j] == 1) {
                List<List<Coord>> result = Find(i, j);
                allResults.AddRange(result);
            }
        }
    }
    if (allResults.Count == 0) {
        // This is an end-point of a new path. Create the new path with current coord.
        allResults.Add(new List<Coord> { new Coord(row, col) });
    } else {
        // Keep only longest results
        int maxLength = allResults.Max(p => p.Count);
        for (int i = allResults.Count - 1; i >= 0; i--) {
            if (allResults[i].Count < maxLength) {
                allResults.RemoveAt(i);
            } else {
                // Prepend current point to path.
                allResults[i].Insert(0, new Coord(row, col));
            }
        }
    }
    _visited[row, col] = false;
    return allResults;
}

Note that the full result tree exists only on the call stack, but not as an explicit data structure. The paths (coordinate lists) are created from the path end-points backwards to the starting point.


With this world

private int[,] _world = new[,] {
    { 0, 1, 0, 1 },
    { 0, 1, 0, 1 },
    { 0, 1, 1, 0 },
    { 1, 0, 0, 1 },
    { 1, 1, 0, 1 },
 };

For the starting coordinates (row = 0, column = 1) my solution prints (the printing routine itself is not shown):

Result #1, Length = 7
| ||1|| ||·|
| ||2|| ||·|
| ||4||3|| |
|5|| || ||·|
|6||7|| ||·|

Result #2, Length = 7
| ||1|| ||·|
| ||2|| ||·|
| ||4||3|| |
|5|| || ||·|
|7||6|| ||·|

If you comment out the section discarding shorter results, you can see that there are 8 possible paths (2 of length 5, 4 of length 6 and 2 of length 7).