DepthFirstSearch not going over other strongly connected components | Together Java | Page 1

brisk willow Nov 22, 2023, 1:41 AM

#

hello, I need some help with a depthFirstSearch, I did it in a way so that it will start at a specific vertex, but now it is not going over the other strongly connected components. when I am printing out the results, it is not working correctly

📎 TestGraphTraversal.java 📎 Graph.java 📎 GraphTraversal.java

hearty rockBOT Nov 22, 2023, 1:41 AM

#

brisk willow hello, I need some help with a depthFirstSearch, I did it in a way so that it wi...

I uploaded your attachments as Gist.

#

<@&987246399047479336> please have a look, thanks.

hearty rockBOT Nov 22, 2023, 1:41 AM

#

brisk willow hello, I need some help with a depthFirstSearch, I did it in a way so that it wi...

#

While you are waiting for getting help, here are some tips to improve your experience:

Code is much easier to read if posted with syntax highlighting and proper formatting.

If nobody is calling back, that usually means that your question was not well asked and hence nobody feels confident enough answering. Try to use your time to elaborate, provide details, context, more code, examples and maybe some screenshots. With enough info, someone knows the answer for sure.

Don't forget to close your thread using the command </help-thread close:1027500463647621170> when your question has been answered, thanks.

#

An error has occurred while trying to communicate with ChatGPT.
Please try again later.

brisk willow Nov 22, 2023, 1:45 AM

#

also here is an example of a the full graph A B
B C
C D
D E
E F
F G
G H
H I
I J
J K
K L
L M
M N
N O
O P
P Q
Q R
R S
S T
T U
U V
V W
W X
X Y
Y Z
Z A
AA BB
BB CC
CC DD
DD EE
EE FF
FF GG
GG HH
HH II
II JJ
JJ KK
KK LL
LL MM
MM NN
NN OO
OO PP
PP QQ
QQ RR
RR SS
SS TT
TT UU
UU VV
VV WW
WW XX
XX YY
YY ZZ
ZZ AA
AAA BBB
BBB CCC
CCC DDD
DDD EEE
EEE FFF
FFF GGG
GGG HHH
HHH III
III JJJ
JJJ KKK
KKK LLL
LLL MMM
MMM NNN
NNN OOO
OOO PPP
PPP QQQ
QQQ RRR
RRR SSS
SSS TTT
TTT UUU
UUU VVV
VVV WWW
WWW XXX
XXX YYY
YYY ZZZ
ZZZ AAA

#

I want the depthFirst Search to go start at A and go through the entire graph

hearty rockBOT Nov 22, 2023, 4:30 AM

#

Graph traversal can be accomplished easily using BFS or DFS. The algorithms only differ in the order in which nodes are visited: https://i.imgur.com/n9WrkQG.png

The code to accomplish them is identical and only differs in the behavior of the Queue they are based on. BFS uses a FIFO-queue and DFS a LIFO-queue.

Queue<Node> nodesToProcess = ... // depending on BFS or DFS
nodesToProcess.add(rootNode); // add all starting nodes

Set<Node> visitedNodes = new HashSet<>();
while (!nodesToProcess.isEmpty()) {
  // Settle node
  Node currentNode = nodesToProcess.poll();
  if (!visitedNodes.add(currentNode)) {
    continue; // Already visited before
  }

  // Do something with the node
  System.out.println(currentNode); // Replace by whatever you need

  // Relax all outgoing edges
  for (Node neighbor : currentNode.getNeighbors()) {
    nodesToProcess.add(neighbor);
  }
}

To get BFS, use a FIFO-queue:

Queue<Node> nodesToProcess = new ArrayDeque<>();

And for DFS a LIFO-queue:

Queue<Node> nodesToProcess = Collections.asLifoQueue(new ArrayDeque<>());

Thats all, very simple to setup and use.

For directed graphs relax all outgoing edges.
For trees the visitedNodes logic can be dropped, since each node can only have maximally one parent, simplifying the algorithm to just:

Queue<Node> nodesToProcess = ... // depending on BFS or DFS
nodesToProcess.add(rootNode); // add all starting nodes

while (!nodesToProcess.isEmpty()) {
  // Settle node
  Node currentNode = nodesToProcess.poll();

  // Do something with the node
  System.out.println(currentNode); // Replace by whatever you need

  // Relax all outgoing edges
  for (Node child : currentNode.getChildren()) {
    nodesToProcess.add(child);
  }
}

burnt parcel Nov 22, 2023, 4:30 AM

#

Why not just use recursion instead of stack?
And If you send code with no comments, its hard to read code and takes time pepe_sad

restive pagoda Nov 22, 2023, 4:30 AM

#

You are doing something like this only kinda

#

I don't see what you are trying to do with allNeighboursVisited

#

And predecessors seems to be redundant

#

You can look at the distances to determine whether the node has been visited before or not

brisk willow Nov 22, 2023, 6:01 PM

#

Oh I have updated my DFS code, it now does go through all the dijointed parts of the graph, but it does it in an out of order

