% Граф задается списком ребер и вершин

test:-minset([1,2,3,4,5],[[1,2],[2,3],[3,4],[4,5],[5,1],[5,2]], Min), write(Min).

minset(V,E, Min):-
    get_edge_set(E, Min), % Порождение множества удаляемых ребер.
    not(is_connected_without(V,E, Min)). % Проверка того что граф становится реберно несвязным при удалении ребер из порожденного множества.


connected(V, E):- 
  not(disconnected(V, E)).
disconnected(V, E):- 
  member(V1, V), 
  member(V2, V), 
  not(eq(V1, V2)), 
  not(path(V1, V2, E,[])).


% Минимальность такого множества обеспечивается построением - сначала порождаются все варианты из одного ребра, потом из двух и т.д.
% Фактически - это построение всех подмножеств данного множества, начиная с мощности = 1 и по возрастанию

get_edge_set(E, Edges):-
    len(Len, E), % Определение мощности множества (длина списка ребер)
    int(N), % Счетчик мощности.
    N < Len,
    subset(N, E, Edges). % Все подмножества множества заданной мощности

% Определение мощности множества 
len(0,[]).
len(NewN, [Head| Tail]):-
    len(N,Tail),
    NewN is N + 1.

%Счетчик мощности
int(1).
int(N):-int(M), N is M + 1.

% Все подмножества множества заданной мощности
subset(0, _, []):- !.
subset(N, E, [Edge | Rest]):-
    members(Edge, E, NewGraph),
    NewN is N - 1,
    subset(NewN, NewGraph, Rest).


% Предикат принадлежности элемента множеству и возвращения множества без этого элемента и всех ему предшествующих.
members(Element, [Element | Tail], Tail).
members(Element, [Head | Tail], Tail2):-
    members(Element, Tail, Tail2).

% Проверка нового графа на реберную связность.
is_connected_without(V,E, Min):-
    minus_set(E, Min, NewGraph), % Вычитание множеств - получение нового графа.
    connected(V, NewGraph). 

connected(V, E):- 
  not(disconnected(V, E)).
disconnected(V, E):- 
  member(V1, V), 
  member(V2, V), 
  not(eq(V1, V2)), 
  not(path(V1, V2, E,[])).

% Вычитание множеств.
minus_set([ ], _, [ ]).
minus_set([Head | Tail], Set2, Set):-
    member(Head, Set2), !,
    minus_set(Tail, Set2, Set). 
minus_set([Head | Tail], Set2, [Head | Set]):-
    minus_set(Tail, Set2, Set). 



path(St, End, E, _):- 
  edge(St, End, E).     
path(St, End, E, Passed):-  
  edge(St, Via, E), 
  not(member([St, Via], Passed)), 
  path(Via, End, E, [[St, Via] | Passed]).

edge(St, End, E):- 
  member([St, End], E). 
edge(St, End, E):- 
  member([End, St], E).
eq(V, V).

member(E, [E | _]).
  member(E, [_ | T]):- 
  member(E, T).

/*
В примере неявно подразумевается неориентированный граф.
Предварительные определения.
1. Маршрутом в графе называется чередующаяся последовательность вершин и ребер,
  в которой любые два соседних элемента инцидентны
  v0, e1, v1, e2, ..., ek, uk
2. Если все ребра различны, то маршрут называется цепью.
3. Если все вершины (а, значит, и ребра) различны, то маршрут называется простой цепью
4. Если есть цепь, соединяющая вершины v0 и e0, то есть и простая цепь,
  соединяющая эти вершины.
5. Две вершины графа называются связными, если существует соединяющая их простая цепь.
6. Граф является связным, если каждые две вершины его связные.
/* Галушкина Ю.И. Конспект лекций по дискретной математике - М.:Айрис-пресс, 2007 */


/*
Построим множество связных вершин и выясним, не остались ли какие-то вершины,
не попавшие в это множество; если таковых нет граф связный,
в противном случае - граф несвязный

1. Из матрицы инцидентности получаем список ребер lines
2. Берем одно ребро (пару вершин). Они образуют множество связных вершин nodes.
3. Просматриваем в цикле все оставшиеся пары.
  Если хотя бы одна из вершин пары встречается в nodes, добавляем в nodes и вторую вершину,
  точнее сказать, if (v1 in nodes) or (v2 in nodes) then nodes := nodes + {v1} + {v2};
  Удаляем пару из списка.
  Цикл завершается, если список ребер пуст либо на последнем шаге не было изменений списка
4. Проверим, все ли вершины есть в множестве nodes
5. Проверим, не осталось ли ребер в списке.
*/

#include <iostream>
#include <list>
#include <set>
using namespace std;

struct CLine // ребро
{
    int node1;
    int node2;
};

int main()
{
    const int rows=13;
    const int cols=20;
    int graph[rows][cols]=
    {
        {1,0,0,0,0,0,0,0,0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  //0
        {0,1,0,0,0,0,0,0,0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  //1
        {0,0,1,0,0,0,0,0,0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  //2
        {0,0,0,1,0,0,0,0,0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  //3
        {0,0,0,0,1,0,0,0,0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  //4
        {1,0,0,0,0,1,0,0,1,1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  //5
        {0,1,0,0,0,0,1,0,0,0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},  //6
        {0,0,1,0,0,0,0,1,0,0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0},  //7
        {0,0,0,1,0,0,0,0,0,0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0},  //8
        {0,0,0,0,1,0,0,0,0,0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},  //9
        {0,0,0,0,0,1,0,0,0,0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0},  //10
        {0,0,0,0,0,0,1,0,0,1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},  //11
        {0,0,0,0,0,0,0,1,1,0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1}   //12
    };
    // все ли вершины указаны в матрице?
    bool node_checked=true;
    for (int i=0; i<rows && node_checked; i++)
    {
        node_checked = false; // вершина не проверена
        for (int j=0;j<cols;j++)
        {
            if (graph[i][j])
            {
                node_checked=true; // вершина проверенаs
                break;
            }
        }
    }
    if (!node_checked)
    {
        cout << "Граф несвязный" << endl;
        return 0;
    }

    CLine line;
    list<CLine>lines; // список ребер
    for (int j=0; j<cols; j++)
    {
        int count=0;
        line.node1=-1; // вспомогательная пара
        line.node2=-1;
        for (int i=0; i<rows; i++)
        {
            if (graph[i][j]==1)
            {
                if (count==0)
                    line.node1=i;
                else if (count==1)
                    line.node2=i;
                else
                {
                    cout << "Неверное заполнение матрицы инцидентности!" << endl;
                    return 1;
                }
                count++;
            }
        }
        if (line.node1!=-1 && line.node2!=-1)
            lines.push_back(line);
    }
    if (lines.empty())
    {
        cout << "Неверное заполнение матрицы инцидентности!" << endl;
        return 1;
    }

    set<int> nodes; // множество связных вершин
    list<CLine>::iterator iter=lines.begin();
    nodes.insert(iter->node1);
    nodes.insert(iter->node2);

    bool changed = true; // было изменение на последнем шаге?
    unsigned i1, i2;
    while (!(lines.empty()) && changed)
    {
        changed = false;
        // в начале очередного просмотра списка ребер считаем, что
        // изменения на последнем шаге не было
        iter = lines.begin();
        while (iter!=lines.end())
        {
            list<CLine>::iterator thisone=iter;
            iter++;
            if (nodes.find(thisone->node1)!=nodes.end() ||
                nodes.find(thisone->node2)!=nodes.end())
            // if (node1 in nodes) or (node2 in nodes)
            {
                // nodes = nodes + {node1} + {node2}
                nodes.insert(thisone->node1);
                nodes.insert(thisone->node2);
                lines.erase(thisone);
                changed = true;
            }
        }
    }

    if (lines.empty())
    {
        cout << "Граф связный" << endl;
    }
    else
    {
        cout << "Граф несвязный" << endl;
        cout << "Не обработаны ребра" << endl;
        for (iter=lines.begin(); iter!=lines.end(); iter++)
        {
            cout << (*iter).node1 << ";" << (*iter).node2 << endl;
        }
    }
    system("Pause");

   return 0;
}