Re: [igraph] making sense of is_separator()

[Gábor Csárdi]

I actually remember thinking a lot about this and that it was a
deliberate choice to do it the way it was done.

But I would need more time to dig out the reasons. Hopefully there are
some comments somewhere in the code.

Gabor

On Thu, Sep 1, 2016 at 9:12 AM, Tamas Nepusz <address@hidden> wrote:
> Aaah, good catch. There is an "optimization" in igraph_is_separator():
> when the vertex sequence that you pass to the graph has more than n-1
> unique vertices, it returns true because for some reason it considers
> a graph with a single vertex disconnected. However, this is
> inconsistent with what igraph_is_connected() says for graphs with a
> single vertex only. (And it is also inconsistent for graphs with no
> vertices at all). I'll fix it.
> T.
>
>
> On Wed, Aug 31, 2016 at 4:31 PM, Szabolcs Horvát <address@hidden> wrote:
>> It would seem that a single node graph is not considered connected by this
>> function.  However, igraph_is_connected does consider a single-node graph
>> connected (imo correctly), so this would be an inconsistency.
>>
>> On 31 August 2016 at 16:12, Szabolcs Horvát <address@hidden> wrote:
>>>
>>> Hello,
>>>
>>> What is the reasoning for the following behaviours of the is_separator()
>>> function?
>>>
>>> http://igraph.org/c/doc/igraph-Separators.html#igraph_is_separator
>>>
>>> This makes sense to me:
>>>
>>> graph: 1 - 2 - 3
>>> vertex set: {2}
>>> result: true
>>>
>>> Removing 2 does disconnect the graph.
>>>
>>> graph: 1 - 2 - 3
>>> vertex set: {3}
>>> result: false
>>>
>>> Removing 3 doesn't.
>>>
>>> graph: 1 - 2 - 3 - 4
>>> vertex set: {1, 4}
>>> result: false
>>>
>>> Removing 1 and 4 doesn't.
>>>
>>> graph: 1 - 2
>>> vertex set: {}
>>> result: false
>>>
>>> Removing nothing does not disconnect it.
>>>
>>> graph: 1, 2  (disconnected)
>>> vertex set: {}
>>> result: true
>>>
>>> Makes sense because the graph was already disconnected
>>>
>>>
>>> But I am puzzled by these:
>>>
>>> graph: 1 - 2 - 3
>>> vertex set: {1,3}
>>> result: true
>>>
>>> graph: 1 - 2
>>> vertex set: {1}
>>> result: true
>>>
>>> Removing these does not disconnect the graph, it merely leaves a 1-node
>>> graph behind.
>>>
>>> Why is the result then true?
>>>
>>>
>>> Szabolcs
>>>
>>>
>>>
>>>
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help