Дискретная математика

//Graph.h
#ifndef _GRAPH_H_
#define _GRAPH_H_
 
#include <vector>
 
class Graph
{
public:
   Graph(){}
   virtual ~Graph(){}
   void SetSize(int size_);
   const int GetSize() const {return size;} 
   virtual void Input()=0;
   void Output();
   void Resize();
protected:
   std::vector<std::vector<int> > VecGraph;
   int size;
};
 
class OrGraph:public Graph
{
public:
   OrGraph(){}
   ~OrGraph(){}
   void Input();
};
 
class UnOrGraph:public Graph
{
public:
   UnOrGraph(){}
   ~UnOrGraph(){}
   void Input();
};
 
#endif

//Graph.cpp
#include "Graph.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
//Functions for abstract Graph
void Graph::SetSize(int size_)
{
   size=size_;
   Resize();
}
 
void Graph::Output()
{
   for(int i=0; i<size; ++i)
   {
      std::copy(VecGraph[i].begin(), VecGraph[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         if(VecGraph[i][j]==1)
            std::cout<<i+1<<" node is connected with "<< j+1 <<" node.\n";
      }
   }
}
 
void Graph::Resize()
{
   VecGraph.resize(size);
   for(int i=0; i<size; ++i)
      VecGraph[i].resize(size);
}
 
//Functions for UnOrGraph
void UnOrGraph::Input()
{  
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         if(i>j)
            continue;
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node: ";
         std::cin>>VecGraph[i][j];
         if(i!=j)
            VecGraph[j][i]=VecGraph[i][j];
      }
   }
}
 
//Functions for OrGraph
void OrGraph::Input()
{
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node: ";
         std::cin>>VecGraph[i][j];
      }
   }
}

//Main.cpp
#include <iostream>
#include <stdexcept>
 
#include "Graph.h"
 
int main()
{
   try
   {
      int size=0;
      int state=0;
   
      Graph*pOb;
 
      std::cout<<"Enter numb of nodes: ";
      std::cin>>size;
 
      if(size<0)
         throw "Numb of nodes can`t be less then zero. End of program\n";
      else if(size==0)
      {
         std::cout<<"It is empty graph\n";
         return 0;
      }
 
      std::cout<<"Enter 1 for unor graph and 2 for or graph: ";
      std::cin>>state;
 
      if((state!=1)&&(state!=2))
      {
         throw "You can only input 1 for unor graph or two for or graph. End of program\n";
      }
 
      if(state==2)
         pOb=new OrGraph;
      else if(state==1)
         pOb=new UnOrGraph;
   
      pOb->SetSize(size);
      pOb->Input();
      pOb->Output();
   }
   
   catch(char*str)
   {
      std::cerr<<str;
      return EXIT_FAILURE;
   }
 
   system("pause");
   return 0;
}

//Matrix_adj.h
#ifndef _MATRIX_ADJ_H_
#define _MATRIX_ADJ_H_
 
#include <vector>
 
class AdjMatr
{
public:
   AdjMatr()
   {
      VecAdj.resize(0);
      VecPath.resize(0);
   }
   ~AdjMatr(){}
   void input();
   void output(const std::vector<std::vector<int> >& Vec);
   void resize(size_t size);
   void find_path();
   void copy_matr();
   size_t set_size();
private:
   std::vector<std::vector<int> > VecAdj;
   std::vector<std::vector<int> > VecPath;
};
 
#endif /*ifndef Matrix_adj*/

//Matrix_adj.cpp
#include "Matrix_adj.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
void AdjMatr::resize(size_t size)
{
   VecAdj.resize(size);
   for(size_t i=0; i<size; ++i)
      VecAdj[i].resize(size);
}
 
void AdjMatr::copy_matr()
{
   VecPath.resize(VecAdj.size());
   for(size_t i=0; i!=VecAdj.size(); i++)
   {
      VecPath[i].resize(VecAdj[i].size());
      std::copy(VecAdj[i].begin(), VecAdj[i].end(), VecPath[i].begin());
   }
}
 
void AdjMatr::input()
{
   size_t size=set_size();
   resize(size);
   for(size_t i=0; i<size; ++i)
   {
      for(size_t j=0; j<size; ++j)
      {
         if(i==j)
         {
            VecAdj[i][j]=0;
            continue;
         }
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node and 0 for not\n";
         std::cin>>VecAdj[i][j];
      }
   }
   std::cout<<"Initial adj matrix\n";
   output(VecAdj);
}
 
