milahu
commented
1 year ago abandoned draft for topo_sort in cmake
- [x] strongly_connected_components
- [x] simple_cycles (90% done)
- [ ] topo_sort
```cmake
cmake_minimum_required(VERSION 3.22)
project(function_topo_sort)
function(quote_string output_name str)
string(REPLACE "\\" "\\\\" str "${str}") # escape \ -> \\
string(REPLACE "\"" "\\\"" str "${str}") # escape " -> \"
set(str "\"${str}\"") # wrap string in quotes
set(${output_name} "${str}" PARENT_SCOPE)
endfunction()
# list of lists
# Nested list support is thoroughly broken
# https://gitlab.kitware.com/cmake/cmake/-/issues/17565
function(deque_create name)
# TODO error if exists
set(__deque__${name}__size 0 PARENT_SCOPE)
set(__deque__${name}__start 0 PARENT_SCOPE)
set(__deque__${name}__end -1 PARENT_SCOPE)
endfunction()
# TODO function(deque_delete name)
function(deque_push_back name value)
# size + 1
MATH(EXPR new_size "${__deque__${name}__size}+1")
set(__deque__${name}__size ${new_size} PARENT_SCOPE)
# end + 1
MATH(EXPR new_end "${__deque__${name}__end}+1")
set(__deque__${name}__end ${new_end} PARENT_SCOPE)
# set value
set(__deque__${name}__value__${new_end} ${value} PARENT_SCOPE)
endfunction()
function(deque_push_front name value)
# size + 1
MATH(EXPR new_size "${__deque__${name}__size}+1")
set(__deque__${name}__size ${new_size} PARENT_SCOPE)
# start - 1
MATH(EXPR new_start "${__deque__${name}__start}-1")
set(__deque__${name}__start ${new_start} PARENT_SCOPE)
# set value
set(__deque__${name}__value__${new_start} ${value} PARENT_SCOPE)
endfunction()
function(deque_get name key result_name)
set(${result_name})
if(${__deque__${name}__size} EQUAL 0)
return() # deque is empty
endif()
# validate key
if(${key} LESS ${__deque__${name}__start} OR ${key} GREATER ${__deque__${name}__end})
message(FATAL_ERROR "out of bound. key=${key} min=${__deque__${name}__start} max=${__deque__${name}__end}")
return()
endif()
set(${result_name} ${__deque__${name}__value__${key}} PARENT_SCOPE)
endfunction()
# get + remove last value
function(deque_pop_back name result_name)
set(${result_name})
if(${__deque__${name}__size} EQUAL 0)
return() # deque is empty
endif()
set(key ${__deque__${name}__end})
set(${result_name} ${__deque__${name}__value__${key}} PARENT_SCOPE)
set(__deque__${name}__value__${key} PARENT_SCOPE) # unset value
# size - 1
MATH(EXPR new_size "${__deque__${name}__size}-1")
set(__deque__${name}__size ${new_size} PARENT_SCOPE)
# end - 1
MATH(EXPR new_end "${__deque__${name}__end}-1")
set(__deque__${name}__end ${new_end} PARENT_SCOPE)
endfunction()
# get + remove first value
function(deque_pop_front name result_name)
set(${result_name})
if(${__deque__${name}__size} EQUAL 0)
return() # deque is empty
endif()
set(key ${__deque__${name}__start})
set(${result_name} ${__deque__${name}__value__${key}} PARENT_SCOPE)
set(__deque__${name}__value__${key} PARENT_SCOPE) # unset value
# size - 1
MATH(EXPR new_size "${__deque__${name}__size}-1")
set(__deque__${name}__size ${new_size} PARENT_SCOPE)
# start + 1
MATH(EXPR new_start "${__deque__${name}__start}+1")
set(__deque__${name}__start ${new_start} PARENT_SCOPE)
endfunction()
function(deque_size name result_name)
set(${result_name} ${__deque__${name}__size} PARENT_SCOPE)
endfunction()
function(deque_front name result_name)
deque_get(${name} ${__deque__${name}__start} value)
set(${result_name} ${value} PARENT_SCOPE)
endfunction()
function(deque_back name result_name)
deque_get(${name} ${__deque__${name}__end} value)
set(${result_name} ${value} PARENT_SCOPE)
endfunction()
function(deque_keys name result_name)
set(result)
if(${__deque__${name}__size} EQUAL 0)
return()
endif()
foreach(key RANGE ${__deque__${name}__start} ${__deque__${name}__end})
list(APPEND result ${key})
endforeach()
set(${result_name} ${result} PARENT_SCOPE)
endfunction()
function(deque_print name)
deque_keys(${name} keys)
foreach(key ${keys})
deque_get(${name} ${key} value)
#message("deque_print: name=${name}, key=${key}, value=${value}")
message("${name}.${key} = ${value}")
endforeach()
endfunction()
function(deque_print_value name key)
deque_get(${name} ${key} value)
message("${name}.${key} = ${value}")
endfunction()
function(deque_to_json name result_json_name)
deque_keys(${name} keys)
set(result_json "[]")
foreach(key ${keys})
# FIXME deque keys can be negative
# json keys should be 0 1 2 3 ...
deque_get(${name} ${key} value)
# workaround for missing string(JSON ... SET_STRING ...)
# https://gitlab.kitware.com/cmake/cmake/-/issues/23750
quote_string(value "${value}")
#message("deque_to_json: name=${name}, key=${key}, value=${value}")
string(JSON result_json
ERROR_VARIABLE json_error
SET "${result_json}" "${key}" "${value}"
)
if(NOT json_error STREQUAL "NOTFOUND")
message(FATAL_ERROR "deque_to_json: failed to set json idx ${key}: ${json_error}")
endif()
#message("deque_to_json: result_json = ${result_json}")
endforeach()
set(${result_json_name} ${result_json} PARENT_SCOPE)
endfunction()
if(FALSE)
# test deque
deque_create(test)
message("empty deque:")
deque_print(test)
deque_push_back(test "a;a;a")
message("deque 1 value:")
deque_print(test)
deque_push_back(test "b;b;b")
message("deque 2 values:")
deque_print(test)
deque_push_front(test "z;z;z")
message("deque 3 values:")
deque_print(test)
deque_front(test value)
message("front = ${value}")
deque_back(test value)
message("back = ${value}")
deque_print_value(test -1)
deque_print_value(test 0)
deque_print_value(test 1)
#deque_print_value(test 2) # error: out of bound
endif()
function(map_create name)
# TODO error if exists
set(__map__${name}__keys PARENT_SCOPE)
endfunction()
function(map_set name key value)
# set value
set(__map__${name}__value__${key} ${value} PARENT_SCOPE)
list(FIND __map__${name}__keys ${key} old_key_idx)
if(${old_key_idx} GREATER -1) # key exists
return()
endif()
# add key
list(APPEND __map__${name}__keys ${key})
set(__map__${name}__keys ${__map__${name}__keys} PARENT_SCOPE)
endfunction()
function(map_get name key result_name)
# TODO check if key exists
set(${result_name} ${__map__${name}__value__${key}} PARENT_SCOPE)
endfunction()
function(map_keys name result_name)
set(${result_name} ${__map__${name}__keys} PARENT_SCOPE)
endfunction()
function(map_size name result_name)
list(LENGTH __map__${name}__keys size)
set(${result_name} ${size} PARENT_SCOPE)
endfunction()
function(map_remove name key)
# remove key
list(REMOVE_ITEM __map__${name}__keys ${key})
set(__map__${name}__keys ${__map__${name}__keys} PARENT_SCOPE)
# remove value
set(${__map__${name}__value__${key}} PARENT_SCOPE)
endfunction()
function(map_print name)
map_keys(${name} keys)
foreach(key ${keys})
map_get(${name} ${key} value)
message("${name}.${key} = ${value}")
endforeach()
endfunction()
if(FALSE)
# test map
map_create(test)
message("empty map:")
map_print(test)
map_set(test a "a;a;a")
map_size(test size)
message("map with ${size} values:")
map_print(test)
map_set(test b "b;b;b")
map_size(test size)
message("map with ${size} values:")
map_print(test)
endif()
#[==[
# test list fns
set(somelist "a;b;c")
list(LENGTH somelist somelist_length)
message("somelist_length = ${somelist_length}")
list(FIND somelist b value_idx)
message("b: value_idx = ${value_idx}")
list(FIND somelist z value_idx)
message("z: value_idx = ${value_idx}")
#message(FATAL_ERROR todo)
]==]
#[==[
# workaround for "bug" in foreach
# foreach(idx RANGE -1) should not enter loop
message("loop 1")
foreach(idx RANGE -1)
message("idx = ${idx}")
endforeach()
message("")
message("loop 2")
foreach(idx RANGE 0 -1 1)
message("idx = ${idx}")
endforeach()
message(FATAL_ERROR todo)
]==]
message("topo_sort ...")
function(strongly_connected_components graph_json result_json_name)
# Generate nodes in strongly connected components of graph
# https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.strongly_connected_components.html
# TODO filter graph to remove extra edges
#preorder = dict()
map_create(preorder)
#lowlink = dict()
map_create(lowlink)
#scc_found = set()
map_create(scc_found)
#scc_queue = list()
deque_create(scc_queue)
# return by value instead of "yield scc"
deque_create(result_deque)
#i = 0
set(i 0) # Preorder counter
#neighbors = {v: iter(G[v]) for v in G}
#map_create(neighbors) # dict()
#for source in G:
message("strongly_connected_components: graph_json = ${graph_json}")
string(JSON last_source_idx LENGTH "${graph_json}")
math(EXPR last_source_idx "${last_source_idx}-1")
foreach(source_idx RANGE 0 ${last_source_idx} 1)
string(JSON source MEMBER "${graph_json}" ${source_idx})
message("strongly_connected_components: source=${source}")
#if source not in scc_found:
map_get(scc_found ${source} source_in_scc_found)
message("strongly_connected_components: source_in_scc_found=${source_in_scc_found}")
if(NOT source_in_scc_found)
message("strongly_connected_components: NOT source_in_scc_found")
#queue = [source]
set(queue ${source})
#while queue:
list(LENGTH queue queue_length)
while(${queue_length} GREATER 0)
message("strongly_connected_components: queue=${queue}")
message("strongly_connected_components: queue_length=${queue_length}")
#v = queue[-1]
list(GET queue -1 v)
message("strongly_connected_components: v=${v}")
#if v not in preorder:
map_get(preorder ${v} v_in_preorder)
message("strongly_connected_components: v_in_preorder=${v_in_preorder}")
if(NOT v_in_preorder)
message("strongly_connected_components: NOT v_in_preorder")
#i = i + 1
math(EXPR i "${i} + 1")
#preorder[v] = i
map_set(preorder ${v} ${i})
endif()
#done = True
set(done TRUE)
#for w in neighbors[v]:
message("strongly_connected_components: graph_json = ${graph_json}")
message("strongly_connected_components: queue = ${queue}")
message("strongly_connected_components: v = ${v}")
string(JSON last_w_idx ERROR_VARIABLE json_error LENGTH "${graph_json}" "${v}")
if(NOT json_error STREQUAL "NOTFOUND")
# value was not found
# extra edge: target-node of edge is not a source-node in graph
#queue.pop()
list(POP_BACK queue)
# update loop counter
list(LENGTH queue queue_length)
continue()
endif()
math(EXPR last_w_idx "${last_w_idx}-1")
message("strongly_connected_components: last_w_idx = ${last_w_idx}")
if(${last_w_idx} GREATER -1)
foreach(w_idx RANGE 0 ${last_w_idx} 1)
message("strongly_connected_components: w_idx = ${w_idx}")
# object
#string(JSON w_key MEMBER "${graph_json}" "${v}" ${w_idx})
#string(JSON w GET "${graph_json}" "${v}" ${w_key})
# array
string(JSON w GET "${graph_json}" "${v}" ${w_idx})
message("strongly_connected_components: w=${w}")
#if w not in preorder:
map_get(preorder ${w} w_in_preorder)
if(NOT w_in_preorder)
#queue.append(w)
list(APPEND queue ${w})
#done = False
set(done FALSE)
#break
break()
endif()
endforeach()
endif()
#if done:
if(${done})
#lowlink[v] = preorder[v]
map_get(preorder ${v} preorder_of_v)
map_set(lowlink ${v} ${preorder_of_v})
message("strongly_connected_components: preorder_of_v = ${preorder_of_v}")
#for w in G[v]:
string(JSON len LENGTH "${graph_json}" "${v}")
if(${len} GREATER 0)
math(EXPR last_w_idx "${len}-1")
foreach(w_idx RANGE 0 ${last_w_idx} 1)
string(JSON w GET "${graph_json}" "${v}" ${w_idx})
message("strongly_connected_components: v = ${v}")
message("strongly_connected_components: w = ${w}")
#if w not in scc_found:
map_get(scc_found "${w}" w_in_scc_found)
if(NOT scc_found)
#if preorder[w] > preorder[v]:
map_get(lowlink ${w} lowlink_w)
message("strongly_connected_components: lowlink_w = ${lowlink_w}")
if(lowlink_w) # wrong???
message("strongly_connected_components: lowlink_w is set. lowlink_w=${lowlink_w}, w=${w}, lowlink_v=${lowlink_v}, v=${v}")
else()
message("strongly_connected_components: lowlink_w is unset. lowlink_w=${lowlink_w}, w=${w}, lowlink_v=${lowlink_v}, v=${v}")
endif()
#if(lowlink_w) # FIXME wrong???
# extra edge
# lowlink_w is empty when the target-node of the edge
# is not a source-node in the graph
message("strongly_connected_components: lowlink_w is set. lowlink_w=${lowlink_w}, w=${w}, lowlink_v=${lowlink_v}, v=${v}")
map_get(preorder ${v} preorder_v)
map_get(preorder ${w} preorder_w)
map_get(lowlink ${v} lowlink_v)
#[[
message("strongly_connected_components: preorder_v = ${preorder_v}")
message("strongly_connected_components: preorder_w = ${preorder_w}")
message("strongly_connected_components: lowlink_v = ${lowlink_v}")
message("strongly_connected_components: lowlink_w = ${lowlink_w}")
]]
if(${preorder_w} GREATER ${preorder_v})
#lowlink[v] = min([lowlink[v], lowlink[w]])
if(${lowlink_w} LESS ${lowlink_v})
set(lowlink_v ${lowlink_w})
endif()
map_set(lowlink ${v} ${lowlink_v})
#else:
else()
#lowlink[v] = min([lowlink[v], preorder[w]])
if(${preorder_w} LESS ${lowlink_v})
set(lowlink_v ${preorder_w})
endif()
map_set(lowlink ${v} ${lowlink_v})
endif()
endif()
endforeach()
endif()
#queue.pop()
list(POP_BACK queue)
#if lowlink[v] == preorder[v]:
message("strongly_connected_components: v = ${v}")
map_get(preorder ${v} preorder_v)
map_get(lowlink ${v} lowlink_v)
if(${lowlink_v} EQUAL ${preorder_v})
#scc = {v} # == set(v)
set(scc ${v})
message("strongly_connected_components: scc = ${scc}")
#while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
deque_size(scc_queue scc_queue_size)
deque_back(scc_queue scc_queue_last) # scc_queue[-1]
map_get(preorder ${scc_queue_last} preorder_scc_queue_last) # preorder[scc_queue[-1]]
while(${scc_queue_size} GREATER 0 AND ${preorder_scc_queue_last} GREATER ${preorder_v})
#k = scc_queue.pop()
message("strongly_connected_components: scc_queue_size = ${scc_queue_size}")
message("strongly_connected_components: scc_queue_last = ${scc_queue_last}")
message("strongly_connected_components: scc_queue:")
deque_print(scc_queue)
deque_pop_back(scc_queue k)
#scc.add(k)
message("strongly_connected_components: scc append: k = ${k}")
list(APPEND scc ${k})
deque_size(scc_queue scc_queue_size)
deque_back(scc_queue scc_queue_last) # scc_queue[-1]
endwhile()
#scc_found.update(scc)
foreach(k ${scc})
map_set(scc_found ${k} TRUE)
endforeach()
#yield scc
#message("strongly_connected_components: result_deque_name = ${result_deque_name}")
#message("strongly_connected_components: yield: scc = ${scc}")
#deque_push_back(${result_deque_name} ${scc})
deque_push_back(result_deque "${scc}")
#else:
else()
#scc_queue.append(v)
deque_push_back(scc_queue ${v})
endif()
endif()
list(LENGTH queue queue_length)
endwhile()
endif()
endforeach()
# debug
message("strongly_connected_components: result_deque:")
deque_print(result_deque)
# return
# TODO return json
deque_to_json(result_deque result_json)
set(${result_json_name} ${result_json} PARENT_SCOPE)
if(FALSE)
set(__deque__${result_deque_name}__size ${__deque__result_deque__size} PARENT_SCOPE)
set(__deque__${result_deque_name}__start ${__deque__result_deque__start} PARENT_SCOPE)
set(__deque__${result_deque_name}__end ${__deque__result_deque__end} PARENT_SCOPE)
deque_keys(result_deque keys)
foreach(key ${keys})
deque_get(result_deque ${key} value)
#message("strongly_connected_components: result[${key}] = ${value}")
set(__deque__${result_deque_name}__value__${key} "${value}" PARENT_SCOPE)
endforeach()
endif()
endfunction()
#[====[ loop json object
set(json_str [[ {"a": 1, "b": 2} ]])
string(JSON len LENGTH ${json_str})
math(EXPR last_idx "${len}-1")
foreach(idx RANGE ${last_idx})
string(JSON key MEMBER ${json_str} ${idx})
string(JSON val GET ${json_str} ${key})
message("json.${key} = ${val}")
endforeach()
]====]
function(simple_cycles graph_json result_json_name)
# Find simple cycles (elementary circuits) of a directed graph.
# https://networkx.org/documentation/stable/_modules/networkx/algorithms/cycles.html#simple_cycles
set(${result_json_name} "[]")
# TODO
#def _unblock(thisnode, blocked, B):
# stack = {thisnode}
# while stack:
# node = stack.pop()
# if node in blocked:
# blocked.remove(node)
# stack.update(B[node])
# B[node].clear()
# Johnson's algorithm requires some ordering of the nodes.
# We assign the arbitrary ordering given by the strongly connected comps
# There is no need to track the ordering as each node removed as processed.
# Also we save the actual graph so we can mutate it. We only take the
# edges because we do not want to copy edge and node attributes here.
#subG = type(G)(G.edges())
# this is a noop?
#sccs = [scc for scc in nx.strongly_connected_components(subG) if len(scc) > 1]
# all_sccs_json: all sccs
# sccs_json: sccs with length > 1
message("simple_cycles: graph_json = ${graph_json}")
strongly_connected_components("${graph_json}" all_sccs_json)
message("simple_cycles: all_sccs_json = ${all_sccs_json}")
set(sccs_json "[]")
string(JSON length LENGTH "${all_sccs_json}")
math(EXPR last_idx "${length}-1")
foreach(idx RANGE 0 ${last_idx} 1)
string(JSON scc GET "${all_sccs_json}" ${idx})
list(LENGTH scc scc_length)
if(scc_length GREATER 1)
string(JSON sccs_json_length LENGTH "${sccs_json}")
quote_string(scc "${scc}")
string(JSON sccs_json SET "${sccs_json}" ${sccs_json_length} "${scc}")
endif()
endforeach()
message("simple_cycles: sccs_json = ${sccs_json}")
#message(FATAL_ERROR todo)
if("${sccs_json}" STREQUAL "[]")
return()
endif()
# TODO
#[[
# Johnson's algorithm exclude self cycle edges like (v, v)
# To be backward compatible, we record those cycles in advance
# and then remove from subG
for v in subG:
if subG.has_edge(v, v):
yield [v]
subG.remove_edge(v, v)
]]
#while sccs:
# TODO while -> foreach
string(JSON sccs_length LENGTH "${sccs_json}")
while(sccs_length GREATER 0)
#scc = sccs.pop()
math(EXPR last_idx "${sccs_length}-1")
string(JSON scc GET "${sccs_json}" ${last_idx})
string(JSON sccs_json REMOVE "${sccs_json}" ${last_idx})
message("scc = ${scc}")
#sccG = subG.subgraph(scc)
# TODO
set(scc_graph_json "{}")
# loop keys of scc
#string(JSON scc_graph_json SET "${scc_graph_json}" "${key}" "${value}")
foreach(scc_node ${scc})
message("scc_node = ${scc_node}")
string(JSON scc_graph_json SET "${scc_graph_json}" "${scc_node}" "[]")
set(edge_idx 0)
# get node from graph
# filter edges of node, add to scc_graph_json
# get intersection of lists: scc n all_edges
string(JSON all_edges_json GET "${graph_json}" "${scc_node}")
message("all_edges_json = ${all_edges_json}")
foreach(scc_edge ${scc})
message("scc_edge = ${scc_edge}")
#[[ all_edges is semicolon list
list(FIND all_edges "${scc_edge}" found_idx)
# TODO find scc_edge in all_edges_json
message("found_idx = ${found_idx}")
if(NOT found_idx EQUAL -1)
# found in both
quote_string(value "${scc_edge}")
string(JSON scc_graph_json SET "${scc_graph_json}" "${scc_node}" ${edge_idx} "${value}")
math(EXPR edge_idx "${edge_idx}+1")
endif()
]]
# all_edges is json list
# loop all edges of scc_node
string(JSON len LENGTH "${graph_json}" "${scc_node}")
if(len GREATER 0)
math(EXPR last_idx "${len}-1")
foreach(idx RANGE 0 ${last_idx} 1)
# get value
string(JSON graph_edge GET "${graph_json}" "${scc_node}" ${idx})
if(graph_edge STREQUAL scc_edge)
# found in both
quote_string(value "${scc_edge}")
string(JSON scc_graph_json SET "${scc_graph_json}" "${scc_node}" ${edge_idx} "${value}")
math(EXPR edge_idx "${edge_idx}+1")
endif()
endforeach()
endif()
endforeach()
endforeach()
message("scc_graph_json = ${scc_graph_json}")
#message(FATAL_ERROR todo)
# order of scc determines ordering of nodes
#startnode = scc.pop()
list(POP_BACK scc startnode)
# Processing node runs "circuit" routine from recursive version
#path = [startnode]
#set(path ${startnode}) # TODO list -> json list
#set(path ${startnode}) # TODO list -> json list
set(path_json "[]")
quote_string(value "${startnode}")
string(JSON path_json SET "${path_json}" 0 "${value}")
set(result_json "[]")
#blocked = set() # vertex: blocked from search?
#blocked.add(startnode)
#set(blocked "${startnode}")
map_create(blocked_map)
map_set(blocked_map "${startnode}" TRUE)
#closed = set() # nodes involved in a cycle
#set(closed "")
map_create(closed_map)
#B = defaultdict(set) # graph portions that yield no elementary circuit
# TODO ???
map_create(Blocked_map)
#stack = [(startnode, list(sccG[startnode]))] # sccG gives comp nbrs
# tuples: (node, neighbors)
set(stack_json "[]")
string(JSON stack_json SET "${stack_json}" 0 "[]")
quote_string(startnode_json "${startnode}")
string(JSON stack_json SET "${stack_json}" 0 0 "${startnode_json}")
string(JSON nbrs GET "${scc_graph_json}" "${startnode}")
string(JSON stack_json SET "${stack_json}" 0 1 "${nbrs}")
#while stack:
string(JSON stack_length LENGTH "${stack_json}")
while(stack_length GREATER 0)
#thisnode, nbrs = stack[-1]
math(EXPR stack_last_idx "${stack_length}-1")
string(JSON thisnode GET "${stack_json}" ${stack_last_idx} 0)
string(JSON nbrs_json GET "${stack_json}" ${stack_last_idx} 1)
message("thisnode = ${thisnode}")
message("nbrs = ${nbrs_json}")
string(JSON nbrs_len LENGTH "${nbrs_json}")
#if nbrs:
if(nbrs_len GREATER 0)
# TODO generalize: transpile python to cmake
# cmake is similar to bash: everything is a string
# goal: less code to maintain
# python code is MUCH cleaner than cmake code
# https://github.com/Luavis/sherlock.py
# https://github.com/py2many/py2many
#nextnode = nbrs.pop()
math(EXPR nbrs_last_idx "${nbrs_len}-1")
string(JSON nextnode GET "${nbrs_json}" ${nbrs_last_idx})
string(JSON nbrs_json REMOVE "${nbrs_json}" ${nbrs_last_idx})
if(nextnode STREQUAL startnode)
#yield path[:]
string(JSON result_length LENGTH "${result_json}")
string(JSON result_json SET "${result_json}" ${result_length} "${path_json}")
#closed.update(path)
# loop path, add nodes to closed
string(JSON path_length LENGTH "${path_json}")
if(path_length GREATER 0)
math(EXPR last_path_idx "${path_length}-1")
foreach(path_idx RANGE ${last_path_idx})
string(JSON path_node GET "${path_json}" ${path_idx})
map_set(closed_map "${path_node}" TRUE)
endforeach()
endif()
#message("Found a cycle: path=${path} closed=${closed}")
else()
map_get(blocked_map "${nextnode}" nextnode_in_blocked_map)
#if nextnode not in blocked:
if(NOT nextnode_in_blocked_map)
#path.append(nextnode)
string(JSON path_length LENGTH "${path_json}")
string(JSON path_json SET "${path_json}" ${path_length} "${nextnode}")
#stack.append((nextnode, list(sccG[nextnode])))
string(JSON stack_length LENGTH "${stack_json}")
string(JSON stack_json SET "${stack_json}" ${stack_length} "[]")
# TODO what is nextnode
quote_string(nextnode_json "${nextnode}")
string(JSON stack_json SET "${stack_json}" ${stack_length} 0 "${nextnode_json}")
string(JSON nbrs GET "${scc_graph_json}" "${nextnode}")
string(JSON stack_json SET "${stack_json}" ${stack_length} 1 "${nbrs}")
#closed.discard(nextnode)
map_remove(closed_map "${nextnode}")
#blocked.add(nextnode)
map_set(blocked_map "${nextnode}" TRUE)
#continue
continue()
endif()
endif()
endif()
# done with nextnode... look for more neighbors
#if not nbrs: # no more nbrs
string(JSON nbrs_len LENGTH "${nbrs_json}")
if(nbrs_len GREATER 0)
#if thisnode in closed:
map_get(closed_map "${thisnode}" thisnode_in_closed)
if(thisnode_in_closed)
# TODO python 2 cmake
#def _unblock(thisnode, blocked, B):
# stack = {thisnode}
# while stack:
# node = stack.pop()
# if node in blocked:
# blocked.remove(node)
# stack.update(B[node])
# B[node].clear()
#_unblock(thisnode, blocked, B)
set(unblock_stack_json "[]")
#stack = {thisnode}
string(JSON unblock_stack_json SET "${unblock_stack_json}" 0 "${thisnode}")
#while stack:
string(JSON unblock_stack_length LENGTH "${unblock_stack_json}")
while(unblock_stack_length GREATER 0)
#node = stack.pop()
math(EXPR unblock_stack_last_idx "${unblock_stack_length}-1")
string(JSON unblock_node GET "${unblock_stack_json}" ${unblock_stack_last_idx})
string(JSON unblock_stack_json REMOVE "${unblock_stack_json}" ${unblock_stack_last_idx})
#if node in blocked:
map_get(blocked_map "${unblock_node}" unblock_node_in_blocked)
if(unblock_node_in_blocked)
#blocked.remove(node)
map_remove(blocked_map "${unblock_node}")
#B = defaultdict(set) # graph portions that yield no elementary circuit
# defaultdict:
# class collections.defaultdict(default_factory=None)
# same as dict, but returns default value for missing keys
#stack.update(B[node])
# TODO what is B
#B[node].clear()
endif()
# update loop counter
string(JSON unblock_stack_length LENGTH "${unblock_stack_json}")
endwhile()
else()
# TODO python 2 cmake
for nbr in sccG[thisnode]:
if thisnode not in B[nbr]:
B[nbr].add(thisnode)
endif()
#stack.pop()
string(JSON stack_length LENGTH "${stack_json}")
math(EXPR stack_last_idx "${stack_length}-1")
string(JSON stack_json REMOVE "${stack_json}" ${stack_last_idx})
##assert path[-1] == thisnode # debug
#path.pop()
string(JSON path_length LENGTH "${path_json}")
math(EXPR path_last_idx "${path_length}-1")
string(JSON path_json REMOVE "${path_json}" ${path_last_idx})
endif()
# update the loop counter
string(JSON stack_length LENGTH "${stack_json}")
endwhile()
# TODO python 2 cmake
# done processing this node
H = subG.subgraph(scc) # make smaller to avoid work in SCC routine
sccs.extend(scc for scc in nx.strongly_connected_components(H) if len(scc) > 1)
# update the loop counter
math(EXPR sccs_length "${sccs_length}-1")
endwhile()
endfunction()
function(topo_sort graph_json result_name)
map_size(${graph_json} size)
message("graph with ${size} nodes:")
map_print(${graph_json})
set(${result_name} todo;todo;todo PARENT_SCOPE)
endfunction()
map_create(graph_map)
map_set(graph_map 0 "1") # 1;2;3
map_set(graph_map 1 "2") # 2;3
map_set(graph_map 2 "0") # loop
#map_set(graph_map 2 "") # no loop
message("graph_map:")
map_print(graph_map)
#deque_create(scc_deque)
set(graph_json [[
{
"0": ["1"],
"1": ["2"],
"2": ["0"],
}
]])
# "2": [], # no cycle
# "2": ["0"], # cycle
# "0": ["1", "10", "11", "12"], # extra edges -> TODO implement
strongly_connected_components("${graph_json}" sccs_json)
message("sccs_json: ${sccs_json}")
#deque_print(scc_deque)
simple_cycles("${graph_json}" simple_cycles_json)
message("simple_cycles_json: ${simple_cycles_json}")
message(FATAL_ERROR todo)
topo_sort(graph_map sorted_nodes)
message("sorted_nodes = ${sorted_nodes}")
```
output
ideally, the cycle error should also print the cycle
in python im using