Re: [igraph] making sense of is_separator()

[Tamas Nepusz]

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
>