size_t AdjMatr::set_size()
{
   size_t size;
   std::cout<<"Enter size: ";
   std::cin>>size;
   return size;
}
 
void AdjMatr::output(const std::vector<std::vector<int> >& Vec)
{
   for(size_t i=0; i<Vec.size(); ++i)
   {
      std::copy(Vec[i].begin(), Vec[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
}
 
void AdjMatr::find_path()
{
   copy_matr();
   std::cout<<"Initial path matrix\n";
   output(VecPath);
   for(size_t k=0; k<VecPath.size(); ++k)
   {
      for(size_t i=0; i<VecPath.size(); ++i)
      {
         if(VecPath[i][k]==1)
         {
            for(size_t j=0; j<VecPath.size(); ++j)
            {
               VecPath[i][j]=(VecPath[i][j]||VecPath[k][j]);
            }
         }
      }
   }
   std::cout<<"Path matrix\n";
   output(VecPath);
}

//Main.cpp
#include "Matrix_adj.h"
 
#include <iostream>
 
int main()
{
   AdjMatr Ob;
   Ob.input();
   Ob.find_path();
   system("pause");
   return 0;
}

//Prufer.h
#ifndef _PRUFER_H_//Страж включения
#define _PRUFER_H_//
 
#include <vector>//Для использования std::vector
#include <iostream>//Для использования потоков ввода/вывода/ошибки
 
class AbstractMatr//Класс-контейнер матрица
{
public:
    AbstractMatr() {}//Конструктор без параметров
    AbstractMatr(size_t n, size_t m);//Конструктор с параметрами размеров
    AbstractMatr(const AbstractMatr&Ob):Matrix(Ob.Matrix) {}//Конструктор копирования. Копируем один вектор в другой
    virtual ~AbstractMatr() {}//Виртуальный деструктор
    void SetSize(size_t n, size_t m);//Функция установки размера
    inline const size_t GetRow() const {return Matrix.size();}//Получение кол-ва строк в векторе
    inline const size_t GetCol() const {return Matrix[0].size();}//Получение кол-ва столбцов в векторе
    void swap(AbstractMatr&);//Меняем местами значения двух объектов.
protected:
    std::vector<std::vector<int> > Matrix;//Вектор векторов типа int. Исходная матрица смежности
};
 
class Prufer:public AbstractMatr//Открытое наследование
{
public:
    Prufer():AbstractMatr() {}//Конструктор без параметров, вызывающий конструктор AbstractMatr()
    Prufer(size_t n, size_t m):AbstractMatr(n, m) {}//Конструктор с параметрами размера, вызывающий констр. AbstractMatr
    Prufer(const AbstractMatr& Ob):AbstractMatr(Ob) {}//Конструктор копирования, вызывающий констр. AbstractMatr
    friend std::ostream& operator <<(std::ostream&, const Prufer&);//Перегрузка оператора вывода в поток
    friend std::istream& operator >>(std::istream&, Prufer&);//Перегрузка оператора ввода в поток
    void Code();//Функция кодирования
    void Decode();//Функция декодирования
    int Degree(int row);//Функция вычисления степени вершины
    int Adjacent(int row);//Функция получения единственной смежной вершины с данной
    bool IsMin(int elem);//Функция проверки на минимальный элемент
    void DeleteEdge(int row, int col);//Функция удаления ребра
    bool IsInPruf(int elem);//Функция проверки на присутствие в коде Прюфера
    bool IsMinNode(int elem, int row);//Функция проверки на минимальный элемент. Для Decode
private:
    std::vector<int> Pruf;//Вектор типа int. Код Прюфера
    std::vector<int> Nodes;//Вектор типа int. Вершины
    std::vector<std::pair<int, int> > Edges;//Вектор типа пары двух интовых значений. Ребра
    std::vector<int> Degrees;//Вектор типа int. Степени
};
 
#endif//

//Prufer.cpp
#include <vector>
#include <algorithm>//Использование стандартных алгоритмов
#include <iostream>
#include <functional>//Использование функторов
#include <stdexcept>//Использование стандартных классов исключений
 
#include "Prufer.h"
 
AbstractMatr::AbstractMatr(size_t n, size_t m)
{
    Matrix.resize(n);//Установка размера исходной матрицы
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);//Установка размера строки исходной матрицы
    }
}
 
void AbstractMatr::SetSize(size_t n, size_t m)
{
    if(GetRow()!=0&&GetCol()!=0)//Если столбцы/строки не равны нулю
        Matrix.clear();//Чистим вектор
    Matrix.resize(n);
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);
    }
}
 
