1
$\begingroup$

It took me about a week to understand how does it works, but still, I'm wondering if it actually works!

I. The algorithm EXPLORE

EXPLORE (S:sommet, D:following vertices of vertex X, visited:TAB)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LIST ≠ 0
    selectionner i ∈ LIST
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
    ELSE LIST←LIST - {i}

II. running the algorithm

Then I tried on this Graph:

graph I tried to Explore

array of the following vertex of each vertex:

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline a & b,c,d\\ b & d,e\\ c & d,f \\ e & d,h \\ f & g,i \\ g & h, e \\ h & \emptyset\\ i & g,h \\ \end{array}

M: the visited tab L: the given list, which is empty in the beginning

Explore (a,$\Gamma$,M)

M$\leftarrow${a}

L$\leftarrow${a}

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

list $ \ \ \ \ \ \ \ $notvisited

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b}$ why do we add b to L??

$\Gamma(b) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d}$ why do we add b to L??

$$...$$

$\Gamma(e) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d,f,g,h}$ That seems normal on the aglorithm, it corresponds to

Else LIST = LIST - i

$$...$$

Until

$\Gamma(d)$

$L\leftarrow a$

which leads to the components we didn't searched for:

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,c}$ Still, wher the hell does this e comes in the algorithm?

$\Gamma(c) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a}$ I'm okay with its disparition

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ L\leftarrow {\emptyset}$ I'm okay with its disparition

III. My ideas to make it works

if ever it doesn't work!

I wonder if something is not lacking in the algorithm, if we shouldn't add an Explore within the 'if' loop.

EXPLORE (S:sommet,  Γ, visited)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LISTE ≠ 0
    selectionner i ∈ LISTE
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
      **EXPLORE(j,Γ,visited)**
    ELSE LISTE←LISTE - {i}
$\endgroup$
  • 1
    $\begingroup$ The problem with this recursion is that you will revisit nodes (LIST is a local variable, do the recursive call will start with a new, empty, one). What you can do instead is add j to LIST. $\endgroup$ – Klaus Draeger Sep 29 '15 at 9:25
  • 2
    $\begingroup$ I think you are really putting a gigantic effort into something that wasn't well-defined from the start, and you are spending much time guessing rather than being productive. As for your guess: yes, BFS / DFS would require recursion, but you would be much better off using a language can be automatically verified and executed to see if your guess is right. I've this Prolog simple DFS implementation: github.com/wvxvw/intro-to-automata-theory/blob/master/automata/… if it helps, but there are plenty of examples of DFS / BFS around. $\endgroup$ – wvxvw Sep 29 '15 at 9:27
  • $\begingroup$ Thank you very much both, I changed it a bit as @Klaus Draeger said, (adding j to LIST in the if loop) $\endgroup$ – ThePassenger Sep 29 '15 at 14:03
  • $\begingroup$ I would love to use it with a language that can be automatically verified @wvxvw but I don't know prolog. I only know VBA ( ;) )and a bit of Java... $\endgroup$ – ThePassenger Sep 29 '15 at 14:03
  • $\begingroup$ Well, you sure know how to pick them :) You might also want to take a look at Cobol... ;) anyhow, I've posted a typical bfs / dfs implementation in Java, not thoroughly tested, but hopefully reasonably correct. $\endgroup$ – wvxvw Sep 29 '15 at 17:26
0
$\begingroup$

This might be a bit too much, but I tried the best I could to condense it. Unfortunately, Java doesn't allow one to write concise code... So, here's breadth-first and depth-first traversal of a graph (I used JGraphT) library for graph implementation. This should better illustrate the idea.

package tld.se.doodles;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultDirectedGraph;

public class GraphSearch {

