Make it possible to reverse the graph.

trekhleb · trekhleb · commit 0c2561197a73 · 2018-05-14T06:29:55.000+03:00
diff --git a/src/data-structures/graph/Graph.js b/src/data-structures/graph/Graph.js
@@ -138,6 +138,26 @@ export default class Graph {
     }, 0);
   }
 
+  /**
+   * Reverse all the edges in directed graph.
+   * @return {Graph}
+   */
+  reverse() {
+    /** @param {GraphEdge} edge */
+    this.getAllEdges().forEach((edge) => {
+      // Delete straight edge from graph and from vertices.
+      this.deleteEdge(edge);
+
+      // Reverse the edge.
+      edge.reverse();
+
+      // Add reversed edge back to the graph and its vertices.
+      this.addEdge(edge);
+    });
+
+    return this;
+  }
+
   /**
    * @return {string}
    */
diff --git a/src/data-structures/graph/GraphEdge.js b/src/data-structures/graph/GraphEdge.js
@@ -20,6 +20,17 @@ export default class GraphEdge {
     return `${startVertexKey}_${endVertexKey}`;
   }
 
+  /**
+   * @return {GraphEdge}
+   */
+  reverse() {
+    const tmp = this.startVertex;
+    this.startVertex = this.endVertex;
+    this.endVertex = tmp;
+
+    return this;
+  }
+
   /**
    * @return {string}
    */
diff --git a/src/data-structures/graph/__test__/Graph.test.js b/src/data-structures/graph/__test__/Graph.test.js
@@ -261,4 +261,43 @@ describe('Graph', () => {
 
     expect(deleteNotExistingEdge).toThrowError();
   });
+
+  it('should be possible to reverse graph', () => {
+    const vertexA = new GraphVertex('A');
+    const vertexB = new GraphVertex('B');
+    const vertexC = new GraphVertex('C');
+    const vertexD = new GraphVertex('D');
+
+    const edgeAB = new GraphEdge(vertexA, vertexB);
+    const edgeAC = new GraphEdge(vertexA, vertexC);
+    const edgeCD = new GraphEdge(vertexC, vertexD);
+
+    const graph = new Graph(true);
+    graph
+      .addEdge(edgeAB)
+      .addEdge(edgeAC)
+      .addEdge(edgeCD);
+
+    expect(graph.toString()).toBe('A,B,C,D');
+    expect(graph.getAllEdges().length).toBe(3);
+    expect(graph.getNeighbors(vertexA).length).toBe(2);
+    expect(graph.getNeighbors(vertexA)[0].getKey()).toBe(vertexB.getKey());
+    expect(graph.getNeighbors(vertexA)[1].getKey()).toBe(vertexC.getKey());
+    expect(graph.getNeighbors(vertexB).length).toBe(0);
+    expect(graph.getNeighbors(vertexC).length).toBe(1);
+    expect(graph.getNeighbors(vertexC)[0].getKey()).toBe(vertexD.getKey());
+    expect(graph.getNeighbors(vertexD).length).toBe(0);
+
+    graph.reverse();
+
+    expect(graph.toString()).toBe('A,B,C,D');
+    expect(graph.getAllEdges().length).toBe(3);
+    expect(graph.getNeighbors(vertexA).length).toBe(0);
+    expect(graph.getNeighbors(vertexB).length).toBe(1);
+    expect(graph.getNeighbors(vertexB)[0].getKey()).toBe(vertexA.getKey());
+    expect(graph.getNeighbors(vertexC).length).toBe(1);
+    expect(graph.getNeighbors(vertexC)[0].getKey()).toBe(vertexA.getKey());
+    expect(graph.getNeighbors(vertexD).length).toBe(1);
+    expect(graph.getNeighbors(vertexD)[0].getKey()).toBe(vertexC.getKey());
+  });
 });
diff --git a/src/data-structures/graph/__test__/GraphEdge.test.js b/src/data-structures/graph/__test__/GraphEdge.test.js
@@ -23,4 +23,20 @@ describe('GraphEdge', () => {
     expect(edge.endVertex).toEqual(endVertex);
     expect(edge.weight).toEqual(10);
   });
+
+  it('should be possible to do edge reverse', () => {
+    const vertexA = new GraphVertex('A');
+    const vertexB = new GraphVertex('B');
+    const edge = new GraphEdge(vertexA, vertexB, 10);
+
+    expect(edge.startVertex).toEqual(vertexA);
+    expect(edge.endVertex).toEqual(vertexB);
+    expect(edge.weight).toEqual(10);
+
+    edge.reverse();
+
+    expect(edge.startVertex).toEqual(vertexB);
+    expect(edge.endVertex).toEqual(vertexA);
+    expect(edge.weight).toEqual(10);
+  });
 });
