--[[
---------------------------------------------------------------------------
Remote Train Control Program for Windows

© Copyright 2019 by Mark DiVecchio

	This file is part of Remote Train Control.

	Remote Train Control is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	Remote Train Control is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with Remote Train Control.  If not, see <http://www.gnu.org/licenses/>.

 Home Page : http://www.silogic.com/trains/RTC_Running.html
---------------------------------------------------------------------------]]
-- Semicolons are not required in Lua code
title = "Graph Test"
require("defines");
require("functions");
local g = require('luagraphs.data.graph').create(44, false, true)	-- an undirected weighted graph with 44 nodes starting at 0

--[[---------------------------------------------------------------------------------------]]
function setup(Engine, TIU)
	-- this function is called once when the [Run Script] button is pushed
	-- Engine : Engine number selected on the RTC Main window
	-- TIU : TIU number selected on the RTC Main window
	print("setup()");
	
	-- an undirected weighted graph
	
	g:addEdge(0, 3, 1)		-- MkKees Rocks Yard 2
	g:addEdge(2, 3, 1)  	-- McKees Rocks Yard 1
	g:addEdge(3, 4, 1)		-- mainline	
	g:addEdge(4, 5, 1)		-- mainline
	g:addEdge(4, 14, 2)		-- J&L passing track
	g:addEdge(14, 12, 2)	-- J&L passing track
	g:addEdge(14, 15, 1)	-- siding lead
	g:addEdge(15, 16, 1)	-- siding
	g:addEdge(15, 17, 1)	-- siging
	g:addEdge(12, 10, 2)	-- J&L passing track
	g:addEdge(12, 13, 1)	-- siding
	g:addEdge(10, 5, 1)		-- J&L passing track
	g:addEdge(10, 11, 1)	-- siding
	g:addEdge(5, 6, 1)		-- mainline
	g:addEdge(6, 7, 1)		-- siding
	g:addEdge(6, 8, 1)		-- mainline
	g:addEdge(8, 18, 1)		-- mainline
	g:addEdge(8, 9, 1)		-- siding
	g:addEdge(18, 20, 10)	-- long run between nodes
	g:addEdge(18, 19, 1)	-- siding
	g:addEdge(20, 22, 10)	-- long run between nodes
	g:addEdge(20, 21, 1)	-- siding
	g:addEdge(22, 23, 1)	-- mainline

	g:addEdge(22, 23, 2)	-- College Hill Station track
	g:addEdge(23, 24, 1)	-- mainline
	g:addEdge(24, 32, 1)	-- mainline
	g:addEdge(24, 25, 1)	-- siding lead
	g:addEdge(25, 31, 1)	-- siding
	g:addEdge(25, 26, 1)	-- siding lead
	g:addEdge(26, 30, 1)	-- siding
	g:addEdge(26, 27, 1)	-- siding lead
	g:addEdge(27, 28, 1)	-- siding
	g:addEdge(27, 29, 1)	-- siding
	
	g:addEdge(32, 33, 1)	-- Struthers Station track
	g:addEdge(32, 34, 2)	-- mainline
	g:addEdge(34, 33, 2)	-- mainline
	g:addEdge(34, 35, 1)	-- siding lead
	g:addEdge(35, 38, 1)	-- siding
	g:addEdge(35, 36, 1)	-- siding lead
	g:addEdge(36, 37, 1)	-- siding
	
	g:addEdge(33, 39, 1)	-- mainline
	g:addEdge(39, 41, 5)	-- long run between nodes
	g:addEdge(39, 40, 1)	-- siding
	
	g:addEdge(41, 42, 1)	-- Youngstown Yard to Cleveland
	g:addEdge(41, 1, 1)		-- Youngstown Yard to Ashtabula

	
	print(g:vertexCount()) 

-- code below prints the adjacency list 
for k = 0, g:vertexCount() - 1 do -- iterate through all vertices in g
    local v = g:vertexAt(k)
    local adj_v = g:adj(v) -- adjacency list for vertex v
    local text = ''
    for i = 0, adj_v:size()-1 do
        local e = adj_v:get(i)
        text = text .. ', ' .. e:other(v) .. '(' .. e.weight .. ')' 
    end
    print(text)
