> ## Documentation Index > Fetch the complete documentation index at: https://demo.agenticlabs.com/llms.txt > Use this file to discover all available pages before exploring further. # graph_utilities.py ## High-level description This code defines functions for constructing and manipulating graphs used in phylogenetic tree reconstruction. It includes functions for building connectivity graphs based on shared mutations, similarity graphs based on a given similarity function, and optimizing graph partitions using hill-climbing procedures. ## Code Structure The code consists of several functions that are used to construct and manipulate graphs for phylogenetic tree reconstruction. The `construct_connectivity_graph` and `construct_similarity_graph` functions are used to build different types of graphs, while `max_cut_improve_cut` and `spectral_improve_cut` are used to optimize partitions on these graphs. The `check_if_cut` function is a utility function used by the optimization functions. ## References This code references the `solver_utilities` module for converting sample names to indices. ## Symbols ### `check_if_cut` #### Description This function checks if two nodes are on opposite sides of a graph partition. #### Inputs | Name | Type | Description | | :--- | :--------- | :------------------------------------------------------------- | | u | int | The index of the first node. | | v | int | The index of the second node. | | cut | List\[int] | A list of node indices representing one side of the partition. | #### Outputs | Name | Type | Description | | :--- | :--- | :----------------------------------------------------------------------------- | | | bool | True if nodes u and v are on opposite sides of the partition, False otherwise. | #### Internal Logic The function simply checks if one node is in the `cut` list and the other is not. ### `construct_connectivity_graph` #### Description This function constructs a connectivity graph for a set of samples based on their observed mutations. The edge weights represent the tendency of two samples to be grouped together or separated based on their shared and differing mutations. #### Inputs | Name | Type | Description | | :------------------------ | :--------------------------------------- | :-------------------------------------------------------------------- | | character\_matrix | pd.DataFrame | The character matrix of observed character states for all samples. | | mutation\_frequencies | Dict\[int, Dict\[int, int]] | A dictionary containing the frequencies of each character/state pair. | | missing\_state\_indicator | int | The character representing missing values. | | samples | List\[str] | A list of sample names to include in the graph. | | weights | Optional\[Dict\[int, Dict\[int, float]]] | Optional weights for character/state pairs. | #### Outputs | Name | Type | Description | | :------- | :------- | :------------------------------------------------------------- | | G\_names | nx.Graph | The constructed connectivity graph with sample names as nodes. | #### Internal Logic The function iterates through all pairs of samples and calculates a score based on their shared and differing mutations. The score is positive if the samples share mutations and negative if they have different mutations. The absolute value of the score is higher for mutations that are less frequent in the dataset. The scores are then used as edge weights in the graph. ### `max_cut_improve_cut` #### Description This function implements a greedy hill-climbing procedure to optimize a partition for the max-cut criterion on a graph. #### Inputs | Name | Type | Description | | :--- | :--------- | :-------------------------------------------------------------- | | G | nx.Graph | The graph to optimize the partition on. | | cut | List\[str] | A list of nodes representing one side of the initial partition. | #### Outputs | Name | Type | Description | | :------- | :--------- | :---------------------------------------------------------------- | | new\_cut | List\[str] | A new partition that is a local maximum to the max-cut criterion. | #### Internal Logic The function iteratively moves nodes between the two sides of the partition, choosing the move that maximizes the weight of edges across the cut. The procedure terminates when no further improvement can be made or a maximum number of iterations is reached. ### `construct_similarity_graph` #### Description This function constructs a similarity graph for a set of samples based on a given similarity function. #### Inputs | Name | Type | Description | | :------------------------ | :--------------------------------------- | :----------------------------------------------------------------- | | character\_matrix | pd.DataFrame | The character matrix of observed character states for all samples. | | missing\_state\_indicator | int | The character representing missing values. | | samples | List\[str] | A list of sample names to include in the graph. | | similarity\_function | Callable | A function that calculates a similarity score between two samples. | | threshold | int | A minimum similarity threshold to include an edge in the graph. | | weights | Optional\[Dict\[int, Dict\[int, float]]] | Optional weights for character/state pairs. | #### Outputs | Name | Type | Description | | :------- | :------- | :----------------------------------------------------------- | | G\_names | nx.Graph | The constructed similarity graph with sample names as nodes. | #### Internal Logic The function iterates through all pairs of samples and calculates their similarity using the provided `similarity_function`. If the similarity score is above the given `threshold`, an edge is added between the corresponding nodes in the graph with the weight equal to the similarity score. ### `spectral_improve_cut` #### Description This function implements a greedy hill-climbing procedure to optimize a partition for a modified normalized cut criterion on a graph. #### Inputs | Name | Type | Description | | :--- | :--------- | :-------------------------------------------------------------- | | G | nx.Graph | The graph to optimize the partition on. | | cut | List\[str] | A list of nodes representing one side of the initial partition. | #### Outputs | Name | Type | Description | | :------- | :--------- | :----------------------------------------------------------------- | | new\_cut | List\[str] | A new partition that is a local minimum to the objective function. | #### Internal Logic The function iteratively moves nodes between the two sides of the partition, choosing the move that minimizes the ratio of the weight of edges across the cut to the minimum of the sum of edge weights within each side of the cut. The procedure terminates when no further improvement can be made or a maximum number of iterations is reached.