method for finding interesting edge subsets
Here we develop general methods for finding all subsets in a family of subsets of graph elements. For example, these families could be simple cycles, cycles, simple paths, or paths.
Define a function of element (vertex or edge) such that we can prove that will return all solutions that contain and no solutions that contain . You can easily see that evaluating for each in the graph, we will obtain all solutions with no repeated solutions.
The challenge now is to find that satisfies the above.
Here is an attempt to write out these ideas using mathematical notation:
THEOREM
If where and is the set of all solutions, then and .
PROOF
END
Depth First Search
Here we define a function that will serve as a recursive component of using a depth-first-search algorithm.
ALGORITHM
for each e in E
g(e, e, {e}, f1, f2)
switch the temporary direction of e
g(e, e, {e}, f1, f2)
where f1 and f2 are specific to the type of feature we are looking for, see below, and g is
function g(e0, e, Q, f1, f2)
e is an edge that temporarily points from v0 to v1
Q is a sequence of edges. Q contains e.
for each edge e1 adjacent to v1
if Q contains e1 then continue
add e1 to the end of Q
orient e1 such that its tail is at v1
add f1(e0, e1, Q) to S
if f2(e0, e1, Q) evaluates true then
g(e0, e1, Q, f1, f2)
remove e from the end of Q
cycles
We define the functions and for finding cycles using the above DFS algorithm
function f1(e0, e1, Q)
if e1 < e0 then return
if tail(e0) == head(e1) then
Q is a cycle, add it to the return set
and
function f2(e0, e1, Q)
if(e1 < e0) then
return false
else
return true