cider.data_structures.relational_graph.RelationalGraph Class Reference
Public Member Functions | |
| __init__ (self, ConfigurationHandler config_handler) | |
| NDArray | adjacency_matrix (self) |
| top_level_nodes (self) | |
Protected Attributes | |
| _handler = config_handler | |
| _adjacency_matrix = np.zeros((self._handler.n_dals, self._handler.n_dals)) | |
Private Member Functions | |
| __generate_adjacency_matrix (self) | |
Detailed Description
Definition at line 18 of file relational_graph.py.
Constructor & Destructor Documentation
◆ __init__()
| cider.data_structures.relational_graph.RelationalGraph.__init__ | ( | self, | |
| ConfigurationHandler | config_handler ) |
Definition at line 19 of file relational_graph.py.
19 def __init__(self, config_handler: ConfigurationHandler):
20 self._handler = config_handler
21
22 self.__generate_adjacency_matrix()
23
Member Function Documentation
◆ __generate_adjacency_matrix()
|
private |
Generates adjacency matrix from configuration handler object i.e. finds connected DALs
Definition at line 24 of file relational_graph.py.
24 def __generate_adjacency_matrix(self):
25 """Generates adjacency matrix from configuration handler object i.e. finds connected DALs
26 """
27 self._adjacency_matrix = np.zeros((self._handler.n_dals, self._handler.n_dals))
28
29 for i, dal in enumerate(self._handler.conf_obj_list):
30 for connection_category in self._handler.get_relationships_for_conf_object(dal):
31 # Allows for multiply connected nodes
32 for connection in list(connection_category.values())[0]:
33 # Loop over just conf objects
34 self._adjacency_matrix[i][self._handler.conf_obj_list.index(connection)] += 1
35
◆ adjacency_matrix()
| NDArray cider.data_structures.relational_graph.RelationalGraph.adjacency_matrix | ( | self | ) |
Definition at line 37 of file relational_graph.py.
37 def adjacency_matrix(self)->NDArray:
38 return self._adjacency_matrix
39
◆ top_level_nodes()
| cider.data_structures.relational_graph.RelationalGraph.top_level_nodes | ( | self | ) |
Definition at line 41 of file relational_graph.py.
41 def top_level_nodes(self):
42 # Means we automatically rebuild the graph, this is inefficient but vaguely fine
43 self.__generate_adjacency_matrix()
44 return [dal for i, dal in enumerate(self._handler.conf_obj_list) if np.all(self.adjacency_matrix[i])==0]
45
46
47'''
48HW: Leaving here for now for posterity, this is a great way to organise a FIXED configuration
49but is horribly slow for constant updates
50
51class RelationalGraph:
52 def __init__(self, config_handler: ConfigurationHandler):
53 """Construct relational graph
54
55 Arguments:
56 config_handler -- ConfigurationHandler object
57 """
58
59 # Configuration handler
60 self._handler = config_handler
61 self.generate_graph()
62
63 def generate_graph(self):
64 # Matrices etc. we require [maybe don't need to be defined at the constructor level, could be
65 # class methods]
66 self._topological_ordered_matrix = np.array([[]])
67
68 # Adjacency matrix has 1 for direct connection, 0 for no connection
69 self._adjacency_matrix = np.zeros((self._handler.n_dals, self._handler.n_dals))
70 # Maximum distance from the "top level" to a given node
71 self._max_distance = np.zeros(self._handler.n_dals)-np.inf
72
73 # Generate the graph
74 self.__generate_adjacency_matrix()
75 # Sort topologically and get longest paths
76 self.__calculate_longest_paths()
77
78
79 def __generate_adjacency_matrix(self):
80 """Generates adjacency matrix from configuration handler object i.e. finds connected DALs
81 """
82 for i, dal in enumerate(self._handler.conf_obj_list):
83 for connection_category in self._handler.get_relationships_for_conf_object(dal):
84 # Allows for multiply connected nodes
85 for connection in list(connection_category.values())[0]:
86 # Loop over just conf objects
87 self._adjacency_matrix[i][self._handler.conf_obj_list.index(connection)] += 1
88
89
90 def __compute_degree(self):
91 """Get number of incoming nodes for each node"""
92 return np.sum(self._adjacency_matrix !=0, axis=0)
93
94 def __get_topological_order(self):
95 """
96 Topological sort of the adjacency graph
97
98 Algorithm implementation roughly based on: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
99
100 """
101 in_degree = self.__compute_degree()
102 queue = deque(np.where(in_degree == 0)[0])
103 topological_ordering = []
104
105 while queue:
106 node = queue.popleft()
107 # Add node to topological ordering
108 topological_ordering.append(node)
109 # Check out going edges
110 outgoing_edges = np.where(self._adjacency_matrix != 0)[0]
111 # Reduce the number of incoming edges for each outgoing edge
112 in_degree[outgoing_edges] -= 1
113 # Change the number of nodes with no outgoing edges
114 zero_in_degree_nodes = outgoing_edges[in_degree[outgoing_edges] == 0]
115 # Add to the queue
116 queue.extend(zero_in_degree_nodes)
117
118 return topological_ordering
119
120 def __update_distances(self, distance: NDArray, node_id: int):
121 """Update maximum distance to each node
122
123 Arguments:
124 distance -- List of distancezs to each node
125 node_id -- ID of a node
126 """
127 outgoing_edges = np.where(self._adjacency_matrix[node_id] != 0)[0]
128 distance[outgoing_edges] = np.maximum(distance[outgoing_edges], distance[node_id] + self._adjacency_matrix[node_id][outgoing_edges])
129
130 def __longest_path(self, start_id: int):
131 """Calculate the longest path in a DAG from the start node."""
132 dist = np.full(self._handler.n_dals, -np.inf)
133 dist[start_id] = 0
134
135 for u in self._topological_ordered_matrix:
136 if dist[u] != -np.inf:
137 self.__update_distances(dist, u)
138 return dist
139
140 def __calculate_longest_paths(self)->None:
141 """
142 Idea is to find shortest paths on -G for each top level node where G is the connection graph.
143 Layer each item lives on is then simply max(longest_path) for each top level item
144 """
145
146 self._topological_ordered_matrix = self.__get_topological_order()
147 for node_id in range(self._handler.n_dals):
148 self._max_distance = np.maximum(self._max_distance, self.__longest_path(node_id))
149
150 self._max_distance = self._max_distance.astype(int)
151
152 def add_node(self, node_dal):
153 pass
154
155 def remove_node(self, node_dal):
156 pass
157
158 @property
159 def top_level_nodes(self):
160 # Means we automatically rebuild the graph
161 if len(self._max_distance!=len(self._handler.conf_obj_list)):
162 self.generate_graph()
163
164 return [dal for i, dal in enumerate(self._handler.conf_obj_list) if self._max_distance[i]==0]
165'''
Member Data Documentation
◆ _adjacency_matrix
|
protected |
Definition at line 27 of file relational_graph.py.
◆ _handler
|
protected |
Definition at line 20 of file relational_graph.py.
The documentation for this class was generated from the following file:
- /github/workspace/dunedaq/sourcecode/daqconf/python/daqconf/cider/data_structures/relational_graph.py
Generated on Sat Jun 28 2025 for DUNE-DAQ by
1.12.0