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

[Moses Boudourides]

Yes, of course, to find cycles of shortest length passing from a
vertex is a much weaker requirement than that of an Eulerian graph.
In any case, the formulation I'm suggesting is based on the
cardinality of classes of equivalence among edges, for a relation of
equivalence among edges defined as follows: two edges are equivalent
if they are both located on a cycle of minimal length among all cycles
passing from the the pairs of vertices to which the two edges are
incident (this definition might need a further refinement). In
particular, this means that if an edge is incident to a vertex for
which there exists no shortest cycle passing through this vertex, then
this edge is not equivalent to any other edge, i.e., the cardinality
of its equivalence class is 1 (in a simple undirected graph). At the
other end, in an Eulerian graph, the cardinality of any such
equivalence class of edges is at least 3.

However, I would appreciate if Nicholas was telling us a little more
about his original problem. Is it just the computation of shortest
cycles passing from an arbitrary vertex in a simple undirected graph?
Or what else?

Best,

--Moses

On Wed, Jun 27, 2012 at 6:33 PM, Gábor Csárdi <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help