如何使用Python中的NetworkX库从双向状态机图中绘制所有可能的路径？

Question

我有一个系统的状态机模型，它有一些节点（状态）和一些边缘（转换）。一些转换是双向的。例如，一次从“State_B”到“State_C”的转换，另一个从“State_C”到“State_B”的转换等。因此，据我所知，这称为循环。

现在这是状态机模型的代码：-

import networkx as nx
import matplotlib.pyplot as plt

global CP_Data_In_Coupler_Connected, CP_Data_In_CPState

# Create a directed graph (DiGraph) for the state machine
G = nx.DiGraph()

# Add states to the graph
G.add_node("State_A_Standby")
G.add_node("State_A")
G.add_node("State_B")
G.add_node("State_C")

# Temporary Nodes
Temp_nodes = ["Connection", "Disconnection"]
for temp_node in Temp_nodes:
    G.add_node(temp_node)

# Add transitions between states with edge labels and conditions
G.add_edge("State_A_Standby", "Connection", label="Connection")
G.add_edge("Connection", "State_A", label="Connected vehicle")
G.add_edge("State_A", "State_B", label="Transition to State_B")
G.add_edge("State_B", "State_C", label="Transition to State_C, Switch k ON")
G.add_edge("State_C", "State_B", label="Transition to State_B, Switch k OFF")
G.add_edge("State_B", "State_A", label="Transition to State_A")
G.add_edge("State_C", "State_A", label="Transition to State_A")
G.add_edge("State_A", "Disconnection", label="Disconnect")
G.add_edge("State_B", "Disconnection", label="Disconnect")
G.add_edge("State_C", "Disconnection", label="Disconnect")
G.add_edge("Disconnection", "State_A_Standby", label="Disconnected vehicle")

# Draw the state machine diagram
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, with_labels=True, node_size=1500, node_color='skyblue', font_size=10, font_weight='bold')
edge_labels = nx.get_edge_attributes(G, 'label')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8)
plt.show()

所以，你可以在Python中运行这段代码。它将显示状态机图。

现在在这里，正如您所看到的，两个相同节点（例如“State_B”和“State_C”）之间存在一些边，以及“State_C”到“State_A”之间的边。

因此，在这个状态机模型中可能存在一些循环和循环。

我想从“State_A”和“Disconnect”节点之间的状态机生成所有可能的路径。

我尝试了下面的代码来生成每条路径，但它只生成只有单向方向的路径。但它不包括循环和循环。

all_possible_paths = []
# Using the inbuilt-function
all_paths = nx.all_simple_paths(G, source="State_A_Standby", target="Disconnection")
for path in all_paths:
    # Check if "Disconnection" is the end node
    if path[-1] == "Disconnection":
        # Replace "Disconnection" with the first node in the path
        path[-1] = path[0]

    # Remove temp nodes
    path = [node for node in path if node not in Temp_nodes]
    all_possible_paths.append(path)
    print("Processed Path:", path)

如果您可以看到这段代码的输出。您会看到它不包括所有边缘。一些边缘仍未包含在这些路径中。

那么，有人可以帮我吗？

Answer 1

Yen 算法 https://en.wikipedia.org/wiki/Yen%27s_algorithm 将为您提供源节点和目标节点之间的每条路径。

也许你的库有一个方法可以实现这个？

不幸的是，维基百科文章的伪代码存在错误和含糊之处。所以自己推出并不那么容易。

仅供参考，这是我自己的 Yen 算法的伪代码

IMPORT graph, source and sink
CLEAR vShortestPaths
calculate shortest path from source to sink, add to vShortestPaths
WHILE TRUE
   CLEAR vPotentialPaths
   SET work = graph
   LOOP PF over vShortestPaths
       LOOP spur over PF
            REMOVE out edge from spur in work used by PF
            calculate spurPath, shortest path from spur to sink in work
            IF spurPath exists
                CONTINUE to next iteration of LOOP spur
            SET newPath to combination of source to spur in PF and spurPath
            IF newPath NOT in vShortestPaths
                ADD newPath to vPotentialPaths
            END LOOP spur
        END LOOP PF
    IF vPotentialPaths NOT empty
        ADD shortest path in vPotentialPaths to vShortestPaths
    END WHILE TRUE  

我的C++实现可以在这里找到https://github.com/JamesBremner/PathFinder/blob/ee27d2393c0bb2700eba8198d4a4043124c63617/src/GraphTheory.cpp#L157-L220