void AbstractMatr::swap(AbstractMatr& Ob)
{
    Matrix.swap(Ob.Matrix);//Меняем местами значения вектора
}
 
void Prufer::Code()
{
    for(int i=0; i!=GetRow(); ++i)
        Nodes.push_back(i+1);//Записываем в вершины элемент i+1
    for(int i=0; i!=GetRow(); ++i)
        Degrees.push_back(Degree(Nodes[i]-1));//Записываем в степени степень i элемента вектора Nodes - 1
    for(int t=0; t!=GetRow()-2; ++t)//От 0 до N-2
    {
        //Проверка на то, что наличие листьев
        if(std::count_if(Degrees.begin(), Degrees.end(), std::bind2nd(std::equal_to<int>(), 1))==0)
        {
            std::cout<<"On "<< t+1 <<" step\n";//Пишем на каком шаге
            //Кидаем исключение, которое будет обработано в main(). Используем стандартный класс
            //std::invalid_argument
            throw std::invalid_argument("Can`t code this graph (tree). There are no nodes with degree 1\n");
        }
        for(int i=0; i!=Nodes.size(); ++i)//От 0 до размера вектора вершин
        {
            if(Degrees[i]==1)//Если i-ая вершина - лист
            {
                if(IsMin(Nodes[i]))//Если i-ая вершина минимальна
                {
                    int Adj=Adjacent(Nodes[i]-1);//Возвращаем смежную с i-1 вершиной вершину
                    Pruf.push_back(Adj+1);//Добавляем в вектор кода Прюфера, смежную вершину+1
                    DeleteEdge(Nodes[i]-1, Adj);//Удаляем ребро Nodes[i]-1, Adj
                    //Удаляем из вектора вершин i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Degrees.clear();//Очищаем вектор степеней
                    for(int i=0; i!=Nodes.size(); ++i)
                    {
                        Degrees.push_back(Degree(Nodes[i]-1));//Заполняем вектор степеней
                    }
                    break;//Брякаем цикл
                }
            }
        }
    }
    Edges.push_back(std::make_pair<int, int>(Nodes[0], Nodes[1]));//Записываем ребро Nodes[0]->Nodes[1] в вектор ребер
    std::cout<<"Prufer`s code\n";//Вывод в консоль строки
    std::copy(Pruf.begin(), Pruf.end(), std::ostream_iterator<int>(std::cout, " "));//Вывод в консоль вектора
    std::cout<<std::endl;//Перевод каретки+очистка буфера
}
 
void Prufer::Decode()
{
    std::pair<int, int> Temp;//Создаем временный элемент типа пары двух интовых значений
    Temp=Edges.front();//Записываем первый элемент из вектора ребер во временный элемент
    Edges.clear();//Чистим вектор ребер
    Nodes.clear();//Чистим вектор вершин
    for(int i=0; i!=Matrix.size(); ++i)
        Nodes.push_back(i+1);//Записываем i+1 вершину (дабы начиналось с 1)
    for(int t=0; t!=GetRow()-2; ++t)//До N-2
    {
        for(int i=0; i!=Nodes.size(); ++i)
        {
            if(!IsInPruf(Nodes[i]))//Если не i-тая вершина не выходит в код прюфера
            {
                if(IsMinNode(Nodes[i], i))//И если она минимальная среди вершин
                {
                    //Делаем пару интовых значений. Первый элемент вектора Прюфера и i-тую вершину.
                    //Записываем ее в вектор ребер
                    Edges.push_back(std::make_pair<int, int>(Pruf[0], Nodes[i]));
                    //Удаляем i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Pruf.erase(std::find(Pruf.begin(), Pruf.end(), Pruf[0]));//Удаляем первый элемент из в. Прюфера
                    break;//Брякаем
                }
            }
        }
    }
    Edges.push_back(Temp);//Записываем в конец вектора значение, записанное во временной переменной
    std::cout<<"Decode from Prufers`s code\nDefault tree\n";//Вывод строки
    //Цикл по итератору. От начала вектора ребер, до конца.
    for(std::vector<std::pair<int, int> >::const_iterator Iter=Edges.begin(); Iter!=Edges.end(); ++Iter)
    {
        std::cout<<"<"<<Iter->first<<','<<Iter->second<<'>'<<'\n';//Выводим в консоль <вершина из прюфера, вершина из nodes>
    }
}
 
