Re: [igraph] Shortest circuit (distance to self)

[Gábor Csárdi]

I don't think the poster is interested in Eulerian paths. I think he
just wants the shortest cycle that goes through a given vertex, at
each edge considered at most once. If I am not mistaken.

Gabor

On Wed, Jun 27, 2012 at 11:24 AM, Moses Boudourides
<address@hidden> wrote:
> Doesn't the existence of a closed tour mean that your graph should be
> Eulerian? If so, then Euler's theorem says that this is equivalent to
> that each vertex has even degree and the set of edges is partitioned
> in cycles. If I remember well this has been solved computationally in
> the 80s by the work of Robert Tarjan, Attalah and Vishkin, essentially
> by applying the computation of Euler tours on trees in order to find
> Euler tours of general Eulerian graphs.
>
> --Moses
>
> On Wed, Jun 27, 2012 at 6:06 PM, Gábor Csárdi <address@hidden> wrote:
>> Yes, I'm afraid that you'll have to write this for yourself, there is
>> no function for it in igraph currently. There are functions for BFS in
>> igraph, however, so you could either just use them with their
>> callbacks, or modify their C code.
>>
>> Best,
>> Gabor
>>
>> On Wed, Jun 27, 2012 at 6:04 AM, Nicholas Dahm <address@hidden> wrote:
>>> Hi All,
>>>
>>> For reasons I won't get into, I wish to find the shortest path from a node 
>>> to itself, passing each edge only once in a simple undirected graph. For a 
>>> directed graph, this is easy, however on an undirected graph I see no easy 
>>> way to do this other than to write my own best-first search algorithm. My 
>>> graphs are simple (no self-edges and no more than 1 edge between 2 nodes).
>>>
>>> Any thoughts?
>>>
>>> cheers
>>>
>>> Nick
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> address@hidden
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>>
>> _______________________________________________
>> 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



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI