c++graphcomplement

Function to check if two graphs are complements


I'm trying to write a function which will take two graphs as parameters and return true if they are complement, otherwise false. I figured graphs are complement if inverse of one matches the other that's the approach I tried using. I built my function on a class and for some reason, it just doesn't let me call it from the main function. I can't even check if my function works. I tried changing the names and references, but I always get a message: Use of undeclared identifier 'is_complement'.

Here's my code:

#include <iostream>
#include <list>

using namespace std;

class Graph
{
    int num_of_vertices;
    list<int> *adj;
    void DFSrecursive (int n, bool visited[]);



public:
    Graph(int numm_of_vertices);
    void addEdge(int n, int m);
    Graph ReverseGraph();
    bool is_complement(Graph g1, Graph g2);

};

int main()
{
    //Test graph 1
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(0, 2);

    //Test graph 2
    Graph g1(4);
    g1.addEdge(0, 1);
    g1.addEdge(1, 2);
    g1.addEdge(2, 3);
    g1.addEdge(0, 2);


    cout<< is_complement(g,g1) <"\n";

    return 0;
}

Graph::Graph(int V)
{
    this->num_of_vertices = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int n, int m)
{
    adj[n].push_back(m);
    adj[m].push_back(n);
}


bool Graph::is_complement(Graph g1, Graph g2)
{
    Graph ga=g1;
    Graph gr=g2;
    bool flag=false;

    gr = ReverseGraph();

    for (int i=0; i<num_of_vertices; i++)
   {
       if (ga.adj[i]==gr.adj[i])
       {
           cout<<"Complement";
           flag=true;
       }
        else
            flag=false;
   }
    return flag;
}

//helping functions

void Graph::DFSrecursive (int n, bool visited[])
{
    visited[n] = true;
    list<int>::iterator i;
    for (i = adj[n].begin(); i != adj[n].end(); ++i)
        if (!visited[*i])
            DFSrecursive(*i, visited);
}

Graph Graph::ReverseGraph()
{
    Graph g(num_of_vertices);
    for (int v = 0; v < num_of_vertices; v++)
    {
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            g.adj[*i].push_back(v);
        }
    }
    return g;
}

Solution

  • Since is_complement is a member function of class Graph, you need to call it using dot operator from object g.

    cout<< g.is_complement(g,g1) << "\n"; should work.