3
\$\begingroup\$

This is the main code. Here I'm joining vertices by edges.

node[] gra=new node[5];
{
    for (int i = 0; i < 5; i++)
        gra[i] = new node(i);  //I'm allocating memory for all the vertices.
}
void add_edge(int to,int from)  //to represent the vertice the edge is going and from is now self explanatory
{
    node new_vert=new node(to); 
    node temp=gra[from];
    while(temp.next!=null)
        temp=temp.next;
    temp.next=new_vert;
}

Now to do this operation I'm using this loop in main method.

for(int i=0;i<5;i++)  //For simplicity I have taken 5 vertices
    {
        int n=sc.nextInt();                     //N is Number of edges from the vertices, for example in figure for vertex 0 the number of edges are 2.
        for(int j=0;j<n;j++)
        {
            int to=sc.nextInt();
            obj.add_edge(to,i);
        }
    }

Example graph

Is my implementation correct or efficient enough so that I can use this code for further use?

Feel free to ask if you don't understand the code; I will try to explain. I know I'm bad at explaining. And please forgive my English.

Here is my node class

    class node
{
    int data;
    node next;
    node(int data)
    {
        this.data=data;
        this.next=null;
    }
} 
\$\endgroup\$

closed as off-topic by VisualMelon, yuri, Graipher, RoToRa, Raystafarian Mar 26 at 2:13

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – yuri, RoToRa, Raystafarian
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Hi Aniket, and welcome! Could you include the code for your node class? This would be very helpful in reviewing the code. \$\endgroup\$ – Benjamin Kuykendall Mar 23 at 6:32
  • \$\begingroup\$ @BenjaminKuykendall Hi Benjamin I just updated my question you can check it again. \$\endgroup\$ – Aniket Saxena Mar 23 at 8:19
  • 1
    \$\begingroup\$ It would be great if you could also include the context in which gra and add_edge are declared (i.e. the declaration of the enclosing class), for the sake of clarity. Right now, you can only guess that gra is a field and not a local variable from the presence of a method declaration directly after it. \$\endgroup\$ – Stingy Mar 24 at 0:30
1
\$\begingroup\$

I found your code rather confusing at first, but I think I now understand your intentions behind the code, so hopefully I can say why these intentions weren't quite clear from the beginning.

The main source of confusion is that, for each adjacency list storing the neighbors of a specific vertex, the vertex this adjacency list corresponds to is represented in two ways: First, through the list's position in the array gra, and second, through the first element in the list. But the second representation is counterintuitive, because you are placing the from-vertex on the same level as the to-vertices. Using the picture you provided as an example, it would be like saying "vertex 0 has edges to the following vertices: 0, 1 and 4". It would be more to the point only to store the to-vertices in the list without the from-vertex, because the relation between the to-vertices and the from-vertex is already represented by the adjacency list's position in the array gra.

And a few words about capitalization: Even though the Java compiler does not require class names to start with a capital letter, there are certain naming conventions which, if followed, make it easier for humans to read code. One of these conventions is that class names in Java should start with a capital letter. In your case, this would mean that the class node should be renamed to Node. You can see that even the syntax highlighter doesn't recognize node as a class name if it's not capitalized:

class node {

    int data;
    node next;

    node(int data) {
        this.data=data;
        this.next=null;
    }
}

vs:

class Node {

    int data;
    Node next;

    Node(int data) {
        this.data=data;
        this.next=null;
    }
}

There are other Java conventions, like naming variables and methods in camelCase (e.g. addEdge instead of add_edge). Also, you might consider using whole words instead of abbreviations, especially if an abbreviation doesn't really save many characters (e.g. newVertex instead of newVert, or graph instead of gra). As far as I can remember, most advice in this regard I came across suggested to avoid abbrevations, and I myself also find newVertex easier to read than newVert.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the effort Stingy I really appreciate it , yesterday someone all ready pointed about that capital letter convention and hearing same again from you, I think I should change.Thanks again man for such a good answer. \$\endgroup\$ – Aniket Saxena Mar 24 at 11:09
2
\$\begingroup\$

Use Java LinkedList class

Almost always prefer built-in data structures to hand-rolled. For instance, your insertion routine takes O(n) time while LinkedList::addLast takes O(1) times.

Also, use an ArrayList instead of an array to hold the lists due to problems with generic arrays in Java.

Write a Graph class

A class offers a great opportunity to re-organize your code. It makes it easy to separate initialization and adding edges.

Correctness issues

Validate the input to addEdge. Throw an exception if either to or from is not in the appropriate range.

Style issues

  • indent and capitalize properly
  • write fewer comments: only when something need explaining
  • write shorter comments: use sentence fragments
import java.util.ArrayList;
import java.util.LinkedList;

public class Graph {
    private ArrayList<LinkedList<Integer>> adjacencyList;

    public Graph(int numberNodes) {
        adjacencyList = new ArrayList<LinkedList<Integer>>(numberNodes);
        for (int i = 0; i < numberNodes; i++) {
            adjacencyList.add(new LinkedList<Integer>());
        }
    }

    private boolean isValidNode(int index) {
        return index >= 0 && index < adjacencyList.size();
    }

    public void addEdge(int to, int from) {
        if (!isValidNode(to) || !isValidNode(from)) {
            throw new IndexOutOfBoundsException();
        }

        adjacencyList.get(from).addLast(to);
    }
}
import java.util.Scanner;

public class GraphRunner {    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        Graph g = new Graph(5);

        for(int from=0; from < 5; from++) {
            int n=sc.nextInt();
            for(int j=0; j < n; j++) {
                int to=sc.nextInt();
                g.addEdge(to, from);
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ ThankYou Benjamin for all the effort you put in reviewing my code I really appreciate it , I will definitely remember all the pointers you gave me. Love Stack Exchange community. \$\endgroup\$ – Aniket Saxena Mar 24 at 11:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.