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

Array Problems in Java: Summation, Average, Min/Max, Searching, Sorting
Homework Solution
$13.00
Java
Programming
Coding
Computer Science
Arrays
Summation
Average
Minimum Number
Maximum Number
Bubble Sort
Selection Sort
Sequential Search
Binary Search
Algorithms
Input
Output
Methods
Integers
Functions
Matrix Problem in Java
Homework Solution
$13.00
Java
Programming
Coding
Computer Science
Matrix
Diagonals
Input File
Output File
Integers
Loops
Conditions
Statements
Swapping Numbers
Random Values
Variables
Cylinder Containers in Java
Homework Solution
$38.00
Java
Programming
Codes
Algorithms
Computer Science
Statements
Variables
Loops
Input
Output
Integers
Strings
Geometry
Mathematics
Cylinder
Radius
Finance
Costs
Containers
Companies
Functions
Builder Dash Game in Java
Homework Solution
$163.00
Java
Programming
Computer Science
Codes
Algorithms
Classes
Timers
Statements
Variables
Moves
Instances
Graphics
Animations
Parking Problem in Java
Homework Solution
$30.00
Java
Programming
Codes
Classes
Computer Science
Parking
OOP
Car Model
License Number
Owner Name
Strings
Integers
Statements
Input
Output
Constructor
Public Methods
Functions
From BS Tree to AVL Tree in Java
Homework Solution
$20.00
Java
Programming
Codes
Algorithms
Binary Search Tree
AVL Tree
Search Operation
Logarithmic Time
Rebalancing
Loops
Statements
Variables
Successors
Ancestors
Parents
Nodes
Edges
Boolean Values
Data Structures
Get help from a qualified tutor
Live Chats