I have a lot of cycles ( indicated by numeric values, for example, `1-2-3-4`

corresponds to a cycle, with 4 edges, edge `1`

is `{1:2}`

, edge `2`

is `{2:3}`

, edge `3`

is `{3,4}`

, edge `4`

is `{4,1}`

, and so on).

A cycle is said to be connected to another cycle if they share one and only one edge.

For example, let's say I have two cycles `1-2-3-4`

and `5-6-7-8`

, then there are two cycle groups because these two cycles are not connecting to each other. If I have two cycles `1-2-3-4`

and `3-4-5-6`

, then I have only one cycle group because these two cycles share the same edge.

The figure below should be able to illustrate my point:

The `R1`

, `R2`

to `R7`

are what I call "cycle". In the above figure, there is only one cycle group encompassing all the `R1`

to `R7`

.

What is the most efficient way to find all the cycle groups?

I'm pretty sure, that this isn't the most efficient way, but this would be my initial attempt:

First exchange edges with vertices: So for your example cycles `1-2-3-4`

, `3-4-5-6`

and `5-6-7-8`

, you'll need:

```
"12" => "A"
"23" => "B"
"34" => "C"
"45" => "D"
"56" => "E"
"67" => "F"
"78" => "G"
"41" => "H"
"63" => "I"
"85" => "J"
```

This gives you up to (v*(v-1))/2 vertices, but okay - it may still be good enough for a O(v^2) algorithm.

Then represent the cycles as bitfields: "1-2-3-4" becomes ABCH

```
ABCDEFGHIJ
1110000100
```

and "3-4-5-6" becomes CDEI

```
ABCDEFGHIJ
0011100010
```

So they have exactly one bit in common, which means that in the original graph, they had exactly one edge in common. This could be checked either bit by bit with O(v^2), or with binary search (first check by ANDing, if they have any bit in common, then check ANDing the first half of bits etc.)

First find all the cycles in the graph and label them for example A, B, C, etc. Now make a new graph where each cycle found in the graph is converted to a single node in the new graph. Join the nodes with an edge in the new graph if the corresponding cycles are "connected" in the old graph, using your (rather unusual) definition of connected.

The number of "cycle groups" is then the number of connected components in the new graph.

Similar Questions

I have a matrix m * n and, for each row, I need to compare all elements among them. For each couple I find, I'll call a function that is going to perform some calculations. Example: my_array -> {1,

I have several radio buttons and checkboxes that all have to be grayed out. Is their a way to group them and then set the attributes for all of them on the same place? Example The QRadioButton and QCh

I have a vector of pairs representing hops between nodes which I would like to collapse when there are cycles (as in aggregate time between the hops in a cycle to display it as just one). So, for exam