int Prufer::Degree(int row)
{
    int cnt=0;//Счетчик
    for(int j=0; j!=GetCol(); ++j)//До кол-ва столбцов
    {
        if(Matrix[row][j]==1)//Если j-ый элемент строки row равен 1
            cnt++;//Плюсуем счетчик
    }
    return cnt;
}
 
int Prufer::Adjacent(int row)
{
    int i;
    for(i=0; i!=GetCol(); ++i)
        if(Matrix[row][i]==1)//Если i-ый элемент строки row равен 1
            break;//Брякаем
    return i;//Вернули i
}
 
bool Prufer::IsMin(int elem)
{
    int min=elem;//min=elem
    for(int i=0; i!=Degrees.size(); ++i)
    {
        if(Degrees[i]==1)//Если i-ая степень=1 
        {
            if(Nodes[i]<min)//Если i-ая вершина меньше минимума
                min=Nodes[i];//Минимум становится равен i-ой вершине
        }
    }
    return (min==elem);//Если min==elem возвращаем true, иначе false
}
 
void Prufer::DeleteEdge(int row, int col)
{
    Matrix[row][col]=0;//col-тый элемент в row-той строке равен 0
    Matrix[col][row]=0;//наоборот
}
 
std::ostream& operator <<(std::ostream& os, const Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        //Вывод на экран. Стандартный алгоритм copy
        std::copy(Ob.Matrix[i].begin(), Ob.Matrix[i].end(), std::ostream_iterator<int>(os, " "));
        os<<'\n';
    }
    return os;
}
 
std::istream& operator >>(std::istream& is, Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        for(int j=0; j!=Ob.GetCol(); ++j)
        {
            if(i>=j)//Если i>=j переходим к след итерации
                continue;
            std::cout<<"Enter 1 for connect "<< i+1 <<" and "<< j+1 <<" nodes, and 0 for not\n";
            is>>Ob.Matrix[i][j];
            if(i!=j)//Если i!=j
                Ob.Matrix[j][i]=Ob.Matrix[i][j];//
        }
    }
    return is;
}
 
bool Prufer::IsInPruf(int elem)
{
    for(int i=0; i!=Pruf.size(); ++i)
    {
        if(elem==Pruf[i])//Если элемент = Pruf[i]
        {
            return true;//Вернули true. То есть элемент присутствует в Прюфере
        }
    }
    return false;//Вернули false. Элемента нет. Все гуд
}
 
bool Prufer::IsMinNode(int elem, int row)
{
    int min=elem;//Минимум = элемент
    for(int i=row; i!=Nodes.size(); ++i)//От номера элемента в массиве до конца
    {
        if(Nodes[i]<min)
            min=Nodes[i];
    }
    return (min==elem);
}

//Main.cpp
#include <iostream>
 
#include "Prufer.h"
 
int main()
{
    Prufer Ob;//Создали объект
    int N;
    std::cout<<"Enter N: ";
    std::cin>>N;//Ввели размер
    Ob.SetSize(N, N);//Установили размер для квадратной матрицы
    std::cout<<"Enter matrix\n";
    std::cin>>Ob;//Ввели матрицу
    std::cout<<"Initial matrix\n";
    std::cout<<Ob;//Вывели матрицу
    try//Блок try, catch
    {
        Ob.Code();//Вызвали кодирование. Если в функции кинулось исключение - перешли в блок catch
        Ob.Decode();//Если нет - декодируем дерево
    }
    catch(const std::invalid_argument& e)//Ловим исключение типа const std::invalid_argument&
    {
        std::cout<<e.what()<<'\n';//what - функция класса invalid_argument.
    }
    system("pause");//Для release версии
    return 0;
}

//Floyd.h
#ifndef _FLOYD_H_
#define _FLOYD_H_
 
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stack>
 
typedef std::vector<std::vector<int> > VM;
typedef std::stack<int> ST;
 
class MatrixAdj
{
public:
    MatrixAdj()
    {
    }
 
    virtual ~MatrixAdj()
    {
    }
 
    void SetSize(const size_t n)
    {
        Matr.resize(n);
        for(size_t i=0; i<n; ++i)
            Matr[i].resize(n);
    }
 
