Returning highest weighted edge in an Adjacency List

Question

I'm trying to solve a practice question, writing a function that return the highest weighted edge from a directed weighted graph, represented as adjacency list.

Since I have just finished this topic recently in my course, there is some confusion for me about the above question, so I really appreciate any help. First the function should return an "edge", but how I return an edge that is represented by object refrences to each other? In other words, I found the highest weight but I didn't know what to return, Also what if there's two vertices both directed to each other with same distance - same weight-?

Here is the code with example graph, I returned D4 as the longest destination to go to which is 110:

Class ListNode

public class ListNode {

protected int destination;
protected float wt;
protected ListNode next;

public ListNode(int destination) {
    this.destination = destination;
}

public void addToSL(ListNode header, ListNode node) {
    if (header == null)
        return;
    else {
        ListNode trav = header;
        while (trav.next != null) {
            trav = trav.next;
        }

        trav.next = node;
        node.next = null;
    }
}
}

Class Adjacency

public class Adjacency {

protected int lastAdded_index_w = -1;// for array of adjacency list
protected ListNode directList_W[];
public void createNewDirectGraphList_w(int numberOfvertices) // w means weighted graph
{
    this.directList_W = new ListNode[numberOfvertices]; //size is number of vertices
}

public void addVerticesToList_W(ListNode node)
{
    // adding all vertices to the adjacency list
    this.directList_W[lastAdded_index_w+1] = node;
    lastAdded_index_w++;
}

public void addAdjacencyVertices(ListNode v, ListNode adjV)
{
   // adding adjacency vertex adj to the linked list of vertex v
        v.addToSL(v, adjV);

}

public ListNode getHighestWeightedEdge(ListNode[] graph)
{
    ListNode highest = graph[0].next;
    for(int i=0; i < this.directList_W.length; i++)
    {
        ListNode trav = this.directList_W[i].next;
        while(trav!=null)
        {
            if(trav.wt >= highest.wt)
                highest = trav;
            trav = trav.next;
        }
    }

    return highest;

}

main class public class main {

public static void main(String[] args) {

Adjacency mat = new Adjacency(3);

 /*   
                 "Both direction"
            *D1-----"30km"-------------*D2
             |  \                       /
 "both"      |   \                     /
 "direction" |    \ "both direction"  /                
             |     \                 /
             |      \"90km"         /"110km" "one direction from D2 to D4"
       "20km"|       \             /
             |        \           /
             D3        \---*D4---/

        */

        // calling method to create graph adjacency list
        mat.createNewDirectGraphList_w(4); 

        // Creating vertices to connect "destination 1" with others.
        ListNode D1 = new ListNode(1);
        ListNode D2 = new ListNode(2);
        ListNode D3 = new ListNode(3);
        ListNode D4 = new ListNode(4);

        mat.addVerticesToList_W(D1);
        mat.addVerticesToList_W(D2);
        mat.addVerticesToList_W(D3);
        mat.addVerticesToList_W(D4);
  // parameter takes name of destinationm type int.
        ListNode D2_fromD1 = new ListNode(2); 
        D2_fromD1.wt = 30;
        ListNode D4_fromD1 = new ListNode(4);
        D4_fromD1.wt = 90;
        ListNode D3_fromD1 = new ListNode(3);
        D3_fromD1.wt = 20;

        // adding first destination and its adjacency vertices.
        mat.addAdjacencyVertices(D1, D2_fromD1); 
        mat.addAdjacencyVertices(D1, D3_fromD1);
        mat.addAdjacencyVertices(D1, D4_fromD1);

        // Creating vertices to connect "destination 2" with others.
        ListNode D4_FromD2 = new ListNode(4);
        D4_FromD2.wt= 110;
        ListNode D1_FromD2 = new ListNode(1);
        D1_FromD2.wt = 30;
        // adding second destination and its adjacency vertices.
        mat.addAdjacencyVertices(D2, D4_FromD2);
        mat.addAdjacencyVertices(D2, D1_FromD2);

        // Creating vertices to connect "destination 3" with others.
        ListNode D1_FromD3 = new ListNode(1);
        D1_FromD3.wt = 20;
        // adding second destination and its adjacency vertices.
        mat.addAdjacencyVertices(D3, D1_FromD3);

        // Creating vertices to connect "destination 3" with others.
        ListNode D1_FromD4 = new ListNode(1);
        D1_FromD4.wt = 90;
        // adding second destination and its adjacency vertices.
        mat.addAdjacencyVertices(D4, D1_FromD4);

       // saving the adjacency list array.
        ListNode weightedDirectedGraph [] = mat.directList_W; 

        // calling method to return highest weighted edge
        ListNode highestWeighted =    mat.getHighestWeightedEdge
                                       (weightedDirectedGraph);    

        System.out.println("Longest distenation in the 
        following destinations- D1, D2, D3, D4- \n"+
        "D"+highestWeighted.destination + "  " + highestWeighted.wt);
 }
    }

Console Output:

Longest distenation in the following destinations- D1, D2, D3, D4- 

D4  110.0

Answer 1

There are many options:

• You could add a pointer back to the header to the ListNode class, turning it into a full edge representation.
• You could change your representation to have dedicated Vertex and Edge classes.
• You could return a node pair (e.g. an ListNode array of size 2) containing the ListNode representing the start edge and the ListNode representing the weight and destination as a result.