Question & Answer: Please Help fast! I need to create a function for an network. Please only create and name it as it is. For example,…..

The Function code for undirectedgraph() in JAVA is as follows:

 public UndirectedGraph(java.util.Scanner sc){
        //Scan the number of vertices in the graph
        this.v = sc.nextInt();
        this.adjMap = new HashMap<>();
        System.out.print(sc.nextLine());  //Set the scanner to the next line.

        while(sc.hasNext()){
            String input = sc.nextLine();
            StringTokenizer strToken = new StringTokenizer(input);
            int count = strToken.countTokens();

            //DEBUG
            //System.out.println(input + " " + count);

            int[] arr = new int[count];
            for(int i = 0; i < count; ++i){
                arr[i] = Integer.parseInt(strToken.nextToken());
            }

            //arr[0] is the number of the vertex
            adjMap.put(arr[0], new Vertex());
            for(int i = 1; i < count; ++i){
                adjMap.get(arr[0]).addNeighbour(arr[i]);
                //System.out.println(arr[i]);
            }
        }
        e = edges();
    }

The Full Code for Create the Undirected Graph in JAVA is Follows:

/**

Note: Please mention your package name.

*/

package graphs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.StringTokenizer;

public class UndirectedGraph implements Graph{
    /**
     * Number of vertices in the graph.
     */
    private int v;

    /**
     * Number of edges in the graph.
     */
    private int e;

    /**
     * The graph is a mapping from the 'vertex number ' to a instance 
     * of the class 'Vertex'.
     * The Vertex is a collection of 'vertex numbers ' of vertices
     * adjacent to itself.
     */
    private Map<Integer, Vertex> adjMap;

    /**
     * Construct a new undirected graph with 'n' vertices.
     * @param n The number of vertices.
     */
    public UndirectedGraph(int n){
        this.v = n;
        this.adjMap = new HashMap<>();
        for(int i = 1; i <= v; ++i){
            adjMap.put(i, new Vertex());
        }
    }

    /**
     * Construct a graph as a copy of another graph.
     * @param rhs The graph to copy.
     */
    public UndirectedGraph(UndirectedGraph rhs){
        this.v = rhs.v;
        this.e = rhs.e;
        this.adjMap = new HashMap<>();
        for(Map.Entry<Integer, Vertex> entry: rhs.adjMap.entrySet()){
            this.adjMap.put(entry.getKey(), new Vertex(entry.getValue()));
        }
    }

    /**
     * Construct a graph from a Scanner.
     * @param sc The scanner.
     */
    public UndiectedrGraph(java.util.Scanner sc){
        //Scan the number of vertices in the graph
        this.v = sc.nextInt();
        this.adjMap = new HashMap<>();
        System.out.print(sc.nextLine());  //Set the scanner to the next line.

        while(sc.hasNext()){
            String input = sc.nextLine();
            StringTokenizer strToken = new StringTokenizer(input);
            int count = strToken.countTokens();

            //DEBUG
            //System.out.println(input + " " + count);

            int[] arr = new int[count];
            for(int i = 0; i < count; ++i){
                arr[i] = Integer.parseInt(strToken.nextToken());
            }

            //arr[0] is the number of the vertex
            adjMap.put(arr[0], new Vertex());
            for(int i = 1; i < count; ++i){
                adjMap.get(arr[0]).addNeighbour(arr[i]);
                //System.out.println(arr[i]);
            }
        }
        e = edges();
    }

    /**
     * Custom Exception type which flags exceptions due to
     * improper use of 'vertex numbers '.
     */
    class NoSuchVertexException extends RuntimeException{
        public NoSuchVertexException(String no_such_vertex) {
            super(no_such_vertex);
        }
    }

    /**
     * Custom exception type which flags exception due to 
     * bad edge specifications.
     */
    class BadEdgeException extends RuntimeException{
        public BadEdgeException(String bad_edge){
            super(bad_edge);
        }
    }

