Components module¶
This algorithm takes the graph created in the body of the script and it will print the vertices in each of the connected components of the graph.
Each vertex starts in its own component. We then iterate adjacency list of every vertex u and merge u’s component with the component of each vertex v on the adjacency list.
The comp_ptr list tracks the component representative for each component to allow quick determinations on whether two vertices are in the same component while the comp_list list of lists facilitates displaying the results of the algorithm in a concise and efficient manner.
Algorithm 2.1.1 on page 25
-
Components.comp_rep(comp_ptr, u)¶ Find the component representative for the input vertex
- Parameters
- comp_ptrlist
The list of component pointers
- uint
The vertex of interest
- Returns
- int :
The component representative of the component u is a part of
-
Components.components(G)¶ Find the components of graph G
- Parameters
- Gnx.Graph
The graph to find the connected components in
- Returns
- List of List
A list of lists such that each non-None list contains the vertices of that component
-
Components.merge(comp_ptr, comp_list, u_rep, v_rep)¶ Merge the smaller component into the larger one
- Parameters
- comp_ptrList of int
The list of component pointers
- comp_listList of List
The list of lists which tracks vertices in a format conducive to printing them
- u_repint
The component representative for the first component
- v_repint
The component representative for the first component
-
Components.print_components(G)¶ Find the connected components of G and print them
- Parameters
- Gnx.Graph
The graph to find the connected components in
Examples
>>> print_components(graph) Component Representative: 0, Component Members: 0 1 Component Representative: 2, Component Members: 2 3 4
The components on the graph in
disconnected.adjlist.