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

[Nicholas Dahm]

Moses,
I'm not sure what multiplicities means in this sense. However I simply want the 
length of the shortest path. The number of shortest paths is irrelevant for me, 
I just want the length of a shortest path.
cheers
Nick
On Thu, Jun 28, 2012 at 07:37:53AM +0300, Moses Boudourides wrote:
> 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
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Nicholas Dahm

Pattern Recognition Researcher
National ICT Australia
Brisbane, QLD, Australia
email: address@hidden

PhD Candidate
Griffith University
Brisbane, QLD, Australia
email: address@hidden