    /**
     * Add a edge between Vertex v1 and Vertex v2.
     * @param v1
     * @param v2 
     */
    @Override
    public void addEdge(int v1, int v2){
        if(!hasVertex(v1) || !hasVertex(v2))
            throw new NoSuchVertexException("No such vertex!");
        adjMap.get(v1).addNeighbour(v2);
        adjMap.get(v2).addNeighbour(v1);
    }

    /**
     * Remove a edge between Vertex v1 and Vertex v2.
     * @param v1
     * @param v2 
     */
    @Override
    public void removeEdge(int v1, int v2){
        if(!edgeExists(v1, v2))
            throw new BadEdgeException("Such an edge does not exist!");
        else{
            adjMap.get(v1).removeNeighbour(v2);
            adjMap.get(v2).removeNeighbour(v1);
        }
    }

    /**
     * Count the total number of edges.
     * @return Integer specifying the total number of edges in the graph.
     */
    private int edges(){
        int total = 0;
        for(Vertex v : adjMap.values()){
            total += v.noOfNeighbours();
        }
        return total / 2;
    }

    /**
     * The number of edges in the graph.
     * @return 'e' which denotes |E| of the graph.
     */
    @Override
    public int numberOfEdges(){
        return e;
    }

    /**
     * The number of vertices in the graph.
     * @return 'v' which denotes |V| of the graph.
     */
    @Override
    public int size(){
        return v;
    }

    /**
     * Determines if a edge exists between Vertex v1 and Vertex v2.
     * @param v1    First Vertex.
     * @param v2    Second Vertex.
     * @return true/false.
     */
    @Override
    public boolean edgeExists(int v1, int v2){
        return adjMap.containsKey(v1) && adjMap.containsKey(v2) &&
                adjMap.get(v1).isNeighbour(v2) && 
                adjMap.get(v2).isNeighbour(v1);
    }

    /**
     * Determines if 'v' is a valid vertex number.
     * @param v
     * @return true/false.
     */
    @Override
    public boolean hasVertex(int v){
        return adjMap.containsKey(v);
    }

    /**
     * Contract the edge between Vertex v1 and Vertex v2.
     * Removes Vertex v2 from the graph.
     * @param v1    First Vertex.
     * @param v2    Second Vertex.
     */
    private void contractEdge(int v1, int v2){
        //System.out.println(v1 + " " + v2);
        if(!hasVertex(v1) || !hasVertex(v2))
            throw new NoSuchVertexException("Invalid vertex!");
        else if(!edgeExists(v1, v2))
            throw new BadEdgeException("Such an edge does not exist!");
        else{
            //remove all v1 from v2 and all v2 from v1.
            adjMap.get(v1).removeAll(v2);
            adjMap.get(v2).removeAll(v1);

            //append list of v2 to v1.
            adjMap.get(v1).append(adjMap.get(v2));

            //remove v2 from the map.
            adjMap.remove(v2);

            //replace all occurences of v2 with v1 in the graph.
            for(Vertex vr : adjMap.values()){
                vr.replaceAll(v1, v2);
            }

            //update v and e
            v = adjMap.size();
            e = edges();
        }
    }

    /**
     * Determine a random cut of the graph.
     * @return The number of crossing edges in the random cut.
     */
    public int Cut(){
        UndirectedGraph copy = new UndiectedrGraph(this);
        while(copy.size() > 2){
            int v1, v2;
            do{
                ArrayList<Integer> keys = new ArrayList<>(copy.adjMap.keySet());
                Random r = new Random();
                v1 = keys.get(r.nextInt(copy.size()));
                v2 = keys.get(r.nextInt(copy.size()));
            }
            while(!copy.edgeExists(v1, v2));

            copy.contractEdge(v1, v2);
        }
        return copy.numberOfEdges();
    }

    /**
     * Determine the minimum cut of the graph using Karger's algorithm.
     * @return The number of crossing edges in the minimum cut.
     */
    public int minCut(){
        int answer = this.numberOfEdges();
        System.out.println(this.size());
        for(int i = 0; i < this.size() * this.size() * 2; ++i)
            answer = Math.min(answer, this.Cut());
        return answer;
    }

