StronglyConnectedComponents

Complexity

Total Complexity

11

Size/Duplication

Total Lines	38
Duplicated Lines	100 %

Importance

Changes	1
Bugs	0	Features	0

5 Methods

Rating	Name	Duplication	Size	Complexity
A	dfs()	6	6	3
A	connected()	2	2	1
B	__init__()	17	17	5
A	count()	2	2	1
A	id()	2	2	1

from abc import ABCMeta, abstractmethod

from pyalgs.algorithms.graphs.topological_sort import DepthFirstOrder
from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph, Digraph


class ConnectedComponents(object):

This code seems to be duplicated in your project.

    marked = None
    _id = None
    _count = 0

    def __init__(self, G):
        if isinstance(G, EdgeWeightedGraph):
            G = G.to_graph()

        vertex_count = G.vertex_count()
        self.marked = [False] * vertex_count
        self._id = [-1] * vertex_count
        for v in range(vertex_count):
            if not self.marked[v]:
                self.dfs(G, v)
                self._count += 1

    def dfs(self, G, v):
        self.marked[v] = True
        self._id[v] = self._count
        for w in G.adj(v):
            if not self.marked[w]:
                self.dfs(G, w)

    def connected(self, v, w):
        return self._id[v] == self._id[w]

    def count(self):
        return self._count

    def id(self, v):
        return self._id[v]


class StronglyConnectedComponents(object):

This code seems to be duplicated in your project.

    marked = None
    _id = None
    _count = 0

    def __init__(self, G):
        if isinstance(G, EdgeWeightedGraph):
            raise ValueError('Graph must be directed graph for strongly connected components')
        if not isinstance(G, Digraph):
            raise ValueError('Graph must be directed graph for strongly connected components')

        vertex_count = G.vertex_count()
        self.marked = [False] * vertex_count
        self._id = [-1] * vertex_count

        dfo = DepthFirstOrder(G.reverse())
        orders = dfo.postOrder()

        for v in orders:
            if not self.marked[v]:
                self.dfs(G, v)
                self._count += 1

    def dfs(self, G, v):
        self.marked[v] = True
        self._id[v] = self._count
        for w in G.adj(v):
            if not self.marked[w]:
                self.dfs(G, w)

    def connected(self, v, w):
        return self._id[v] == self._id[w]

    def count(self):
        return self._count

    def id(self, v):
        return self._id[v]