Moving a graph represented in an adjacency matrix

Question

I want to use depth and first order methods to move the graph. I have done this in a simple list of nodes before, but I have never tried it with an adjacency matrix, and I honestly don’t even know where to start.

Here is my matrix:

999999999 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 999999999 0 3 1 0 0 0 0 0 0 0 0 0 0 0 1 0 999999999 3 0 1 0 0 0 0 0 0 0 0 0 0 0 3 3 999999999 0 0 0 8 0 0 0 0 0 0 0 0 0 1 0 0 999999999 0 1 3 0 0 0 0 0 0 0 0 0 0 1 0 0 999999999 0 3 1 0 0 0 0 0 0 0 0 0 0 0 1 0 999999999 0 0 3 0 1 0 0 0 0 0 0 0 8 3 3 0 999999999 0 8 8 0 3 0 0 0 0 0 0 0 0 1 0 0 999999999 0 3 0 0 1 0 0 0 0 0 0 0 0 3 8 0 999999999 0 0 0 0 3 0 0 0 0 0 0 0 0 8 3 0 999999999 0 0 0 0 3 0 0 0 0 0 0 1 0 0 0 0 999999999 0 0 1 0 0 0 0 0 0 0 0 3 0 0 0 0 999999999 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 999999999 0 1 0 0 0 0 0 0 0 0 0 3 0 1 1 0 999999999 0 0 0 0 0 0 0 0 0 0 0 3 0 1 1 0 999999999 

This is how I created this matrix (C #):

 private static int[,] CreateMatrix() { int A = 0; int B = 1; int C = 2; int D = 3; int E = 4; int F = 5; int G = 6; int H = 7; int I = 8; int J = 9; int K = 10; int L = 11; int M = 12; int N = 13; int O = 14; int P = 15; int[,] matrix = new int[16, 16]; matrix[A, B] = 1; matrix[A, C] = 1; matrix[B, D] = 3; matrix[B, E] = 1; matrix[C, D] = 3; matrix[C, F] = 1; matrix[D, H] = 8; matrix[E, G] = 1; matrix[E, H] = 3; matrix[F, H] = 3; matrix[F, I] = 1; matrix[G, J] = 3; matrix[G, L] = 1; matrix[H, J] = 8; matrix[H, K] = 8; matrix[H, M] = 3; matrix[I, K] = 3; matrix[I, N] = 1; matrix[J, O] = 3; matrix[K, P] = 3; matrix[L, O] = 1; matrix[M, O] = 1; matrix[M, P] = 1; matrix[N, P] = 1; matrix[B, A] = 1; matrix[C, A] = 1; matrix[D, B] = 3; matrix[E, B] = 1; matrix[D, C] = 3; matrix[F, C] = 1; matrix[H, D] = 8; matrix[G, E] = 1; matrix[H, E] = 3; matrix[H, F] = 3; matrix[I, F] = 1; matrix[J, G] = 3; matrix[L, G] = 1; matrix[J, H] = 8; matrix[K, H] = 8; matrix[M, H] = 3; matrix[K, I] = 3; matrix[N, I] = 1; matrix[O, J] = 3; matrix[P, K] = 3; matrix[O, L] = 1; matrix[O, M] = 1; matrix[P, M] = 1; matrix[P, N] = 1; for (int i = 0; i < 16; i++) { for (int j = 0; j < 16; j++) { if (matrix[i, j] == 0) matrix[i, j] = 0; if (i == j) matrix[i, j] = 999999999; } } return matrix; } 

Any help would be appreciated! Thanks, advanced!

The graph that this matrix represents:

Answer 1

Every problem in computer science, except for one, can be solved by adding more abstraction.

Start by writing the width traversal in the most abstract way:

 void BreadthFirstTraversal(Graph graph, Vertex start) { /* A miracle happens */ } 

We have a method that does what we want. Except that it is not written yet. So write it with a slightly less abstraction:

 void BreadthFirstTraversal(Graph graph, Vertex start) { /* make a queue of vertices */ /* make a mark set of vertices */ /* enqueue and mark start */ /* while the queue is not empty */ /* dequeue a vertext */ /* enqueue and mark all the unmarked neighbours of the vertex */ } 

Continue by removing more and more abstraction.

 void BreadthFirstTraversal(Graph graph, Vertex start) { var queue = new VertexQueue(); var markSet = new VertexMarkSet(); queue.Enqueue(start); markSet.Add(start); while(queue.NotEmpty()) { var vertex = queue.Dequeue(); foreach(Vertex neighbour in graph.ListNeighbours(vertex)) { if (!markSet.Contains(neighbour)) { markSet.Add(neighbour); queue.Enqueue(neighbour); } } } } 

OK, now you have an algorithm that will work for any chart, regardless of its internal representation. So all you have to do is write ListNeighbours(Vertex) and you're done. (Assuming you already know how to write a queue and a set, or are ready to use types that are part of the base class library.) How are you going to do this?

Do you see how I used abstraction there? I really don't care if his adjacency matrix or adjacency list, all I care about is that the graph provides me with the service of giving me the neighbors of the vertex.

So, how are you going to write ListNeighbours(Vertex) based on your adjacency matrix?

Two possible solutions for research:

• Make the Graph.ListNeighbours(Vertex) method return List<Vertex> . Create a list and submit it.

• Make return IEnumerable<Vertex> and use yield return to get a sequence of neighboring vertices.

---

UPDATE: OK, so how can we make a sequence of neighbors outside the adjacency matrix?

Suppose each vertex is numbered, so Vertex really int ; this is traditionally done with adjacent matrices. We want to take to the vertex - int - and return a sequence of vertices that are its neighbors.

We have an array with the property that array[i, j] is nonzero if vertex j is a neighbor of vertex i .

Start the essay again and make your way to implementation:

 public List<int> ListNeighbours(int vertex) { /* a miracle happens */ } 

What do we need to do to accomplish this miracle?

 public List<int> ListNeighbours(int vertex) { /* create a new list */ /* for each vertex j in the graph */ /* if j is a neighbour of i then add it to the list */ /* return the list */ } 

Alternatively, you can use yield return to create a sequence:

 public IEnumerable<int> ListNeighbours(int vertex) { /* for each vertex j in the graph */ /* if j is a neighbour of i then yield return j */ } 

yield return Iterators tend to be simpler, but novice programmers often have difficulty challenging the control flow. Try writing it in both directions and see how it happens.