Skip to main content

Count number of edges in an undirected graph

This is an basic problem in graph find all the edges which are connecting a two nodes in an undirected graph. Let see an example.

Count number of edges in an undirected graph

In this graph are have total 10 edges. Here given code implementation process.

//C Program 
//Count number of edges in an undirected graph
#include <stdio.h>
#include <stdlib.h>

struct AjlistNode
{
    int vId;//Vertices id
    struct AjlistNode*next;
};

struct Graph
{
    int data; //node key value
    struct AjlistNode*next;
};

void setData(struct Graph *);
int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
  if(node!=NULL && size>0)
  {
    int index=0;
    for(index;index<size;index++)
    {
        //set vertic node data
        node[index].data=index;//set node key
        //Initial no AjlistNode
        //set NULL Value
        node[index].next=NULL;
    }
  }else{
      printf("Vertic Node is Empty");
  }
}

void connectEdge(struct Graph*node, int V ,int E)
{
 
  // create Adjacency node
  struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
      sizeof(struct AjlistNode)
  );
  if(newEdge!=NULL)
  {
                  
      newEdge->next=NULL;
      newEdge->vId=E;

      struct AjlistNode *temp=node[V].next;

      if(temp==NULL)
      {
        node[V].next=newEdge;

      }else
      {
          //Add node at last
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }      
        temp->next=newEdge;          
      }
  }else
  {
    printf("\n Memory overflow");
  }
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
    if(V<size && E <size)
    {
        if(V==E)
        {
          //self loop
          connectEdge(node,V,E);
          return;
        }
      connectEdge(node,V,E);
      connectEdge(node,E,V);

    }else
    {
      //not valid Vertices
      printf("Invalid Node Vertices %d  %d", V,E);
    }
}

//Display Adjacency list of vertex
void printGraph(struct Graph*node)
{
    if(node!=NULL)
    {
      struct AjlistNode *temp=NULL;
      for(int index=0; index < size; index++)
      {
        printf("\n Adjacency list of vertex %d  :",index);
        temp=node[index].next;
        while(temp!=NULL)
        {
            //temp->vId is graph node vertices
            //in this case temp->vId is same as 
            //node[temp->vId].data
            
            printf("  %d",node[temp->vId].data);
            temp=temp->next;
        }
      }
    }else
    {
      printf("Empty Graph");
    }
}
//Count number of edges
void countEdge(struct Graph*node)
{
    if(node!=NULL)
    {
      struct AjlistNode *temp=NULL;

      int counter=0,self_loop=0;

      for(int index=0;index<size;index++)
      {
        
        temp=node[index].next;
        while(temp!=NULL)
        {
          if(temp->vId==index)
          {
            //when self loop
            self_loop++;
          }else
          {
             counter++; 
          }
          //counter edge
          temp=temp->next;
        }
      }
      printf("\nTotal Edges : %d\n",(counter/2)+self_loop );
    }else
    {
        printf("Empty Graph");
    }
}

int main()
{
    
    size=6;

    struct Graph*node=(struct Graph*)malloc( 
      sizeof(struct Graph)*size );
    
    if(node==NULL)
    {
      printf("\n Memory overflow");

    }
    else
    {
        //First set node keys
        setData(node); 
        //Connected two node with Edges

        addEdge(node,0,1);
        addEdge(node,0,3);
        addEdge(node,0,5);
        addEdge(node,1,4);
        addEdge(node,1,5);
        addEdge(node,2,3);
        addEdge(node,3,5);
        addEdge(node,4,4);
        addEdge(node,4,5);
        addEdge(node,5,5);
        printGraph(node);
        countEdge(node);
    }  


  return 0;
}

Output

 Adjacency list of vertex 0  :  1  3  5
 Adjacency list of vertex 1  :  0  4  5
 Adjacency list of vertex 2  :  3
 Adjacency list of vertex 3  :  0  2  5
 Adjacency list of vertex 4  :  1  4  5
 Adjacency list of vertex 5  :  0  1  3  4  5
Total Edges : 10

//C++ program
//Count number of edges in an undirected graph
#include<iostream>
using namespace std;

struct AjlistNode
{
    int vId;//Vertices id
    struct AjlistNode*next;
};

struct Vertices
{
    int data; //node key value
    struct AjlistNode*next;
};

