how to find all cycles is in given undirected graph

Question

I want to find the cycles with impar amount of nodes is in graphs. To do that I made the following algorithm which does a dfs walk through the graph and when it finds a cycle it goes back and tries to find small cycles that intersect with the big cycle it found.

let graph = JSON.parse('{"nodes":[{"x":876,"y":448},{"x":868,"y":564},{"x":845,"y":710},{"x":1050,"y":710},{"x":1075,"y":568},{"x":1087,"y":458},{"x":870,"y":191}],"connections":[{"from":0,"to":1},{"from":1,"to":2},{"from":2,"to":3},{"from":3,"to":1},{"from":3,"to":4},{"from":4,"to":5},{"from":5,"to":0}]}')

const connections = [];

for (let i = 0; i < graph.nodes.length; i++)
    connections.push([]);

for (let i = 0; i < graph.connections.length; i++)
{
    connections[graph.connections[i].to].push(graph.connections[i].from);
    connections[graph.connections[i].from].push(graph.connections[i].to);
}

const visited = [];
const finished = [];
for (let i = 0; i < graph.nodes.length; i++)
{
    visited.push(false);
    finished.push(false);
}
console.clear();
const cycles = []
for(let i = 0; i < graph.nodes.length; i++)
{
    dfs(i)
}
document.write(cycles.map(item => item.join(',')).join('<br>'));


function dfs(node, stack=[])
{
    if(visited[node])
    {
        let position = 0

        for(const stack_node of stack)
        {
            for(const connection of connections[stack_node])
            {
                if(connection == node)
                {
                    let current_stack = [...[...stack].splice(position), node]
                    let i = 0
                    for(; i < current_stack.length; i++)
                            if(current_stack[i] == node)
                            break
                    if(i != current_stack.length-1)
                    current_stack = current_stack.splice(i+1)
                    if(current_stack.length <= 2) continue
                    if(current_stack.length % 2 == 0) continue
                    if(!cycles.find(cycle => cycle.length == current_stack.length && cycle.every((value, index) => value == current_stack[index])))
                    cycles.push(current_stack)
                }
            }
            position ++
        }
        return;
    }
    visited[node] = true;
    for(const connection of connections[node])
    {
        dfs(connection,[...stack, node])
    }
}

graph:

https://i.sstatic.net/rTv4g.png

expectedo output

2, 3, 1

1, 3, 4, 5, 0

given output

2, 3, 1

But it doesn't find all the impar cycles on every graph. Is there a better way to find each cycle on a undirected graph?

Answer 1

i made a solution for my problem, but if you want all the cycles just remove the if(current_stack.length % 2 == 0) continue

let graph = JSON.parse('{"nodes":[{"x":876,"y":448},{"x":868,"y":564},{"x":845,"y":710},{"x":1050,"y":710},{"x":1075,"y":568},{"x":1087,"y":458},{"x":870,"y":191}],"connections":[{"from":0,"to":1},{"from":1,"to":2},{"from":2,"to":3},{"from":3,"to":1},{"from":3,"to":4},{"from":4,"to":5},{"from":5,"to":0}]}')
 const connections = [];

for (let i = 0; i < graph.nodes.length; i++)
    connections.push([]);

for (let i = 0; i < graph.connections.length; i++)
{
    connections[graph.connections[i].to].push(graph.connections[i].from);
    connections[graph.connections[i].from].push(graph.connections[i].to);
}

const loops= [];

const globally_visited = Array(graph.nodes.length).fill(false)

for(const node in graph.nodes)
{
    if(!globally_visited[node])
    dfs(node)
}
document.write(loops.map(item=>item.join(', ')).join('<br>'))

function dfs(node,stack=[],visited= [].fill(0, 0, graph.length))
{
    globally_visited[node] = true;
    visited[node] = 1;
    for(const current of connections[node])
    {
        if(visited[current] === 1)
        {
            let current_stack = [...stack,node]
            let i = 0
            for(; i < current_stack.length; i++)
            if(current_stack[i] == current)
            break
            if(i !== current_stack.length)
            {
                current_stack = current_stack.splice(i)
            }
            current_stack = current_stack.map(item=>Number(item));
            if(current_stack.length <= 2) continue
            if(current_stack.length % 2 == 0) continue
            
            for(const loop of loops)
            {
                if(loop.length !== current_stack.length) continue
                let found = false
                for(const number of current_stack)
                {
                    if(!loop.includes(number))
                    {
                        found = true
                        break
                    }
                }
                if(!found) return
            }
            if(connections[current_stack[0]].includes(node))

            loops.push(current_stack);
        }
        else
        {
            dfs(current, [...stack,Number(node)],[...visited]);
        }
    }
}