    void Fill()
    {
        for(size_t i=0; i<Matr.size(); ++i)
        {
            for(size_t j=0; j<Matr.size(); ++j)
            {
                if(i==j)
                    Matr[i][j]=0;
                else if(i>j)
                {
                    Matr[i][j]=Matr[j][i];
                }
                else
                {
                    std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                        <<"0 for not connect them\n";
                    std::cin>>Matr[i][j];
                    if(Matr[i][j]==0)
                        Matr[i][j]=100;
                }
            }
        }
    }
protected:
    VM Matr;
};
 
class Floyd:public MatrixAdj
{
public:
    Floyd():MatrixAdj()
    {
    }
 
    ~Floyd()
    {
    }
 
    void Initialise()
    {
        MatrPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrPath[i].resize(Matr.size());
        for(size_t i=0; i<MatrPath.size(); ++i)
        {
            for(size_t j=0; j<MatrPath.size(); ++j)
            {
                if(Matr[i][j]==100)
                    MatrPath[i][j]=100;
                else
                    MatrPath[i][j]=j;
            }
        }
        Copy();
    }
    
    void FindPathMatr()
    {
        for(size_t k=0; k<Matr.size(); ++k)
        {
            for(size_t i=0; i<Matr.size(); ++i)
            {
                for(size_t j=0; j<Matr.size(); ++j)
                {
                    int b=MatrSPath[i][k]+MatrSPath[k][j];
                    if(b<MatrSPath[i][j])
                    {
                        MatrSPath[i][j]=b;
                        MatrPath[i][j]=k;
                    }
                }
            }
        }
    }
 
    void FindPath(size_t first, size_t second)
    {
        if(first>=MatrPath.size() || second>=MatrPath.size())
            throw std::invalid_argument("One of nodes for searching is more than Matr size");
        ST Goals;
        Path.push(first);
        Goals.push(second);
        while(!Goals.empty())
        {
            int u=Path.top();
            int v=Goals.top();
            int s=MatrPath[u][v];
            if(v==s)
            {
                Path.push(v);
                Goals.pop();
            }
            else
                Goals.push(s);
        }
    }
 
    void PrintWMatr(std::ostream& os) const
    {
        PrintMatr(Matr, os);
    }
 
    void PrintSPMatr(std::ostream& os) const
    {
        PrintMatr(MatrSPath, os);
    }
 
    void PrintPMatr(std::ostream& os) const
    {
        PrintMatr(MatrPath, os);
    }
 
    void PrintSt(std::ostream& os)
    {
        while(!Path.empty())
        {
            os<<Path.top()<<' ';
            Path.pop();
        }
        os<<'\n';
    }
private:
    VM MatrPath;
    VM MatrSPath;
    ST Path;
    
    void PrintMatr(const VM& Vec, std::ostream& os) const
    {
        for(size_t i=0; i<Vec.size(); ++i)
        {
            for(size_t j=0; j<Vec.size(); ++j)
            {
                os<<std::setw(3)<<Vec[i][j]<<' ';
            }
            os<<'\n';
        }
    }
 
    void Copy()
    {
        MatrSPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrSPath[i].resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            std::copy(Matr[i].begin(), Matr[i].end(), MatrSPath[i].begin());
    }
};
 
std::ostream& operator <<(std::ostream& os, const Floyd& Ob)
{
    os<<"Weight matrix\n";
    Ob.PrintWMatr(os);
    os<<"Shortest paths matrix\n";
    Ob.PrintSPMatr(os);
    os<<"Shortest path nodes matrix\n";
    Ob.PrintPMatr(os);
    return os;
}
 
#endif

//Floyd.cpp
#include "Floyd.h"
 
int main()
{
    try
    {
        int n;
        std::cout<<"Enter numb of nodes: ";
        std::cin>>n;
        Floyd Ob;
        Ob.SetSize(n);
        Ob.Fill();
        Ob.Initialise();
        Ob.FindPathMatr();
        std::cout<<Ob;
        size_t first, second;
        std::cout<<"Enter first and second nodes for search path between them\n";
        std::cin>>first>>second;
        Ob.FindPath(first, second);
        std::cout<<"Shortest path between " << first <<" and "<< second <<" nodes is\n";
        Ob.PrintSt(std::cout);
    }
    catch(std::exception& e)
    {
        std::cerr<<e.what()<<'\n';
        return 1;
    }
    return 0;
}