Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
connected components of vector?

Subject: connected components of vector?

From: Misha Koshelev

Date: 4 May, 2009 00:09:02

Message: 1 of 9

Hi,

I have a vector, say

a = [ 1 2 3 8 9 ];

I would like a command that will give me the vectors [ 1 2 3 ] and [ 8 9 ] in some form. Is there a command like this, especially a vectorized one? I am vectorizing a function and it seems like if I have to iterate through anyway and find the connected components I don't think my vectorization will help much... am I wrong?

Thank you
Misha

Subject: connected components of vector?

From: John D'Errico

Date: 4 May, 2009 00:30:04

Message: 2 of 9

"Misha Koshelev" <mk144210@bcm.edu> wrote in message <gtlbmu$888$1@fred.mathworks.com>...
> Hi,
>
> I have a vector, say
>
> a = [ 1 2 3 8 9 ];
>
> I would like a command that will give me the vectors [ 1 2 3 ] and [ 8 9 ] in some form. Is there a command like this, especially a vectorized one? I am vectorizing a function and it seems like if I have to iterate through anyway and find the connected components I don't think my vectorization will help much... am I wrong?
>

It seems to me that finding an algorithm for anything
requires that you define what your goal is, defining
the specific problem. So before you start, tell us
what is the characteristic of a connected component?

Does it have something to do with the difference
between successive elements? If so, compute that
difference and think about what characteristic the
difference must have for elements that are "connected".

John

Subject: connected components of vector?

From: Nasser Abbasi

Date: 4 May, 2009 00:31:22

Message: 3 of 9


"Misha Koshelev" <mk144210@bcm.edu> wrote in message
news:gtlbmu$888$1@fred.mathworks.com...
> Hi,
>
> I have a vector, say
>
> a = [ 1 2 3 8 9 ];
>
> I would like a command that will give me the vectors [ 1 2 3 ] and [ 8 9 ]
> in some form.

a = [ 1 2 3 8 9 ];

K>> a = [ 1 2 3 8 9 ];
K>> a(1:3)

     1 2 3

K>> a(4:end)

     8 9


" Is there a command like this, especially a vectorized one? I am
vectorizing a function and it seems like if I have to iterate through anyway
and find the connected components I don't think my vectorization will help
much... am I wrong?
>
> Thank you
> Misha

You are welcome

--Nasser

Subject: connected components of vector?

From: Misha Koshelev

Date: 4 May, 2009 12:45:02

Message: 4 of 9

"Misha Koshelev" <mk144210@bcm.edu> wrote in message <gtlbmu$888$1@fred.mathworks.com>...
> Hi,
>
> I have a vector, say
>
> a = [ 1 2 3 8 9 ];
>
> I would like a command that will give me the vectors [ 1 2 3 ] and [ 8 9 ] in some form. Is there a command like this, especially a vectorized one? I am vectorizing a function and it seems like if I have to iterate through anyway and find the connected components I don't think my vectorization will help much... am I wrong?
>
> Thank you
> Misha

Perhaps I was not clear. I have an arbitrary vector a. I want to find all the _largest_ vectors such that each element

[ x_1 x_2 x_3 ... x_n ]

is such that x_i = x_{i-1}

In other words, for an arbitrary vector, i would like a command that returns _all_ the vectors that are part of the original vector that match this criterion.

So, for example, for [1 2 3 8 9 10 22 23 24]

the command should return the vectors:
[1 2 3], [8 9 10], [22 23 24].

Alternately, how can I code this so it is either (a) vectorized or (b) JIT-able?

Thank you
Misha

Subject: connected components of vector?

From: John D'Errico

Date: 4 May, 2009 13:33:01

Message: 5 of 9