How can I calculate all fields in a while? Example: I have a while, those has four rows. Every row had a specific number. What I want is, what is the total of the numbers same? while ($row= mysql_fetc

Here I have O(n^2) algorithm implemented in C++ function to determine if a string have all unique characters. bool IsUnique2(char *str) { char instr[256]; strcpy(instr,str); bool repeat = false; int i

I'm using the Yammer REST API to fetch data about messages posted in our Yammer network. I can get messages from any group by passing the group ID. But I don't know the group ID for the All Company gr

I'm having trouble understanding how compilers and linkers work and the files they create. More specifically, how do .cpp, .h, .lib, .dll, .o, .exe all work together? I am mostly interested in C++, bu

If I have an undirected graph, how can I get a list of all cycles? For example, from the following graph, I would want the cycles: (a,b,d,e,c) (a,b,c) (b,d,e)

What is the most efficient algorithm for grouping identical items together in an array, given the following: Almost all items are duplicated several times. The items are not necessarily integers or a

I'm trying to group a few class fields together without modifying any code. I realize I could create a new class which would then group them under that class name, but I don't want to do that. I have

I was given a task to do which requires a long time to do. The image say it all : This is what I have : (x100 times): And I need to extract this value only How can I capture the value ? I have ma

I'm using tabbar to define groups of files. Some are in the Emacs buffer group, others are in the Dired group and all others, ATM, are in the User buffer group. I would like to add another group

There are already a couple of questions on finding cycles, but I did not find a solution in SQL (MSSQL preferred). The tables would be Node (NodeID INT) and Edge (EdgeID INT, NodeID1 INT, NodeID2 INT)

I'm looking for a way to group similar results together. I have a table with a lot of bands images. Each images name are identified with the band's name, followed by a number. Example: Metallica 1 Met

I'm trying to speed up a query which I currently have as: SELECT * FROM `events` WHERE (field1 = 'some string' or field1 = 'some string') and is_current = true GROUP BY event_id ORDER BY pub_date thi

I try to find an quick algorithm to obtain all connected subgraphs form an undirected graph with subgraphs length restricted. Simple methods, such as BFS or DFS from every vertex generate huge amount

What is the best way to execute this query in Active Record / Ruby on Rails SELECT sum(amount) as total_amount FROM payments GROUP BY person_id, product_id I can't seem to chain sum with group method.

I want to group_concate image_id and small_pic_path path based on messageid. But group concate is showing all image_id and path to first messageid How to resolve this Without group_concate it is worki

I feel like I'm missing something basic here, and I would appreciate it if you'd help me pull it all together. Let's say that I have two view controllers... ViewAController and ViewBController. If I w

I am looking for guidance in creating an algorithm to minimize the total travel time for a group of travelers to get to a group of fixed destinations. The travelers do not all start in the same place,

id | group | text 1 | 1 | sadsd 2 | 1 | sdffs 3 | 1 | sdffs 4 | 2 | sdf 5 | 2 | sdfs 6 | 3 | sdfsdf 7 | 4 | 243 8 | 4 | dfgd How can i get with SQL all group, but only one? I would like show: group:

I'm writing a spares grid code and need to combine N 1-dimensional grid points (written in vector form) into the an array of all possible points. For example one can mix two vectors (a,b) with (c,d,e)

First off, here's my code: Sub SimulatePortfolio() Dim lambda As Double Dim num As Integer Dim cycles As Long Column = 12 q = 1.5 lambda = 0.05 cycles = 100000 Dim data(1 To 100000, 1 To 10) As Intege

In this question, I asked about the following code and retain cycles: __weak Cell *weakSelf = self; NSBlockOperation *op = [NSBlockOperation blockOperationWithBlock:^{ UIImage *image = /* render some

I have an application that uses the bluetooth to receive some data (bytes) from other device. everything is going well, but I have a small issue on receiving the bytes all together. After receiving th

I'd like to find all the posts made by users on a facebook group. I tried different things but none works. group-id/feed?limit=2000 only gives me few results, I also tried with different things, such

I'm using the backtracking algorithm described in this youtube video. Now, I should be able to get ALL possible solutions. Am I able to do this with the backtracking algoritme and how? If not possible

I am trying to combine two different tables in a select statement where all the rows in the first table are matched with all the rows in the second table. For example: Table1 Table1_ID | FKey_Table2_

I want to add a syntax group to all syntaxes. Namely, I want to highlight characters like +,-,*,/ and other punctuation chars for every programming language. I know that I can add a <language>.v

I am looking for an algorithm (optimal) for generating all possible combinations of a word. For example: Given the word love, the following would be outputted: Generated words: 24 elov elvo eolv eo

Is it possible to multiply all the columns in a Pandas.DataFrame together to get a single value for every row in the DataFrame? As an example, using df = pd.DataFrame(np.random.randn(5,3)*10) I want

Does anyone have a demo of a jQuery accordion that cycles through content automatically with an option to set the number of loops or cycles?

I have a table with more than 2 columns (let's say A, B and C). One column holds some numbers (C) and I want to do a group by like grouping, summing the numbers in C, but I don't know the algorithm

I have N number of groups of promises and I simply want to run all promises in group 1, and then when all successful, all the promises in group 2, etc up to group N. My promises are all wrapping tradi

I've always looked at the ALL keyword in the context of GROUP BY clause as really useful and meaningful. I didn't experience any performance issues when using it. MSDN documentation states that it's g

I am developing an app that creates podcasts. They are just .m4a files. However, even though I am setting the album name in the file, I cant seem to get them to group together as a podcast when I load

I am looking for an efficient algorithm which can help me to list out all the cuts in a graph. The graph is a flow network (directed graph) and has a source and a sink fixed. I want to find out what a

I may be over looking something but is there a simple way in C++ to group cases together instead of writing them out individually? I remember in basic I could just do: SELECT CASE Answer CASE 1, 2, 3,

I can get a single post data by GET /{post-id}, but how to get list of all my posts on a single group by group-id?

Given an image composed entirely of different shapes that do not move and are grouped together, how would I convert this group into an image or similar element that has this same graphic but all toget

I've seen a number of posts regarding disabling the Nagle algorithm in WCF when working on Azure. I've been wondering about if this is only applicable for Azure or if this should be a more generic bes

I have two on premise databases in my synchronization group in sql azure. When I synchronize the group manually, I see that only one of the premise database gets all the updated data and the other one

I'm stuck at the following problem: Given a weighted digraph G, I'd like to construct the minimal subgraph of G that contains all negative (simple) cycles of G. I do know how to find a negative cycle

How can I use Newton's method to find all roots of polynomial, not only unique? Link to code: http://quantcorner.wordpress.com/2012/09/14/an-implementation-of-the-newton-raphson-algorithm-in-c-cpp-and

I have searched through all of apples docs for their push service. The app I am designing sometimes pushes many notifications. These notifications are very useful if you are inside the app, because th

I am looking for an optimal algorithm to find out remaining all possible permutation of a give binary number. For ex: Binary number is : ........1. algorithm should return the remaining 2^7 remaining

I have 4 checkboxes added as a group so that I will be able to select only one checkbox. But if I select one of them and now want to uncheck all of them in a group, I am unable to do that. Any one has

Can you give me an algorithm to print all permutations of a string, with no duplicates, both recursively and iteratively?

Will Dijkstra's Algorithm work if the digraph has only one negative weight edge and does not contain negative weight cycles?

There are three field. i want check each a of field if have value, show class .koko. if on all field not have value, hide class .koko. How is it? in the this code, each field is check separate but i w