Apply stream() and filter() as used in Prims to Dijkstra's algorithm. To the program below

(Help me out)

/*

Uses AtomicInteger for in_count

*/

import java.util.List;

import java.util.ArrayList;

import java.util.Dictionary;

import java.util.Hashtable;

import java.util.concurrent.atomic.AtomicInteger;

class NodeNotFoundException extends Exception

{

private String name;

public NodeNotFoundException(String name)

{

this.name = name;

}

}

//-------------------------------------------------------------

// One Node in the Graph

//

class Node

{

public Node(String name)

{

this.name = name;

}

public String name;

public boolean visited = false;

public AtomicInteger in_count = new AtomicInteger(0);

public List out_edge_list = new ArrayList<>();

public String toString(){ return name; }

}

//-------------------------------------------------------------

// A Directed Edge in the Graph

//

class Edge

{

public Edge(String name, double weight, Node from, Node to)

{

this.name = name;

this.weight = weight;

this.from = from;

this.to = to;

}

public String toString(){ return name + ": " + from + " " + to; }

public String name;

public double weight;

public Node from;

public Node to;

}

//-------------------------------------------------------------

// A Directed Graph of Nodes and Edges

//

class Graph

{

public List node_list = new ArrayList<>();

public List edge_list = new ArrayList<>();

Dictionary d_Nodes = new Hashtable<>();

//----------------------------------------------------------

// Initialize a graph (State before DFS performed)

//

public void init_graph()

{

node_list.parallelStream().forEach(n -> { n.visited = false; n.in_count.set(0); });

edge_list.parallelStream().forEach(e -> { e.to.in_count.incrementAndGet(); } );

}

//----------------------------------------------------------

// Add a new edge ( and possibly new nodes) to the graph.

//

public void add_edge(String name, double weight, String node_name_from, String node_name_to)

{

Node node_from, node_to;

if ((node_from = d_Nodes.get(node_name_from)) == null){

node_list.add(node_from = new Node(node_name_from));

d_Nodes.put(node_name_from, node_from);

}

if ((node_to = d_Nodes.get(node_name_to)) == null){

node_list.add(node_to = new Node(node_name_to));

d_Nodes.put(node_name_to, node_to);

}

Edge new_edge = new Edge(name, weight, node_from, node_to);

edge_list.add(new_edge);

node_from.out_edge_list.add(new_edge);

}

//----------------------------------------------------------

// Describe a Graph

//

public String toString()

{

String s = " Nodes --------------- ";

for(Node n : node_list)

{

s += n + " " + n.visited + " ";

}

s += " Edges --------------- ";

for(Edge e : edge_list)

{

s += e + " ";

}

return s;

}

//----------------------------------------------------------

// Depth First Search (DFS)

//

public void dfs(String node_name)

{

System.out.println(" DFS Source Node: " + node_name + " -------------------- ");

init_graph();

dfs(d_Nodes.get(node_name));

}

private void dfs(Node n)

{

System.out.println("Visiting Node " + n);

n.visited = true;

for (Edge e : n.out_edge_list)

if (e.to.visited == false)

{

System.out.println("\tFollow Edge " + e);

dfs(e.to);

System.out.println("\tReverse Edge " + e);

}

System.out.println("Backup From " + n);

}

//----------------------------------------------------------

// Topological Sort

//

public List top_sort()

{

init_graph();

List visit_list = new ArrayList<>();

Node n;

while((n = node_list.parallelStream().filter(f -> !f.visited && f.in_count.equals(0)).findFirst().orElse(null)) != null)

{

visit_list.add(n);

n.visited = true;

n.out_edge_list.parallelStream().forEach(e -> { e.to.in_count.decrementAndGet(); });

}

return visit_list;

}

//----------------------------------------------------------

// Prim

//

public void prim(String node_name)

{

System.out.println(" Prim Source Node: " + node_name + " -------------------- ");

init_graph();

d_Nodes.get(node_name).visited = true;

for(Edge e; (e = edge_list.stream()

.filter(f -> f.from.visited != f.to.visited) // edge between visited and un-visited Nodes

.min((a, b) -> (int)(a.weight - b.weight)) // of minimum weight

.orElse(null)) != null;) // null when all Nodes are visited

{

System.out.println(e); // output the edge

e.to.visited = e.from.visited = true; // Node at un-visited end of edge is now visited

}

}

//----------------------------------------------------------

// Dijkstra's Algorithm.

//

public void dijkstra(String source_name)

{

/*

Initialize all Nodes as unvisited, and all back pointers to null.

Remember to add weight and back_ptr data members to

the Node class.

set the source Node weight to 0

while (min_node = find the minimum weight unvisited Node) != null

mark min_node as visited

for each edge e outgoing from min_node to an unvisited Node

t = to Node of e

f = from Node of e

w = weight of f + weight of e

if w < weight of t

weight of t = w

back pointer of t = f

*/

}

//-------------------------------------------------------------------

// Print the names of the Nodes from destination Node to source Node.

//

public void path_rev(String dest_name)

{

}

//-------------------------------------------------------------------

// Print the names of the Nodes from source Node to destination Node.

//

public void path_fow(String dest_name)

{

}

//-------------------------------------------------------------------

// Print the names of the Nodes from source Node to Node n.

// Implement as a recursive function.

//

private void path_fow_rec(Node n)

{

/*

if n is null return

call function recursively on n back pointer

print name of Node n

*/

}

//----------------------------------------------------------

// Topological Sort - Compute all possible topological sorts

//

private List visit_list = new ArrayList<>();

private int sort_count = 0;

public void top_sort_all()

{

System.out.println("Topological Sorts ---------------------- ");

init_graph();

sort_count = 0;

top_sort_all_rec();

System.out.println("Done ");

}

private void top_sort_all_rec()

{

if(visit_list.size() == node_list.size()) // successful sort

{

System.out.print(String.format("%4d", ++sort_count) + ") ");

for(Node v : visit_list)

System.out.print(" " + v);

System.out.println();

return;

}

for(Node n : node_list) // look for next Node in sort

if(!n.visited && n.in_count.equals(0)) // found one

{

visit_list.add(n);

n.visited = true; // remove Node and outgoing Edges

n.out_edge_list.stream().forEach(e -> { e.to.in_count.decrementAndGet(); });

top_sort_all_rec(); // recursively sort

n.visited = false; // put back Node and outgoing Edges

n.out_edge_list.stream().forEach(e -> { e.to.in_count.incrementAndGet(); });

visit_list.remove(visit_list.size() - 1);

}

}

}

