Java/src/test/java/com/examplehub/datastructures/graph/AdjacencyMatrixTest.java at basics · letscode-17/Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package com.examplehub.datastructures.graph;

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Test;

class AdjacencyMatrixTest {
  @Test
  void test() {
    String[] vertex = {"A", "B", "C", "D", "E"};
    int[][] adj = {
      {0, 1, 1, 1, 0},
      {1, 0, 0, 1, 1},
      {1, 0, 0, 1, 0},
      {1, 1, 1, 1, 1},
      {0, 1, 0, 1, 0}
    };
    AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex, adj);
    assertEquals("A->B->D->C->E", adjacencyMatrix.dfsPath());

    adjacencyMatrix = new AdjacencyMatrix<>(vertex);
    adjacencyMatrix.addEdge(0, 1); /* A - B */
    adjacencyMatrix.addEdge(0, 2); /* A - C */
    adjacencyMatrix.addEdge(0, 3); /* A - D */
    adjacencyMatrix.addEdge(1, 3); /* B - D */
    adjacencyMatrix.addEdge(2, 3); /* C - D */
    adjacencyMatrix.addEdge(1, 4); /* B - E */
    adjacencyMatrix.addEdge(3, 4); /* D - E */
    assertEquals("A->B->D->C->E", adjacencyMatrix.dfsPath());
  }

  @Test
  void testGetVertexDegree() {
    String[] vertex = {"A", "B", "C", "D", "E"};
    AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
    adjacencyMatrix.addEdge(0, 1); /* A - B */
    adjacencyMatrix.addEdge(0, 2); /* A - C */
    adjacencyMatrix.addEdge(0, 3); /* A - D */
    adjacencyMatrix.addEdge(1, 3); /* B - D */
    adjacencyMatrix.addEdge(2, 3); /* C - D */
    adjacencyMatrix.addEdge(1, 4); /* B - E */
    adjacencyMatrix.addEdge(3, 4); /* D - E */
    assertEquals("A->B->D->C->E", adjacencyMatrix.dfsPath());

    assertEquals(3, adjacencyMatrix.getVertexDegree("A"));
    assertEquals(3, adjacencyMatrix.getVertexDegree("B"));
    assertEquals(2, adjacencyMatrix.getVertexDegree("C"));
    assertEquals(4, adjacencyMatrix.getVertexDegree("D"));
    assertEquals(2, adjacencyMatrix.getVertexDegree("E"));
  }

  @Test
  void testFindAllPath() {
    String[] vertex = {"A", "B", "C", "D", "E"};
    AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
    adjacencyMatrix.addEdge(0, 1); /* A - B */
    adjacencyMatrix.addEdge(0, 2); /* A - C */
    adjacencyMatrix.addEdge(0, 3); /* A - D */
    adjacencyMatrix.addEdge(1, 3); /* B - D */
    adjacencyMatrix.addEdge(2, 3); /* C - D */
    adjacencyMatrix.addEdge(1, 4); /* B - E */
    adjacencyMatrix.addEdge(3, 4); /* D - E */
    assertEquals(
        "A->B->D->E, A->B->E, A->C->D->B->E, A->C->D->E, A->D->B->E, A->D->E",
        String.join(", ", adjacencyMatrix.findAllPath("A", "E")));

    assertNull(adjacencyMatrix.findAllPath("A", "F"));
  }

  @Test
  void testAddEdge() {
    String[] vertex = {"A", "B", "C", "D", "E"};
    AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
    adjacencyMatrix.addEdge(0, 1); /* A - B */
    adjacencyMatrix.addEdge(0, 2); /* A - C */
    adjacencyMatrix.addEdge(0, 3); /* A - D */
    adjacencyMatrix.addEdge(1, 3); /* B - D */
    adjacencyMatrix.addEdge(2, 3); /* C - D */
    adjacencyMatrix.addEdge(1, 4); /* B - E */
    adjacencyMatrix.addEdge(3, 4); /* D - E */

    adjacencyMatrix.addEdge(1, 2); /* B - C */
    assertEquals("A->B->C->D->E", adjacencyMatrix.dfsPath());
  }

  @Test
  void testRemoveEdge() {
    String[] vertex = {"A", "B", "C", "D", "E"};
    AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
    adjacencyMatrix.addEdge(0, 1); /* A - B */
    adjacencyMatrix.addEdge(0, 2); /* A - C */
    adjacencyMatrix.addEdge(0, 3); /* A - D */
    adjacencyMatrix.addEdge(1, 3); /* B - D */
    adjacencyMatrix.addEdge(2, 3); /* C - D */
    adjacencyMatrix.addEdge(1, 4); /* B - E */
    adjacencyMatrix.addEdge(3, 4); /* D - E */

    adjacencyMatrix.removeEdge(0, 1);
    adjacencyMatrix.removeEdge(0, 2);
    assertEquals("A->D->B->E->C", adjacencyMatrix.dfsPath());
  }

  @Test
  void testBFS() {
    String[] vertex = {"A", "B", "C", "D", "E"};
    AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
    adjacencyMatrix.addEdge(0, 1); /* A - B */
    adjacencyMatrix.addEdge(0, 2); /* A - C */
    adjacencyMatrix.addEdge(0, 3); /* A - D */
    adjacencyMatrix.addEdge(1, 3); /* B - D */
    adjacencyMatrix.addEdge(2, 3); /* C - D */
    adjacencyMatrix.addEdge(1, 4); /* B - E */
    adjacencyMatrix.addEdge(3, 4); /* D - E */

    assertEquals("A->B->C->D->E", adjacencyMatrix.bfsPath());
  }
}