network-complexity/BipGraph.m at main · marcofabris92/network-complexity · 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
118
119
120
121
122
123
% BipGraph class for graph transformation and Hopcroft-Karp algorithm
classdef BipGraph < handle

    properties (SetAccess = 'private', GetAccess = 'private')
        n
        Adj
        Pair_U
        Pair_V
        Dist
        max_Odeg
    end

    %% methods
    % BipGraph          % constructor
    % hopcroftKarp      % returns size of maximum matching
    % bfs               % breadth-first search (= true if augmenting path
                        % it is found)
    % dfs               % depth-first search (adds augmenting path if there
                        % is one beginning with u
    methods

        %% constructor
        function obj = BipGraph(A)
            obj.n = length(A(1,:));
            obj.Pair_U = NaN*ones(obj.n,1);
            obj.Pair_V = NaN*ones(obj.n,1);
            obj.Dist = -ones(obj.n+1,1);
            obj.Adj = cell(obj.n,1);
            obj.max_Odeg = 0;
            for i = 1:obj.n
                Odeg_i = sum(A(i,:));
                if Odeg_i > obj.max_Odeg
                    obj.max_Odeg = Odeg_i;
                end
                obj.Adj{i} = zeros(1,Odeg_i);
                j_ = 0;
                for j = 1:obj.n
                    if A(i,j) == 1
                        j_ = j_ + 1;
                        obj.Adj{i}(j_) = j;
                    end
                end
            end
        end

        %% hopcroftKarp
        function matching_size = hopcroftKarp(obj)
            matching_size = 0;
            while obj.bfs()
                for u = 1:obj.n
                    if isnan(obj.Pair_U(u)) && obj.dfs(u)
                        matching_size = matching_size + 1;
                    end
                end
            end
        end

    end

    methods (Access = private)

        %% bfs
        function found = bfs(obj)
            Q = FiniteQueue(obj.max_Odeg+1);
            for u = 1:obj.n
                if isnan(obj.Pair_U(u))
                    obj.Dist(u) = 0;
                    Q.enqueue(u);
                else
                    obj.Dist(u) = +Inf;
                end
            end
            obj.Dist(end) = +Inf;
            while ~Q.isEmpty()
                u = Q.front();
                Q.dequeue();
                if ~isnan(u) && obj.Dist(u) < obj.Dist(end)
                    for v = obj.Adj{u}
                        u_prime = obj.Pair_V(v);
                        if isnan(u_prime) && ...
                               obj.Dist(end) == +Inf || ...
                               ~isnan(u_prime) && ...
                               obj.Dist(u_prime) == +Inf
                            if isnan(u_prime)
                                obj.Dist(end) = obj.Dist(u)+1;
                            else
                                obj.Dist(u_prime) = obj.Dist(u)+1;
                            end
                            Q.enqueue(u_prime);
                        end
                    end
                end
            end
            found = (obj.Dist(end) ~= +Inf);
            Q.del();
        end

        %% dfs
        function found = dfs(obj,u)
            if ~isnan(u)
                for v = obj.Adj{u}
                    u_prime = obj.Pair_V(v);
                    if isnan(u_prime) && ...
                            obj.Dist(end) == obj.Dist(u)+1 || ...
                            ~isnan(u_prime) && ...
                            obj.Dist(u_prime) == obj.Dist(u)+1
                        if obj.dfs(u_prime)
                            obj.Pair_V(v) = u;
                            obj.Pair_U(u) = v;
                            found = 1;
                            return
                        end
                    end
                end
                obj.Dist(u) = +Inf;
                found = 0;
                return
            end
            found = 1;
        end

    end
end