#

    // Initialize colorMap for all vertices to WHITE
    for (T vertex : graph.getVertices()) {
        colorMap.put(vertex, "WHITE");
    }

    time = 0;

    // Perform DFS for each unvisited vertex
    for (T vertex : graph.getVertices()) {
        if (colorMap.get(vertex).equals("WHITE")) {
            DFSVisit(vertex);
        }
    }

    // Check if there are more vertices not covered by the initial traversal
    for (T vertex : graph.getVertices()) {
        if (colorMap.get(vertex).equals("WHITE")) {
            DFSVisit(vertex);
        }
    }
}

public void depthFirstSearch(T startVertex) {
    // Initialize colorMap for all vertices to WHITE
    for (T vertex : graph.getVertices()) {
        colorMap.put(vertex, "WHITE");
    }

    time = 0;

    // Start DFS from the specified vertex
    DFSVisit(startVertex);

    // Check if there are more vertices not covered by the initial traversal
    for (T vertex : graph.getVertices()) {
        if (colorMap.get(vertex).equals("WHITE")) {
            DFSVisit(vertex);
        }
    }
}

private void DFSVisit(T u) {
    time = time + 1;
    discoveryTimes.put(u, time);
    colorMap.put(u, "GRAY");

    // Explore neighbors of the current vertex
    for (Edge<T> v : graph.getAdjacentVertices(u)) {
        if (colorMap.get(v.getVertex()).equals("WHITE")) {
            DFSVisit(v.getVertex());
        }
    }

    colorMap.put(u, "BLACK");
    time = time + 1;
    finishTimes.put(u, time);
    finishTimesStack.push(u);
}```

#

here whats prints it out ```java private static <T> void printDFSOutcomes(GraphTraversal<T> graphTraversal) {
// Create a list of vertices sorted by their discovery times
List<T> vertices = new ArrayList<>(graphTraversal.getDiscoveryTimes().keySet());
vertices.sort(Comparator.comparingInt(graphTraversal.getDiscoveryTimes()::get));

// Print the column headers
System.out.println("Vertex\tDiscovery\tFinish");

// Print outcomes for each vertex in the sorted order
for (T vertex : vertices) {
    System.out.println(vertex + "\t" + graphTraversal.getDiscoveryTimes().get(vertex) + "\t\t" + graphTraversal.getFinishTimes().get(vertex));
}```

}

#

here is the output

#

Vertex    Discovery    Finish
A    1        52
B    2        51
C    3        50
D    4        49
E    5        48
F    6        47
G    7        46
H    8        45
I    9        44
J    10        43
K    11        42
L    12        41
M    13        40
N    14        39
O    15        38
P    16        37
Q    17        36
R    18        35
S    19        34
T    20        33
U    21        32
V    22        31
W    23        30
X    24        29
Y    25        28
Z    26        27
HH    53        90
II    54        89
JJ    55        88
KK    56        87
LL    57        86
MM    58        85
NN    59        84
OO    60        83
PP    61        82
QQ    62        81
RR    63        80
SS    64        79
TT    65        78
UU    66        77
VV    67        76
WW    68        75
XX    69        74
YY    70        73
ZZ    71        72
DD    91        98
EE    92        97
FF    93        96
GG    94        95
BBB    99        148
CCC    100        147
DDD    101        146
EEE    102        145
FFF    103        144
GGG    104        143
HHH    105        142
III    106        141
JJJ    107        140
KKK    108        139
LLL    109        138
MMM    110        137
NNN    111        136
OOO    112        135
PPP    113        134
QQQ    114        133
RRR    115        132
SSS    116        131
TTT    117        130
UUU    118        129
VVV    119        128
WWW    120        127
XXX    121        126
YYY    122        125
ZZZ    123        124
AA    149        154
BB    150        153
CC    151        152
AAA    155        156```

#

The discovery time is weird as this is how the graph is made

#

B C
C D
D E
E F
F G
G H
H I
I J
J K
K L
L M
M N
N O
O P
P Q
Q R
R S
S T
T U
U V
V W
W X
X Y
Y Z
Z Y
AA BB
BB CC
CC DD
DD EE
EE FF
FF GG
GG HH
HH II
II JJ
JJ KK
KK LL
LL MM
MM NN
NN OO
OO PP
PP QQ
QQ RR
RR SS
SS TT
TT UU
UU VV
VV WW
WW XX
XX YY
YY ZZ
ZZ YY
AAA BBB
BBB CCC
CCC DDD
DDD EEE
EEE FFF
FFF GGG
GGG HHH
HHH III
III JJJ
JJJ KKK
KKK LLL
LLL MMM
MMM NNN
NNN OOO
OOO PPP
PPP QQQ
QQQ RRR
RRR SSS
SSS TTT
TTT UUU
UUU VVV
VVV WWW
WWW XXX
XXX YYY
YYY ZZZ
ZZZ YYY```

restive pagoda Nov 22, 2023, 6:10 PM

#

Do you want it to be an inorder traversal?

#

Usually u do a postorder traversal

brisk willow Nov 22, 2023, 6:13 PM

#

I would like to, the reason i am asking is the output results are very out of order with there finish times and discovery times, I am going to use the finish times and the depthFirstSearch to make a class to find strongly connected componenets, and I want its output to be like this Strongly Connected Components:
[A, B, C, ..., Z]
[AA, BB, CC, ..., ZZ]
[AAA, BBB, CCC, ..., ZZZ],

#DepthFirstSearch not going over other strongly connected components