Return a suitable starting vertex for an Eulerian path. If no path exists, return None.
(G)
| 85 | |
| 86 | |
| 87 | def _find_path_start(G): |
| 88 | """Return a suitable starting vertex for an Eulerian path. |
| 89 | |
| 90 | If no path exists, return None. |
| 91 | """ |
| 92 | if not has_eulerian_path(G): |
| 93 | return None |
| 94 | |
| 95 | if is_eulerian(G): |
| 96 | return arbitrary_element(G) |
| 97 | |
| 98 | if G.is_directed(): |
| 99 | v1, v2 = (v for v in G if G.in_degree(v) != G.out_degree(v)) |
| 100 | # Determines which is the 'start' node (as opposed to the 'end') |
| 101 | if G.out_degree(v1) > G.in_degree(v1): |
| 102 | return v1 |
| 103 | else: |
| 104 | return v2 |
| 105 | |
| 106 | else: |
| 107 | # In an undirected graph randomly choose one of the possibilities |
| 108 | start = [v for v in G if G.degree(v) % 2 != 0][0] |
| 109 | return start |
| 110 | |
| 111 | |
| 112 | def _simplegraph_eulerian_circuit(G, source): |
no test coverage detected
searching dependent graphs…