Posted on by Kalkicode
Code Graph

# 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.

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
``````

## 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.

Categories
Relative Post