class Graph
{
    Vertices *node;
    int size;//number of 
public:
    Graph(int);
    void setData();
    void addEdge(int,int);
    void printGraph();
    void countEdge();
};
Graph::Graph(int size)
{
    this->size = size;
    //set number of nodes
    node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
    if(node!=NULL)
    {
        int index=0;

        for(index;index<size;index++)
        {
			//set vertic node data
			node[index].data=index;//set node key
			//Initial no AjlistNode
			//set NULL Value
			node[index].next=NULL;
    	}
  	}
  	else
  	{
    	cout<<"Vertic Node is Empty"<<endl;
  	}
}
//Add Edge from Two given Nodes
void Graph ::addEdge(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
    if(V<size && E <size)
    {
        //Add first node
        AjlistNode *newEdge=new AjlistNode;
        if(newEdge!=NULL)
        {
            newEdge->next=node[V].next;
            newEdge->vId=E;
            node[V].next=newEdge;
        }
        if(V==E)
        {   //self loop
        	return;
        }
        //add second node
        newEdge=new AjlistNode;
        if(newEdge!=NULL)
        {
            newEdge->next=node[E].next;
            newEdge->vId=V;
            node[E].next=newEdge;
        }

    }else
    {
        //not valid Vertices
        cout<<"Invalid Node Vertices "<< V<<" "<<E;
    }
}
//Display Adjacency list of vertex
void Graph::printGraph()
{
    if(node!=NULL)
    {
        AjlistNode *temp=NULL;
        for(int index=0; index < size; index++)
        {
            cout<<"\n Adjacency list of vertex "<<index<<" :";
            temp=node[index].next;
            while(temp!=NULL)
            {
                //temp->vId is graph node vertices
                //in this case temp->vId is same as 
                //node[temp->vId].data
                
                cout<<" "<<node[temp->vId].data;
                temp=temp->next;
            }
        }
    }else
    {
        cout<<"Empty Graph"<<endl;
    }
}

//Count number of edges
void Graph:: countEdge()
{
    if(node!=NULL)
    {
      AjlistNode *temp=NULL;

      int counter=0,self_loop=0;

      for(int index=0;index<size;index++)
      {
        
        temp=node[index].next;
        while(temp!=NULL)
        {
          if(temp->vId==index)
          {
            //when self loop
            self_loop++;
          }else
          {
             counter++; 
          }
          //counter edge
          temp=temp->next;
        }
      }
     cout<<"\n Total Edges : "<< (counter/2)+self_loop ;
    }else
    {
        cout<<"Empty Graph";
    }
}

int main()
{
    //Create Object
    Graph g(6);
     //First set node keys
    g.setData();


    g.addEdge(0,1);
    g.addEdge(0,3);
    g.addEdge(0,5);
    g.addEdge(1,4);
    g.addEdge(1,5);
    g.addEdge(2,3);
    g.addEdge(3,5);
    g.addEdge(4,4);
    g.addEdge(4,5);
    g.addEdge(5,5);
    g.printGraph();
    g.countEdge();
    return 0;
}

Output

 Adjacency list of vertex 0 : 5 3 1
 Adjacency list of vertex 1 : 5 4 0
 Adjacency list of vertex 2 : 3
 Adjacency list of vertex 3 : 5 2 0
 Adjacency list of vertex 4 : 5 4 1
 Adjacency list of vertex 5 : 5 4 3 1 0
 Total Edges : 10
//Java program
//Count number of edges in an undirected graph
public class MyGraph
{

    static class AjlistNode
    {
        int id;//Vertices node key
        AjlistNode next;
    }
    static class Vertices
    {
        int data;
        AjlistNode next;
    }

    //number of Vertices
    static int size;
    Vertices node[];

    MyGraph(int size)
    {
        //set value
        this.size = size;
        node = new Vertices[size];
    }

    //set initial node value
    public void setData()
    {
        if(node == null)
        {
            System.out.println("\nEmpty Graph");
        }else
        {
            for(int index = 0; index < size; index++)
            {
                // avoid java.lang.nullPointerException
                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null;
            }
        }
    }

    public void addEdge(int S,int E)
    {
        if(S < size && E < size && node != null)
        {
            AjlistNode newEdge=new AjlistNode();
            newEdge.id=E;//end node
            newEdge.next=node[S].next;
            node[S].next=newEdge;
            
            //self loop
            if(S == E) return;

            newEdge = new AjlistNode();
            newEdge.id = S;//end node
            newEdge.next=node[E].next;
            node[E].next=newEdge;

        }else
        {
            System.out.println("\nEmpty Graph");
        }
    }

