Question

1 - modify the given program to take a txt file as an argument
java LongestPathinDAG < inSample.txt
the txt file contains
2
5 7
1 2 7
1 3 10
2 4 8
...
The first line of input is an integer C, denoting the number of graphs. This is followed by C instances of a graph description.   The first line of a graph description is a line containing two integers, N and M.N is the number of nodes - the nodes are 1 ; 2; 3; : : : ; N - and M is the number of edges. There follow M lines describing each edge. An edge description is a line containing three integers

(the program already finding the Longest Path)
2 - modify the program to find the number of distinct paths from 1 to n that have the longest length

the output should be like this:

graph number: 1
longest path: 20
number of longest paths: 3


import java.util.Scanner;
import java.util.Vector;


class Node

{

    int name; // node ID, started from 0 to n-1

    Vector<Integer> preds; // predecessors (String)

    Vector<Integer> neibs; // neighbors (String)

    Vector<Integer> backs; // backward edges -node is end vertex (Integer)

    Vector<Integer> fors; // forward edges -node is start vertex (Integer)

    int pNode; // previous node on the augmenting path

    int pEdge; // from which edge this node comes on the augmenting

                           // path



    public Node(int id)

    {

       name = id;

       backs = new Vector<Integer>();

       fors = new Vector<Integer>();

       pNode = -1;

       pEdge = -1;

    }

}



class Edge

{

    int name;    // edge ID, started from 0 to n-1

    int start;   // start vertex of this edge

    int end;    // end vertex of this edge

    int direct; // forwards (+1) or backwards (-1) on augmenting path

                  // if 0 then not part of augmenting path

    int capacity; // capacity

    int flow;    // current flow



    public Edge(int id)

    {

       name = id;

       start = -1;

       end = -1;

       direct = 0; // default is neither

       capacity = 0;

       flow = 0;

    }



    public String toString()

    {

       return name + ": s=" + start + " e=" + end + " d=" + direct;

    }

}


public class LongestPathinDAG

{

    int n;                      // number of nodes

    int target;                // destination node

    int minLength;             // the minimal length of each path

    Node[] v;                      // used to store Nodes

    Edge[] e;                      // used to store Edges

    int[] path;                   // used to store temporary path

    int length       = 0;       // length of the path

    int distance    = 0;       // distance of the path

    int[] bestPath;               // used to store temporary path

    int bestLength   = 0;       // length of the longest path

    int bestDistance = -1000000; // distance of the longest path

    int[] visited;                // used to mark a node as visited if set as

                                    // 1


    public LongestPathinDAG()

    {

       Scanner sc = new Scanner(System.in);

       System.out.println("Enter the number of vertices: ");

       n = sc.nextInt();

       System.out.println("Enter the number of edges: ");

       int m = sc.nextInt();

       v = new Node[n];

       e = new Edge[m];

       System.out.println(n + " nodes and " + m + " edges.");

       for (int i = 0; i < n; i++)

            v[i] = new Node(i);

       int i = 0;

       while (i < e.length)

       {

            Edge edge = new Edge(i);

            int sVal = sc.nextInt();

            edge.start = sVal;// sc.nextInt();

            int eVal = sc.nextInt();

            edge.end = eVal;// sc.nextInt();

            edge.capacity = sc.nextInt();

            System.out.println(" edge: " + edge.start + " - " + edge.end

                   + " : " + edge.capacity);

            edge.flow = 0;

            e[i] = edge;

            v[sVal].fors.add(i);

            v[eVal].backs.add(i);

            i++;

            if (i == m)

                break;

       }

       visited = new int[v.length];

       path = new int[v.length];

       bestPath = new int[v.length];

       sc.close();

    }



    /*

    * this function looks for a longest path starting from being to end,

    * using the backtrack depth-first search.

    */

    public boolean findLongestPath(int begin, int end, int minLen)

    {

       /*

         * compute a longest path from begin to end

         */

       target = end;

       bestDistance = -100000000;

       minLength = minLen;

       dfsLongestPath(begin);

       if (bestDistance == -100000000)

            return false;

       else

            return true;

    }



    private void dfsLongestPath(int current)

