diff options
Diffstat (limited to 'apps/plugins/puzzles/src/findloop.c')
-rw-r--r-- | apps/plugins/puzzles/src/findloop.c | 31 |
1 files changed, 30 insertions, 1 deletions
diff --git a/apps/plugins/puzzles/src/findloop.c b/apps/plugins/puzzles/src/findloop.c index ffda12d716..4ebdea1f85 100644 --- a/apps/plugins/puzzles/src/findloop.c +++ b/apps/plugins/puzzles/src/findloop.c | |||
@@ -14,7 +14,7 @@ | |||
14 | #include "puzzles.h" | 14 | #include "puzzles.h" |
15 | 15 | ||
16 | struct findloopstate { | 16 | struct findloopstate { |
17 | int parent, child, sibling; | 17 | int parent, child, sibling, component_root; |
18 | bool visited; | 18 | bool visited; |
19 | int index, minindex, maxindex; | 19 | int index, minindex, maxindex; |
20 | int minreachable, maxreachable; | 20 | int minreachable, maxreachable; |
@@ -57,6 +57,33 @@ bool findloop_is_loop_edge(struct findloopstate *pv, int u, int v) | |||
57 | return !(pv[u].bridge == v || pv[v].bridge == u); | 57 | return !(pv[u].bridge == v || pv[v].bridge == u); |
58 | } | 58 | } |
59 | 59 | ||
60 | static bool findloop_is_bridge_oneway( | ||
61 | struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices) | ||
62 | { | ||
63 | int r, total, below; | ||
64 | |||
65 | if (pv[u].bridge != v) | ||
66 | return false; | ||
67 | |||
68 | r = pv[u].component_root; | ||
69 | total = pv[r].maxindex - pv[r].minindex + 1; | ||
70 | below = pv[u].maxindex - pv[u].minindex + 1; | ||
71 | |||
72 | if (u_vertices) | ||
73 | *u_vertices = below; | ||
74 | if (v_vertices) | ||
75 | *v_vertices = total - below; | ||
76 | |||
77 | return true; | ||
78 | } | ||
79 | |||
80 | bool findloop_is_bridge( | ||
81 | struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices) | ||
82 | { | ||
83 | return (findloop_is_bridge_oneway(pv, u, v, u_vertices, v_vertices) || | ||
84 | findloop_is_bridge_oneway(pv, v, u, v_vertices, u_vertices)); | ||
85 | } | ||
86 | |||
60 | bool findloop_run(struct findloopstate *pv, int nvertices, | 87 | bool findloop_run(struct findloopstate *pv, int nvertices, |
61 | neighbour_fn_t neighbour, void *ctx) | 88 | neighbour_fn_t neighbour, void *ctx) |
62 | { | 89 | { |
@@ -94,6 +121,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices, | |||
94 | */ | 121 | */ |
95 | pv[v].sibling = pv[root].child; | 122 | pv[v].sibling = pv[root].child; |
96 | pv[root].child = v; | 123 | pv[root].child = v; |
124 | pv[v].component_root = v; | ||
97 | debug(("%d is new child of root\n", v)); | 125 | debug(("%d is new child of root\n", v)); |
98 | 126 | ||
99 | u = v; | 127 | u = v; |
@@ -116,6 +144,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices, | |||
116 | pv[w].child = -1; | 144 | pv[w].child = -1; |
117 | pv[w].sibling = pv[u].child; | 145 | pv[w].sibling = pv[u].child; |
118 | pv[w].parent = u; | 146 | pv[w].parent = u; |
147 | pv[w].component_root = pv[u].component_root; | ||
119 | pv[u].child = w; | 148 | pv[u].child = w; |
120 | } | 149 | } |
121 | 150 | ||