igraph-help
[Top][All Lists]

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

 From: Nicholas Dahm Subject: Re: [igraph] Shortest circuit (distance to self) Date: Thu, 28 Jun 2012 11:23:16 +1000 User-agent: Mutt/1.5.21 (2010-09-15)

```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
> >> 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
> >>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
> >>>
> >>>
> >>>
> >>> --
> >>> Gabor Csardi <address@hidden>     MTA KFKI RMKI
> >>>
> >>> _______________________________________________
> >>> igraph-help mailing list
> >>> https://lists.nongnu.org/mailman/listinfo/igraph-help
> >>
> >> _______________________________________________
> >> igraph-help mailing list
> >> https://lists.nongnu.org/mailman/listinfo/igraph-help
> >
> >
> >
> > --
> > Gabor Csardi <address@hidden>     MTA KFKI RMKI
> >
> > _______________________________________________
> > igraph-help mailing list