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

[Moses Boudourides]

Nick, would you count multiplicities? I mean in cases you have
multiple shortest cycles passing from a given vertex. --Moses

On Thu, Jun 28, 2012 at 4:23 AM, Nicholas Dahm <address@hidden> wrote:
> I appreciate the help guys. Let me be a little bit more clear.
>
> My work involves finding topological node "features" (characteristics of a 
> node) that can be used to define compatibilities during graph matching.
> For examle, the degree of a node should be equal in graph isomorphism with 
> it's mapped counterpart, or <= in subgraph isomorphism.
>
> The attribute I am trying to calculate here is distance-to-self. This is as 
> Gabor said, "the shortest cycle that goes through a given vertex, with each 
> edge considered at most once".
>
> I only need the length of the cycle, but I am not sure how to calculate it 
> without finding the cycle itself.
>
> cheers
>
> Nick
>
> On Wed, Jun 27, 2012 at 07:20:37PM +0300, Moses Boudourides wrote:
>> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help