    public void printGraph()
    {

        if(size>0&&node!=null)
        {
            for(int index=0;index<size;index++)
            {
                System.out.print("\nAdjacency list of vertex "+index+" :");
                
                AjlistNode temp=node[index].next;

                while(temp!=null)
                {
                    System.out.print(" "+node[temp.id].data);

                    temp=temp.next;
                }
            }
        }
    }
    //Count number of edges
    public void  countEdge()
    {
        if(node != null)
        {
          AjlistNode  temp=null;

          int counter=0,self_loop=0;

          for(int index = 0;index < size; index++)
          {
            
            temp=node[index].next;
            while(temp != null)
            {
              if(temp.id==index)
              {
                //when self loop
                self_loop++;
              }else
              {
                 counter++; 
              }
              //counter edge
              temp=temp.next;
            }
          }
          System.out.println("\nTotal Edges : "+ ((counter/2)+self_loop));
         
        }else
        {
            System.out.println("Empty Graph");
        }
    }
    public static void main(String[] args) 
    {
        int totalNode=6;
        
        MyGraph g=new MyGraph(totalNode);
        g.setData();
        //Connected two node with Edges

        g.addEdge(0,1);
        g.addEdge(0,3);
        g.addEdge(0,5);
        g.addEdge(1,4);
        g.addEdge(1,5);
        g.addEdge(2,3);
        g.addEdge(3,5);
        g.addEdge(4,4);
        g.addEdge(4,5);
        g.addEdge(5,5);
        g.printGraph();
        g.countEdge();

    }
}

Output

Adjacency list of vertex 0 : 5 3 1
Adjacency list of vertex 1 : 5 4 0
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 5 2 0
Adjacency list of vertex 4 : 5 4 1
Adjacency list of vertex 5 : 5 4 3 1 0
Total Edges : 10

#Python program
#Count number of edges in an undirected graph
class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[];

  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1

  def addEdge(self,S,E):

    #S and E is two nodes
    if(self.size>S and self.size>E):
      #first
      new_edge=AjLinkeNode(E)
      new_edge.next=self.node[S].next
      self.node[S].next=new_edge

      if(S==E):
        return #self loop
      #second
      new_edge=AjLinkeNode(S)
      new_edge.next=self.node[E].next
      self.node[E].next=new_edge
    else:
      print("Invalid nodes")

  def printGraph(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):

        print("\nAdjacency list of vertex  {0} :".format(index),end=" ")
        
        temp=self.node[index].next
        
        while temp!=None:

          print("  {0}".format(temp.id),end=" ")

          temp=temp.next

        index+=1

  #Count number of edges
  def countEdge(self):

    if(self.node != None):
      temp=None

      counter=0
      self_loop=0
      index = 0
      
      while(index < self.size):
        
        temp = self.node[index].next;

        while(temp != None) :

          if(temp.id == index):

            #when self loop
            self_loop += 1

          else:
            counter += 1
          #counter edge
          temp=temp.next

        index += 1
        
      
      print("\nTotal Edges : ", (int(counter/2)+self_loop))
     
    else :
      print("Empty Graph")
        
    
def main():
  g=Graph(6)
  g.setData(); 
  #Connected two node with Edges
  g.addEdge(0,1);
  g.addEdge(0,3);
  g.addEdge(0,5);
  g.addEdge(1,4);
  g.addEdge(1,5);
  g.addEdge(2,3);
  g.addEdge(3,5);
  g.addEdge(4,4);
  g.addEdge(4,5);
  g.addEdge(5,5);
  g.printGraph();
  g.countEdge();

if __name__=="__main__":
    main()

Output

Adjacency list of vertex  0 :   5   3   1 
Adjacency list of vertex  1 :   5   4   0 
Adjacency list of vertex  2 :   3 
Adjacency list of vertex  3 :   5   2   0 
Adjacency list of vertex  4 :   5   4   1 
Adjacency list of vertex  5 :   5   4   3   1   0 
Total Edges :  10

//C# Graph 
//Count number of edges in an undirected graph
using System;
class AjlistNode
{
	public int key;
	public AjlistNode next;
	public AjlistNode(int key)
	{
		this.key=key;
		this.next=null;
	}
}
class Node
{
	public int data;
	public AjlistNode next;
	public Node(int data)
	{
		this.data=data;
		this.next=null;

	}
}
class MyGraph
{
	//empty array
	public Node[]node= new Node[] {};
	public int size;
	public MyGraph(int size)
	{
		this.size=size;
		node=new Node[size];
	}
	public void setData()
	{
		if(size>0 && this.node!=null)
		{
			for(int index=0;index<size;index++)
			{
				node[index]=new Node(index);
			}

		}
	}
	public void addEdge(int start,int end)
	{
		if(this.size>start && this.size>end)
		{
			AjlistNode newEdge=new AjlistNode(end);
			newEdge.next=node[start].next;
			node[start].next=newEdge;
			if (start == end)
				return;
			newEdge=new AjlistNode(start);
			newEdge.next=node[end].next;
			node[end].next=newEdge;
		}
	}
	public void printGraph()
	{
		if(size>0 && node.Length>0 && node!=null)
		{
			for(int index=0;index<size;index++)
			{
				Console.Write("\nAdjacency list of vertex {0} :",index);
				AjlistNode temp=node[index].next;
				while(temp!=null)
				{
					Console.Write(" "+node[temp.key].data);
						temp=temp.next;
			    }
			}
		}
	}
	//Count number of edges
	public void  countEdge()
	{
		if(node != null)
		{
			AjlistNode  temp=null;

			int counter=0,self_loop=0;

			for(int index = 0;index < size; index++)
			{

				temp=node[index].next;
				while(temp != null)
				{
					if(temp.key==index)
					{
						//when self loop
						self_loop++;
					}else
					{
						counter++; 
					}
					//counter edge
					temp=temp.next;
				}
			}
			Console.WriteLine("\nTotal Edges : {0}", ((counter/2)+self_loop));

		}else
		{
			Console.WriteLine("Empty Graph");
		}
	}

}
class Program
{

