Анализ графа

--  Расчёт надёжности цепи от [email]program48@gmail.com[/email]
--  [url]https://www.cyberforum.ru/algorithms/thread1673501.html[/url]
 
--  исходные данные
local data=[[
IN | 1 2
1 | 3 4
2 | 5
3 | 6
4 | 6
5 | OUT
6 | OUT
]]
 
local points={} --  узлы
 
local parallel=function(p1,p2)
    return (p1=='1' or p2=='1') and '1' or ('(1-(1-%s)*(1-%s))'):format(p1,p2)
end
 
local sequence=function(p1,p2)
    return p1=='1' and p2 or p2=='1' and p1 or p1..'*'..p2
end
 
--  Основная функция расчёта надёжности
--[[    a   --  узел
            P0  --  надёжность линии до узла a
            возвращаем надёжность до конца линии и следующий после линии узел (к которому соединяются другие параллельные линии)
]]
local function calcP(a,P0)
    P0=sequence(P0,a.P)
 
    if #a.outs==0 then  --  если у a нет выходов, то это OUT
        return P0
    end
 
    if #a.outs==1 then  --  если у a только один выход
        local bPointName=a.outs[1]
        local b=points[bPointName]
        if b.freeInCount==1 then    --  если у b только один вход (или уже все входы объеденены)
            return calcP(b,P0)
        else    --  если в b входит не только a, то линия окончена
            return P0,b
        end
    else    --  обработка ветвления
        local linesCount=#a.outs
 
        local linesByFinish={}  --  линии сгруппированные по узлам, в которые они входят
        --  каждый выход из a образует линию
        for id,outName in ipairs(a.outs) do
            local out=points[outName]
            linesByFinish[out]={
                P='1',  --  Надёжность этой линии до узла out
            }
        end
 
        repeat
            local newLBF={}
            local calcWas
            --  продолжаем расчёт каждой линии отдельно
            for finish,lbf in pairs(linesByFinish) do
                local P
                if finish.freeInCount==1 then   --  продолжаем расчёт, только если у узла finish все другие входы реализованы
                    P,finish=calcP(finish,lbf.P)
                    calcWas=true
                else
                    assert(finish.freeInCount==0,'Такого не должно быть')
                    P=lbf.P
                end
                local newlbf=newLBF[finish]
                if newlbf then  --  если линия к узлу finish уже есть, то объединяем эти параллельные линии
                    finish.freeInCount=finish.freeInCount-1
                    newlbf.P=parallel(newlbf.P,P)
                    linesCount=linesCount-1
                else    --  иначе новая линия
                    newlbf={
                        P=P,
                    }
                    newLBF[finish]=newlbf
                end
            end
            linesByFinish=newLBF
 
            assert(calcWas,'не было расчета')
 
            --  если все линии свелись к одному элементу, выходим
            if linesCount==1 then
                local b,lbf=next(linesByFinish)
                P0=sequence(P0,lbf.P)
 
                if b.freeInCount==1 then    --  если у b только один вход или уже все входы объеденены (последовательное присоединение b)
                    return calcP(b,P0)
                else    --  если в b входит не только a, то линия окончена
                    return P0,b
                end
            end
        until false
    end
end
 
--  заполняем таблицу узлов, входы и выходы
for startTxt,finishTxt in data:gmatch'([^|\n]+)|([^|\n]+)' do
    for start in startTxt:gmatch'%S+' do
        if not points[start] then
            points[start]={ins={},outs={}}
        end
        for finish in finishTxt:gmatch'%S+' do
            if not points[finish] then
                points[finish]={ins={},outs={}}
            end
            table.insert(points[start].outs,finish)
            table.insert(points[finish].ins,start)
        end
    end
end
 
for name,point in pairs(points) do
    point.freeInCount=#point.ins    --  запоминаем количество нереализованных входов в каждый узел
    point.name=name
    point.P='P'..name
end
 
--  получаем ответ
print(calcP(points.IN,'1'))

        else    --  если в b входит не только a, то линия окончена
            return P0,b

 for id,outName in ipairs(a.outs) do
            local out=points[outName]
            linesByFinish[out]={
                P='1',  --  Надёжность этой линии до узла out
            }
        end

linesByFinish[out]='1'  --  Надёжность этой линии до узла out