"Misha Koshelev" <mk144210@bcm.edu> wrote in message <gtmo0e$c40$1@fred.mathworks.com>...
> "Misha Koshelev" <mk144210@bcm.edu> wrote in message <gtlbmu$888$1@fred.mathworks.com>...
> > Hi,
> >
> > I have a vector, say
> >
> > a = [ 1 2 3 8 9 ];
> >
> > I would like a command that will give me the vectors [ 1 2 3 ] and [ 8 9 ] in some form. Is there a command like this, especially a vectorized one? I am vectorizing a function and it seems like if I have to iterate through anyway and find the connected components I don't think my vectorization will help much... am I wrong?
> >
> > Thank you
> > Misha
>
> Perhaps I was not clear. I have an arbitrary vector a. I want to find all the _largest_ vectors such that each element
>
> [ x_1 x_2 x_3 ... x_n ]
>
> is such that x_i = x_{i-1}
>
> In other words, for an arbitrary vector, i would like a command that returns _all_ the vectors that are part of the original vector that match this criterion.
>
> So, for example, for [1 2 3 8 9 10 22 23 24]
>
> the command should return the vectors:
> [1 2 3], [8 9 10], [22 23 24].
>
> Alternately, how can I code this so it is either (a) vectorized or (b) JIT-able?
>
> Thank you
> Misha

Sigh. OBVIOUSLY I was not clear either.

What characteristic of these SUBvectors are
you looking for? It is clearly NOT

   x_i == x_{i-1}

as you state, as that never happens in the
examples you give. It APPEARS to be

   x(i) == (x(i-1) + 1)

Is this the distinguishing characteristic of a
"vector", as you chose to define it?

If that is the case, what happens when you
apply diff to x?

What characteristic will you see for consecutive
elements of such a sequence that differ by
exactly 1? Can you find them?

Break your problem into smaller subproblems
that you can solve. In case I was still being
insufficiently blunt here, what does this do?

  find(diff(x)~=1)

Can you use this?

Again. Break a difficult problem into simpler,
smaller subproblems that you can solve. When
you have a problem that you are unable to solve,
carefully (and correctly) define your goal in the
problem. That definition will often contain the
solution to your problem.

John

Subject: connected components of vector?

From: Bruno Luong

Date: 4 May, 2009 15:03:02

Message: 6 of 9

This seems to be a recurrent question asked in the news group. I'll submitted in FEX to cover these questions. But here is:

a = [ 1 2 3 8 9 ]; % call unique if necessary to put a in such form

b=a-(1:length(a));
b = [true; diff(b(:))~=0; true];
split = mat2cell(a(:).',1,diff(find(b)));

split{:}

% Bruno

Subject: connected components of vector?

From: Misha Koshelev

Date: 4 May, 2009 18:33:01

Message: 7 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtn036$spf$1@fred.mathworks.com>...
> This seems to be a recurrent question asked in the news group. I'll submitted in FEX to cover these questions. But here is:
>
> a = [ 1 2 3 8 9 ]; % call unique if necessary to put a in such form
>
> b=a-(1:length(a));
> b = [true; diff(b(:))~=0; true];
> split = mat2cell(a(:).',1,diff(find(b)));
>
> split{:}
>
> % Bruno

Thank you. Very helpful. A bit cryptic but very very helpful.

Misha

Subject: connected components of vector?

From: Matt Fig

Date: 4 May, 2009 18:37:01

Message: 8 of 9

"Misha Koshelev" <mk144210@bcm.edu> wrote in message
> Thank you. Very helpful. A bit cryptic but very very helpful.
>
> Misha


Vectorized code often is cryptic! Bruno's code is actually not that bad (as far as being cryptic) compared to some snippets I have seen.

Subject: connected components of vector?

From: Misha Koshelev

Date: 5 May, 2009 17:37:01

Message: 9 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtn036$spf$1@fred.mathworks.com>...
> This seems to be a recurrent question asked in the news group. I'll submitted in FEX to cover these questions. But here is:
>
> a = [ 1 2 3 8 9 ]; % call unique if necessary to put a in such form
>
> b=a-(1:length(a));
> b = [true; diff(b(:))~=0; true];
> split = mat2cell(a(:).',1,diff(find(b)));
>
> split{:}
>
> % Bruno

Thanks again for the code.

I am iterating over the split cell array as follows:
for idx=1:numel(split)
ks=split{idx};
ks=union(ks,ks+1);
...
end

I am guessing the union here (and growing ks vector) will ruin vectorization. Idea is I need to add last element here, but I can't add it to my original vector as that will mess up how it is split and I don't know how to add it to the cell array (union doesn't seem to work). Any advice?

Thanks
Misha

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us