Repository: ConstantinRuhdorfer/GraphLib

Issue:
Refactor
Make the directed version of Graph and Edge inherit from normal graph and edge.

Discussion:

Patch:
diff --git a/graph_lib/directed_edge.py b/graph_lib/directed_edge.py
new file mode 100644
index 0000000..2371d16
--- /dev/null
+++ b/graph_lib/directed_edge.py
@@ -0,0 +1,26 @@
+from __future__ import annotations
+
+from graph_lib.edge import Edge
+
+
+class DirectedEdge(Edge):
+    """
+    The direction of the edge goes:
+
+    DirectedEdge.vertex_a -> DirectedEdge.vertex_b.
+    """
+
+    def __eq__(self, other: DirectedEdge) -> bool:
+        """
+        Compares two edges by the ids of the vertecies.
+
+        :param other: DirectedEdge to compare against
+        :return: Equality as boolean
+        """
+        if isinstance(other, self.__class__):
+            return (self.vertex_a == other.vertex_a
+                    and self.vertex_b == other.vertex_b)
+
+    def __str__(self) -> str:
+        return f'Edge Id {self.id}: ' \
+            f'{self.vertex_a.id} -> {self.vertex_b.id}\n'
diff --git a/graph_lib/directed_graph.py b/graph_lib/directed_graph.py
new file mode 100644
index 0000000..849332d
--- /dev/null
+++ b/graph_lib/directed_graph.py
@@ -0,0 +1,127 @@
+from __future__ import annotations
+from typing import List
+
+import os
+
+from graph_lib.graph import Graph
+from graph_lib.directed_edge import DirectedEdge
+from graph_lib.vertex import Vertex
+
+
+class DirectedGraph(Graph):
+
+    def __init__(self, verticies: List[Vertex], edges: List[DirectedEdge]):
+        """
+        Constructs a directed Graph.
+
+        :param vertecies: List of vertecies
+        :param edges: List of directed edges
+        """
+        super().__init__(verticies, edges)
+
+    @classmethod
+    def from_file(cls: DirectedGraph, file: str) -> Graph:
+        """
+        Constructs a directed graph from a file of the form:
+
+        <number of vertecies>
+        <vertecie a of edge 1> <vertecie b of edge 1>
+        ...
+
+        :param file: Path to the file (can either be a relative path from
+                     the current cwd or an absolute one).
+        :return: a directed Graph object.
+        """
+        if not os.path.isabs(file):
+            file = f'{os.getcwd()}/{file}'
+
+        vertecies: List = []
+        edges: List[DirectedEdge] = []
+
+        with open(file, 'r') as f:
+            for i, line in enumerate(f):
+                if i == 0:
+                    num_verticies = int(line)
+                    vertecies = [Vertex(x) for x in range(num_verticies)]
+                    continue
+                input_vertecies = line.split()
+                edges.append(DirectedEdge(vertecies[int(input_vertecies[0])],
+                                          vertecies[int(input_vertecies[1])],
+                                          i-1))
+        return cls(vertecies, edges)
+
+    def insert_edge(self, edge: DirectedEdge) -> None:
+        """
+        Inserts a edge to the graph.
+        If the vertecies do not already exist they are added to the graph.
+        Performs health checks, e.g. no same vertex/edge ids.
+
+        :param edge: The edge to add.
+        :return: None
+        """
+        for elem in self.edges:
+            if elem == edge:
+                raise ValueError(f'Edge id already exists in the graph.')
+
+        try:
+            self.insert_vertex(edge.vertex_a)
+        except ValueError:
+            pass
+
+        try:
+            self.insert_vertex(edge.vertex_b)
+        except ValueError:
+            pass
+
+        if edge.id > self._current_highest_edge_id:
+            self._current_highest_edge_id = edge.id
+        self.edges.append(edge)
+
+    def create_edge(self, vertex_a: Vertex, vertex_b: Vertex,
+                    edge_id: int = None) -> DirectedEdge:
+        """
+        Creates an edge and adds it to the graph.
+
+        :param vertex_a: Vertex
+        :param vertex_b: Vertex
+        :param edge_id: A edge id. If None one is automatically assigned.
+                        Defaults to None.
+        :return: Created Edge
+        """
+        if edge_id is None:
+            edge_id = self.get_free_edge_id()
+
+        new_edge = DirectedEdge(vertex_a, vertex_b, edge_id)
+        self.insert_edge(new_edge)
+        return new_edge
+
+    def get_edge_by_id(self, edge_id: int) -> DirectedEdge:
+        """
+        Gets a vertex from the graph by id.
+
+        :param edge_id: The id to be searched.
+        :return: The found vertex
+        """
+        for edge in self.edges:
+            if edge.id == edge_id:
+                return edge
+        raise ValueError(f'{edge_id} does not exist in {self.edges}')
+
+    def create_vertex(self, contained_edges: List[DirectedEdge] = None,
+                      vertex_id: int = None) -> Vertex:
+        """
+        Creates a vertex and inserts it into the graph.
+        If the vertex has edges assaigned to it they are
+        also added to the graph.
+
+        :param contained_edges: List of directed edges on the vertex.
+                                Note: They will be added to the graph.
+        :param vertex_id: A vertex id. If None one is automatically assigned.
+                          Defaults to None.
+        :return: Created Vertex
+        """
+        return super().create_vertex(contained_edges, vertex_id)
+
+    def __str__(self) -> str:
+        return f'Directed Graph with {self.num_verticies}' \
+            f' number of vertecies and edges {self.edges}'
diff --git a/graph_lib/edge.py b/graph_lib/edge.py
index f14b191..c810f65 100644
--- a/graph_lib/edge.py
+++ b/graph_lib/edge.py
@@ -5,33 +5,29 @@ import graph_lib.vertex as v
 
 class Edge:
 