    {

       visited[current] = 1;

       path[length++] = current;

       if (current == target && length >= minLength)

       {

            if (distance > bestDistance)

            {

                for (int i = 0; i < length; i++)

                   bestPath[i] = path[i];

                bestLength = length;

                bestDistance = distance;

            }

       }

       else

       {

            Vector<Integer> fors = v[current].fors;

            for (int i = 0; i < fors.size(); i++)

            {

                Integer edge_obj = (Integer) fors.elementAt(i);

                int edge = edge_obj.intValue();

                if (visited[e[edge].end] == 0)

                {

                   distance += e[edge].capacity;

                   dfsLongestPath(e[edge].end);

                   distance -= e[edge].capacity;

                }

            }

       }

       visited[current] = 0;

       length--;

    }



    public String toString()

    {

       String output = "v" + bestPath[0];

       for (int i = 1; i < bestLength; i++)

            output = output + " -> v" + bestPath[i];

       return output;

    }



    public static void main(String arg[])

    {

       LongestPathinDAG lp = new LongestPathinDAG();

       /*

         * find a longest path from vertex 0 to vertex n-1.

         */

       if (lp.findLongestPath(0, lp.n - 1, 1))

            System.out.println("Longest Path is " + lp

                   + " and the distance is " + lp.bestDistance);

       else

            System.out.println("No path from v0 to v" + (lp.n - 1));

       /*

         * find a longest path from vertex 3 to vertex 5.

         */

       if (lp.findLongestPath(3, 5, 1))

            System.out.println("Longest Path is " + lp

                   + " and the distance is " + lp.bestDistance);

       else

            System.out.println("No path from v3 to v5");

       /*

         * find a longest path from vertex 5 to vertex 3.

         */

       if (lp.findLongestPath(lp.n - 1, 3, 1))

            System.out.println("Longest Path is " + lp

                   + " and the distance is " + lp.bestDistance);

       else

            System.out.println("No path from v5 to v3");

    }

}

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public LongestPathsInDAG(Scanner input)
{
distancesAtTarget = new HashMap<Integer, Integer>();
n = input.nextInt();
int m = input.nextInt();
v = new Node[n];
e = new Edge[m];
for (int i = 0; i < n; i++)
v[i] = new Node(i);
int i = 0;
while (i < e.length)
{
Edge edge = new Edge(i);
int sVal = input.nextInt();
edge.start = sVal-1;// sc.nextInt();
int eVal = input.nextInt();
edge.end = eVal-1;// sc.nextInt();
edge.capacity = input.nextInt();
edge.flow = 0;
e[i] = edge;
v[sVal-1].fors.add(i);
v[eVal-1].backs.add(i);
i++;
if (i == m)
break;
}
visited = new int[v.length];
path = new int[v.length];
bestPath = new int[v.length];
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Java Programming: Stack & Queue
Homework Solution
$40.00
Programming
Java
Coding
Computer Science
Data Sets
Stack
Queue
Matrix
Circular Array
Algorithm
Duplicates
Sequences
Test Files
Random Functions
Mathematicians
Josephus Problem
Statements
Variables
Java Programming: Arrays Of Marks & Circles
Homework Solution
$50.00
Java
Programming
Codes
Computer Science
Algorithms
Arrays
Marks
Circles
Geometry
Mathematics
Radius
Random Numbers
Boundaries
Statements
Loops
Variables
Points
Coordinates
Perimeters
Area
Directed Graph in Java
Homework Solution
$40.00
Java
Programming
Codes
Algorithms
Graphs
Nodes
Edges
Dept-First-Search
Statements
Variables
Loops
Variables
Input
Output
Gradebook Using Java Programming
Homework Solution
$20.00
Java
Programming
Computer Science
Random Numbers
Scores
Students
Input
Output
Loops
Statements
Conditions
Average Values
Variables
Mathematics
Binary Tree in Java
Homework Solution
$40.00
Java
Programming
Coding
Computer Science
Binary Tree
Data
Generic Types
Functions
Variables
Recursive Methods
Nodes
Input
Output
Get help from a qualified tutor
Live Chats