Java Program to Optimize Wire Length in Electrical Circuit

«
»
This is a java program to find the optimized wire length between any two components in an electric circuits. This problem is similar to the problem of finding the shortest path between any two cities in the state. A simple Dijkstra’s algorithm would result in providing the shortest wire length between any two components in electric circuits.

Here is the source code of the Java Program to Optimize Wire Length in Electrical Circuit. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a sample program to find the minimum wire length between two component in a electrical circuits
  2. import java.util.*;
  3. class Node 
  4. {
  5.     public int label; // this node's label (parent node in path tree)
  6.     public int weight; // weight of edge to this node (distance to start)
  7.  
  8.     public Node(int v, int w) 
  9.     { 
  10.         label = v;
  11.         weight = w;
  12.     }
  13. }
  14.  
  15. public class ShortestPath 
  16. {
  17.     public static Scanner in; // for standard input
  18.     public static int n, m; // n = #vertices, m = #edges
  19.     public static LinkedList[] graph; // adjacency list representation
  20.     public static int start, end; // start and end points for shortest path
  21.  
  22.     public static void main(String[] args) 
  23.     {
  24.         in = new Scanner(System.in);
  25.  
  26.         // Input the graph:
  27.         System.out
  28.                 .println("Enter the number of components and wires in a circuit:");
  29.         n = in.nextInt();
  30.         m = in.nextInt();
  31.  
  32.         // Initialize adjacency list structure to empty lists:
  33.         graph = new LinkedList[n];
  34.         for (int i = 0; i < n; i++)
  35.             graph[i] = new LinkedList();
  36.  
  37.         // Add each edge twice, once for each endpoint:
  38.         System.out
  39.                 .println("Mention the wire between components and its length:");
  40.         for (int i = 0; i < m; i++) 
  41.         {
  42.             int v1 = in.nextInt();
  43.             int v2 = in.nextInt();
  44.             int w = in.nextInt();
  45.             graph[v1].add(new Node(v2, w));
  46.             graph[v2].add(new Node(v1, w));
  47.         }
  48.  
  49.         // Input starting and ending vertices:
  50.         System.out
  51.                 .println("Enter the start and end for which length is to be minimized: ");
  52.         start = in.nextInt();
  53.         end = in.nextInt();
  54.  
  55.         // FOR DEBUGGING ONLY:
  56.         displayGraph();
  57.  
  58.         // Print shortest path from start to end:
  59.         shortest();
  60.     }
  61.  
  62.     public static void shortest() 
  63.     {
  64.         boolean[] done = new boolean[n];
  65.         Node[] table = new Node[n];
  66.         for (int i = 0; i < n; i++)
  67.             table[i] = new Node(-1, Integer.MAX_VALUE); 
  68.  
  69.         table[start].weight = 0; 
  70.  
  71.         for (int count = 0; count < n; count++) 
  72.         {
  73.             int min = Integer.MAX_VALUE;
  74.             int minNode = -1;
  75.             for (int i = 0; i < n; i++)
  76.                 if (!done[i] && table[i].weight < min) 
  77.                 {
  78.                     min = table[i].weight;
  79.                     minNode = i;
  80.                 }
  81.  
  82.             done[minNode] = true;
  83.  
  84.             ListIterator iter = graph[minNode].listIterator();
  85.             while (iter.hasNext()) 
  86.             {
  87.                 Node nd = (Node) iter.next();
  88.                 int v = nd.label;
  89.                 int w = nd.weight;
  90.  
  91.                 if (!done[v] && table[minNode].weight + w < table[v].weight) 
  92.                 {
  93.                     table[v].weight = table[minNode].weight + w;
  94.                     table[v].label = minNode;
  95.                 }
  96.             }
  97.         }
  98.         for (int i = 0; i < n; i++) 
  99.         {
  100.             if (table[i].weight < Integer.MAX_VALUE) 
  101.             {
  102.                 System.out.print("Wire from " + i + " to " + start
  103.                         + " with length " + table[i].weight + ": ");
  104.                 int next = table[i].label;
  105.                 while (next >= 0) 
  106.                 {
  107.                     System.out.print(next + " ");
  108.                     next = table[next].label;
  109.                 }
  110.                 System.out.println();
  111.             } else
  112.                 System.out.println("No wire from " + i + " to " + start);
  113.         }
  114.     }
  115.  
  116.     public static void displayGraph() 
  117.     {
  118.         for (int i = 0; i < n; i++) 
  119.         {
  120.             System.out.print(i + ": ");
  121.             ListIterator nbrs = graph[i].listIterator(0);
  122.             while (nbrs.hasNext()) 
  123.             {
  124.                 Node nd = (Node) nbrs.next();
  125.                 System.out.print(nd.label + "(" + nd.weight + ") ");
  126.             }
  127.             System.out.println();
  128.         }
  129.     }
  130. }

Output:

advertisement
$ javac ShortestPath.java
$ java ShortestPath
Enter the number of components and wires in a circuit:
4 3 
Mention the wire between components and its length:
0 1 2 
1 3 3
1 2 2
Enter the start and end for which length is to be minimized: 
0 1
0: 1(2) 
1: 0(2) 3(3) 2(2) 
2: 1(2) 
3: 1(3) 
Wire from 0 to 0 with length 0: 
Wire from 1 to 0 with length 2: 0 
Wire from 2 to 0 with length 4: 1 0 
Wire from 3 to 0 with length 5: 1 0

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