fork(33) download
copy 
  1. #include <vector>
  2. #include <cassert>
  3. #include <iostream>
  4.  
  5. typedef std::vector<bool> matrix_row;
  6. typedef std::vector<matrix_row> matrix;
  7.  
  8. matrix adj = 
  9. {
  10.     { 1, 1, 1, 0 },
  11.     { 1, 0, 0, 1 },
  12.     { 1, 0, 0, 1 },
  13.     { 0, 1, 1, 0 }
  14. };
  15.  
  16. matrix adjacency_to_incidence(const matrix &adj)
  17. {
  18.     int cols = adj.size();
  19.     assert(cols > 0);
  20.  
  21.     int rows = adj[0].size();
  22.     assert(rows > 0);
  23.  
  24.     assert(rows == cols);
  25.  
  26.     int edge = 0;
  27.     matrix incidence;
  28.  
  29.     for (int col = 0; col < cols; ++col) {
  30.         for (int row = 0; row <= col; ++row) {
  31.             if (adj[col][row]) {
  32.                 incidence.push_back(matrix_row(cols, 0));
  33.                 incidence[edge][row] = incidence[edge][col] = 1;
  34.                 ++edge;
  35.             }
  36.         }
  37.     }
  38.  
  39.     return incidence;
  40. }
  41.  
  42. matrix incidence_to_adjacency(const matrix &inc)
  43. {
  44.     int edges = inc.size();
  45.     assert(edges > 0);
  46.  
  47.     int vertices = inc[0].size();
  48.     assert(vertices > 0);
  49.  
  50.     matrix adjacency(vertices, matrix_row(vertices, 0));
  51.  
  52.     for (int edge = 0; edge < edges; ++edge) {
  53.         int a = -1, b = -1, vertex = 0;
  54.         for (; vertex < vertices && a == -1; ++vertex) {
  55.             if (inc[edge][vertex]) a = vertex;
  56.         }
  57.         for (; vertex < vertices && b == -1; ++vertex) {
  58.             if (inc[edge][vertex]) b = vertex;
  59.         }
  60.         if (b == -1) b = a;
  61.         adjacency[a][b] = adjacency[b][a] = 1;
  62.     }
  63.  
  64.     return adjacency;
  65. }
  66.  
  67. void print_matrix(const matrix &m)
  68. {
  69.     int cols = m.size();
  70.     if (cols == 0) return;
  71.     int rows = m[0].size();
  72.     if (rows == 0) return;
  73.  
  74.     for (int c = 0; c < cols; ++c) {
  75.         for (int r = 0; r < rows; ++r) {
  76.             std::cout << m[c][r] << " ";
  77.         }
  78.         std::cout << std::endl;
  79.     }
  80.     std::cout << std::endl;
  81. }
  82.  
  83. int main()
  84. {
  85.     matrix incidence = adjacency_to_incidence(adj);
  86.     print_matrix(incidence);
  87.  
  88.     matrix adjacency = incidence_to_adjacency(incidence);
  89.     print_matrix(adjacency);
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 0 0 0 
1 1 0 0 
1 0 1 0 
0 1 0 1 
0 0 1 1 

1 1 1 0 
1 0 0 1 
1 0 0 1 
0 1 1 0
https://ideone.com/9S974t
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!