Topological Sort using dfsOut method

[Tigerdude]

I'm working on yet another graph problem. This time, we have to sort it topologically, using a DFS Based algorithm. I've been able to write most of it down, but there is one for loop that confuses me. Our instructor did not make it very clear as to how it should loop though. As of now I have:

private static void dfsOut(Graph<City> g, int i, boolean seen[], int linearOrder[], int count)
   {
        int w = 0;
        City cTo;
        City cFrom = g.retrieveVertex(new City(i));

        seen[i] = true;
        for(w     ) {                     \\This is where I'm stuck
          if( seen[w] == false)
            dfsOut(g, w, seen, linearOrder, count);
        }
        linearOrder[count] = i;
        count--;
   }

The city variable is the vertex. Not sure I need the city variable, but at least that lets you see how I declared it :lol: This method is called from the actual Topological sort method. He did give me a line that says

For each vertex w such that there is another vertex v and there is an edge
between the two vertices.

Any help would be much appreciated ;)

[wickerman]

Hey man, I've completed that method. But, couldnd't do Adjancet & Transitive Closure Matrix well..

Also, getting probs with number of edges. Wanna share GraphTester.java?

Hahah.

[Tigerdude]

Hey man, I've completed that method. But, couldnd't do Adjancet & Transitive Closure Matrix well...

You got it completed, yet decided not to post any response as to how you got it to work, along with asking me how to get another part to work? Does that seem fair to you... :o

Anyways, I'm past the deadline for the project :sad: , but would still like to know what's going on. I ended up with this, and I know there is a lot of extra junk, I just tried so many different things and forgot to delete some of the extra. Cluttered and unprofessional I know, but that's beside the point ;) :

private static void dfsOut(Graph<City> g, int v, boolean seen[], int linearOrder[], int count) throws GraphException
   {
        if(g.isEmpty())
          throw new GraphException("Graph is empty!");;
        int w;
        int j =v  ;
        int index = (int)g.size() -1;
        City cTo = g.retrieveVertex(new City(v+1));
        City cFrom;

        seen[v] = true;
        for(w = 0; w < g.size(); w++) {
          cFrom = g.retrieveVertex(new City(w+1));
          if( g.isEdge(cTo,cFrom) && seen[w] == false)
            dfsOut(g, w, seen, linearOrder, count);
        }
        linearOrder[count] = v+1;
        count--;
   }
   
private static void topoSort(Graph<City> g, int linearOrder[]) throws GraphException
   {
        int i;
        int v;
        boolean[] seen = new boolean[(int)g.size()];
        int count = (int)g.size()-1;
        int[] index= new int[(int)g.size()];
        City c1;

        for (i = 0; i < g.size(); i++)  {
          seen[i] = false;
          index[i] = i +1;
        }

        for ( i =0; i < g.size(); i++)  {
          v = i;
          if( seen[v] == false)
            dfsOut(g,v, seen, linearOrder,count);
            if(g.isEmpty())
              throw new GraphException("Graph is Empty!");
        }
   }

And to answer at least part of your question. There should be a countEdges() function in the graph class. Just loop through each vertex, count the in degree and the out degree of each, and then divide the number by 2.

For the Adjacency matrix, you need the isEdge(cTo, cFrom) method working. From there, set up 2 for loops to iterate through the citys, and test 3 conditions: If the cities are the same, if there is an edge between the 2 cities, and if there is no edge between them.

For the Transitive matrix, you need the isReachable(cFrom, cTo) method. This can be implemented similarly to the BFS Traversal code. Just use the same setup, but you only need while(stack is not empty) to go through it.