-    def __init__(self, a: v.Vertex, b: v.Vertex, edge_id: int, directed: bool):
+    def __init__(self, a: v.Vertex, b: v.Vertex, edge_id: int):
         """
         Constructs a edge.
 
         :param a: Vertex
         :param b: Vertex
         :param edge_id: A integer that identifies the edge.
-        :param directed: Wether the edge is directed; If so it goes a -> b.
         """
-
         self.vertex_a = a
         self.vertex_b = b
         self.id = edge_id
-        self.directed = directed
 
         a.add_edge(self)
         b.add_edge(self)
 
     def get_partner_vertex(self, given: v.Vertex) -> v.Vertex:
         """
-        For a edge x (<)-> y returns the partner to the given vertex,
+        For a edge x <-> y returns the partner to the given vertex,
         e.g. given x returns y.
 
         :param given: Vertex
         :return: Vertex
         """
-
         if self.vertex_a == given:
             return self.vertex_b
         elif self.vertex_b == given:
@@ -58,12 +54,6 @@ class Edge:
         :return: Equality as boolean
         """
         if isinstance(other, self.__class__):
-            if self.directed != other.directed:
-                return False
-            if self.directed and other.directed:
-                return (self.vertex_a == other.vertex_a
-                        and self.vertex_b == other.vertex_b
-                        and self.id == other.id)
             return ((self.vertex_a == other.vertex_a
                      or self.vertex_a == other.vertex_b)
                     and (self.vertex_b == other.vertex_a
@@ -71,8 +61,5 @@ class Edge:
         return False
 
     def __str__(self) -> str:
-        if self.directed:
-            return f'Edge Id {self.id}: ' \
-                f'{self.vertex_a.id} -> {self.vertex_b.id}\n'
         return f'Edge Id {self.id}: ' \
             f'{self.vertex_a.id} <-> {self.vertex_b.id}\n'
diff --git a/graph_lib/graph.py b/graph_lib/graph.py
index 02d572f..2a50027 100644
--- a/graph_lib/graph.py
+++ b/graph_lib/graph.py
@@ -8,33 +8,23 @@ from graph_lib.vertex import Vertex
 
 class Graph:
 
-    def __init__(self, verticies: List, edges: List, directed: bool):
+    def __init__(self, verticies: List[Vertex], edges: List[Edge]):
         """
         Constructs a Graph.
-        Performs a health check on the input,
-        e.g. a directed graph can only have directed edges.
 
         :param vertecies: List of vertecies
         :param edges: List of edges
