Sage环境下基于上下界生成符合条件的邻接矩阵路径

Hey there! Since you're new to Sage, let's break this problem down into manageable steps to get you up and running. Let's start by clarifying what we're aiming for: given an adjacency matrix, we want to generate all possible "paths" where each path picks exactly one entry from every row, the total weight of the path falls between your specified lower and upper bounds, and then organize those paths as needed.

Step 1: Define Your Inputs #

First, let's set up your adjacency matrix and bounds in Sage. Here's a concrete example you can adapt to your own data:

# Replace this with your actual adjacency matrix
adj_matrix = Matrix([
    [1, 3, 5],
    [2, 4, 6],
    [3, 1, 2]
])

# Set your weight bounds
lower_bound = 5
upper_bound = 10

Step 2: Generate All Possible Paths (and Filter Valid Ones) #

A "path" here means selecting one column index per row (since each row represents a node's outgoing edges, the column index corresponds to the next node in the path). We can use Python's itertools.product to generate all possible column index combinations, then filter those whose total weight falls within your bounds.

import itertools

n = adj_matrix.nrows()  # Number of rows (and columns, assuming square matrix)

# Generate all possible column index sequences (one index per row)
all_path_index_combos = itertools.product(range(n), repeat=n)

# Filter to keep only paths with weights in [lower_bound, upper_bound]
valid_paths = []
for indices in all_path_index_combos:
    # Calculate the total weight of the path
    path_weight = sum(adj_matrix[row][col] for row, col in enumerate(indices))
    if lower_bound <= path_weight <= upper_bound:
        # Store both the index sequence and its weight for easy organization later
        valid_paths.append( (indices, path_weight) )

Step 3: Organize the Valid Paths #

You mentioned wanting to organize the paths—here are a few common ways to do that in Sage/Python:

• Sort by path weight:

  # Sort paths from lowest to highest weight
  sorted_by_weight = sorted(valid_paths, key=lambda x: x[1])
  

• Sort lexicographically by index sequence:

  # Sort paths like you would sort words in a dictionary
  sorted_lex = sorted(valid_paths, key=lambda x: x[0])
  

• Extract just the path elements (instead of indices):

  # Get a list of the actual weight values in each valid path
  path_element_lists = [
      [adj_matrix[row][col] for row, col in enumerate(indices)]
      for indices, weight in valid_paths
  ]
  

Optimizing for Larger Matrices #

If your adjacency matrix is large, generating all possible combinations upfront can be slow or use too much memory. A better approach is backtracking with pruning: we build paths row by row, and stop exploring a branch if the current sum already exceeds the upper bound (since adding more weights will only make it larger).

def find_valid_paths_backtrack(matrix, lower, upper):
    n = matrix.nrows()
    valid_paths = []
    
    def backtrack(current_row, current_indices, current_sum):
        # If we've picked an entry from every row, check if the sum is valid
        if current_row == n:
            if lower <= current_sum <= upper:
                valid_paths.append( (tuple(current_indices), current_sum) )
            return
        
        # Try every column in the current row
        for col in range(n):
            new_sum = current_sum + matrix[current_row][col]
            # Prune this branch if the sum already exceeds the upper bound
            if new_sum > upper:
                continue
            # Recurse to the next row
            backtrack(current_row + 1, current_indices + [col], new_sum)
    
    backtrack(0, [], 0)
    return valid_paths

# Use the backtracking function
valid_paths_optimized = find_valid_paths_backtrack(adj_matrix, lower_bound, upper_bound)

A quick note: if your "paths" require additional constraints (like no repeated nodes, which is common in graph theory), you can modify the backtracking function to track visited nodes and skip columns that correspond to already visited nodes.

内容的提问来源于stack exchange，提问作者Travis Black