***python*** This section of the assignment requires you to implement a method t

Question

***python***

This section of the assignment requires you to implement a method to find the girth

of a digraph. You must implement your method from first principles and cannot use an existing library method

that finds the girth.

Girth of a digraph For a digraph G, the length of the shortest cycle is called the directed girth of the graph. If the digraph has no cycle then the girth is undefined, and we will say it has girth 0. Your task is to determine the directed girth of each input digraph Input Format Input for this problem consists of a sequence of one or more digraphs taken from the keyboard (System.in). Each graph is represented by an adjacency list. The first line is an integer n indicating the order of the graph. This is followed by n white space separated lists of adjacencies for nodes labeled 0 ton- 1. The input will be terminated by a line consisting of one zero (0). This line should not be processed. Two sample input digraphs are listed below. The test cases are digraphs of order at most 30 4 1 3 2 3 0 1 2 0 OutputFormat Output will be just one integer per line sent to the console (e.g. System.out). For the above, input we would output the following two integers denoting the girth of the two graphs, using 0 to indicate the graph has no cycle 0

Explanation / Answer

Java Source Code:-
-------------------------
package com.challenges;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.Scanner;
class GreedySearch
{
public PriorityQueue<Vertex> priorityQueue;
public int heuristicvalues[];
public int numberOfNodes;
public static final int MAX_VALUE = 999;
public GreedySearch(int numberOfNodes)
{
this.numberOfNodes = numberOfNodes;
this.priorityQueue = new PriorityQueue<Vertex>(this.numberOfNodes);
}
public void Search(int adjacencyMatrix[][], int[] heuristicvalues,int source)
{
int evaluationNode;
int destinationNode;
int visited[] = new int [numberOfNodes + 1];
this.heuristicvalues = heuristicvalues;
priorityQueue.add(new Vertex(source, this.heuristicvalues[source]));
visited[source] = 1;

while (!priorityQueue.isEmpty())
{
evaluationNode = getNodeWithMinimumHeuristicValue();
destinationNode = 1;

System.out.print(evaluationNode + " ");
while (destinationNode <= numberOfNodes)
{
Vertex vertex = new Vertex(destinationNode,this.heuristicvalues[destinationNode]);
if ((adjacencyMatrix[evaluationNode][destinationNode] != MAX_VALUE
&& evaluationNode != destinationNode)&& visited[destinationNode] == 0)
{
priorityQueue.add(vertex);
visited[destinationNode] = 1;
}
destinationNode++;
}
}
}
public int getNodeWithMinimumHeuristicValue()
{
Vertex vertex = priorityQueue.remove();
return vertex.node;
}
}
public class TravellingSales
{
public int array[][]=new int[10][10];
public int completed[]=new int[10];
public int n,cost=0;
public void ReadInput()
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number of villages: ");
n=sc.nextInt();
System.out.println(" Enter the Cost Matrix");
for(int i=0;i<n;i++)
{
System.out.println(" Enter Elements of Row: "+(i+1)+" ");
for(int j=0;j < n;j++)
array[i][j]=sc.nextInt();
completed[i]=0;
}
System.out.println(" The cost of the list is:");
for(int i=0;i<n;i++)
{
System.out.println(" ");
for(int j=0;j<n;j++)
System.out.println(" "+array[i][j]);
}
sc.close();
}
public void MinimumCost(int city)
{
int i,no_ofcity;
completed[city]=1;
System.out.println((city+1)+"--->");
no_ofcity=leastpath(city);
if(no_ofcity==999)
{
no_ofcity=0;
System.out.println(no_ofcity+1);
cost=cost+array[city][no_ofcity];
return;
}
MinimumCost(no_ofcity);
}
public int leastpath(int city)
{
int nc=999;
int min=999,kmin = 0;
for(int i=0;i<n;i++)
{
if((array[city][i]!=0)&&(completed[i]==0))
if(array[city][i]+array[i][city] < min)
{
min=array[i][0]+array[city][i];
kmin=array[city][i];
nc=i;
}
}
if(min!=999)
{
cost=cost+kmin;
}
return nc;
}
public static void main(String[] args)
{
TravellingSales obj=new TravellingSales();
int adjacency_matrix[][] = { { 1, 30, 85, 70 },{ 30, 1, 55, 25 },{ 85, 55, 1, 60 },{70, 25, 60, 1 } };
int option;
int number_of_vertices=5;
int source = 0;
int heuristicvalues[];
Scanner sc=new Scanner(System.in);
System.out.println(" ------------------------------------");
System.out.println(" *** Travelling SalesMan Problem ***");
System.out.println(" ------------------------------------");
while(true)
{
System.out.println(" 1.Uniform cost search");
System.out.println(" 2.Using Greedy Search");
System.out.println(" 3.Exit");
System.out.println(" Select any option: ");
option=sc.nextInt();
switch(option)
{
case 1:
obj.ReadInput();
System.out.println(" The Path is: ");
obj.MinimumCost(0); //passing 0 because starting vertex
System.out.println(" The Minimum cost is: "+obj.cost);
break;
case 2:
try
{
heuristicvalues = new int[number_of_vertices + 1];
for(int i=1;i<=number_of_vertices;i++)
{
for (int j=1;j<=number_of_vertices;j++)
{
if(adjacency_matrix[i][j]==1 && adjacency_matrix[j][i]==0)
{
adjacency_matrix[j][i] = 1;
}
}
}
System.out.println("Enter the heuristic values of the nodes");
for (int vertex = 1;vertex<= number_of_vertices; vertex++)
{
System.out.print(vertex + ".");
heuristicvalues[vertex]=sc.nextInt();
System.out.println();
}
System.out.println("Enter the source ");
source = sc.nextInt();
System.out.println("The graph is explored as follows");
GreedySearch grredy = new GreedySearch(number_of_vertices);
grredy.Search(adjacency_matrix, heuristicvalues,source);

}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
break;
case 3:
System.exit(0);
default:
System.out.println(" !invalid Option");
}
}
}
}
class Vertex implements Comparator<Vertex>
{
public int heuristicvalue;
public int node;
public Vertex(int node, int heuristicvalue)
{
this.heuristicvalue = heuristicvalue;
this.node = node;
}
public int compare(Vertex vertex1, Vertex vertex2)
{
if (vertex1.heuristicvalue < vertex2.heuristicvalue)
return -1;
if (vertex1.heuristicvalue > vertex2.heuristicvalue)
return 1;
return 0;
}
public boolean equals(Object obj)
{
if (obj instanceof Vertex)
{
Vertex node = (Vertex) obj;
if (this.node == node.node)
{
return true;
}
}
return false;
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.