C++ Program to Remove the Edges in a Cyclic Graph such that its Linear Extension can be Found

«
»
This is a C++ Program to find feedback arc set. This is the set which contains edges which when removed from the graph, graph becomes directed acyclic graph.

Here is source code of the C++ Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<conio.h>
  4. using namespace std;
  5. int c = 0;
  6. struct adj_list
  7. {
  8.         int dest;
  9.         adj_list *next;
  10. }*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
  11. struct Graph
  12. {
  13.         int v;
  14.         adj_list *ptr;
  15. } array[6];
  16. void addReverseEdge(int src, int dest)
  17. {
  18.     np1 = new adj_list;
  19.     np1->dest = src;
  20.     np1->next = NULL;
  21.     if (array[dest].ptr == NULL)
  22.     {
  23.         array[dest].ptr = np1;
  24.         q = array[dest].ptr;
  25.         q->next = NULL;
  26.     }
  27.     else
  28.     {
  29.         q = array[dest].ptr;
  30.         while (q->next != NULL)
  31.         {
  32.             q = q->next;
  33.         }
  34.         q->next = np1;
  35.     }
  36. }
  37. void addEdge(int src, int dest)
  38. {
  39.     np = new adj_list;
  40.     np->dest = dest;
  41.     np->next = NULL;
  42.     if (array[src].ptr == NULL)
  43.     {
  44.         array[src].ptr = np;
  45.         p = array[src].ptr;
  46.         p->next = NULL;
  47.     }
  48.     else
  49.     {
  50.         p = array[src].ptr;
  51.         while (p->next != NULL)
  52.         {
  53.             p = p->next;
  54.         }
  55.         p->next = np;
  56.     }
  57.     //addReverseEdge(src, dest);
  58. }
  59. void print_graph(int n)
  60. {
  61.     for (int i = 0; i < n; i++)
  62.     {
  63.         cout << "Adjacency List of " << array[i].v << ": ";
  64.         while (array[i].ptr != NULL)
  65.         {
  66.             cout << (array[i].ptr)->dest << " ";
  67.             array[i].ptr = (array[i].ptr)->next;
  68.         }
  69.         cout << endl;
  70.     }
  71. }
  72.  
  73. int checkDAG(int n)
  74. {
  75.     int count = 0;
  76.     int size = n - 1;
  77.     for (int i = 0; i < n; i++)
  78.     {
  79.         if (count == size)
  80.         {
  81.             return 0;
  82.         }
  83.         if (array[i].ptr == NULL)
  84.         {
  85.             count++;
  86.             for (int j = 0; j < n; j++)
  87.             {
  88.  
  89.                 while (array[j].ptr != NULL)
  90.                 {
  91.                     if ((array[j].ptr)->dest == (array[i].ptr)->dest)
  92.                     {
  93.                         (array[j].ptr)->dest = -1;
  94.                     }
  95.                     array[i].ptr = (array[i].ptr)->next;
  96.                 }
  97.             }
  98.  
  99.         }
  100.     }
  101.     cout<<"after checking dag";    int visited[n + 1];
  102.     for (int i = 0; i < n; i++)
  103.     {
  104.         while (array[i].ptr != NULL)
  105.         {
  106.             cout << (array[i].ptr)->dest << " ";
  107.             visited[i] = 1;
  108.             for (int j = 0; j < n; j++)
  109.             {
  110.  
  111.                 while (array[j].ptr != NULL)
  112.                 {
  113.                     cout << (array[j].ptr)->dest << " ";
  114.                     if (visited[array[j].v] == 1)
  115.                     {
  116.                         cout << array[i].v << " - " << array[j].v;
  117.                     }
  118.                     array[j].ptr = (array[j].ptr)->next;
  119.                 }
  120.                 cout << endl;
  121.             }
  122.  
  123.             array[i].ptr = (array[i].ptr)->next;
  124.         }
  125.         cout << endl;
  126.     }
  127.     return 1;
  128. }
  129. int main()
  130. {
  131.     int n = 6;
  132.     cout << "Number of vertices: " << n << endl;
  133.  
  134.     for (int i = 0; i < n; i++)
  135.     {
  136.         array[i].v = i;
  137.         array[i].ptr = NULL;
  138.     }
  139.     addEdge(0, 1);
  140.     addEdge(1, 2);
  141.     addEdge(1, 3);
  142.     addEdge(3, 4);
  143.     addEdge(4, 5);
  144.     addEdge(3, 5);
  145.     addEdge(5, 2);
  146.     print_graph(n);
  147.     cout << "Feedback arc Set: ";
  148.     if (checkDAG(n) == 0)
  149.         cout << " None";
  150. }

Output:

advertisement
$ g++ MakeDAG.cpp
$ a.out
 
Number of vertices: 6
Adjacency List of 0: 1 
Adjacency List of 1: 2 3 
Adjacency List of 2: 
Adjacency List of 3: 4 5 
Adjacency List of 4: 5 
Adjacency List of 5: 2 
Feedback arc Set:  None
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.