Algorithm Jarnik-Prim

[small bison]

Hello, I have a problem to solve for my studies. Determining the shortest path of a spanning tree using the Jarnik-Prima algorithm.

I write in Java.

I already have some code, but my biggest problem is loading data from the file, because it is given in the following form:

13
2 1 5 2
1 1 3 1 13 2
2 1 4 2 11 3 12 1 13 2
3 2 5 3 11 2
1 2 4 3 6 1 8 2 11 1
5 1 7 4 11 4
6 4 8 3 12 3
5 2 7 3 10 1 11 1
11 1
8 1 11 2
3 3 4 2 5 1 6 4 8 1 9 1 10 2
3 1 7 3
2 2 3 2

• The first line of the In0304.txt file contains the number n N+ denoting the number of vertices.
• The next n lines contain a description of subsequent lists of incidents (the notation "2 1, 5 2" in the second line means that vertex 1 is connected to vertices 2 and 5 by single edges with weights 1 and 2, respectively).

Any suggestions? Thanks!

[earnest herald]

<@&987246399047479336> please have a look, thanks.

<Edge> {
Vertex source;
Vertex destination;
int weight;

public Edge(Vertex source, Vertex destination, int weight) {
    this.source = source;
    this.destination = destination;
    this.weight = weight;
}

@Override
public int compareTo(Edge other) {
    return Integer.compare(this.weight, other.weight);
}

}

class Graph {
List<Vertex> vertices = new ArrayList<>();
}

public class PrimAlgorithm {

public static void primMST(Graph graph) {
    Set<Vertex> visited = new HashSet<>();
    PriorityQueue<Edge> pq = new PriorityQueue<>();

    Vertex startVertex = graph.vertices.get(0);
    visited.add(startVertex);

    for (Edge edge : startVertex.edges) {
        pq.add(edge);
    }

    while (!pq.isEmpty()) {
        Edge minEdge = pq.poll();
        Vertex sourceVertex = minEdge.source;
        Vertex destinationVertex = minEdge.destination;

        if (!visited.contains(destinationVertex)) {
            visited.add(destinationVertex);

[earnest herald]

System.out.println("Edge: " + sourceVertex.id + " - " + destinationVertex.id + ", Weight: " + minEdge.weight);

            for (Edge edge : destinationVertex.edges) {
                if (!visited.contains(edge.destination)) {
                    pq.add(edge);
                }
            }
        }
    }
}

public static void main(String[] args) throws IOException{
    
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	int n=Integer.parseInt(br.readLine());
	Graph graph=new Graph();
	for(int i=0;i<n;i++) graph.vertices.add(new Vertex(i));
	
	int m=Integer.parseInt(br.readLine());
	for(int i=0;i<m;i++){
		StringTokenizer st=new StringTokenizer(br.readLine());
		int u=Integer.parseInt(st.nextToken()),v=Integer.parseInt(st.nextToken()),w=Integer.parseInt(st.nextToken());
		graph.vertices.get(u).edges.add(new Edge(graph.vertices.get(u),graph.vertices.get(v),w));
		graph.vertices.get(v).edges.add(new Edge(graph.vertices.get(v),graph.vertices.get(u),w));
	}
	
    primMST(graph);
}

}

[keen pivot]

share what u tried?

[small bison]

https://codeshare.io/lom3JB

Actually is problem with table index.

[earnest herald]

@small bison

Your question has been closed due to inactivity.

If it was not resolved yet, feel free to just post a message below
to reopen it, or create a new thread.

Note that usually the reason for nobody calling back is that your
question may have been not well asked and hence no one felt confident
enough answering.

When you reopen the thread, try to use your time to improve the quality
of the question by elaborating, providing details, context, all relevant code
snippets, any errors you are getting, concrete examples and perhaps also some
screenshots. Share your attempt, explain the expected results and compare
them to the current results.

Also try to make the information easily accessible by sharing code
or assignment descriptions directly on Discord, not behind a link or
PDF-file; provide some guidance for long code snippets and ensure
the code is well formatted and has syntax highlighting. Kindly read through
https://stackoverflow.com/help/how-to-ask for more.

With enough info, someone knows the answer for sure 👍

[small bison]

.

[keen pivot]

I don't understand, which vertex is connected to which and how u taking weight?
Can u explain line 4 input?

[small bison]

The first line specifies the number of vertice.

For example: The second line is the first vertex and we connect them in pairs. The first number in the pair determines the vertex, the second the weight.

4 line is vertex (3) and it's connecting with vertex (2) weight 1; (4) w. 2; (11) w. 3; (12) w. 1; (13) w. 2

You understand?

[keen pivot]

ohh gotcha, index determines one of it, got it, lemme check ur code

