Store Grid N*N into an Adjacency Graph? Position and Neighbors

Question

Updating this post, once again.

This time to make things clearer. I am trying, to parse in a Grid of size 9x9, but this size can change overtime, its not fixed. This is a board game called Quoridor. What I have at my disposal, is a Board class. This provides me with the following, horizontal bool[,], and vertical bool[,], I can loop over each and print out x, y position. But these differ, depending on if its horizontal direction, or vertical direction and position.

The player can move one step ONLY either north, south, west, or east in terms of direction. The other player (human) can put a wall (obstacle) which covers two blocks horizontally or vertically. My automated player has to build a Graph of Nodes from the board, and refresh the Graph based on the changes on the board and its own position. For example, if the player cannot go to left, from current position, then an edge which connects two nodes will be deleted between them, only if caused by an obstacle. And then the BFS will run again against the Graph and return a new position (x, y) which this (automated) player uses and performs its move.

Every single block on the 9x9 grid, will represent one Node in the Graph. Meaning the number of vertices or nodes List in the Graph will be 9x9=81. Each of the Nodes hold a list or 2D array of size 4 for representing North, South, West, and East which could be of a bool type.

Now, I have provided a sample code of the Graph class I wrote along with a Node class. I hope the latest information herein makes it clear. I have already implemented the BFS algorithm. But this part is what I cannot understand correctly. I watched this video for some ideas: https://www.youtube.com/watch?v=KiCBXu4P-2Y

---

---

Code

class Graph<T>
{        
    private int _V;
    private List<T>[] _Nodes;

    public Graph(int v) 
    {
        _V = v;
        _Nodes = new List<T>[v];
        for (int i = 0; i < _Nodes.Length; i++)
            _Nodes [i] = new List<T>();
    }

    public IEnumerable<T> Nodes(int v) { return (IEnumerable<T>)_Nodes[v];}
    public int V { get => _V; }
    public bool EdgeExists(){}
    public void AddEdge(Node n, T u, T w){}
    public void RemoveEdge(){}
}

and,

class Node<T>
{        
    private int _E;    
    private List<T>[] _Adj;

    public Node(int e) 
    {
        _E = e;
        _Adj = new List<T>[e];
        for (int i = 0; i < _Adj.Length; i++)
            _Adj [e] = new List<T>();
    }

    public IEnumerable<T> Adj(int e) { return (IEnumerable<T>)_Adj[e];}
    public int E { get => _E; }

    public void AddEdge(Node n, T u, T w){}
    public void RemoveEdge(T value){}
}

---

I read the following SO threads:

• How can you make an adjacency matrix which would emulate a 2d grid
• Implementing 2D Grid Network ( Graph ) and Adjacency Matrix of it in C
• Representing a graph with a 2D array
• How can I build a graph from a 2D array?
• Creating an adjacency list graph from a matrix in python
• https://learn.microsoft.com/en-us/previous-versions/ms379574(v=vs.80)?redirectedfrom=MSDN
• How can I make my BFS algorithm run faster?

Answer 1

This is one way to build an adjacency matrix that has the same layout as a 2D array:

internal record Graph
{
    public List<Node> Nodes { get; set; }

    public Graph(int numberOfTiles)
    {
        var matrixSize = (int)Math.Sqrt(numberOfTiles);
        var rows = matrixSize;
        var columns = matrixSize;
        var nodes = new Node[rows, columns];
        for (int row = 0; row < rows; row++)
        {
            for (int column = 0; column < columns; column++)
            {
                nodes[row, column] = new Node(row, column);
            }
        }

        Nodes = new List<Node>(rows * columns);
        foreach (var node in nodes)
        {
            var row = node.Row;
            var column = node.Column;
            if (row > 0) node.West = nodes[row - 1, column];
            if (column > 0) node.North = nodes[row, column - 1];
            if (row < rows - 1) node.East = nodes[row + 1, column];
            if (column < columns - 1) node.South = nodes[row, column + 1];
            Nodes.Add(node);
        }

    }
}

