Changing the data structure of my class to work with strings

Question

I have a working int Topological sorting class. but I need to change my methods to take string "a", "b" instead of integers, but the problem is that the methods that also count the nodes are also being used for the arraylist so I've been trying for weeks just to change or but it always says bad conversion, or cannot be converted to int, even when there isn't an int in my class(at one point) so my problem is all I want is for it to say q.addEdge("a","b"); here is my code, any help at all maybe to turn this into nodes or strings and I would be forever in your debt.

// A Java program to print topological sorting of a graph
// using indegrees
import java.util.*;

//Class to represent a graph
class Graph
{
int V;// No. of vertices

//An Array of List which contains 
//references to the Adjacency List of 
//each vertex
List <Integer> adj[];
public Graph(int V){//constructor
    this.V = V;
    adj = new ArrayList[V];
    for(int i = 0; i < V; i++)
        adj[i]=new ArrayList<Integer>();
}   
// function to add an tasks to tree
public void addEdge(int u,int v){
    adj[u].add(v);
}
// prints a Topological Sort of the complete graph  
public void topologicalSort(){
    // Create a array to store indegrees of all
    // vertices. Initialize all indegrees as 0.
    int indegree[] = new int[V];

    // Traverse adjacency lists to fill indegrees of
    // vertices. This step takes O(V+E) time        
    for(int i = 0; i < V; i++){
        ArrayList<Integer> temp = (ArrayList<Integer>) adj[i];
        for(int node : temp){
            indegree[node]++;
        }
    }

    // Create a queue and enqueue all vertices with
    // indegree 0
    Queue<Integer> q = new LinkedList<Integer>();
    for(int i = 0;i < V; i++){
        if(indegree[i]==0)
            q.add(i);
    }    
    // Initialize count of visited vertices
    int cnt = 0;
    // Create a vector to store result (A topological
    // ordering of the vertices)
    Vector <Integer> topOrder=new Vector<Integer>();
    while(!q.isEmpty()){
        // Extract front of queue (or perform dequeue)
        // and add it to topological order
        int u=q.poll();
        topOrder.add(u);
        // Iterate through all its neighbouring nodes
        // of dequeued node u and decrease their in-degree
        // by 1
        for(int node : adj[u]){
            // If in-degree becomes zero, add it to queue
            if(--indegree[node] == 0)
                q.add(node);
        }
        cnt++;
    }  
    // Check if there was a cycle       
    if(cnt != V){
        System.out.println("There exists a cycle in the graph");
        return ;
    }//else{System.out.println("no cycle in the graph");}
    // Print topological order          
    for(int i : topOrder){
        System.out.print(i+" ");
    }
 }
}
// Driver program to test above functions
class Main
{
public static void main(String args[])
{
    Graph g=new Graph(8);//must be max number of letters+1
    Node one=new Node("a");
    Node two=new Node("b");
    g.addEdge(one,two);

   /*
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(7, 5);
    g.addEdge(5, 4);
    g.addEdge(3, 4);
    g.addEdge(4, 6);
    g.addEdge(2, 4);*/
    System.out.println("Following is a Topological Sort");
    g.topologicalSort();
 }
 }

Answer 1

You could add a type to Graph, then it would support any type. For example:

class Graph<T> {
    private final Map<T, List<T>> edgesByRoot = new HashMap<>();

    public void addEdge(T a, T b){
        getEdges(a).add(b);
    }

    private List<T> getEdges(T root) {
        List<T> edges = edgesByRoot.get(root);
        if (edges == null) {
            edges = new ArrayList<>();
            edgesByRoot.put(root, edges);
        }
        return edges;
    }
}

class Main {
    public static void main(String args[]) {
        Graph<String> g=new Graph<>();
        g.addEdge("a", "b");

        System.out.println("Following is a Topological Sort");
        g.topologicalSort();
    }
}

From there, implement your topological sort to use the Map instead of an array for edge lookups via getEdges and build out a List<T>. Make sure you also use .equals instead of == where necessary, and don't use mutable types for T (String is an immutable type, so you're good there).

One other note, don't use Vector. It's exactly the same as an ArrayList but with synchronized keywords on all its methods. It's really not that useful, and it's recommended to use Collections.synchronizedList if you really need it (which your code does not since it's not multi-threaded).

References

• Generic Types Java Trail (docs.oracle.com)
• Map interface Java Trail (docs.oracle.com)
• Why is Java Vector class considered obsolete or deprecated? (StackOverflow)