{"algorithm":"condensation","about":["A strongly connected component is a group of vertices that can all reach each other. The condensation replaces each one with a single vertex, and all the edges from one component to another with a single edge. A cycle never leaves its component, so the condensed graph has none.","connectivity.Condense runs Tarjan once and numbers the components so that every edge between two of them goes from a lower number to a higher one, which is a topological order. The members of each component keep the graph's vertex order, and Members and ComponentOf map between the two graphs. It costs O(V+E).","WithComponentWeight gives each component a weight from its members, such as the sum of their weights, and WithCrossingWeight gives each condensed edge a weight from the edges it stands for. A build tool does this with packages that import each other: each loop is built as one unit, and the units are sorted like any other dependency graph."],"template":{"id":"web-crawl","name":"Web crawl","description":"A hundred pages on ten sites that a crawler reached by following links, P1 to P100, where P stands for page. Pages are numbered site by site: an encyclopedia (P1 to P16), news (P17 to P30), a city (P31 to P37), a university (P38 to P46), a link directory (P47 to P52), docs (P53 to P62), a forum (P63 to P74), videos (P75 to P82), a blog (P83 to P90) and a shop (P91 to P100). Each edge counts the links from one page to another. The docs, shop and city sites never link back, and no page links to the directory.","family":"cyclic","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"P1","x":479,"y":511},{"id":"P2","x":506,"y":465},{"id":"P3","x":519,"y":542},{"id":"P4","x":444,"y":481},{"id":"P5","x":556,"y":475},{"id":"P6","x":468,"y":564},{"id":"P7","x":474,"y":427},{"id":"P8","x":568,"y":541},{"id":"P9","x":412,"y":519},{"id":"P10","x":550,"y":424},{"id":"P11","x":510,"y":596},{"id":"P12","x":419,"y":435},{"id":"P13","x":603,"y":495},{"id":"P14","x":420,"y":578},{"id":"P15","x":502,"y":386},{"id":"P16","x":573,"y":590},{"id":"P17","x":264,"y":830},{"id":"P18","x":240,"y":782},{"id":"P19","x":311,"y":814},{"id":"P20","x":219,"y":843},{"id":"P21","x":276,"y":747},{"id":"P22","x":301,"y":869},{"id":"P23","x":191,"y":788},{"id":"P24","x":337,"y":772},{"id":"P25","x":233,"y":891},{"id":"P26","x":230,"y":723},{"id":"P27","x":351,"y":851},{"id":"P28","x":167,"y":838},{"id":"P29","x":318,"y":718},{"id":"P30","x":286,"y":917},{"id":"P31","x":127,"y":590},{"id":"P32","x":82,"y":560},{"id":"P33","x":160,"y":552},{"id":"P34","x":94,"y":623},{"id":"P35","x":96,"y":512},{"id":"P36","x":178,"y":605},{"id":"P37","x":43,"y":591},{"id":"P38","x":171,"y":332},{"id":"P39","x":119,"y":316},{"id":"P40","x":192,"y":287},{"id":"P41","x":148,"y":373},{"id":"P42","x":119,"y":265},{"id":"P43","x":224,"y":333},{"id":"P44","x":90,"y":355},{"id":"P45","x":180,"y":239},{"id":"P46","x":192,"y":396},{"id":"P47","x":289,"y":121},{"id":"P48","x":334,"y":113},{"id":"P49","x":364,"y":149},{"id":"P50","x":347,"y":192},{"id":"P51","x":302,"y":200},{"id":"P52","x":272,"y":164},{"id":"P53","x":527,"y":121},{"id":"P54","x":569,"y":86},{"id":"P55","x":554,"y":163},{"id":"P56","x":505,"y":80},{"id":"P57","x":611,"y":114},{"id":"P58","x":498,"y":166},{"id":"P59","x":551,"y":40},{"id":"P60","x":600,"y":179},{"id":"P61","x":461,"y":104},{"id":"P62","x":623,"y":64},{"id":"P63","x":792,"y":236},{"id":"P64","x":829,"y":275},{"id":"P65","x":751,"y":266},{"id":"P66","x":831,"y":211},{"id":"P67","x":805,"y":319},{"id":"P68","x":745,"y":210},{"id":"P69","x":874,"y":254},{"id":"P70","x":739,"y":313},{"id":"P71","x":803,"y":169},{"id":"P72","x":856,"y":328},{"id":"P73","x":702,"y":242},{"id":"P74","x":882,"y":200},{"id":"P75","x":867,"y":532},{"id":"P76","x":891,"y":483},{"id":"P77","x":908,"y":560},{"id":"P78","x":830,"y":504},{"id":"P79","x":940,"y":491},{"id":"P80","x":859,"y":585},{"id":"P81","x":856,"y":448},{"id":"P82","x":957,"y":555},{"id":"P83","x":805,"y":767},{"id":"P84","x":751,"y":769},{"id":"P85","x":809,"y":717},{"id":"P86","x":798,"y":812},{"id":"P87","x":733,"y":722},{"id":"P88","x":855,"y":748},{"id":"P89","x":737,"y":817},{"id":"P90","x":782,"y":676},{"id":"P91","x":567,"y":872},{"id":"P92","x":540,"y":919},{"id":"P93","x":527,"y":842},{"id":"P94","x":602,"y":902},{"id":"P95","x":491,"y":909},{"id":"P96","x":578,"y":819},{"id":"P97","x":573,"y":956},{"id":"P98","x":477,"y":844},{"id":"P99","x":634,"y":863},{"id":"P100","x":498,"y":960}],"edges":[{"from":"P1","to":"P3","weight":1},{"from":"P1","to":"P11","weight":1},{"from":"P1","to":"P2","weight":1},{"from":"P1","to":"P17","weight":1},{"from":"P2","to":"P1","weight":1},{"from":"P2","to":"P9","weight":1},{"from":"P3","to":"P1","weight":1},{"from":"P3","to":"P4","weight":3},{"from":"P3","to":"P5","weight":3},{"from":"P3","to":"P6","weight":2},{"from":"P3","to":"P7","weight":2},{"from":"P3","to":"P10","weight":1},{"from":"P3","to":"P41","weight":1},{"from":"P4","to":"P3","weight":2},{"from":"P4","to":"P5","weight":1},{"from":"P5","to":"P3","weight":2},{"from":"P6","to":"P3","weight":1},{"from":"P6","to":"P8","weight":1},{"from":"P7","to":"P3","weight":1},{"from":"P7","to":"P8","weight":2},{"from":"P7","to":"P9","weight":1},{"from":"P8","to":"P3","weight":1},{"from":"P8","to":"P7","weight":1},{"from":"P9","to":"P3","weight":2},{"from":"P10","to":"P3","weight":2},{"from":"P10","to":"P11","weight":2},{"from":"P11","to":"P10","weight":1},{"from":"P11","to":"P12","weight":3},{"from":"P11","to":"P19","weight":1},{"from":"P12","to":"P11","weight":1},{"from":"P12","to":"P13","weight":2},{"from":"P12","to":"P14","weight":1},{"from":"P12","to":"P16","weight":1},{"from":"P13","to":"P12","weight":2},{"from":"P13","to":"P1","weight":1},{"from":"P14","to":"P12","weight":1},{"from":"P14","to":"P15","weight":2},{"from":"P15","to":"P14","weight":1},{"from":"P15","to":"P3","weight":1},{"from":"P15","to":"P43","weight":1},{"from":"P16","to":"P12","weight":1},{"from":"P16","to":"P86","weight":1},{"from":"P17","to":"P18","weight":2},{"from":"P17","to":"P19","weight":2},{"from":"P17","to":"P20","weight":1},{"from":"P17","to":"P21","weight":2},{"from":"P17","to":"P22","weight":1},{"from":"P17","to":"P23","weight":1},{"from":"P17","to":"P24","weight":1},{"from":"P17","to":"P25","weight":1},{"from":"P17","to":"P26","weight":1},{"from":"P17","to":"P27","weight":1},{"from":"P17","to":"P29","weight":1},{"from":"P18","to":"P17","weight":1},{"from":"P18","to":"P22","weight":1},{"from":"P19","to":"P17","weight":1},{"from":"P19","to":"P86","weight":1},{"from":"P19","to":"P80","weight":1},{"from":"P20","to":"P17","weight":1},{"from":"P20","to":"P43","weight":2},{"from":"P20","to":"P15","weight":1},{"from":"P21","to":"P17","weight":1},{"from":"P21","to":"P25","weight":2},{"from":"P21","to":"P34","weight":1},{"from":"P22","to":"P17","weight":1},{"from":"P22","to":"P93","weight":1},{"from":"P23","to":"P17","weight":1},{"from":"P23","to":"P69","weight":1},{"from":"P24","to":"P17","weight":1},{"from":"P24","to":"P32","weight":1},{"from":"P25","to":"P17","weight":1},{"from":"P25","to":"P76","weight":2},{"from":"P26","to":"P17","weight":1},{"from":"P26","to":"P19","weight":1},{"from":"P27","to":"P17","weight":1},{"from":"P27","to":"P28","weight":1},{"from":"P27","to":"P30","weight":1},{"from":"P28","to":"P27","weight":1},{"from":"P29","to":"P17","weight":1},{"from":"P30","to":"P27","weight":1},{"from":"P31","to":"P32","weight":1},{"from":"P31","to":"P33","weight":1},{"from":"P31","to":"P34","weight":1},{"from":"P31","to":"P35","weight":1},{"from":"P31","to":"P36","weight":1},{"from":"P31","to":"P37","weight":1},{"from":"P32","to":"P31","weight":1},{"from":"P32","to":"P36","weight":2},{"from":"P33","to":"P31","weight":1},{"from":"P33","to":"P34","weight":1},{"from":"P34","to":"P31","weight":1},{"from":"P34","to":"P33","weight":1},{"from":"P35","to":"P31","weight":1},{"from":"P35","to":"P37","weight":1},{"from":"P36","to":"P31","weight":1},{"from":"P37","to":"P31","weight":1},{"from":"P38","to":"P39","weight":1},{"from":"P38","to":"P40","weight":1},{"from":"P38","to":"P42","weight":1},{"from":"P38","to":"P45","weight":2},{"from":"P38","to":"P46","weight":1},{"from":"P38","to":"P36","weight":1},{"from":"P39","to":"P38","weight":1},{"from":"P39","to":"P41","weight":1},{"from":"P39","to":"P43","weight":1},{"from":"P39","to":"P44","weight":1},{"from":"P40","to":"P38","weight":1},{"from":"P40","to":"P41","weight":1},{"from":"P41","to":"P39","weight":1},{"from":"P41","to":"P44","weight":1},{"from":"P41","to":"P3","weight":2},{"from":"P41","to":"P80","weight":1},{"from":"P41","to":"P96","weight":1},{"from":"P42","to":"P38","weight":1},{"from":"P42","to":"P1","weight":1},{"from":"P43","to":"P39","weight":1},{"from":"P43","to":"P44","weight":2},{"from":"P43","to":"P20","weight":1},{"from":"P44","to":"P39","weight":1},{"from":"P44","to":"P43","weight":1},{"from":"P45","to":"P38","weight":1},{"from":"P45","to":"P32","weight":1},{"from":"P46","to":"P38","weight":1},{"from":"P46","to":"P20","weight":1},{"from":"P47","to":"P48","weight":1},{"from":"P47","to":"P49","weight":1},{"from":"P47","to":"P50","weight":1},{"from":"P47","to":"P51","weight":1},{"from":"P47","to":"P52","weight":1},{"from":"P48","to":"P47","weight":1},{"from":"P48","to":"P1","weight":1},{"from":"P48","to":"P38","weight":1},{"from":"P48","to":"P20","weight":1},{"from":"P49","to":"P47","weight":1},{"from":"P49","to":"P53","weight":1},{"from":"P49","to":"P63","weight":1},{"from":"P50","to":"P47","weight":1},{"from":"P50","to":"P91","weight":1},{"from":"P51","to":"P47","weight":1},{"from":"P51","to":"P31","weight":1},{"from":"P51","to":"P24","weight":1},{"from":"P52","to":"P47","weight":1},{"from":"P53","to":"P54","weight":2},{"from":"P53","to":"P55","weight":1},{"from":"P53","to":"P58","weight":1},{"from":"P53","to":"P60","weight":1},{"from":"P53","to":"P61","weight":1},{"from":"P53","to":"P62","weight":1},{"from":"P54","to":"P53","weight":1},{"from":"P54","to":"P55","weight":2},{"from":"P55","to":"P53","weight":1},{"from":"P55","to":"P56","weight":1},{"from":"P55","to":"P57","weight":1},{"from":"P55","to":"P59","weight":2},{"from":"P56","to":"P55","weight":1},{"from":"P56","to":"P57","weight":1},{"from":"P57","to":"P55","weight":1},{"from":"P57","to":"P56","weight":1},{"from":"P58","to":"P53","weight":1},{"from":"P58","to":"P59","weight":1},{"from":"P59","to":"P55","weight":1},{"from":"P59","to":"P58","weight":2},{"from":"P60","to":"P53","weight":1},{"from":"P60","to":"P54","weight":1},{"from":"P61","to":"P53","weight":1},{"from":"P62","to":"P53","weight":1},{"from":"P63","to":"P68","weight":1},{"from":"P63","to":"P69","weight":1},{"from":"P63","to":"P70","weight":1},{"from":"P63","to":"P71","weight":1},{"from":"P63","to":"P64","weight":1},{"from":"P63","to":"P65","weight":1},{"from":"P63","to":"P66","weight":1},{"from":"P64","to":"P63","weight":1},{"from":"P65","to":"P63","weight":1},{"from":"P65","to":"P70","weight":1},{"from":"P66","to":"P63","weight":1},{"from":"P66","to":"P67","weight":1},{"from":"P67","to":"P63","weight":1},{"from":"P68","to":"P63","weight":1},{"from":"P68","to":"P72","weight":2},{"from":"P68","to":"P3","weight":1},{"from":"P68","to":"P82","weight":1},{"from":"P69","to":"P63","weight":1},{"from":"P69","to":"P73","weight":2},{"from":"P69","to":"P86","weight":2},{"from":"P69","to":"P58","weight":1},{"from":"P70","to":"P63","weight":1},{"from":"P70","to":"P74","weight":1},{"from":"P70","to":"P60","weight":2},{"from":"P71","to":"P63","weight":1},{"from":"P71","to":"P74","weight":1},{"from":"P71","to":"P34","weight":1},{"from":"P71","to":"P38","weight":1},{"from":"P72","to":"P68","weight":1},{"from":"P72","to":"P83","weight":1},{"from":"P73","to":"P69","weight":1},{"from":"P73","to":"P68","weight":1},{"from":"P74","to":"P70","weight":1},{"from":"P74","to":"P71","weight":1},{"from":"P75","to":"P76","weight":1},{"from":"P75","to":"P77","weight":1},{"from":"P75","to":"P78","weight":1},{"from":"P75","to":"P79","weight":1},{"from":"P76","to":"P75","weight":1},{"from":"P76","to":"P80","weight":1},{"from":"P77","to":"P75","weight":1},{"from":"P78","to":"P75","weight":1},{"from":"P79","to":"P75","weight":1},{"from":"P79","to":"P80","weight":1},{"from":"P79","to":"P82","weight":1},{"from":"P79","to":"P83","weight":1},{"from":"P80","to":"P79","weight":1},{"from":"P80","to":"P81","weight":1},{"from":"P80","to":"P3","weight":1},{"from":"P81","to":"P79","weight":1},{"from":"P81","to":"P82","weight":1},{"from":"P81","to":"P68","weight":1},{"from":"P82","to":"P79","weight":1},{"from":"P82","to":"P81","weight":1},{"from":"P83","to":"P85","weight":1},{"from":"P83","to":"P86","weight":1},{"from":"P83","to":"P87","weight":1},{"from":"P83","to":"P88","weight":1},{"from":"P83","to":"P84","weight":1},{"from":"P83","to":"P89","weight":1},{"from":"P84","to":"P83","weight":1},{"from":"P84","to":"P72","weight":1},{"from":"P85","to":"P83","weight":1},{"from":"P85","to":"P3","weight":3},{"from":"P85","to":"P81","weight":1},{"from":"P85","to":"P95","weight":1},{"from":"P86","to":"P83","weight":1},{"from":"P86","to":"P16","weight":2},{"from":"P86","to":"P55","weight":1},{"from":"P86","to":"P69","weight":1},{"from":"P87","to":"P85","weight":1},{"from":"P87","to":"P15","weight":2},{"from":"P87","to":"P43","weight":1},{"from":"P88","to":"P83","weight":1},{"from":"P88","to":"P85","weight":1},{"from":"P88","to":"P86","weight":1},{"from":"P89","to":"P83","weight":1},{"from":"P89","to":"P17","weight":1},{"from":"P89","to":"P1","weight":1},{"from":"P89","to":"P79","weight":1},{"from":"P90","to":"P83","weight":1},{"from":"P90","to":"P85","weight":1},{"from":"P91","to":"P92","weight":1},{"from":"P91","to":"P93","weight":2},{"from":"P91","to":"P94","weight":1},{"from":"P91","to":"P97","weight":1},{"from":"P91","to":"P99","weight":1},{"from":"P91","to":"P100","weight":1},{"from":"P92","to":"P91","weight":1},{"from":"P92","to":"P94","weight":1},{"from":"P93","to":"P91","weight":1},{"from":"P93","to":"P96","weight":1},{"from":"P94","to":"P91","weight":1},{"from":"P94","to":"P95","weight":1},{"from":"P94","to":"P96","weight":1},{"from":"P95","to":"P94","weight":1},{"from":"P95","to":"P97","weight":2},{"from":"P96","to":"P94","weight":1},{"from":"P96","to":"P97","weight":2},{"from":"P96","to":"P95","weight":1},{"from":"P97","to":"P91","weight":1},{"from":"P97","to":"P98","weight":2},{"from":"P98","to":"P97","weight":1},{"from":"P98","to":"P99","weight":1},{"from":"P98","to":"P100","weight":1},{"from":"P99","to":"P91","weight":1},{"from":"P100","to":"P91","weight":1},{"from":"P100","to":"P99","weight":1}],"details":{"vertices":100,"edges":274,"directed":true,"weighted":true,"acyclic":false,"weightMin":1,"weightMax":3,"negativeWeights":false,"density":0.027676767676767678,"inDegree":{"min":0,"avg":2.74,"max":13},"outDegree":{"min":1,"avg":2.74,"max":11},"selfLoops":0,"components":1}},"problem":"Which groups of pages can a crawler move around freely, and which groups lead on to which once each group counts as one page?","params":{},"result":{"kind":"groups","groups":[["P90"],["P47","P48","P49","P50","P51","P52"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18","P19","P20","P21","P22","P23","P24","P25","P26","P27","P28","P29","P30","P38","P39","P40","P41","P42","P43","P44","P45","P46","P63","P64","P65","P66","P67","P68","P69","P70","P71","P72","P73","P74","P75","P76","P77","P78","P79","P80","P81","P82","P83","P84","P85","P86","P87","P88","P89"],["P53","P54","P55","P56","P57","P58","P59","P60","P61","P62"],["P31","P32","P33","P34","P35","P36","P37"],["P91","P92","P93","P94","P95","P96","P97","P98","P99","P100"]]},"answer":"The 100 vertices condense into 6 components joined by 8 edges, with no cycle left. The largest component has 66 vertices: P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 56 more. The components are listed in topological order: every edge between two of them goes from an earlier one to a later one, so in reverse, each component comes after every component it has an edge into.","legend":{"vertex":[{"id":"idle","label":"Not in a component yet","color":"#64748B","shape":"hollow"},{"id":"component-2","label":"Component 2, 6 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-3","label":"Component 3, 66 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-4","label":"Component 4, 10 vertices","color":"#E69F00","shape":"filled"},{"id":"component-5","label":"Component 5, 7 vertices","color":"#F0E442","shape":"dashed-square"},{"id":"component-6","label":"Component 6, 10 vertices","color":"#D55E00","shape":"filled"},{"id":"single","label":"A component of one vertex","color":"#CBD5E1","shape":"hollow"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"inside","label":"Inside a component, dropped","color":"#475569","shape":"dashed"},{"id":"between","label":"Stands for the edges between two components","color":"#009E73","shape":"thick"},{"id":"merged","label":"Merged into the edge between the same components","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"components","title":"Components, in order","kind":"groups"},{"id":"edges","title":"Edges between components","kind":"list"}]},"steps":[{"say":"Condense runs Tarjan once to find the strongly connected components, the groups of vertices that can all reach each other. It numbers them so that every edge between two components goes from a lower number to a higher one. Then each component becomes one vertex, and the edges from one component to another become one edge."},{"say":"Component 1: P90 reaches no vertex that reaches it back, so it is a component on its own.","ops":[{"v":"P90","state":"single"},{"panel":"components","groups":[["P90"]]}]},{"say":"Component 2: P47, P48, P49, P50, P51 and P52 can all reach each other, so they become one vertex. The 10 edges among them drop out.","ops":[{"e":["P47","P48"],"state":"inside"},{"e":["P47","P49"],"state":"inside"},{"e":["P47","P50"],"state":"inside"},{"e":["P47","P51"],"state":"inside"},{"e":["P47","P52"],"state":"inside"},{"e":["P48","P47"],"state":"inside"},{"e":["P49","P47"],"state":"inside"},{"e":["P50","P47"],"state":"inside"},{"e":["P51","P47"],"state":"inside"},{"e":["P52","P47"],"state":"inside"},{"v":"P47","state":"component-2"},{"v":"P48","state":"component-2"},{"v":"P49","state":"component-2"},{"v":"P50","state":"component-2"},{"v":"P51","state":"component-2"},{"v":"P52","state":"component-2"},{"panel":"components","groups":[["P90"],["P47","P48","P49","P50","P51","P52"]]}]},{"say":"Component 3: P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 56 more can all reach each other, so they become one vertex. The 177 edges among them drop out.","ops":[{"e":["P1","P3"],"state":"inside"},{"e":["P1","P11"],"state":"inside"},{"e":["P1","P2"],"state":"inside"},{"e":["P1","P17"],"state":"inside"},{"e":["P2","P1"],"state":"inside"},{"e":["P2","P9"],"state":"inside"},{"e":["P3","P1"],"state":"inside"},{"e":["P3","P4"],"state":"inside"},{"e":["P3","P5"],"state":"inside"},{"e":["P3","P6"],"state":"inside"},{"e":["P3","P7"],"state":"inside"},{"e":["P3","P10"],"state":"inside"},{"e":["P3","P41"],"state":"inside"},{"e":["P4","P3"],"state":"inside"},{"e":["P4","P5"],"state":"inside"},{"e":["P5","P3"],"state":"inside"},{"e":["P6","P3"],"state":"inside"},{"e":["P6","P8"],"state":"inside"},{"e":["P7","P3"],"state":"inside"},{"e":["P7","P8"],"state":"inside"},{"e":["P7","P9"],"state":"inside"},{"e":["P8","P3"],"state":"inside"},{"e":["P8","P7"],"state":"inside"},{"e":["P9","P3"],"state":"inside"},{"e":["P10","P3"],"state":"inside"},{"e":["P10","P11"],"state":"inside"},{"e":["P11","P10"],"state":"inside"},{"e":["P11","P12"],"state":"inside"},{"e":["P11","P19"],"state":"inside"},{"e":["P12","P11"],"state":"inside"},{"e":["P12","P13"],"state":"inside"},{"e":["P12","P14"],"state":"inside"},{"e":["P12","P16"],"state":"inside"},{"e":["P13","P12"],"state":"inside"},{"e":["P13","P1"],"state":"inside"},{"e":["P14","P12"],"state":"inside"},{"e":["P14","P15"],"state":"inside"},{"e":["P15","P14"],"state":"inside"},{"e":["P15","P3"],"state":"inside"},{"e":["P15","P43"],"state":"inside"},{"e":["P16","P12"],"state":"inside"},{"e":["P16","P86"],"state":"inside"},{"e":["P17","P18"],"state":"inside"},{"e":["P17","P19"],"state":"inside"},{"e":["P17","P20"],"state":"inside"},{"e":["P17","P21"],"state":"inside"},{"e":["P17","P22"],"state":"inside"},{"e":["P17","P23"],"state":"inside"},{"e":["P17","P24"],"state":"inside"},{"e":["P17","P25"],"state":"inside"},{"e":["P17","P26"],"state":"inside"},{"e":["P17","P27"],"state":"inside"},{"e":["P17","P29"],"state":"inside"},{"e":["P18","P17"],"state":"inside"},{"e":["P18","P22"],"state":"inside"},{"e":["P19","P17"],"state":"inside"},{"e":["P19","P86"],"state":"inside"},{"e":["P19","P80"],"state":"inside"},{"e":["P20","P17"],"state":"inside"},{"e":["P20","P43"],"state":"inside"},{"e":["P20","P15"],"state":"inside"},{"e":["P21","P17"],"state":"inside"},{"e":["P21","P25"],"state":"inside"},{"e":["P22","P17"],"state":"inside"},{"e":["P23","P17"],"state":"inside"},{"e":["P23","P69"],"state":"inside"},{"e":["P24","P17"],"state":"inside"},{"e":["P25","P17"],"state":"inside"},{"e":["P25","P76"],"state":"inside"},{"e":["P26","P17"],"state":"inside"},{"e":["P26","P19"],"state":"inside"},{"e":["P27","P17"],"state":"inside"},{"e":["P27","P28"],"state":"inside"},{"e":["P27","P30"],"state":"inside"},{"e":["P28","P27"],"state":"inside"},{"e":["P29","P17"],"state":"inside"},{"e":["P30","P27"],"state":"inside"},{"e":["P38","P39"],"state":"inside"},{"e":["P38","P40"],"state":"inside"},{"e":["P38","P42"],"state":"inside"},{"e":["P38","P45"],"state":"inside"},{"e":["P38","P46"],"state":"inside"},{"e":["P39","P38"],"state":"inside"},{"e":["P39","P41"],"state":"inside"},{"e":["P39","P43"],"state":"inside"},{"e":["P39","P44"],"state":"inside"},{"e":["P40","P38"],"state":"inside"},{"e":["P40","P41"],"state":"inside"},{"e":["P41","P39"],"state":"inside"},{"e":["P41","P44"],"state":"inside"},{"e":["P41","P3"],"state":"inside"},{"e":["P41","P80"],"state":"inside"},{"e":["P42","P38"],"state":"inside"},{"e":["P42","P1"],"state":"inside"},{"e":["P43","P39"],"state":"inside"},{"e":["P43","P44"],"state":"inside"},{"e":["P43","P20"],"state":"inside"},{"e":["P44","P39"],"state":"inside"},{"e":["P44","P43"],"state":"inside"},{"e":["P45","P38"],"state":"inside"},{"e":["P46","P38"],"state":"inside"},{"e":["P46","P20"],"state":"inside"},{"e":["P63","P68"],"state":"inside"},{"e":["P63","P69"],"state":"inside"},{"e":["P63","P70"],"state":"inside"},{"e":["P63","P71"],"state":"inside"},{"e":["P63","P64"],"state":"inside"},{"e":["P63","P65"],"state":"inside"},{"e":["P63","P66"],"state":"inside"},{"e":["P64","P63"],"state":"inside"},{"e":["P65","P63"],"state":"inside"},{"e":["P65","P70"],"state":"inside"},{"e":["P66","P63"],"state":"inside"},{"e":["P66","P67"],"state":"inside"},{"e":["P67","P63"],"state":"inside"},{"e":["P68","P63"],"state":"inside"},{"e":["P68","P72"],"state":"inside"},{"e":["P68","P3"],"state":"inside"},{"e":["P68","P82"],"state":"inside"},{"e":["P69","P63"],"state":"inside"},{"e":["P69","P73"],"state":"inside"},{"e":["P69","P86"],"state":"inside"},{"e":["P70","P63"],"state":"inside"},{"e":["P70","P74"],"state":"inside"},{"e":["P71","P63"],"state":"inside"},{"e":["P71","P74"],"state":"inside"},{"e":["P71","P38"],"state":"inside"},{"e":["P72","P68"],"state":"inside"},{"e":["P72","P83"],"state":"inside"},{"e":["P73","P69"],"state":"inside"},{"e":["P73","P68"],"state":"inside"},{"e":["P74","P70"],"state":"inside"},{"e":["P74","P71"],"state":"inside"},{"e":["P75","P76"],"state":"inside"},{"e":["P75","P77"],"state":"inside"},{"e":["P75","P78"],"state":"inside"},{"e":["P75","P79"],"state":"inside"},{"e":["P76","P75"],"state":"inside"},{"e":["P76","P80"],"state":"inside"},{"e":["P77","P75"],"state":"inside"},{"e":["P78","P75"],"state":"inside"},{"e":["P79","P75"],"state":"inside"},{"e":["P79","P80"],"state":"inside"},{"e":["P79","P82"],"state":"inside"},{"e":["P79","P83"],"state":"inside"},{"e":["P80","P79"],"state":"inside"},{"e":["P80","P81"],"state":"inside"},{"e":["P80","P3"],"state":"inside"},{"e":["P81","P79"],"state":"inside"},{"e":["P81","P82"],"state":"inside"},{"e":["P81","P68"],"state":"inside"},{"e":["P82","P79"],"state":"inside"},{"e":["P82","P81"],"state":"inside"},{"e":["P83","P85"],"state":"inside"},{"e":["P83","P86"],"state":"inside"},{"e":["P83","P87"],"state":"inside"},{"e":["P83","P88"],"state":"inside"},{"e":["P83","P84"],"state":"inside"},{"e":["P83","P89"],"state":"inside"},{"e":["P84","P83"],"state":"inside"},{"e":["P84","P72"],"state":"inside"},{"e":["P85","P83"],"state":"inside"},{"e":["P85","P3"],"state":"inside"},{"e":["P85","P81"],"state":"inside"},{"e":["P86","P83"],"state":"inside"},{"e":["P86","P16"],"state":"inside"},{"e":["P86","P69"],"state":"inside"},{"e":["P87","P85"],"state":"inside"},{"e":["P87","P15"],"state":"inside"},{"e":["P87","P43"],"state":"inside"},{"e":["P88","P83"],"state":"inside"},{"e":["P88","P85"],"state":"inside"},{"e":["P88","P86"],"state":"inside"},{"e":["P89","P83"],"state":"inside"},{"e":["P89","P17"],"state":"inside"},{"e":["P89","P1"],"state":"inside"},{"e":["P89","P79"],"state":"inside"},{"v":"P1","state":"component-3"},{"v":"P2","state":"component-3"},{"v":"P3","state":"component-3"},{"v":"P4","state":"component-3"},{"v":"P5","state":"component-3"},{"v":"P6","state":"component-3"},{"v":"P7","state":"component-3"},{"v":"P8","state":"component-3"},{"v":"P9","state":"component-3"},{"v":"P10","state":"component-3"},{"v":"P11","state":"component-3"},{"v":"P12","state":"component-3"},{"v":"P13","state":"component-3"},{"v":"P14","state":"component-3"},{"v":"P15","state":"component-3"},{"v":"P16","state":"component-3"},{"v":"P17","state":"component-3"},{"v":"P18","state":"component-3"},{"v":"P19","state":"component-3"},{"v":"P20","state":"component-3"},{"v":"P21","state":"component-3"},{"v":"P22","state":"component-3"},{"v":"P23","state":"component-3"},{"v":"P24","state":"component-3"},{"v":"P25","state":"component-3"},{"v":"P26","state":"component-3"},{"v":"P27","state":"component-3"},{"v":"P28","state":"component-3"},{"v":"P29","state":"component-3"},{"v":"P30","state":"component-3"},{"v":"P38","state":"component-3"},{"v":"P39","state":"component-3"},{"v":"P40","state":"component-3"},{"v":"P41","state":"component-3"},{"v":"P42","state":"component-3"},{"v":"P43","state":"component-3"},{"v":"P44","state":"component-3"},{"v":"P45","state":"component-3"},{"v":"P46","state":"component-3"},{"v":"P63","state":"component-3"},{"v":"P64","state":"component-3"},{"v":"P65","state":"component-3"},{"v":"P66","state":"component-3"},{"v":"P67","state":"component-3"},{"v":"P68","state":"component-3"},{"v":"P69","state":"component-3"},{"v":"P70","state":"component-3"},{"v":"P71","state":"component-3"},{"v":"P72","state":"component-3"},{"v":"P73","state":"component-3"},{"v":"P74","state":"component-3"},{"v":"P75","state":"component-3"},{"v":"P76","state":"component-3"},{"v":"P77","state":"component-3"},{"v":"P78","state":"component-3"},{"v":"P79","state":"component-3"},{"v":"P80","state":"component-3"},{"v":"P81","state":"component-3"},{"v":"P82","state":"component-3"},{"v":"P83","state":"component-3"},{"v":"P84","state":"component-3"},{"v":"P85","state":"component-3"},{"v":"P86","state":"component-3"},{"v":"P87","state":"component-3"},{"v":"P88","state":"component-3"},{"v":"P89","state":"component-3"},{"panel":"components","groups":[["P90"],["P47","P48","P49","P50","P51","P52"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18","P19","P20","P21","P22","P23","P24","P25","P26","P27","P28","P29","P30","P38","P39","P40","P41","P42","P43","P44","P45","P46","P63","P64","P65","P66","P67","P68","P69","P70","P71","P72","P73","P74","P75","P76","P77","P78","P79","P80","P81","P82","P83","P84","P85","P86","P87","P88","P89"]]}]},{"say":"Component 4: P53, P54, P55, P56, P57, P58, P59, P60, P61 and P62 can all reach each other, so they become one vertex. The 24 edges among them drop out.","ops":[{"e":["P53","P54"],"state":"inside"},{"e":["P53","P55"],"state":"inside"},{"e":["P53","P58"],"state":"inside"},{"e":["P53","P60"],"state":"inside"},{"e":["P53","P61"],"state":"inside"},{"e":["P53","P62"],"state":"inside"},{"e":["P54","P53"],"state":"inside"},{"e":["P54","P55"],"state":"inside"},{"e":["P55","P53"],"state":"inside"},{"e":["P55","P56"],"state":"inside"},{"e":["P55","P57"],"state":"inside"},{"e":["P55","P59"],"state":"inside"},{"e":["P56","P55"],"state":"inside"},{"e":["P56","P57"],"state":"inside"},{"e":["P57","P55"],"state":"inside"},{"e":["P57","P56"],"state":"inside"},{"e":["P58","P53"],"state":"inside"},{"e":["P58","P59"],"state":"inside"},{"e":["P59","P55"],"state":"inside"},{"e":["P59","P58"],"state":"inside"},{"e":["P60","P53"],"state":"inside"},{"e":["P60","P54"],"state":"inside"},{"e":["P61","P53"],"state":"inside"},{"e":["P62","P53"],"state":"inside"},{"v":"P53","state":"component-4"},{"v":"P54","state":"component-4"},{"v":"P55","state":"component-4"},{"v":"P56","state":"component-4"},{"v":"P57","state":"component-4"},{"v":"P58","state":"component-4"},{"v":"P59","state":"component-4"},{"v":"P60","state":"component-4"},{"v":"P61","state":"component-4"},{"v":"P62","state":"component-4"},{"panel":"components","groups":[["P90"],["P47","P48","P49","P50","P51","P52"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18","P19","P20","P21","P22","P23","P24","P25","P26","P27","P28","P29","P30","P38","P39","P40","P41","P42","P43","P44","P45","P46","P63","P64","P65","P66","P67","P68","P69","P70","P71","P72","P73","P74","P75","P76","P77","P78","P79","P80","P81","P82","P83","P84","P85","P86","P87","P88","P89"],["P53","P54","P55","P56","P57","P58","P59","P60","P61","P62"]]}]},{"say":"Component 5: P31, P32, P33, P34, P35, P36 and P37 can all reach each other, so they become one vertex. The 16 edges among them drop out.","ops":[{"e":["P31","P32"],"state":"inside"},{"e":["P31","P33"],"state":"inside"},{"e":["P31","P34"],"state":"inside"},{"e":["P31","P35"],"state":"inside"},{"e":["P31","P36"],"state":"inside"},{"e":["P31","P37"],"state":"inside"},{"e":["P32","P31"],"state":"inside"},{"e":["P32","P36"],"state":"inside"},{"e":["P33","P31"],"state":"inside"},{"e":["P33","P34"],"state":"inside"},{"e":["P34","P31"],"state":"inside"},{"e":["P34","P33"],"state":"inside"},{"e":["P35","P31"],"state":"inside"},{"e":["P35","P37"],"state":"inside"},{"e":["P36","P31"],"state":"inside"},{"e":["P37","P31"],"state":"inside"},{"v":"P31","state":"component-5"},{"v":"P32","state":"component-5"},{"v":"P33","state":"component-5"},{"v":"P34","state":"component-5"},{"v":"P35","state":"component-5"},{"v":"P36","state":"component-5"},{"v":"P37","state":"component-5"},{"panel":"components","groups":[["P90"],["P47","P48","P49","P50","P51","P52"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18","P19","P20","P21","P22","P23","P24","P25","P26","P27","P28","P29","P30","P38","P39","P40","P41","P42","P43","P44","P45","P46","P63","P64","P65","P66","P67","P68","P69","P70","P71","P72","P73","P74","P75","P76","P77","P78","P79","P80","P81","P82","P83","P84","P85","P86","P87","P88","P89"],["P53","P54","P55","P56","P57","P58","P59","P60","P61","P62"],["P31","P32","P33","P34","P35","P36","P37"]]}]},{"say":"Component 6: P91, P92, P93, P94, P95, P96, P97, P98, P99 and P100 can all reach each other, so they become one vertex. The 26 edges among them drop out.","ops":[{"e":["P91","P92"],"state":"inside"},{"e":["P91","P93"],"state":"inside"},{"e":["P91","P94"],"state":"inside"},{"e":["P91","P97"],"state":"inside"},{"e":["P91","P99"],"state":"inside"},{"e":["P91","P100"],"state":"inside"},{"e":["P92","P91"],"state":"inside"},{"e":["P92","P94"],"state":"inside"},{"e":["P93","P91"],"state":"inside"},{"e":["P93","P96"],"state":"inside"},{"e":["P94","P91"],"state":"inside"},{"e":["P94","P95"],"state":"inside"},{"e":["P94","P96"],"state":"inside"},{"e":["P95","P94"],"state":"inside"},{"e":["P95","P97"],"state":"inside"},{"e":["P96","P94"],"state":"inside"},{"e":["P96","P97"],"state":"inside"},{"e":["P96","P95"],"state":"inside"},{"e":["P97","P91"],"state":"inside"},{"e":["P97","P98"],"state":"inside"},{"e":["P98","P97"],"state":"inside"},{"e":["P98","P99"],"state":"inside"},{"e":["P98","P100"],"state":"inside"},{"e":["P99","P91"],"state":"inside"},{"e":["P100","P91"],"state":"inside"},{"e":["P100","P99"],"state":"inside"},{"v":"P91","state":"component-6"},{"v":"P92","state":"component-6"},{"v":"P93","state":"component-6"},{"v":"P94","state":"component-6"},{"v":"P95","state":"component-6"},{"v":"P96","state":"component-6"},{"v":"P97","state":"component-6"},{"v":"P98","state":"component-6"},{"v":"P99","state":"component-6"},{"v":"P100","state":"component-6"},{"panel":"components","groups":[["P90"],["P47","P48","P49","P50","P51","P52"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18","P19","P20","P21","P22","P23","P24","P25","P26","P27","P28","P29","P30","P38","P39","P40","P41","P42","P43","P44","P45","P46","P63","P64","P65","P66","P67","P68","P69","P70","P71","P72","P73","P74","P75","P76","P77","P78","P79","P80","P81","P82","P83","P84","P85","P86","P87","P88","P89"],["P53","P54","P55","P56","P57","P58","P59","P60","P61","P62"],["P31","P32","P33","P34","P35","P36","P37"],["P91","P92","P93","P94","P95","P96","P97","P98","P99","P100"]]}]},{"say":"Out of component 1: The 2 edges P90 to P83 and P90 to P85 become one edge, 1 to 3.","ops":[{"e":["P90","P83"],"state":"between"},{"e":["P90","P85"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 3","note":"2 edges"}]}]},{"say":"Out of component 2: The 5 edges P48 to P1, P48 to P20, P48 to P38, P49 to P63 and P51 to P24 become one edge, 2 to 3. P49 to P53 becomes the edge 2 to 4. P51 to P31 becomes the edge 2 to 5. P50 to P91 becomes the edge 2 to 6.","ops":[{"e":["P48","P1"],"state":"between"},{"e":["P48","P38"],"state":"merged"},{"e":["P48","P20"],"state":"merged"},{"e":["P49","P63"],"state":"merged"},{"e":["P51","P24"],"state":"merged"},{"e":["P49","P53"],"state":"between"},{"e":["P51","P31"],"state":"between"},{"e":["P50","P91"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 3","note":"2 edges"},{"key":"2 to 3","note":"5 edges"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 5","note":"1 edge"},{"key":"2 to 6","note":"1 edge"}]}]},{"say":"Out of component 3: The 3 edges P69 to P58, P70 to P60 and P86 to P55 become one edge, 3 to 4. The 5 edges P21 to P34, P24 to P32, P38 to P36, P45 to P32 and P71 to P34 become one edge, 3 to 5. The 3 edges P22 to P93, P41 to P96 and P85 to P95 become one edge, 3 to 6.","ops":[{"e":["P69","P58"],"state":"between"},{"e":["P70","P60"],"state":"merged"},{"e":["P86","P55"],"state":"merged"},{"e":["P21","P34"],"state":"between"},{"e":["P24","P32"],"state":"merged"},{"e":["P38","P36"],"state":"merged"},{"e":["P45","P32"],"state":"merged"},{"e":["P71","P34"],"state":"merged"},{"e":["P22","P93"],"state":"between"},{"e":["P41","P96"],"state":"merged"},{"e":["P85","P95"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 3","note":"2 edges"},{"key":"2 to 3","note":"5 edges"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 5","note":"1 edge"},{"key":"2 to 6","note":"1 edge"},{"key":"3 to 4","note":"3 edges"},{"key":"3 to 5","note":"5 edges"},{"key":"3 to 6","note":"3 edges"}]}]},{"say":"Done. The 100 vertices condense into 6 components and 8 edges between them. The condensed graph has no cycle, and its vertices are listed in topological order."}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"sum := func(members []*gograph.Vertex[string]) float64 {\n\tvar total float64\n\tfor _, v := range members {\n\t\ttotal += v.Weight()\n\t}\n\treturn total\n}\nc, err := connectivity.Condense(g, connectivity.WithComponentWeight(sum))\nif err != nil {\n\treturn err\n}\nfor i, members := range c.Members {\n\tvar names []string\n\tfor _, v := range members {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(i, strings.Join(names, \", \"), c.Graph.GetVertexByID(i).Weight())\n}\nfor _, e := range c.Graph.AllEdges() {\n\tfmt.Println(e.Source().Label(), \"->\", e.Destination().Label())\n}"}