Java Program to Represent Graph Using Incidence Matrix

«
»
This is a java program to represent graph as a incidence list. The incidence matrix of G is a n × m matrix (b_{ij}), where n and m are the numbers of vertices and edges respectively, such that b_{ij} = 1 if the vertex v_i and edge x_j are incident and 0 otherwise.

Here is the source code of the Java Program to Represent Graph Using Incidence Matrix. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to represent graph as a incidence matrix
  2. import java.util.Scanner;
  3.  
  4. public class Represent_Graph_Incidence_Matrix 
  5. {
  6.     private final int rows;
  7.     private final int cols;
  8.     private int[][] incidence_matrix;
  9.  
  10.     public Represent_Graph_Incidence_Matrix(int v, int e) 
  11.     {
  12.         rows = v;
  13.         cols = e;
  14.         incidence_matrix = new int[rows + 1][cols + 1];
  15.     }
  16.  
  17.     public void makeEdge(int to, int from, int edge, int edge_number) 
  18.     {
  19.         try 
  20.         {
  21.             incidence_matrix[to][edge_number] = edge;
  22.             incidence_matrix[from][edge_number] = edge;
  23.         }
  24.         catch (ArrayIndexOutOfBoundsException index) 
  25.         {
  26.             System.out.println("The vertices does not exists");
  27.         }
  28.     }
  29.  
  30.     public int getEdge(int edge_number, int v) 
  31.     {
  32.         try 
  33.         {
  34.             return incidence_matrix[edge_number][v];
  35.         }
  36.         catch (ArrayIndexOutOfBoundsException index) 
  37.         {
  38.             System.out.println("The vertices does not exists");
  39.         }
  40.         return -1;
  41.     }
  42.  
  43.     public static void main(String args[]) 
  44.     {
  45.         int v, e, count = 1, to = 0, from = 0, edge_number;
  46.         Scanner sc = new Scanner(System.in);
  47.         Represent_Graph_Incidence_Matrix graph;
  48.         try 
  49.         {
  50.             System.out.println("Enter the number of vertices: ");
  51.             v = sc.nextInt();
  52.             System.out.println("Enter the number of edges: ");
  53.             e = sc.nextInt();
  54.  
  55.             graph = new Represent_Graph_Incidence_Matrix(v, e);
  56.  
  57.             System.out.println("Enter the edges: <edge_number> <to> <from>");
  58.             while (count <= e) 
  59.             {
  60.                 edge_number = sc.nextInt();
  61.                 to = sc.nextInt();
  62.                 from = sc.nextInt();
  63.  
  64.                 graph.makeEdge(to, from, 1, edge_number);
  65.                 count++;
  66.             }
  67.  
  68.             System.out.println("The incidence matrix for the given graph is: ");
  69.             System.out.print("  ");
  70.             for (int i = 1; i <= v; i++)
  71.                 System.out.print(i + " ");
  72.             System.out.println();
  73.  
  74.             for (int i = 1; i <= v; i++) 
  75.             {
  76.                 System.out.print(i + " ");
  77.                 for (int j = 1; j <= v; j++) 
  78.                     System.out.print(graph.getEdge(i, j) + " ");
  79.                 System.out.println();
  80.             }
  81.  
  82.         }
  83.         catch (Exception E) 
  84.         {
  85.             System.out.println("Somthing went wrong");
  86.         }
  87.  
  88.         sc.close();
  89.     }
  90.  
  91. }

Output:

advertisement
$ javac Represent_Graph_Incidence_Matrix.java
$ java Represent_Graph_Incidence_Matrix
 
Enter the number of vertices: 
4 
Enter the number of edges: 
5
Enter the edges: <edge_number> <to> <from>
1 1 2
2 2 3
3 3 4 
4 4 1
1 1 3
The incidence matrix for the given graph is: 
  1 2 3 4 
1 1 0 0 1 
2 1 1 0 0 
3 1 1 1 0 
4 0 0 1 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

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

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter