{"algorithm":"connected-components","about":["Two vertices are in the same connected component when some path joins them. The components are the separate pieces of a graph: no edge runs between two of them, so nothing in one piece can reach anything in another.","gograph searches breadth-first from the first vertex and gives every vertex it reaches the same component. When that search runs out, it starts the next one at the first vertex no search has reached, and so on, so the components come out in the order of their first vertex. Every vertex and edge is looked at once, so it costs O(V+E).","On a directed graph, gograph ignores the edge directions and returns the weakly connected components. It joins the two ends of each edge with union-find instead of searching, since a vertex doesn't keep a list of the edges that end at it. To find the groups that can reach each other along the edge directions, use Tarjan, Kosaraju or Gabow. Use connected components to find the islands of a network after an outage, or to handle each piece of a graph on its own."],"template":{"id":"office-outage","name":"Office outage","description":"The office network after the core switch and the Support switch lose power. The switches and rooms still wired to each other stay in touch, and the rest can't reach them.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"Sales","x":320,"y":192},{"id":"Ops","x":704,"y":448},{"id":"Dev","x":320,"y":448},{"id":"Uplink","x":512,"y":64},{"id":"Sales 1","x":128,"y":128},{"id":"Lab","x":160,"y":320},{"id":"Dev 1","x":128,"y":528},{"id":"Dev 2","x":512,"y":576},{"id":"Support 1","x":896,"y":112},{"id":"Shared","x":912,"y":304},{"id":"Ops 1","x":896,"y":544}],"edges":[{"from":"Sales","to":"Uplink"},{"from":"Sales","to":"Sales 1"},{"from":"Sales","to":"Lab"},{"from":"Ops","to":"Shared"},{"from":"Ops","to":"Ops 1"},{"from":"Dev","to":"Lab"},{"from":"Dev","to":"Dev 1"},{"from":"Dev","to":"Dev 2"},{"from":"Lab","to":"Dev 1"}],"details":{"vertices":11,"edges":9,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.16363636363636364,"degree":{"min":0,"avg":1.6363636363636365,"max":3},"selfLoops":0,"components":3}},"problem":"The core switch and the Support switch have lost power. Which switches and rooms can still reach each other?","params":{},"result":{"kind":"groups","groups":[["Dev","Dev 1","Dev 2","Lab","Sales","Sales 1","Uplink"],["Ops","Ops 1","Shared"],["Support 1"]]},"answer":"The graph falls into 3 connected components, with 7, 3 and 1 vertices. No edge joins two of them, so each vertex can reach only the vertices in its own component.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being checked","color":"#56B4E9","shape":"ring"},{"id":"done","label":"In a component","color":"#009E73","shape":"filled"},{"id":"component-1","label":"Component 1, 7 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-2","label":"Component 2, 3 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"single","label":"A component of one vertex","color":"#CBD5E1","shape":"hollow"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Reached a new vertex","color":"#009E73","shape":"thick"}],"panels":[{"id":"queue","title":"Queue","kind":"list"},{"id":"components","title":"Components found","kind":"groups"}]},"steps":[{"say":"ConnectedComponents searches breadth-first from each vertex no earlier search has reached, in the graph's vertex order. Every vertex a search reaches is in the same component as the vertex it started from. When the queue runs out, the component is complete."},{"say":"Start component 1 at Sales, the first vertex. Put it in the queue.","ops":[{"v":"Sales","state":"waiting"},{"panel":"queue","list":[{"key":"Sales"}]}]},{"say":"Take Sales from the front of the queue. Its neighbors Uplink, Sales 1 and Lab are new, so they join the back of the queue.","ops":[{"v":"Sales","state":"current"},{"v":"Uplink","state":"waiting"},{"e":["Sales","Uplink"],"state":"tree"},{"v":"Sales 1","state":"waiting"},{"e":["Sales","Sales 1"],"state":"tree"},{"v":"Lab","state":"waiting"},{"e":["Sales","Lab"],"state":"tree"},{"panel":"queue","list":[{"key":"Uplink"},{"key":"Sales 1"},{"key":"Lab"}]}]},{"say":"Take Uplink from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"Uplink","state":"current"},{"v":"Sales","state":"done"},{"panel":"queue","list":[{"key":"Sales 1"},{"key":"Lab"}]}]},{"say":"Take Sales 1 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"Sales 1","state":"current"},{"v":"Uplink","state":"done"},{"panel":"queue","list":[{"key":"Lab"}]}]},{"say":"Take Lab from the front of the queue. Its neighbors Dev and Dev 1 are new, so they join the back of the queue.","ops":[{"v":"Lab","state":"current"},{"v":"Sales 1","state":"done"},{"v":"Dev","state":"waiting"},{"e":["Lab","Dev"],"state":"tree"},{"v":"Dev 1","state":"waiting"},{"e":["Lab","Dev 1"],"state":"tree"},{"panel":"queue","list":[{"key":"Dev"},{"key":"Dev 1"}]}]},{"say":"Take Dev from the front of the queue. Its neighbor Dev 2 is new, so it joins the back of the queue.","ops":[{"v":"Dev","state":"current"},{"v":"Lab","state":"done"},{"v":"Dev 2","state":"waiting"},{"e":["Dev","Dev 2"],"state":"tree"},{"panel":"queue","list":[{"key":"Dev 1"},{"key":"Dev 2"}]}]},{"say":"Take Dev 1 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"Dev 1","state":"current"},{"v":"Dev","state":"done"},{"panel":"queue","list":[{"key":"Dev 2"}]}]},{"say":"Take Dev 2 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"Dev 2","state":"current"},{"v":"Dev 1","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 1 is complete with 7 vertices.","ops":[{"v":"Sales","state":"done"},{"v":"Uplink","state":"done"},{"v":"Sales 1","state":"done"},{"v":"Lab","state":"done"},{"v":"Dev","state":"done"},{"v":"Dev 1","state":"done"},{"v":"Dev 2","state":"done"},{"panel":"components","groups":[["Sales","Uplink","Sales 1","Lab","Dev","Dev 1","Dev 2"]]}]},{"say":"Start component 2 at Ops, the next vertex no search has reached. Put it in the queue.","ops":[{"v":"Ops","state":"waiting"},{"panel":"queue","list":[{"key":"Ops"}]}]},{"say":"Take Ops from the front of the queue. Its neighbors Shared and Ops 1 are new, so they join the back of the queue.","ops":[{"v":"Ops","state":"current"},{"v":"Shared","state":"waiting"},{"e":["Ops","Shared"],"state":"tree"},{"v":"Ops 1","state":"waiting"},{"e":["Ops","Ops 1"],"state":"tree"},{"panel":"queue","list":[{"key":"Shared"},{"key":"Ops 1"}]}]},{"say":"Take Shared from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"Shared","state":"current"},{"v":"Ops","state":"done"},{"panel":"queue","list":[{"key":"Ops 1"}]}]},{"say":"Take Ops 1 from the front of the queue. Every neighbor it has is already in the component.","ops":[{"v":"Ops 1","state":"current"},{"v":"Shared","state":"done"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so component 2 is complete with 3 vertices.","ops":[{"v":"Ops","state":"done"},{"v":"Shared","state":"done"},{"v":"Ops 1","state":"done"},{"panel":"components","groups":[["Sales","Uplink","Sales 1","Lab","Dev","Dev 1","Dev 2"],["Ops","Shared","Ops 1"]]}]},{"say":"Start component 3 at Support 1, the next vertex no search has reached. Put it in the queue.","ops":[{"v":"Support 1","state":"waiting"},{"panel":"queue","list":[{"key":"Support 1"}]}]},{"say":"Take Support 1 from the front of the queue. It has no edges.","ops":[{"v":"Support 1","state":"current"},{"panel":"queue","list":[]}]},{"say":"The queue is empty, so Support 1 is component 3 on its own.","ops":[{"v":"Support 1","state":"done"},{"panel":"components","groups":[["Sales","Uplink","Sales 1","Lab","Dev","Dev 1","Dev 2"],["Ops","Shared","Ops 1"],["Support 1"]]}]},{"say":"Done. ConnectedComponents found 3 components. They come out in the order of their first vertex. Every vertex now shows the component it belongs to.","ops":[{"v":"Sales","state":"component-1"},{"v":"Uplink","state":"component-1"},{"v":"Sales 1","state":"component-1"},{"v":"Lab","state":"component-1"},{"v":"Dev","state":"component-1"},{"v":"Dev 1","state":"component-1"},{"v":"Dev 2","state":"component-1"},{"v":"Ops","state":"component-2"},{"v":"Shared","state":"component-2"},{"v":"Ops 1","state":"component-2"},{"v":"Support 1","state":"single"}]}],"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":"for _, component := range gograph.ConnectedComponents(g) {\n\tvar names []string\n\tfor _, v := range component {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(strings.Join(names, \", \"))\n}"}