internal record Node
{
    public int Row { get; }
    public int Column { get; }
    public Node[] Neighbors { get; } = new Node[4];
    public Node North
    {
        get => Neighbors[0];
        set => Neighbors[0] = value;
    }
    public Node East
    {
        get => Neighbors[1];
        set => Neighbors[1] = value;
    }
    public Node South
    {
        get => Neighbors[2];
        set => Neighbors[2] = value;
    }
    public Node West
    {
        get => Neighbors[3];
        set => Neighbors[3] = value;
    }
    public Node(int row, int column)
    {
        Row = row;
        Column = column;
    }
}

And this works for BFS. Edges/boundaries are defined by a node's neighbor being null.To create an edge, just set the appropriate neighbor to null. For example to create a horizontal edge, set the East neighbor of the western node to null, and the West neighbor of the eastern node to null.

Answer 2

Based on what you said I understand your question as follows: How the to handle Nodes that on the edges like (x=0,y=0), (x=9,y=5) or (x=9.y=9) ..... you should handle 8 cases

for case of left top corner the node only have 2 neighbors so set the top and left neighbors Null

Answer 3

If we have a 9x9 square matrix we can do the follow: First step, fill the Graph Nodes List with all Nodes. Second Step, make a loop to handle the neighbors. if we say the Node in the middle of the Graph then, currentNode.LeftNode = NodeList[currentNodePosition-1] currentNode.RightNode = NodeList[currentNodePosition+1] currentNode.TopNode = NodeList[currentNodePosition+9] currentNode.BottomNode = NodeList[currentNodePosition-9]. and as I said before you should handle the null cases in the picture above. I hop you get the point

Answer 4

To store nodes ( with associated data )arranged in a 2D grid into an adjacency graph, I prefer to do things in three steps.

1 Read the node data into a 2D vector 2 Add nodes to a graph class 2 Scan the vector adding links between adjacent nodes to graph class

Let's assume the input is a text file with the node data arranged in space delimited orthoganol rows ( indicated by the 'o' ). For a 3 by 3 it might look like this

o 1 2 3
o 2 5 2
o 3 2 1

Some C++ code to read this into a vector

            std::vector<std::vector<float>> grid;
            int RowCount = 0;
            int ColCount = -1;
            int start = -1;
            int end = -1;
            std::string line;
            while (std::getline(myFile, line))
            {
                std::cout << line << "\n";
                auto token = ParseSpaceDelimited(line);
                if (!token.size())
                    continue;
                switch (token[0][0])
                {
                case 'o':
                {
                    if (ColCount == -1)
                        ColCount = token.size() - 1;
                    else if (token.size() - 1 != ColCount)
                        throw std::runtime_error("Bad column count");
                    std::vector<float> row;
                    for (int k = 1; k < token.size(); k++)
                        row.push_back(atof(token[k].c_str()));
                    grid.push_back(row);
                }
                ... other cases if needed to parse other kinds of input data

Now we can add the nodes to a graph class. I have a handy method ( orthogonalGridNodeName ) that provides human readable names to nodes located on a grid

        cGraph myFinder;
        RowCount = grid.size();

        // add nodes at each grid cell
        for (int row = 0; row < RowCount; row++)
        {
            for (int col = 0; col < ColCount; col++)
            {
                int n = myFinder.findoradd(
                    orthogonalGridNodeName(row, col));
                 // TODO: add data for this node from grid
            }
        }

Now we should be able to add the links between the nodes. Here I assume that every link has a cost of 1.

        // link cells orthogonally
        for (int row = 0; row < RowCount; row++)
            for (int col = 0; col < ColCount; col++)
            {
                int n = row * ColCount + col;

                if (fDirected)
                {
                    if (col > 0)
                    {
                        int left = row * ColCount + col - 1;
                        myFinder.addLink(n, left, 1);
                    }
                }
                if (col < ColCount - 1)
                {
                    int right = row * ColCount + col + 1;
                    myFinder.addLink(n, right, 1);
                }
                if (fDirected)
                {
                    if (row > 0)
                    {
                        int up = (row - 1) * ColCount + col;
                        myFinder.addLink(n, up, 1);
                    }
                }
                if (row < RowCount - 1)
                {
                    int down = (row + 1) * ColCount + col;
                    myFinder.addLink(n, down, 1);
                }
            }

I think this should be easily ported to C#