| 171 | |
| 172 | |
| 173 | class DiGraph(Graph): |
| 174 | def __init__(self, V, E): |
| 175 | """ |
| 176 | A generic directed graph object. |
| 177 | |
| 178 | Parameters |
| 179 | ---------- |
| 180 | V : list |
| 181 | A list of vertex IDs. |
| 182 | E : list of :class:`Edge <numpy_ml.utils.graphs.Edge>` objects |
| 183 | A list of directed edges connecting pairs of vertices in ``V``. |
| 184 | """ |
| 185 | super().__init__(V, E) |
| 186 | self.is_directed = True |
| 187 | self._topological_ordering = [] |
| 188 | |
| 189 | def _build_adjacency_list(self): |
| 190 | """Encode directed graph as an adjancency list""" |
| 191 | # assumes no parallel edges |
| 192 | for e in self.edges: |
| 193 | fr_i = self._V2I[e.fr] |
| 194 | self._G[fr_i].add(e) |
| 195 | |
| 196 | def reverse(self): |
| 197 | """Reverse the direction of all edges in the graph""" |
| 198 | return DiGraph(self.vertices, [e.reverse() for e in self.edges]) |
| 199 | |
| 200 | def topological_ordering(self): |
| 201 | """ |
| 202 | Returns a (non-unique) topological sort / linearization of the nodes |
| 203 | IFF the graph is acyclic, otherwise returns None. |
| 204 | |
| 205 | Notes |
| 206 | ----- |
| 207 | A topological sort is an ordering on the nodes in `G` such that for every |
| 208 | directed edge :math:`u \\rightarrow v` in the graph, `u` appears before |
| 209 | `v` in the ordering. The topological ordering is produced by ordering |
| 210 | the nodes in `G` by their DFS "last visit time," from greatest to |
| 211 | smallest. |
| 212 | |
| 213 | This implementation follows a recursive, DFS-based approach [1]_ which |
| 214 | may break if the graph is very large. For an iterative version, see |
| 215 | Khan's algorithm [2]_ . |
| 216 | |
| 217 | References |
| 218 | ---------- |
| 219 | .. [1] Tarjan, R. (1976), Edge-disjoint spanning trees and depth-first |
| 220 | search, *Acta Informatica, 6 (2)*: 171–185. |
| 221 | .. [2] Kahn, A. (1962), Topological sorting of large networks, |
| 222 | *Communications of the ACM, 5 (11)*: 558–562. |
| 223 | |
| 224 | Returns |
| 225 | ------- |
| 226 | ordering : list or None |
| 227 | A topoligical ordering of the vertex indices if the graph is a DAG, |
| 228 | otherwise None. |
| 229 | """ |
| 230 | ordering = [] |
no outgoing calls