-        :param directed: Wether the graph is directed.
         """
         self.num_verticies = len(verticies)
         self.verticies = verticies
         self.edges = edges
         self.num_edges = len(edges)
-        self.directed = directed
 
-        self.__current_highest_vertex_id = self.__calc_highest_id(verticies)
-        self.__current_highest_edge_id = self.__calc_highest_id(edges)
-
-        if directed:
-            for edge in edges:
-                if edge.directed is False:
-                    raise ValueError(
-                        f'{edge} not directed eventough the graph {self} is.')
+        self._current_highest_vertex_id = self._calc_highest_id(verticies)
+        self._current_highest_edge_id = self._calc_highest_id(edges)
 
     @classmethod
-    def from_file(cls: Graph, file: str, directed: bool) -> Graph:
+    def from_file(cls: Graph, file: str) -> Graph:
         """
         Constructs a graph from a file of the form:
 
@@ -61,9 +51,8 @@ class Graph:
                 input_vertecies = line.split()
                 edges.append(Edge(vertecies[int(input_vertecies[0])],
                                   vertecies[int(input_vertecies[1])],
-                                  i-1,
-                                  directed))
-        return cls(vertecies, edges, directed)
+                                  i-1))
+        return cls(vertecies, edges)
 
     def insert_edge(self, edge: Edge) -> None:
         """
@@ -74,13 +63,8 @@ class Graph:
         :param edge: The edge to add.
         :return: None
         """
-        if self.directed != edge.directed:
-            raise ValueError(
-                f'Graph is directed {self.directed} '
-                f'and edge is directed {edge.directed}')
-
         for elem in self.edges:
-            if elem.id == edge.id:
+            if elem == edge:
                 raise ValueError(f'Edge id already exists in the graph.')
 
         try:
@@ -93,8 +77,8 @@ class Graph:
         except ValueError:
             pass
 