end
---[[
print("Shortest Paths (Dijkstra)");
-- https://github.com/chen0040/lua-graph#shortest-paths-dijkstra
local source = 0
local dijkstra = require('luagraphs.shortest_paths.Dijkstra').create()
dijkstra:run(g, source) -- "source" is the id of the source node in the path search
for k = 0,g:vertexCount() - 1 do
    local v = g:vertexAt(k)
    if v ~= source and dijkstra:hasPathTo(v) then
        print('path from ' .. source .. ' to ' .. v .. ' ( cost: '  .. dijkstra:getPathLength(v) .. ' )')
        local path = dijkstra:getPathTo(v)
        for i = 0,path:size()-1 do
            print('# from ' .. path:get(i):from() .. ' to ' .. path:get(i):to() .. ' ( distance: ' .. path:get(i).weight .. ' )')
        end
    end
end
--]]

--[[
print("Depth First Search");
    local dfs = require('luagraphs.search.DepthFirstSearch').create()
    local s = 0
    dfs:run(g, s)

    for i = 0, g:vertexCount()-1 do
        local v = g:vertexAt(i)
        if v ~= s and dfs:hasPathTo(v) then
            print('Vertex ' .. s .. ' has path to ' .. v)
            local path = dfs:getPathTo(v)
            local pathText = ''
            while path:isEmpty() == false do
                local x = path:pop()
                if pathText == '' then
                    pathText = pathText .. x
                else
                    pathText = pathText .. ' -> ' .. x
                end
            end
            print(pathText)

        end
    end


--]]

--[[
print("Breadth First Search");
-- https://github.com/chen0040/lua-graph#breadth-first-search
local bfs = require('luagraphs.search.BreadthFirstSearch').create()
local s = 22
bfs:run(g, s)

for k = 0, g:vertexCount()-1 do
    local v = g:vertexAt(k)
    if v ~= s and bfs:hasPathTo(v) then
        local path = bfs:getPathTo(v)
        local pathText = ''
        while path:isEmpty() == false do
            local x = path:pop()
            if pathText == '' then
                pathText = pathText .. x
            else
                pathText = pathText .. ' -> ' .. x
            end
        end
        print(pathText)

    end
end
--]]
--[[
print("Connected Components");
-- https://github.com/chen0040/lua-graph#connected-components
local cc = require('luagraphs.connectivity.ConnectedComponents').create()
cc:run(g)

print('count: ' .. cc.count)
print(cc.count) -- return 3 connected components
for k = 0,g:vertexCount()-1 do
    local v = g:vertexAt(k)
    print('id[' .. v .. ']: ' .. cc:component(v))
end
--]]
--[[
print("Topological Sort");
-- https://github.com/chen0040/lua-graph#topological-sort
local ts = require('luagraphs.sort.TopologicalSort').create()
ts:run(g)

local path = ts:path()
for i=0, path:size()-1 do
    print('sort #' .. i .. ': ' .. path:get(i))
end
--]]
--[[
print("Shortest Paths (Topological Sort)");
-- https://github.com/chen0040/lua-graph#shortest-paths-topological-sort
local source = 0
local finder = require('luagraphs.shortest_paths.Dijkstra').create()
finder:run(g, source) -- 0 is the source node in the path search
for k = 0,g:vertexCount()-1 do
    local v= g:vertexAt(k)
    if v ~= source and finder:hasPathTo(v) then
        print('path from 0 to ' .. v .. ' ( cost: '  .. finder:getPathLength(v) .. ' )')
        local path = finder:getPathTo(v)
        for i = 0,path:size()-1 do
            print('# from ' .. path:get(i):from() .. ' to ' .. path:get(i):to() .. ' ( distance: ' .. path:get(i).weight .. ' )')
        end
    end
end
--]]
--[[
print("MinCut-MaxFlow (Ford Fulkerson implementation)");
-- https://github.com/chen0040/lua-graph#mincut-maxflow-ford-fulkerson-implementation
local method = require('luagraphs.flow.FordFulkerson').create()
local maxFlow = method:run(g, 0, 43)
print('FordFulkerson max flow: ' .. maxFlow)


local minCuts = method:minCuts()

for i = 0,minCuts:size()-1 do
    local e =minCuts:get(i)
    print('min cut: ' .. e:toString())
end
--]]
	print(string.format("RunTime = %.2f seconds", RunTime()));
	return Stop("End of Graph Test");
	end

--[[---------------------------------------------------------------------------------------]]
function cleanup(Engine, TIU)
	-- this function is called once when the user presses the [STOP] button
	print(string.format("cleanup() Complete at %.2f", RunTime()));
	return true;		-- false=cleanup failed, true=cleanup succeeded
	end
--[[---------------------------------------------------------------------------------------]]