r - how to find path of a cycle from an adjacency list -


i have directed subgraph nodes in cycle (with 21 nodes , ~250 edges) , want know order of how nodes form cycle.

i'm not familiar graph algorithm. thought using igraph::graph.dfs function original or reverse graph. , use order or order.out returned order, didn't work.

the subgraph connected components found igraph::clusters

i've asked similar question graph.get.subisomorphisms.vf2 takes long run in case.

i'm thinking if can ordered adjacency list this, may able find cycle starting longest list

enter image description here

but can unordered list using igraph::get.adjlist, i'd know if there's way ordered list below.

and suggestions find node order of cycle?

thanks in advance!

data

> dput(adjlist) structure(list(`26` = c(2, 3, 4, 5, 6, 7, 8, 10, 11, 15, 16,  18, 19), `2` = c(1, 3, 4, 5, 6, 7, 8, 10, 15, 16, 18), `30` = c(1,  2, 4, 5, 6, 7, 8, 10, 11, 14, 15, 16, 17, 18, 19, 21), `25` = c(1,  2, 3, 5, 6, 7, 8, 9, 10, 11, 15, 16, 18, 21), `29` = c(1, 2,  3, 4, 6, 7, 8, 9, 10, 11, 15, 16, 18, 21), `9` = c(1, 2, 3, 4,  5, 7, 8, 10, 14, 15, 16, 18, 19), `27` = c(1, 2, 3, 4, 5, 6,  8, 14, 15, 18), `13` = c(3, 4, 5, 15), `14` = c(1, 2, 3, 4, 5,  6, 7, 8, 10, 11, 14, 15, 16, 18, 19, 21), `8` = c(1, 2, 3, 4,  5, 6, 7, 8, 14, 15, 16, 18), `23` = c(1, 2, 3, 4, 5, 6, 7, 8,  10, 14, 15, 16, 17, 18, 19), `20` = c(1, 2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21), `19` = c(1, 2,  3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21),      `17` = c(1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 15, 16, 17, 18,      21), `12` = c(3, 4, 5, 6, 8), `24` = c(4, 6, 7, 8, 9, 10,      11, 15), `21` = c(13, 14), `6` = c(2, 3, 4, 5, 6, 8, 10,      15), `28` = c(1, 7, 11, 16), `15` = c(1, 2, 3, 4, 5, 6, 7,      8, 9, 10, 11, 14, 15, 16, 17, 18, 19, 21), `11` = c(3, 4,      5, 6, 8, 15)), .names = c("26", "2", "30", "25", "29", "9",  "27", "13", "14", "8", "23", "20", "19", "17", "12", "24", "21",  "6", "28", "15", "11"))

just make sure problem correctly understood: have subgraph of directed graph induced vertices of connected component. have cycle containing vertices of component. 2 possible versions (see the introductory paragraphs here clarification on confusing terminology has developed in respect):

a) each vertex allowed appear once on cycle, i.e. want simple cycle each vertex incident 2 edges of cycle. finding such cycle hamiltonian cycle problem, staple of complexity theory np-hard; no human known have efficient algorithm that.

b) vertices allowed adjacent more 2 edges of cycle, i.e. want closed walk through component. can identifying cycles connect component (you should able extract enough algorithm identifies connected components), , build eulerian cycle of union of cycles found, ignoring other edges in component. possible efficiently, , should straightforward implement.


Comments

Post a Comment

Popular posts from this blog

Email notification in google apps script -

https://support.google.com/docs/answer/91588?hl=en i have sheet the cells filled in data pulled via apps script, website. pull in exact same data, not. on old sheets version use able emails when data "changes" different value. new sheets, email when new data pasted cells, though exact same data......and, can't set @ ranges anymore, entire document. there easy way watch cells when data changes, , email myself? this looks lot you're trying do. for checking whether value has changed after edit, this gives necessary information it. hence, know whether new value same 1 or not. implementing "workaround" talked in second link, able compare , send email myself if value changed. initiate onedit trigger goes off onedit function uses these lines after checks in place have passed. var email = "xyz@whatever.com"; mailapp.sendemail(email, "triggermail", "a change has occurred in sheet"); note: sends "notification...
Read more

c++ - Difference between pre and post decrement in recursive function argument -

i have following sample code used pre-decrement void function(int c) { if(c == 0) { return; } else { cout << "dp" << c << endl; function(--c); cout << c << endl; return; } } this function give output input 4 : dp3 dp2 dp1 dp0 0 1 2 3 but when use post decrement void function(int c) { if(c == 0) { return; } else { cout << "dp" << c << endl; function(c--); cout << c << endl; return; } } output goes in infinite loop dp4 can explain me in detail why happens ? this happens because function(c--) called same value of c , when finishes c decremented. recursively called, hence called same value no chance of return , hit stack overflow error. assume this, int x = 1, y = 0; y = x++ result y == 1 , x == 2. if y = ++x , bot x , y 2.
Read more

javascript - IE11 incompatibility with jQuery's 'readonly'? -

the code i'm running has no issues in firefox, or chrome. user typing 1 textbox, tabs next , can continue typing that. when run webpage on ie11, user tabs next textbox , can't type in. textbox has double-clicked before user can insert anything. i've googled , seems ie give problems when using older jquery (i.e. prefers 'prop' 'attr' ). in code below jquery's readonly keyword being used in way ie11 no longer recognise/accept? i assume issue readonly , removeclass('ignore') working expected. //when focus on textbox 1 $("#field1").focus(function() { //remove readonly property textbox 1 $('#field1').prop('readonly', false).removeclass('ignore'); //add readonly property other textboxes $('#field2, #field3, #field4') .prop('readonly', 'readonly').addclass('ignore').val(''); }); i'm using jquery 2.1.3 ...
Read more