    /**
     * Print the graph.
     */
    @Override
    public void print(){
        System.out.println("The Graph:- ");
        for(Map.Entry<Integer, Vertex> entry : adjMap.entrySet()){
            System.out.print(entry.getKey() + " -> ");
            for(Integer i : entry.getValue())
                System.out.print(i + " ");
            System.out.println("n");
        }
    }
}

You have to create two more java files to implement this i.e. Graph.java and Vertex.java that are as follows:

Graph.java:

package graphs;


public interface Graph {
    int numberOfEdges();
    int size();
    boolean edgeExists(int a, int b);
    boolean hasVertex(int v);
    void removeEdge(int a, int b);
    void addEdge(int a, int b);
    void print();
}

Vertex.java

package graphs;

import java.util.ArrayList;
import java.util.Iterator;

class Vertex implements Iterable<Integer>{
    /**
     * Used for search algorithms.
     */
    private boolean visited;

    /**
     * List of vertices adjacent to this vertex.
     */
    private ArrayList<Integer> neighbours;

    /**
     * No parameter constructor.
     */
    public Vertex(){
        this.visited = false;
        this.neighbours = new ArrayList<>();
    }

    /**
     * Copy a vertex.(Deep copy)
     * @param rhs The vertex to copy from.
     */
    public Vertex(Vertex rhs){
        this.visited = rhs.visited;
        this.neighbours = new ArrayList<>(rhs.neighbours);
    }

    /**
     * Check to see if the vertex is marked as visited.
     * @return true/false
     */
    public boolean isVisited(){
        return visited;
    }

    /**
     * Remove a vertex from the list of neighbor.
     * @param v The vertex to remove.
     */
    public void removeNeighbour(int v){
        this.neighbours.remove(v);
    }

    /**
     * 
     * @return The number of neighbors to this vertex.
     */
    public int noOfNeighbours(){
        return this.neighbours.size();
    }

    /**
     * Checks if 'v' is a neighbor of this vertex.
     * @param v The vertex in question.
     * @return true/false
     */
    public boolean isNeighbour(int v){
        return this.neighbours.contains(v);
    }

    /**
     * Adds a new neighbor.
     * @param v The vertex to be added.
     */
    public void addNeighbour(int v){
        this.neighbours.add(v);
    }

    /**
     * Become neighbors with all the neighbors of 'other'
     * @param other The vertex in question.
     */
    public void append(Vertex other){
        for(int i : other){
            this.neighbours.add(i);
        }
    }

    /**
     * Remove all edges with 'v'.
     * @param v
     */
    public void removeAll(int v){
        this.neighbours.removeIf(x -> x == v);
    }

    /**
     * Replace all 'v2' with 'v1'.
     * @param v1    The substitute vertex.
     * @param v2    The vertex to be substituted.
     */
    public void replaceAll(int v1, int v2){
        this.neighbours.replaceAll(x -> { if(x == v2) return v1; else return x; });
    }

    /**
     * Mark the vertex as visited.
     * @param b 
     */
    public void setVisited(boolean b){
        this.visited = b;
    }

    @Override
    public Iterator<Integer> iterator(){
        return this.neighbours.iterator();
    }
}

Java function for Find distance finddistance() is as follows:

finddistance(int a)

System.out.println(“Enter the source “);

source = a;

System.out.println(“Enter the destination “);

destination = scan.nextInt();

Dijkstras_Shortest_Path dijkstrasAlgorithm = new Dijkstras_Shortest_Path(number_of_vertices);

dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source);

System.out.println(“The Shorted Path from ” + source + ” to ” + destination + ” is: “);

for (int i = 1; i <= dijkstrasAlgorithm.distances.length – 1; i++)

{

if (i == destination)

System.out.println(source + ” to ” + i + ” is “+ dijkstrasAlgorithm.distances[i]);

}