	static void Main(string[] args)
	{
		//create object
		MyGraph g=new MyGraph(6);
		g.setData();
		//Connected two node with Edges

		g.addEdge(0,1);
		g.addEdge(0,3);
		g.addEdge(0,5);
		g.addEdge(1,4);
		g.addEdge(1,5);
		g.addEdge(2,3);
		g.addEdge(3,5);
		g.addEdge(4,4);
		g.addEdge(4,5);
		g.addEdge(5,5);
		g.printGraph();
		g.countEdge();
	}
}

Output

Adjacency list of vertex 0 : 5 3 1
Adjacency list of vertex 1 : 5 4 0
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 5 2 0
Adjacency list of vertex 4 : 5 4 1
Adjacency list of vertex 5 : 5 4 3 1 0
Total Edges : 10

<?php 
/*
* PHP Program 
* Count number of edges in an undirected graph
*/

class AjlistNode
{
  public $key;
  public $next;
  function __construct($key)
  {
    $this->key=$key;
    $this->next=NULL;
}
}
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data=$data;
    $this->next=NULL;

}
}
class MyGraph
{

    public $node;
    public $size;
    function __construct($size)
    {
        $this->size=$size;
        $this->node=[];  //empty array
    }
    public function setData()
    {
        if($this->size>0)
        {
            for($index=0;$index<$this->size;$index++)
            {
                $this->node[$index]=new Node($index);
            }

        }
    }
    public function addEdge($start,$end)
    {
        if($this->size>$start && $this->size>$end)
        {
            //first
            $newEdge=new AjlistNode($end);
            $newEdge->next=$this->node[$start]->next;
            $this->node[$start]->next=$newEdge;
            if($start == $end)
            {
                return;
            }
            //second
            $newEdge=new AjlistNode($start);
            $newEdge->next=$this->node[$end]->next;
            $this->node[$end]->next=$newEdge;
        }
    }
    public function printGraph()
    {
        if($this->size>0 && count($this->node)>0 && $this->node!=NULL)
        {
            for($index=0;$index<$this->size;$index++)
            {
                echo ("\nAdjacency list of vertex ".$index." : ");
                $temp=$this->node[$index]->next;
                while($temp!=NULL)
                {
                    echo (" ".$this->node[$temp->key]->data);
                    $temp=$temp->next;
                }
            }
        }
    }
    //Count number of edges
    public function  countEdge()
    {   

        if($this->node!=NULL)
        {
            $temp=NULL;

            $counter=0;
            $self_loop=0;

            for($index=0;$index < $this->size;$index++)
            { 
                $temp=$this->node[$index]->next;
                while($temp!=NULL)
                {
                    if($temp->key==$index)
                    {
                        //when self loop
                        $self_loop++;
                    }else
                    {
                        $counter++; 
                    }
                    //counter edge
                    $temp=$temp->next;
                }
            }
            echo ("\nTotal Edges : ".(($counter/2)+$self_loop) ."\n");
        }else
        {
            echo ("Empty Graph\n");
        }
    }

}


function main()
{
    //create object
    $g=new MyGraph(6);
    $g->setData();

    //Connected two node with Edges
    $g->addEdge(0,1);
    $g->addEdge(0,3);
    $g->addEdge(0,5);
    $g->addEdge(1,4);
    $g->addEdge(1,5);
    $g->addEdge(2,3);
    $g->addEdge(3,5);
    $g->addEdge(4,4);
    $g->addEdge(4,5);
    $g->addEdge(5,5);
    $g->printGraph();
    $g->countEdge();

}
main();
?>

Output

Adjacency list of vertex 0 :  5 3 1
Adjacency list of vertex 1 :  5 4 0
Adjacency list of vertex 2 :  3
Adjacency list of vertex 3 :  5 2 0
Adjacency list of vertex 4 :  5 4 1
Adjacency list of vertex 5 :  5 4 3 1 0
Total Edges : 10
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment