KC/ACPM.cs at master · Dm2004co/KC · 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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection.Metadata;
using System.Text;
using System.Threading.Tasks;

namespace KC
{
    class ACPM
    {
        static Graphe g = new Graphe();
        int root;
        const int poids = 1;
        List<(int, int)> A;
        List<int> S;
        bool spanning = false;
        List<Noeud> n;
        public ACPM()
        {
            //this.n = g.N();
            this.root = Selection_Root();
            Suppression();
            //Edmonds();

        }
        int Selection_Root()
        {

            int temp = int.MinValue;
            int racine = 0;
            int t = 0;

            for (int i = 0; i < n.Count; i++)
            {

                if (n[i].Degre > temp)
                {
                    temp = n[i].Degre;
                    t = n[i].Sommet;
                }
                racine = t;
            }
            return racine;
        }
        void Suppression()
        {
            for (int j = 0; j < g.AreteList.Count; j++)
            {
                if (g.AreteList[j].Item2 == this.root)
                {
                    g.AreteList.RemoveAt(j);
                }
            }
        }
        void Selection()
        {
            int p = int.MaxValue;
            foreach (var s in g.Sommet)
            {
                foreach (var a in g.AreteList)
                {
                    Noeud l1 = new Noeud(a.Item1);
                    Noeud l2 = new Noeud(a.Item2);
                    if (a.Item2 == s)
                    {
                        Lien l = new Lien(l1, l2);
                        if(l.Poids < p)
                        {
                            p = l.Poids;

                        }

                    }
                    g.AreteList.Remove((a.Item1, a.Item2));
                }

            }
        }
        bool Identification_Contraction_de_Cycle()
        {
            #region Identification de Cycle
            bool c = false;
            (int,int)[] A0 = new (int, int)[g.AreteList.Count];
            g.AreteList.CopyTo(A0);
            int[] S0 = new  int[g.Sommet.Count];
            g.Sommet.CopyTo(S0);
            S = g.Sommet;
            A = g.AreteList;
            int vc = 0;
            foreach (var s in S)
            {
                foreach (var a in A)
                {
                    if (a.Item1 == s)
                    {
                        Noeud n1 = new Noeud(s);
                        if(g.Existence_Circuit(n1).Item1 == false)continue ;
                        else
                        {
                            c = true;

                            #region Contraction sortant
                            for (int i = 0; i < g.Existence_Circuit(n1).Item2.Count; i++)
                            {
                                int sommet = g.Existence_Circuit(n1).Item2[i];
                                S.Remove(sommet);
                            }
                           (int,int) e = (s, vc);
                            A.Add(e);
                            #endregion
                        }
                    }
                    if (a.Item2 == s)
                    {
                        Noeud n2 = new Noeud(s);
                        if (g.Existence_Circuit(n2).Item1 == false) continue;
                        else
                        {
                            c = true;
                            #region Contraction entrant
                            for (int i = 0; i < g.Existence_Circuit(n2).Item2.Count;i++)
                            {
                                int sommet = g.Existence_Circuit(n2).Item2[i];
                                S.Remove(sommet);
                            }
                            (int, int) e = (vc,s);
                            A.Add(e);
                            #endregion
                        }
                    }

                }
            }
            #endregion


            return c;

        }
       void Edmonds()
        {
            int e = 0;

            foreach(var element in n)
            {
                while (e != n.D2)
                {
                    Selection();
                    Identification_Contraction_de_Cycle();
                    e++;
                }
            }

        }
    }
}