[Lemon-user] Lemon usage and cycles

[Balázs Dezső]

On Aug 1, 2012 1:51 PM, "Pierre Moulon" <pmoulon at gmail.com> wrote:
>
> Hi,
>
> I have done some experiments:
>
> I have observed that lemon::biEdgeConnected(g) with an empty graph return
true.
> Does it is normal ? (an empty graph do not have any connection, so how it
could have a biedge ?)
I was implementing this function, and it returns the result by the
following definition: "Each bi-edge-connected component of the graph is a
subset of the edges, which satisfies that every two edges in the component
is on a cycle. If no more than one component exists of the graph, then the
graph is bi-edge-connected." It could be better, to require exactly 1
component. It also not usual, that isolated nodes do not count to the
components (since the equivalence relation is defined over edges).

>
> typedef lemon::ListGraph Graph;
> Graph g;
> std::cout << lemon::biEdgeConnected(g);
>
>
> BTW, biEdgeConnectedCutEdges() seems to perform the job I need. Thanks a
lot for your tip !
>
> But I don't understand how I remove the edges and empty nodes from the
graph that the cutMap send me.
You have to use ListGraph in order to delete nodes and edges from the graph.

ListGraph g;
ListGraph::EdgeMap<bool> cutEdges(g);
...

biEdgeConnectedCutEdges(g, cutEdges);

ListGraph::EdgeIt e(g);
while (e != INVALID) {
  if (cutEdges[e]) {
    ListGraph::Edge de = e;
    ++e;
    g.erase(de);
  } else {
    ++e;
  }
}

ListGraph::NodeIt n(g);
while (n != INVALID) {
  if (ListGraph::OutArcIt(g, n) == INVALID) {  // ISOLATED
    ListGraph::Node dn = n;
    ++n;
    g.erase(dn);
  } else {
    ++n
  }
}

Other solution can be to use SubGraph.
>
> Could you give me again pointer to do that (or an example of the library)
?
>
> Sorry to be such a newbie under your great lemon library.
>
> Regards,
> Pierre
>
>
> 2012/8/1 Pierre Moulon <pmoulon at gmail.com>
>>
>> Thanks a lot I will try it ;-) and keep you updated if it fit my needs !
>>
>>
>> 2012/8/1 Balázs Dezső <deba.mf at gmail.com>
>>>
>>> Hi Pierre,
>>>
>>> I have answer for the first question. You just have to use the
biEdgeConnectedCutEdges() function, and remove the selected edges and then
the isolated nodes:
>>>
http://lemon.cs.elte.hu/pub/doc/1.2.3/a00538.html#gafc18050604b516d4583e7595c5476078
>>>
>>> It is indeed linear time algorithm. I think, your algorithm doesn't
really work, because it will keep cut edges, i.e. edges connecting two
biconnected components.
>>>
>>> Balazs
>>>
>>> On Aug 1, 2012 9:13 AM, "Pierre Moulon" <pmoulon at gmail.com> wrote:
>>>>
>>>> Hi,
>>>>
>>>> First congratulation for the great lemon library contribution.
>>>>
>>>> I have some question in order to obtain tips to realize some operation
under lemon, so I ask to the mailing list.
>>>>
>>>> 1. Considering a graph, I want to keep only the edge and nodes of the
graph that belong to cycles.
>>>>
>>>> i.e:
>>>>   _____
>>>> _|___|
>>>>   |_|_|
>>>>
>>>> Must give :
>>>>   ___
>>>>   |___|
>>>>   |_|_|
>>>>
>>>> Do you have any ideas about algorithms to realize this objective ?
>>>> Removing node with 1 connexity can work bust must be iterated since
the 1connexity is not satisfied on the graph. (iterative manner).
>>>> i.e : _.__._
>>>> Will remove the first edge and after a not cyling graph will remain.
>>>>  .__._
>>>> one more iteration
>>>> ._.
>>>> one more iteration
>>>> All edges and nodes have been removed.
>>>>
>>>> I think there can be better approach that are linear with the graph
size.
>>>>
>>>> 2. Considering this loopy graph I want select many random cycle :
>>>>
>>>> Any suggestion ?
>>>>
>>>> Thanks in advance for any help of tips ;-)
>>>>
>>>> --
>>>> Regards/Cordialement,
>>>> Pierre M
>>>>
>>>>
>>>> _______________________________________________
>>>> Lemon-user mailing list
>>>> Lemon-user at lemon.cs.elte.hu
>>>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>>>>
>>
>>
>>
>> --
>> Regards/Cordialement,
>> Pierre M
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20120803/f4fe91cf/attachment.html>