    public static void main(String ...args) {
        DefaultDirectedGraph<Integer, DefaultEdge> graph =
                new DefaultDirectedGraph<>(DefaultEdge.class);
        int[][] vertices = {
            {1, 2}, {1, 3}, {2, 1}, {2, 3},
            {3, 5}, {3, 6}, {3, 4}, {4, 7},
            {5, 2}, {5, 6}, {6, 3}, {6, 7}
        };
        Arrays.stream(vertices)
                .forEach(pair -> {
                        graph.addVertex(pair[0]);
                        graph.addVertex(pair[1]);
                        graph.addEdge(pair[0], pair[1]);
                    });
        depthFirstTraversal(graph);
        breadthFirstTraversal(graph);
    }

    private static void depthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Depth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        dftHashed(start, graph, cache);
    }

    private static void dftHashed(
        Integer from, DefaultDirectedGraph graph, HashSet cache) {
        if (!cache.contains(from)) {
            cache.add(from);
            System.out.format("Visiting: %d%n", from);
            graph.<DefaultEdge>edgesOf(from).stream()
                    .forEach(edge ->
                             dftHashed((Integer)graph.getEdgeTarget(edge),
                                       graph, cache));
        }
    }

    private static void breadthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Breadth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        HashSet<Integer> firstGen = new HashSet<>();
        firstGen.add(start);
        bftHashed(firstGen, graph, cache);
    }

    private static void bftHashed(
        HashSet previous, DefaultDirectedGraph graph, HashSet cache) {
        cache.addAll(previous);
        HashSet<Integer> next = (HashSet<Integer>)previous.stream()
                .flatMap(vertex -> {
                        System.out.format("Visiting: %d%n", vertex);
                        return graph.<DefaultEdge>edgesOf(vertex)
                            .stream().map(graph::getEdgeTarget);
                    })
                 .collect(Collectors.toCollection(HashSet::new));
        next.removeAll(cache);
        if (!next.isEmpty()) bftHashed(next, graph, cache);
    }
}
$\endgroup$
  • $\begingroup$ I'm trying to understand it since 2 days but I think that's a bit too dificult for me... I dont understand the dftHashed method for instance. But thank you that's very nice from you, I promise I will try to model myself my algorithm with Java. Still I'm such a newbie in compouter sciences... ;) $\endgroup$ – ThePassenger Oct 1 '15 at 23:02
  • $\begingroup$ @Marine1 in your algorithm it is not clear what LISTE is. I assumed it is the same as LIST. Second, in the recursive call, you call Explore with only two arguments, but you defined it to have three formal arguments. Also, in the recursive call j is defined but never assigned a value to, G is not defined (I think you meant D instead). I think you are missing the first argument in the recursive call, and that would have come from you looking at each vertex adjacent to S. At least I'd try to make these changes to see if it makes sense. $\endgroup$ – wvxvw Oct 2 '15 at 8:27
  • $\begingroup$ @Marine1 as for the dftHashed it is called with a vertex from a graph, the graph itself and the vertices seen so far. If the vertex has already been visited, it bails out, otherwise it visits the vertex (adds it to the cache), and for each vertex adjacent to it it executes dftHashed again. $\endgroup$ – wvxvw Oct 2 '15 at 8:31
  • $\begingroup$ okay, your first comment made me understand the algorithm, thanks. Here are some points for the time spent helping me. Make good use of it! ;) I don't perfectly understand your java code, but I'm struggling to! I now understand where they are called: from depthFirstTraversal I understand that it visit the vertex if it is not in the cache... There are the breadth search and the depth one, don't you print the result? $\endgroup$ – ThePassenger Oct 3 '15 at 16:18
  • $\begingroup$ @Marine1 right, of course I print the result, it prints nodes in the order they are visited. The functions with longer names set off the stage for the functions with shorter names to do the job recursively. This is a common thing to do, when you want a function with nice interface, i.e. to hide some additional arguments needed for recursive call. If you could run this code in, say Eclipse, you could use its debugger to set breakpoints and to examine values during execution - that together with hints for functions would help (you need JDK 1.8 for this code). $\endgroup$ – wvxvw Oct 3 '15 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.