wait, u only need to help with input

[small bison]

I don't know, it hasn't worked, so if it works it may be good or it may be bad.

[keen pivot]

u can use bufferedReader for it, usually it gets one line as a string at a time, and u can split data using split(" ")

[small bison]

And how to replace scanner.hasNextLine()?

And scanner.nextLine().split(" ")

[keen pivot]

        List<String> input = new ArrayList<>();

        BufferedWriter put = new BufferedWriter(new OutputStreamWriter(System.out));

        try {
            br = new BufferedReader(new FileReader("input.txt"));
            String data = null;

            while((data = br.readLine()) != null)
                input.add(data);
        }
        catch (IOException ioe) {
            ioe.printStackTrace();
        }
        finally {

            try {
                if (br != null)
                    br.close();
            }
            catch (IOException ioe) {
                ioe.printStackTrace();
            }
        }```

[earnest herald]

Detected code, here are some useful tools:

[keen pivot]

This is what i use to input the data one by one in Advent of code too

it fills all the data in string form inside the "input" list from the file

later then, u can just use String[] s = list.get(i).split(" "); This means the i+1 vertex connect, s[0] with wei s[i+1] , s[i+2] with wei s[i+3] ... .like that

u can parse these to integer or however u wanna use

@small bison

[small bison]

Omg this is difficult

public class Main {
    public static void main(String[] args) throws IOException {
        // Read graph from file
        Map<Integer, Vertex> vertices = new HashMap<>();

        BufferedReader br = null;
        BufferedWriter writer = null;

        try {
            br = new BufferedReader(new FileReader("In0304.txt"));
            String data = null;

            while ((data = br.readLine()) != null) {
                String[] line = data.split(" ");
                int srcId = Integer.parseInt(line[0]);
                Vertex src = vertices.getOrDefault(srcId, new Vertex(srcId));
                vertices.put(srcId, src);
                for (int i = 1; i < line.length; i += 2) {
                    int destId = Integer.parseInt(line[i]);
                    int weight = Integer.parseInt(line[i + 1]);
                    Vertex dest = vertices.getOrDefault(destId, new Vertex(destId));
                    vertices.put(destId, dest);
                    Edge edge = new Edge(src, dest, weight);
                    src.edges.add(edge);
                    dest.edges.add(edge);
                }
            }

            // Algorithm Jarnik-Prim
            List<Edge> mst = new ArrayList<>();
            PriorityQueue<Edge> pq = new PriorityQueue<>();
            Set<Vertex> visited = new HashSet<>();
            Vertex start = vertices.values().iterator().next();
            visited.add(start);
            pq.addAll(start.edges);
            while (!pq.isEmpty()) {
                Edge minEdge = pq.poll();
                Vertex v = visited.contains(minEdge.src) ? minEdge.dest : minEdge.src;
                if (visited.add(v)) {
                    mst.add(minEdge);
                    pq.addAll(v.edges);
                }
            }

[earnest herald]

Detected code, here are some useful tools:

[small bison]

            // Write to file
            writer = new BufferedWriter(new FileWriter("Out0304.txt"));
            for (Edge edge : mst) {
                writer.write(edge.src.id + " " + edge.dest.id + " " + edge.weight + "\n");
            }
        } catch (IOException ioe) {
            ioe.printStackTrace();
        } finally {
            try {
                if (br != null)
                    br.close();
                if (writer != null)
                    writer.close();
            } catch (IOException ioe) {
                ioe.printStackTrace();
            }
        }
    }
}

[earnest herald]

Detected code, here are some useful tools:

[keen pivot]

ohh nvm gotcha

U need to think first, how its working

when u call, br.readLine(), it get u the current line and move the pointer to next line

so, every time u calling this command, u are changing lines

as u need only one variable first, try calling it out, to get that variable

and then start in while loop getting all other stuff

u need to use it according to how u want stuff to work

[small bison]

On paper, this algorithm looks trivial, but the code kills me. I'll try to do it again later.

[keen pivot]

for sure, its not an easy one to implement but not hard, so u can do it!

[small bison]

I know that if the teacher knew programming, her help would be enough. But when checking these algorithms, we have to explain it to her, because she can't check it herself, but she requires it.

[keen pivot]

imma go sleep now

[small bison]

America?

[keen pivot]

naah, was feeling sleepy so i slept in daytime 😄

[small bison]

@keen pivot I guess it worked - the result is correct, no errors.

https://codeshare.io/X8R9Ej

Could you take a look and see if there is anything you would improve in the structure of the code?
@keen pivot

[keen pivot]

great then!

[small bison]

Thanks for help @keen pivot

[keen pivot]

np, not much of help, u did all 😄

anythime tho