WeaklyConnectedComponents

WeaklyConnectedComponents[g]

gives the weakly connected components of the graph g.

WeaklyConnectedComponents[g,{v1,v2,…}]

gives the weakly connected components that include at least one of the vertices v1, v2, ….

WeaklyConnectedComponents[g,patt]

gives the connected components that include a vertex that matches the pattern patt.

WeaklyConnectedComponents[{vw,…},…]

uses rules vw to specify the graph g.

Details

  • In a directed graph, the weakly connected components are the connected components that remain when the graph is considered undirected.
  • WeaklyConnectedComponents returns a list of components {c1,c2,…}, where each component ci is given as a list of vertices.
  • Vertices u and v are in the same component ci if there is a sequence of edges joining u and v.
  • Components ci are ordered by their length, with the largest component first.
  • WeaklyConnectedComponents works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open allclose all

Basic Examples  (1)

Give the weakly connected components of a graph:

Highlight the components:

Scope  (8)

WeaklyConnectedComponents works with undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

Use rules to specify the graph:

Select weakly connected components that include at least one of the specified vertices:

Use patterns to select a subset of weakly connected components:

WeaklyConnectedComponents works with large graphs:

Applications  (1)

A frog in a lily pond is able to jump 1.5 feet to get from one of the 25 lily pads to another. Model the frog's jumping network from the lily leaf density and SpatialGraphDistribution:

Sample a random pond:

Find the largest collection of lily pads the frog can jump between:

Use simulation to find the sizes of the largest collections of lily pads for similar ponds:

Find the number of times the frog would have to swim to visit all lily pads:

Simulate to get results for similar lily ponds:

Properties & Relations  (3)

For undirected graphs, connected and weakly connected components are identical:

Use WeaklyConnectedGraphQ to test whether a graph is weakly connected:

Weakly connected components are ordered by their length, with the largest component first:

Wolfram Research (2012), WeaklyConnectedComponents, Wolfram Language function, https://reference.wolfram.com/language/ref/WeaklyConnectedComponents.html (updated 2015).

Text

Wolfram Research (2012), WeaklyConnectedComponents, Wolfram Language function, https://reference.wolfram.com/language/ref/WeaklyConnectedComponents.html (updated 2015).

CMS

Wolfram Language. 2012. "WeaklyConnectedComponents." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/WeaklyConnectedComponents.html.

APA

Wolfram Language. (2012). WeaklyConnectedComponents. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/WeaklyConnectedComponents.html

BibTeX

@misc{reference.wolfram_2024_weaklyconnectedcomponents, author="Wolfram Research", title="{WeaklyConnectedComponents}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/WeaklyConnectedComponents.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_weaklyconnectedcomponents, organization={Wolfram Research}, title={WeaklyConnectedComponents}, year={2015}, url={https://reference.wolfram.com/language/ref/WeaklyConnectedComponents.html}, note=[Accessed: 18-November-2024 ]}