nested vectors & connected components of a graph

schudome13 (1)
So i am trying to count the connected components in a graph that is represented by a vector of strings, such as:

============
=====####===
=====#==##==
###==#===#==
#=#==###=#==
###====###==
============

where the equals are blank spaces and the #'s are parts of the graph. the number of connected components of this particular example would be 2.

I have a general idea of how to go about doing this, but when i compile my code, i get a segmentation fault.

I tried using a debugger on it, but all it gives is a strange error, saying:


File "/usr/local/gcc/lib/libstdc++.so.6.0.14-gdb.py", line 59, in <module>
from libstdcxx.v6.printers import register_libstdcxx_printers
File "/usr/local/gcc/lib/../share/gcc-4.5.2/python/libstdcxx/v6/printers.py", line 19, in <module>
import itertools
ImportError: ld.so.1: gdb: fatal: relocation error: file /usr/local/lib/python2.6/lib-dynload/itertools.so: symbol _Py_NoneStruct: referenced symbol not found

I have no idea what it means, or how it even comes about. it comes from the following section of code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
int CastlesandKnights::castle_count(vector<string> &image)
{
    int count = 1;
    int height = image.size();

    vector<vector<bool> > visited;

    visited.resize(height);

    for(int i = 0; i < height; i++)  // initializing the array to false
    {

        string temp = image[i];

        visited[i].resize(temp.length());
        for(int j = 0; j < temp.length(); j++)
        {
            visited[i][j] = false;
        }
    }

    for(int i = 0; i < height; i++)
    {
        string temp = image[i];
        for(int j = 0; j < temp.length(); j++)
        {
            if(temp[j] == '#')  // looks for the first piece of castle wall
            {
                if(visited[i][j] == false)
                {

                    DFS(i, j, image, visited);     // traverses the wall
                    count++;
                }
            }
            else
            {
                visited[i][j] = true;  // not a wall, so move on/
            }
        }
    }

    return count;
}


void CastlesandKnights::DFS(int i, int j, vector<string> &image,
                            vector<vector<bool> > &visited)
{
    visited[i][j] = true;
    string line = image[i];

    // 4 cases depending on which of the 4 directions needs to be followed.
    // The first if-condition is there to prevent you from walking off the edge
    // of the image or the visited array.


    if(i != 0 && image[i - 1][j] == '#' && visited[i - 1][j] == false)
    {
        DFS(i - 1, j, image, visited);
    }

    if(i != image.size() && image[i + 1][j] == '#'
       && visited[i + 1][j] == false)
    {
        DFS(i + 1, j, image, visited);
    }

    if(j != 0 && image[i][j - 1] == '#' && visited[i][j - 1] == false)
    {
        DFS(i, j - 1, image, visited);
    }

    if(j != line.length() && image[i][j + 1] == '#'
       && visited[i][j + 1] == false)
    {
        DFS(i, j + 1, image, visited);
    }

    return;
}

Any ideas what may be causing this? I have tried everything I can think of.
Last edited on
coder777 (8450)
I had a similar problem whenever I tried to step into a certain function with gdb (mingw) the debugger crashed. So I updated both the compiler and the debugger. Now it works mucch better than before
ne555 (10692)
I suppose that you compiling with debug info.
You are accessing out of bounds in DFS
1
2
 
   if(i != image.size() && image[i + 1][j] == '#'
       && visited[i + 1][j] == false)
¿what if i==image.size()-1?
Last edited on
Topic archived. No new replies allowed.