wehub-resource-sync
159 lines
4.5 KiB
Python
159 lines
4.5 KiB
Python
import unittest
|
|
|
|
import easygraph as eg
|
|
|
|
from easygraph.utils.exception import EasyGraphNotImplemented
|
|
|
|
|
|
class test_bridges(unittest.TestCase):
|
|
def setUp(self):
|
|
self.g1 = eg.get_graph_karateclub()
|
|
|
|
# source graph: https://zh.wikipedia.org/zh-cn/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95#/media/File:Dijkstra_Animation.gif
|
|
edges = [(1, 2), (1, 3), (1, 6), (2, 3), (2, 4), (3, 4), (3, 6), (4, 5), (5, 6)]
|
|
self.g2 = eg.Graph(edges)
|
|
self.g2.add_edges(
|
|
edges,
|
|
edges_attr=[
|
|
{"weight": 7},
|
|
{"weight": 9},
|
|
{"weight": 14},
|
|
{"weight": 10},
|
|
{"weight": 15},
|
|
{"weight": 11},
|
|
{"weight": 2},
|
|
{"weight": 6},
|
|
{"weight": 9},
|
|
],
|
|
)
|
|
|
|
# source graph: https://static.javatpoint.com/tutorial/daa/images/dijkstra-algorithm.png
|
|
self.g3 = eg.Graph()
|
|
edges = [
|
|
(0, 1),
|
|
(0, 4),
|
|
(1, 4),
|
|
(1, 2),
|
|
(4, 5),
|
|
(4, 8),
|
|
(2, 3),
|
|
(2, 6),
|
|
(2, 8),
|
|
(5, 6),
|
|
(5, 8),
|
|
(3, 6),
|
|
(3, 7),
|
|
(6, 7),
|
|
]
|
|
|
|
self.g3.add_edges(
|
|
edges,
|
|
edges_attr=[
|
|
{"weight": 4},
|
|
{"weight": 1},
|
|
{"weight": 11},
|
|
{"weight": 8},
|
|
{"weight": 1},
|
|
{"weight": 7},
|
|
{"weight": 7},
|
|
{"weight": 4},
|
|
{"weight": 2},
|
|
{"weight": 2},
|
|
{"weight": 6},
|
|
{"weight": 14},
|
|
{"weight": 9},
|
|
{"weight": 10},
|
|
],
|
|
)
|
|
self.g4 = eg.Graph()
|
|
edges = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3)]
|
|
self.g4.add_edges(
|
|
edges,
|
|
edges_attr=[
|
|
{"weight": -1},
|
|
{"weight": -2},
|
|
{"weight": -3},
|
|
{"weight": -4},
|
|
{"weight": -5},
|
|
{"weight": -6},
|
|
],
|
|
)
|
|
|
|
def result(self, g: eg.Graph):
|
|
res = eg.bridges(g)
|
|
for i in res:
|
|
print(i)
|
|
|
|
def test_bridges(self):
|
|
self.result(g=self.g2)
|
|
self.result(g=self.g3)
|
|
self.result(g=self.g4)
|
|
|
|
def test_has_bridges(self):
|
|
print(eg.has_bridges(self.g2))
|
|
|
|
def test_empty_graph(self):
|
|
g = eg.Graph()
|
|
self.assertFalse(eg.has_bridges(g))
|
|
self.assertEqual(list(eg.bridges(g)), [])
|
|
|
|
def test_single_node_graph(self):
|
|
g = eg.Graph()
|
|
g.add_node(1)
|
|
self.assertFalse(eg.has_bridges(g))
|
|
self.assertEqual(list(eg.bridges(g)), [])
|
|
|
|
def test_disconnected_graph(self):
|
|
g = eg.Graph()
|
|
g.add_edges_from([(0, 1), (2, 3)])
|
|
self.assertTrue(eg.has_bridges(g))
|
|
self.assertCountEqual(list(eg.bridges(g)), [(0, 1), (2, 3)])
|
|
|
|
def test_cycle_graph(self):
|
|
g = eg.DiGraph([(1, 2), (2, 3), (3, 1)])
|
|
self.assertFalse(eg.has_bridges(g))
|
|
self.assertEqual(list(eg.bridges(g)), [])
|
|
|
|
def test_path_graph(self):
|
|
g = eg.path_graph(4)
|
|
self.assertTrue(eg.has_bridges(g))
|
|
self.assertCountEqual(list(eg.bridges(g)), [(0, 1), (1, 2), (2, 3)])
|
|
|
|
def test_star_graph(self):
|
|
g = eg.Graph()
|
|
g.add_edges_from([(0, i) for i in range(1, 5)])
|
|
|
|
expected = [(0, 1), (0, 2), (0, 3), (0, 4)]
|
|
self.assertTrue(eg.has_bridges(g))
|
|
self.assertCountEqual(list(eg.bridges(g)), expected)
|
|
|
|
def test_complete_graph(self):
|
|
g = eg.complete_graph(5)
|
|
self.assertFalse(eg.has_bridges(g))
|
|
self.assertEqual(list(eg.bridges(g)), [])
|
|
|
|
def test_graph_with_invalid_root(self):
|
|
g = eg.path_graph(3)
|
|
with self.assertRaises(eg.NodeNotFound):
|
|
list(eg.bridges(g, root=10))
|
|
|
|
def test_multigraph_exception(self):
|
|
g = eg.MultiGraph()
|
|
g.add_edges_from([(0, 1), (1, 2)])
|
|
with self.assertRaises(EasyGraphNotImplemented):
|
|
list(eg.bridges(g))
|
|
with self.assertRaises(EasyGraphNotImplemented):
|
|
eg.has_bridges(g)
|
|
|
|
def test_weighted_graph_should_ignore_weights(self):
|
|
g = eg.Graph()
|
|
g.add_edges_from(
|
|
[(0, 1), (1, 2), (2, 3), (3, 0)],
|
|
edges_attr=[{"weight": 10}, {"weight": 20}, {"weight": 30}, {"weight": 40}],
|
|
)
|
|
self.assertFalse(eg.has_bridges(g))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main()
|