//-------------------------------------------------------------

// Main. Performs DFS for graph in image topo_07.png

//

class Graph_Dijkstra_B

{

public static void main(String[] args) throws Exception

{

Graph g = new Graph();

g.add_edge("14", 1.0, "1", "4");

g.add_edge("15", 1.0, "1", "5");

g.add_edge("23", 1.0, "2", "3");

g.add_edge("24", 1.0, "2", "4");

g.add_edge("34", 1.0, "3", "4");

g.add_edge("36", 1.0, "3", "6");

g.add_edge("38", 1.0, "3", "8");

g.add_edge("45", 1.0, "4", "5");

g.add_edge("57", 1.0, "5", "7");

g.add_edge("59", 1.0, "5", "9");

g.add_edge("67", 1.0, "6", "7");

g.add_edge("79", 1.0, "7", "9");

g.add_edge("89", 1.0, "8", "9");

System.out.println(g);

g.top_sort_all();

System.out.println("Top Sort (non-recursive)");

for(Node n : g.top_sort())

System.out.print(" " + n);

System.out.println();

g.dfs("1");

g = new Graph();

g.add_edge("14", 1.0, "1", "4");

g.add_edge("15", 1.0, "1", "5");

g.add_edge("23", 1.0, "2", "3");

g.add_edge("24", 1.0, "2", "4");

g.add_edge("34", 1.0, "3", "4");

g.add_edge("36", 1.0, "3", "6");

g.add_edge("38", 1.0, "3", "8");

g.add_edge("45", 1.0, "4", "5");

g.add_edge("57", 1.0, "5", "7");

g.add_edge("95", 1.0, "9", "5");

g.add_edge("67", 1.0, "6", "7");

g.add_edge("79", 1.0, "7", "9");

g.add_edge("89", 1.0, "8", "9");

System.out.println(g);

g.top_sort_all();

System.out.print(" Press Enter to Exit");

System.in.read();

}

}

/*

Nodes

---------------

1 false

4 false

5 false

2 false

3 false

6 false

8 false

7 false

9 false

Edges

---------------

14: 1 4

15: 1 5

23: 2 3

24: 2 4

34: 3 4

36: 3 6

38: 3 8

45: 4 5

57: 5 7

59: 5 9

67: 6 7

79: 7 9

89: 8 9

DFS Source Node: 1

--------------------

Visiting Node 1

Follow Edge 14: 1 4

Visiting Node 4

Follow Edge 45: 4 5

Visiting Node 5

Follow Edge 57: 5 7

Visiting Node 7

Follow Edge 79: 7 9

Visiting Node 9

Backup From 9

Reverse Edge 79: 7 9

Backup From 7

Reverse Edge 57: 5 7

Backup From 5

Reverse Edge 45: 4 5

Backup From 4

Reverse Edge 14: 1 4

Backup From 1

DFS Source Node: 2

--------------------

Visiting Node 2

Follow Edge 23: 2 3

Visiting Node 3

Follow Edge 34: 3 4

Visiting Node 4

Follow Edge 45: 4 5

Visiting Node 5

Follow Edge 57: 5 7

Visiting Node 7

Follow Edge 79: 7 9

Visiting Node 9

Backup From 9

Reverse Edge 79: 7 9

Backup From 7

Reverse Edge 57: 5 7

Backup From 5

Reverse Edge 45: 4 5

Backup From 4

Reverse Edge 34: 3 4

Follow Edge 36: 3 6

Visiting Node 6

Backup From 6

Reverse Edge 36: 3 6

Follow Edge 38: 3 8

Visiting Node 8

Backup From 8

Reverse Edge 38: 3 8

Backup From 3

Reverse Edge 23: 2 3

Backup From 2

Press Enter to Exit

*/

Answer rating: 100% (QA)

To apply stream and filter in Dijkstras algorithm you can modify the initgraph method in the Graph c... View the full answer