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

[Moses Boudourides]

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