-        if edge.id > self.__current_highest_edge_id:
-            self.__current_highest_edge_id = edge.id
+        if edge.id > self._current_highest_edge_id:
+            self._current_highest_edge_id = edge.id
         self.edges.append(edge)
 
     def create_edge(self, vertex_a: Vertex, vertex_b: Vertex,
@@ -111,7 +95,7 @@ class Graph:
         if edge_id is None:
             edge_id = self.get_free_edge_id()
 
-        new_edge = Edge(vertex_a, vertex_b, edge_id, self.directed)
+        new_edge = Edge(vertex_a, vertex_b, edge_id)
         self.insert_edge(new_edge)
         return new_edge
 
@@ -140,8 +124,8 @@ class Graph:
             if elem.id == vertex.id:
                 raise ValueError(f'Vertex id already exists in the graph.')
 
-        if vertex.id > self.__current_highest_vertex_id:
-            self.__current_highest_vertex_id = vertex.id
+        if vertex.id > self._current_highest_vertex_id:
+            self._current_highest_vertex_id = vertex.id
         self.verticies.append(vertex)
 
     def create_vertex(self, contained_edges: List = None,
@@ -188,8 +172,8 @@ class Graph:
 
         :return: A edge id.
         """
-        self.__current_highest_edge_id = self.__current_highest_edge_id + 1
-        return self.__current_highest_edge_id
+        self._current_highest_edge_id = self._current_highest_edge_id + 1
+        return self._current_highest_edge_id
 
     def get_free_vertex_id(self) -> int:
         """
@@ -197,10 +181,10 @@ class Graph:
 
         :return: A vertex id.
         """
-        self.__current_highest_vertex_id = self.__current_highest_vertex_id + 1
-        return self.__current_highest_vertex_id
+        self._current_highest_vertex_id = self._current_highest_vertex_id + 1
+        return self._current_highest_vertex_id
 
-    def __calc_highest_id(self, list: List) -> int:
+    def _calc_highest_id(self, list: List) -> int:
         """
         Takes in list of elements with an id property
         and returns the highest one.
@@ -230,15 +214,10 @@ class Graph:
                 return False
             if len(self.edges) != len(other.edges):
                 return False
-            if self.directed != other.directed:
-                return False
             return (self.edges == other.edges
                     and self.verticies == other.verticies)
         return False
 
     def __str__(self) -> str:
-        if self.directed:
-            f'Directed Graph with {self.num_verticies}' \
-                f' number of vertecies and edges {self.edges}'
         return f'Graph with {self.num_verticies}' \
             f' number of vertecies and edges {self.edges}'
diff --git a/graph_lib/vertex.py b/graph_lib/vertex.py
index 6b53ac3..d9c2a40 100644
--- a/graph_lib/vertex.py
+++ b/graph_lib/vertex.py
@@ -24,7 +24,6 @@ class Vertex:
         :param edge: The edge to add.
         :return: None
         """
-
         if edge not in self.edges:
             self.edges.append(edge)
             self.num_edges = self.num_edges + 1


Test patch:
diff --git a/test/test_directed_edge.py b/test/test_directed_edge.py
new file mode 100644
index 0000000..449e862
--- /dev/null
+++ b/test/test_directed_edge.py
@@ -0,0 +1,44 @@
+import unittest
+
+import graph_lib.vertex as v
+from graph_lib.directed_edge import DirectedEdge
+
+
+class TestDirectedEdge(unittest.TestCase):
+
+    def setUp(self) -> None:
+        """
+        Setup constants for tests here.
+
+        :return: None
+        """
+        pass
+
+    def test_automatic_add_vertex_to_edge(self):
+        a = v.Vertex(1)
+        b = v.Vertex(2)
+        e = DirectedEdge(a, b, 0)
+        self.assertTrue(e in a.edges,
+                        f'{e} with {e.id} should be in the eges of a {a}:'
+                        + f'\n {a.edges}')
+
+    def test_equal_directed(self):
+        a = v.Vertex(1)
+        b = v.Vertex(2)
+        e1 = DirectedEdge(a, b, 0)
+        e2 = DirectedEdge(a, b, 0)
+        self.assertEqual(e1, e2)
+
+    def test_equal_fail_directed(self):
+        a = v.Vertex(1)
+        b = v.Vertex(2)
+        e1 = DirectedEdge(a, b, 0)
+        e2 = DirectedEdge(b, a, 0)
+        self.assertNotEqual(e1, e2)
+
+    def tearDown(self) -> None:
+        """
+        Things to do on test suite completion.
+        :return: None
+        """
+        pass
diff --git a/test/test_directed_graph.py b/test/test_directed_graph.py
new file mode 100644
index 0000000..b23ad32
--- /dev/null
+++ b/test/test_directed_graph.py
@@ -0,0 +1,89 @@
+import unittest
+
+from graph_lib.directed_graph import DirectedGraph
+import graph_lib.vertex as v
+import graph_lib.directed_edge as e
+
+
+class TestDirectedGraph(unittest.TestCase):
+
+    def setUp(self) -> None:
+        """
+        Setup constants for tests here.
+
+        :return: None
+        """
+        self.test_file_path_small = "input/graph1.plain"
+        self.test_file_path_big = f'/Users/ruhdocon/dev' + \
+            f'/python_graph/input/graph4.plain'
+
+    def test_basic_constructor(self):
+        a, b = v.Vertex(1), v.Vertex(2)
+        test_vertecies = [a, b]
+        test_edges = [e.DirectedEdge(a, b, 1)]
+        g = DirectedGraph(test_vertecies, test_edges)
+        actual = (g.num_edges == 1
+                  and g.num_verticies == 2
+                  and test_vertecies == g.verticies
+                  and test_edges == g.edges)
+        self.assertTrue(actual,
+                        f'Failed: Graph: {g.num_edges} == Test: 1'
+                        + f'and Graph: {g.num_verticies} == Test: 2'
+                        + f'and Test: {test_vertecies} == Graph: {g.verticies}'
+                        + f'and Test: {test_edges} == Graph: {g.edges}')
+
+    def test_parser_for_number_of_vertecies(self):
+        g = DirectedGraph.from_file(self.test_file_path_small)
+        self.assertEqual(g.num_verticies, 9)
+
+    def test_equal(self):
+        g1 = DirectedGraph.from_file(self.test_file_path_big)
+        g2 = DirectedGraph.from_file(self.test_file_path_big)
+        self.assertEqual(g1, g2)
+
+    def test_get_vertex_by_id(self):
+        g = DirectedGraph.from_file(self.test_file_path_small)
+        actual = g.get_vertex_by_id(2)
+        expected = v.Vertex(2)
+        self.assertEqual(actual, expected)
+
+    def test_insert_vertex(self):
+        g = DirectedGraph.from_file(self.test_file_path_small)
+        vertex_id = g.get_free_vertex_id()
+        expected = v.Vertex(vertex_id)
+        g.insert_vertex(expected)
+        actual = g.get_vertex_by_id(vertex_id)
+        self.assertEqual(actual, expected)
+
+    def test_create_vertex(self):
+        g = DirectedGraph.from_file(self.test_file_path_small)
+        expected = g.create_vertex()
+        actual = g.get_vertex_by_id(expected.id)
+        self.assertEqual(actual, expected)
+
+    def test_get_edge_by_id(self):
+        g = DirectedGraph.from_file(self.test_file_path_small)
+        actual = g.get_edge_by_id(0)
+        expected = e.DirectedEdge(v.Vertex(0), v.Vertex(1), 0)
+        self.assertEqual(actual, expected)
+
+    def test_insert_edge(self):
+        g = DirectedGraph.from_file(self.test_file_path_small)
+        edge_id = g.get_free_edge_id()
+        expected = e.DirectedEdge(v.Vertex(12), v.Vertex(0), edge_id)
+        g.insert_edge(expected)
+        actual = g.get_edge_by_id(edge_id)
+        self.assertEqual(actual, expected)
+
+    def test_create_edge(self):
+        g = DirectedGraph.from_file(self.test_file_path_small)
+        expected = g.create_edge(v.Vertex(12), v.Vertex(37))
+        actual = g.get_edge_by_id(expected.id)
+        self.assertEqual(actual, expected)
+
+    def tearDown(self) -> None:
+        """
+        Things to do on test suite completion.
+        :return: None
+        """
+        pass
diff --git a/test/test_edge.py b/test/test_edge.py
index d738e96..14a4cb5 100644
--- a/test/test_edge.py
+++ b/test/test_edge.py
@@ -17,7 +17,7 @@ class TestEdge(unittest.TestCase):
     def test_automatic_add_vertex_to_edge(self):
         a = v.Vertex(1)
         b = v.Vertex(2)
-        e = Edge(a, b, 0, False)
+        e = Edge(a, b, 0)
         self.assertTrue(e in a.edges,
                         f'{e} with {e.id} should be in the eges of a {a}:'
                         + f'\n {a.edges}')
@@ -25,7 +25,7 @@ class TestEdge(unittest.TestCase):
     def test_get_partner_vertex(self):
         a = v.Vertex(1)
         b = v.Vertex(2)
-        e = Edge(a, b, 0, False)
+        e = Edge(a, b, 0)
         expected = a
         actual = e.get_partner_vertex(b)
         self.assertEqual(expected, actual)
@@ -33,28 +33,21 @@ class TestEdge(unittest.TestCase):
     def test_is_part_true(self):
         a = v.Vertex(1)
         b = v.Vertex(2)
-        e = Edge(a, b, 0, False)
+        e = Edge(a, b, 0)
         self.assertTrue(e.is_part(a), f'{a} should be a part of {e}')
 
     def test_is_part_false(self):
         a = v.Vertex(1)
         b = v.Vertex(2)
         c = v.Vertex(2)
-        e = Edge(a, b, 0, False)
+        e = Edge(a, b, 0)
         self.assertFalse(e.is_part(c), f'{c} should not be a part of {e}')
 
-    def test_equal_fail_directed(self):
-        a = v.Vertex(1)
-        b = v.Vertex(2)
-        e1 = Edge(a, b, 0, False)
-        e2 = Edge(a, b, 0, True)
-        self.assertNotEqual(e1, e2)
-
     def test_equal(self):
         a = v.Vertex(1)
         b = v.Vertex(2)
-        e1 = Edge(a, b, 0, False)
-        e2 = Edge(a, b, 1, False)
+        e1 = Edge(a, b, 0)
+        e2 = Edge(a, b, 1)
         self.assertEqual(e1, e2)
 
     def tearDown(self) -> None:
diff --git a/test/test_graph.py b/test/test_graph.py
index 129c961..1ed89de 100644
--- a/test/test_graph.py
+++ b/test/test_graph.py
@@ -20,8 +20,8 @@ class TestGraph(unittest.TestCase):
     def test_basic_constructor(self):
         a, b = v.Vertex(1), v.Vertex(2)
         test_vertecies = [a, b]
-        test_edges = [e.Edge(a, b, 1, False)]
-        g = Graph(test_vertecies, test_edges, False)
+        test_edges = [e.Edge(a, b, 1)]
+        g = Graph(test_vertecies, test_edges)
         actual = (g.num_edges == 1
                   and g.num_verticies == 2
                   and test_vertecies == g.verticies
@@ -33,29 +33,22 @@ class TestGraph(unittest.TestCase):
                         + f'and Test: {test_edges} == Graph: {g.edges}')
 
     def test_parser_for_number_of_vertecies(self):
-        g = Graph.from_file(self.test_file_path_small, False)
+        g = Graph.from_file(self.test_file_path_small)
         self.assertEqual(g.num_verticies, 9)
 
-    def test_for_fail_on_different_directed(self):
-        a, b = v.Vertex(1), v.Vertex(2)
-        test_vertecies = [a, b]
-        test_edges = [e.Edge(a, b, 1, False)]
-        self.assertRaises(ValueError, lambda: Graph(
-            test_vertecies, test_edges, True))
-
     def test_equal(self):
-        g1 = Graph.from_file(self.test_file_path_big, False)
-        g2 = Graph.from_file(self.test_file_path_big, False)
+        g1 = Graph.from_file(self.test_file_path_big)
+        g2 = Graph.from_file(self.test_file_path_big)
         self.assertEqual(g1, g2)
 
     def test_get_vertex_by_id(self):
-        g = Graph.from_file(self.test_file_path_small, False)
+        g = Graph.from_file(self.test_file_path_small)
         actual = g.get_vertex_by_id(2)
         expected = v.Vertex(2)
         self.assertEqual(actual, expected)
 
     def test_insert_vertex(self):
-        g = Graph.from_file(self.test_file_path_small, False)
+        g = Graph.from_file(self.test_file_path_small)
         vertex_id = g.get_free_vertex_id()
         expected = v.Vertex(vertex_id)
         g.insert_vertex(expected)
@@ -63,27 +56,27 @@ class TestGraph(unittest.TestCase):
         self.assertEqual(actual, expected)
 
     def test_create_vertex(self):
-        g = Graph.from_file(self.test_file_path_small, False)
+        g = Graph.from_file(self.test_file_path_small)
         expected = g.create_vertex()
         actual = g.get_vertex_by_id(expected.id)
         self.assertEqual(actual, expected)
 
     def test_get_edge_by_id(self):
-        g = Graph.from_file(self.test_file_path_small, False)
+        g = Graph.from_file(self.test_file_path_small)
         actual = g.get_edge_by_id(0)
-        expected = e.Edge(v.Vertex(0), v.Vertex(1), 0, False)
+        expected = e.Edge(v.Vertex(0), v.Vertex(1), 0)
         self.assertEqual(actual, expected)
 
     def test_insert_edge(self):
-        g = Graph.from_file(self.test_file_path_small, False)
+        g = Graph.from_file(self.test_file_path_small)
         edge_id = g.get_free_edge_id()
-        expected = e.Edge(v.Vertex(12), v.Vertex(0), edge_id, False)
+        expected = e.Edge(v.Vertex(12), v.Vertex(0), edge_id)
         g.insert_edge(expected)
         actual = g.get_edge_by_id(edge_id)
         self.assertEqual(actual, expected)
 
     def test_create_edge(self):
-        g = Graph.from_file(self.test_file_path_small, False)
+        g = Graph.from_file(self.test_file_path_small)
         expected = g.create_edge(v.Vertex(12), v.Vertex(37))
         actual = g.get_edge_by_id(expected.id)
         self.assertEqual(actual, expected)
diff --git a/test/test_vertex.py b/test/test_vertex.py
index e7487fb..78f5615 100644
--- a/test/test_vertex.py
+++ b/test/test_vertex.py
@@ -17,7 +17,7 @@ class TestVertex(unittest.TestCase):
     def test_add_edge(self) -> None:
         a = Vertex(2, [])
         b = Vertex(3, [])
-        test_edge = e.Edge(a, b, 1, False)
+        test_edge = e.Edge(a, b, 1)
 
         actual = Vertex(1, [])
         actual.add_edge(test_edge)