Построение графа

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
void vivod(int *T, int x) {
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < x; j++) {
            printf("%d", *(T + i*x + j));
        }
        printf("\n");
    }
}
 
int main() {
    int x, a, b, k = 0, i, j, q;
    int *G, *T;
    printf("Vvedite 4islo vershin\n");
    scanf("%d", &x);
    G = (int *)malloc(sizeof(int)*x*x);
    for (i = 0; i < x; i++) {
        for (j = 0; j < x; j++) {
            *(G + i*x + j) = 0;
        }
    }
    FILE *input = fopen("input.txt", "r");
    while (!feof(input)) {
        fscanf(input, "%d", &a);  //вершина
        fscanf(input, "%d", &b);  //степень вершины
        k += b;
        for (j = 0; j < b; j++) {
            fscanf(input, "%d", &q);
            *(G + a*x + q) = 1;
        }
    }
    k /= 2;
    T = (int *)malloc(sizeof(int)*(k + x)*(k + x));
    for (i = 0; i < (k + x); i++) {  //заполнение Т нулями
        for (j = 0; j < (k + x); j++) {
            *(T + i*(x + k) + j) = 0;
        }
    }
    for (i = 0; i < x; i++) {  //перенос вершин в Т
        for (j = 0; j < x; j++) {
            *(T + i*(k + x) + j) = *(G + i*x + j);
        }
    }
    for (i = 0; i < x; i++) {  //в G удаляются дублирующие значения
        for (j = 0; j < x; j++) {
            if (*(G + i*x + j) == 1) *(G + j*x + i) = 0;
        }
    }
    a = x;
    for (i = 0; i < x; i++) {  //поиск инцидентных ребер
        for (j = 0; j < x; j++) {
            if (*(G + i*x + j) == 1) {
                *(T + i*(x + k) + a) = 1;
                *(T + j*(x + k) + a) = 1;
                *(T + a*(x + k) + i) = 1;
                *(T + a*(x + k) + j) = 1;
                a++;
            }
        }
    }
    for (i = 0; i < x; i++) {  //поиск смежных ребер
        for (j = k; j < (k + x); j++) {
            if (*(T + i*(k + x) + j) == 1) {
                for (a = j + 1; a < (k + x); a++)
                    if (*(T + i*(k + x) + a) == 1) {
                        *(T + j*(k + x) + a) = 1;
                        *(T + a*(k + x) + j) = 1;
                    }
            }
        }
    }
    vivod(T, (k + x));
    _getch();
}

//Вершины и ребра графа назовем его элементами. По графу G построить граф T(G),
//у которого в качестве вершин взяты элементы G, а две вершины смежны тогда
//и только тогда, когда соответствующие элементы в G смежны или инцидентны.
//Еще нужно использовать списки смежности, желательно одномерные массивы
//Чтение из файла как задать лучше?
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                                 T_str;
typedef T_str                                       T_vertex;
typedef std::set    < T_vertex                  >   T_vertices;
typedef std::map    < T_vertex,     T_vertices  >   T_adjacent_vertices_of;
typedef std::pair   < T_vertex,     T_vertex    >   T_edge;
typedef std::set    < T_edge    >                   T_edges;
///////////////////////////////////////////////////////////////////////////////
class   T_undirected_graph
{
    //-------------------------------------------------------------------------
    T_vertices              vertices_;
    T_adjacent_vertices_of  adjacent_vertices_of_;
    //-------------------------------------------------------------------------
public:
    //-------------------------------------------------------------------------
    void    add_vertex( T_vertex    const   &   vertex )
    {
        vertices_.insert( vertex );
    }
    //-------------------------------------------------------------------------
    void    add_edge( T_edge    const   &   edge )
    {
        auto    vertex_A    =   edge.first;
        auto    vertex_B    =   edge.second;
 
        adjacent_vertices_of_[ vertex_A ].insert( vertex_B );
        adjacent_vertices_of_[ vertex_B ].insert( vertex_A );
    }
    //-------------------------------------------------------------------------
    friend
    std::ostream    &   operator<<
        (
            std::ostream                &   ostr,
            T_undirected_graph  const   &   graph
        )
    {
        ostr    <<  graph.vertices_.size()
                <<  std::endl;
 
        for (
                auto    const   &   vert_cur    :
                graph.vertices_
            )
        {
            ostr    <<  vert_cur
                    <<  '\t';
        }//for
 
        auto    edges   =   graph.get_edges();
 
        ostr    <<  std::endl
                <<  std::endl
                <<  edges.size()
                <<  std::endl;
 
        for (
                auto    const   &   edge_cur    :
                edges
            )
        {
            ostr    <<  edge_cur.first
                    <<  '\t'
                    <<  edge_cur.second
                    <<  std::endl;
        }//for
 
        ostr    <<  std::endl
                <<  std::endl;
 
        return  ostr;
    }
    //-------------------------------------------------------------------------
    void    print_with_comment( T_str   const   &   comment )               const
    {
        std::cout   <<  comment
                    <<  std::endl
                    <<  *this;
    }
    //-------------------------------------------------------------------------
    T_undirected_graph     get_tgraph()                                 const
    {
        T_undirected_graph  res_graph;
        add_adjacend_and_incident_elements_to( res_graph );
        return  res_graph;
    }
    //-------------------------------------------------------------------------
    static
    T_edge  get_edge_with_vertices
        (
            T_vertex    vertex_A,
            T_vertex    vertex_B
        )
    {
        if  (
                    vertex_A
                >   vertex_B
            )
        {
            std::swap   (
                            vertex_A,
                            vertex_B
                        );
        }//if
 
        return  T_edge( vertex_A,   vertex_B );
    }
    //-------------------------------------------------------------------------
private:
    //-------------------------------------------------------------------------
    void    add_edges( T_edges  const   &   edges )
    {
        for (
                auto    const   &   edge    :
                edges
            )
        {
            add_edge( edge );
        }//for
    }
    //-------------------------------------------------------------------------
    void    add_vertices( T_vertices    const   &   vertices )
    {
        for (
                auto    const   &   vertex     :
                vertices
            )
        {
            add_vertex( vertex );
        }//for
    }
    //-------------------------------------------------------------------------
    T_edges     get_edges()                                                 const
    {
        T_edges     res_edges;
 
        for (
                auto    const   &   vert_and_adjacent   :
                adjacent_vertices_of_
            )
        {
            auto    vert_A  =   vert_and_adjacent.first;
 
            for (
                    auto    const   &   vert_B  :
                    vert_and_adjacent.second
                )
            {
                if  (
                            vert_A
                        <=  vert_B
                    )
                {
                    res_edges.insert
                        (
                            {
                                vert_A,
                                vert_B
                            }
                        );
                }//if
            }//for
        }//for
 
        return  res_edges;
    }
    //-------------------------------------------------------------------------
    void    add_adjacend_and_incident_elements_to( T_undirected_graph    &   graph ) const
    {
        add_adjacend_vertices_as_elements_to    ( graph );
        add_adjacend_edges_as_elements_to       ( graph );
        add_incident_elements_to                ( graph );
    }
    //-------------------------------------------------------------------------
    void    add_adjacend_vertices_as_elements_to
        ( T_undirected_graph    &   graph )                                 const
    {
        auto    edges   =   get_edges();
 
        for (
                auto    const   &   edge_cur    :
                edges
            )
        {
            graph.add_vertex    ( edge_cur.first    );
            graph.add_vertex    ( edge_cur.second   );
            graph.add_edge      ( edge_cur          );
        }//for
    }
    //-------------------------------------------------------------------------
    T_edges     get_edges_of_vertex( T_vertex   const   &   vertex )        const
    {
        T_edges             edges_res;
 
        auto        it  =   adjacent_vertices_of_.find( vertex );
 
        if  (
                it  !=  adjacent_vertices_of_.end()
            )
        {
            auto    const   &   adjacend_vertices   =   it->second;
 
            for (
                    auto    const   &   adj_vertex  :
                    adjacend_vertices
                )
            {
                edges_res.insert
                    (
                        get_edge_with_vertices
                            (
                                vertex,
                                adj_vertex
                            )
                    );
            }//for
 
        }//if
 
        return  edges_res;
    }
    //-------------------------------------------------------------------------
    static
    T_vertices  get_edges_as_vertices( T_edges  const   &   edges )
    {
        T_vertices  vertices_res;
 
        for (
                auto    const   &   edge    :
                edges
            )
        {
            vertices_res.insert
                (
                    get_edge_as_vertex( edge )
                );
        }//for
 
        return  vertices_res;
    }
    //-------------------------------------------------------------------------
    static
    T_vertex    get_edge_as_vertex( T_edge     const   &   edge )
    {
        return      edge.first
                +   "_"
                +   edge.second;
    }
    //-------------------------------------------------------------------------
    static
    T_edges     get_pairwise_edges( T_vertices  const   &   vertices )
    {
        T_edges     edges_res;
 
        for (
                auto
                it  =   vertices.begin   ();
                it  !=  vertices.end     ();
                ++it
            )
        {
            auto    it_next_begin   =   it;
 
            std::advance
                (
                    it_next_begin,
                    1
                );
 
            auto    vert_A    =     *it;
 
            for (
                    auto
                    it_next     =   it_next_begin;
                    it_next     !=  vertices.end();
                    ++it_next
                )
            {
                auto    vert_B    =   *it_next;
 
                edges_res.insert
                    (
                        get_edge_with_vertices
                            (
                                vert_A,
                                vert_B
                            )
                    );
            }//for
        }//for
 
        return  edges_res;
    }
    //-------------------------------------------------------------------------
    void    add_adjacend_edges_as_elements_to( T_undirected_graph   &   graph ) const
    {
        for (
                auto    const   &   vertex_cur  :
                vertices_
            )
        {
            auto    edges_of_vertex_cur     =   get_edges_of_vertex( vertex_cur );
 
            if  (
                    edges_of_vertex_cur.size()  >   1
                )
            {
                auto    vertices_from_edges
                    =   get_edges_as_vertices( edges_of_vertex_cur );
 
                graph.add_vertices( vertices_from_edges );
 
                graph.add_edges
                    (
                        get_pairwise_edges( vertices_from_edges )
                    );
            }//if
        }//for
    }
    //-------------------------------------------------------------------------
    void    add_incident_elements_to( T_undirected_graph    &   graph ) const
    {
        for (
                auto    const   &   vertex_cur  :
                vertices_
            )
        {
            auto    edges_of_vertex_cur     =   get_edges_of_vertex( vertex_cur );
 
            if  (
                    edges_of_vertex_cur.empty()
                )
            {
                continue;
            }//if
 
            graph.add_vertex( vertex_cur );
 
            for (
                    auto    const   &   edge    :
                    edges_of_vertex_cur
                )
            {
                auto    edge_as_vertex  =   get_edge_as_vertex( edge );
                graph.add_vertex( edge_as_vertex );
 
                graph.add_edge
                    (
                        get_edge_with_vertices
                            (
                                vertex_cur,
                                edge_as_vertex
                            )
                    );
            }//for
        }//for
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
std::istream    &   operator>>
    (
        std::istream        &   istr,
        T_undirected_graph  &   graph
    )
{
    int     vertices_total{};
    istr    >>  vertices_total;
 
    for( int  i{}; i < vertices_total; ++i )
    {
        T_vertex    vertex_cur;
        istr    >>  vertex_cur;
        graph.add_vertex( vertex_cur );
    }//for
 
    int     edges_total{};
    istr    >>  edges_total;
 
    for( int  i{}; i < edges_total; ++i )
    {
        T_vertex    vertex_A;
        T_vertex    vertex_B;
 
        istr    >>  vertex_A;
        istr    >>  vertex_B;
 
        graph.add_edge
            (
                graph.get_edge_with_vertices
                    (
                        vertex_A,
                        vertex_B
                    )
            );
    }//for
 
    return  istr;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_str   const       FILE_NAME   { "g.txt"   };
    std::ifstream       ifile       ( FILE_NAME );
 
    if( !ifile )
    {
        std::cout   <<  "Cannot read from file '"
                    <<  FILE_NAME
                    <<  "'."
                    <<  std::endl;
 
        exit(1);
    }//if
 
    T_undirected_graph  graph;
 
    //Неориетнированный граф записан в файле следующим образом:
    //количество вершин
    //имена вершин
    //количество ребер
    //ребра, где каждое - это просто две входящие в него вершины, разделенные пробельным
    //символом.
    ifile   >>  graph;
    graph.print_with_comment    ( "Source graph:" );
 
    auto    tgraph     =   graph.get_tgraph();
    std::ofstream   ofile("tg.txt");
    ofile   <<  tgraph;
    tgraph.print_with_comment   ( "Result graph:" );
}