(* ::Package:: *)

BeginPackage["PathOperations`"]

(* \[Copyright] Copyright 2016 Tom Verhoeff *)

(*
    This package 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.

    This package 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 this package.  If not, see <http://www.gnu.org/licenses/>.
*)

closePath::usage=
	"Closes an open path, by appending the first element.";

pathQ::usage=
	"Whether perms form a path.";

cycleQ::usage=
	"Whether perms form a cycle.";

pathEdges::usage=
	"splits a path or list of paths into edges (vertex pairs).  This is idempotent.";

pathsEdges::usage=
	"splits a list of paths into edges (vertex pairs).  This is idempotent.";

stitchPaths::usage=
	"Stitches a list of paths into one path (greedy).  This is idempotent.";

splitPath::usage=
	"Splits a path at given vetices.";

cutCycle::usage=
	"Cuts a cycle at a given vertex.";

spurBaseIndex::usage=
	"Determines index of base of spur for given path and spur tip.";

spur::usage=
	"Returns spur {base, tip} for given path and vertex.";

spurs::usage=
	"Returns list of spurs for given path and vertices.";

incorporateSpur::usage=
	"Incorporates a vertex at distance 1 of a given path as a spur.";

incorporateSpurs::usage=
	"Incorporates all vertices at distance 1 of a given path as a spur.";

createZigZagPath::usage=
	"Creates a zigzag path/cycle from a path/cycle of even length.";

incorporateSpurInZigZag::usage=
	"Incorporates given vertex into a zigzag path/cycle.";

incorporateSpursInZigZag::usage=
	"Incorporates given verticesinto a zigzag path/cycle.";

createSquareTube::usage=
	"Creates a square tube from a path of even length, ending in opposite corner.";

parallelEdgesQ::usage=
	"Determines whether two given edges are parallel.";

parallelEdges::usage=
	"Finds all parallel edges on two given paths.";


Begin["Private`"];


closePath[{}] := {};
closePath[{a_}] := {a};
closePath[{a_,b_}] := {a,b};
closePath[{a_,z__,a_}] := {a,z,a};
closePath[{a_,b_,z__}] := {a,b,z,a};


(* pathQ[perms], cycleQ[perms]

	pre: perms is a list of permutations.
	ret: whether perms is a path/cycle
*)

pathQ[path_List, edgeQ_] :=
	AllTrue[Partition[path, 2, 1], edgeQ];

cycleQ[path_List, edgeQ_] :=
	pathQ[path, edgeQ] && Length[path] > 2 && edgeQ[{Last[path], First[path]}];


(* pathEdges, pathsEdges

	pre: path is a list of verices; paths is a list of paths
	ret: a list of edges as vertex pairs
*)

pathEdges[path_List] :=
	Partition[path, 2, 1];

pathsEdges[paths:{___List}] :=
	Catenate @ Map[pathEdges, paths];


(* stitchPaths[paths]

	pre: paths is a list of paths
	ret: list where as many paths in the list have been combined, possibly by reversing

N.B. stitchPaths[pathEdges[path]] \[Equal] {path}
*)

stitchPaths[{x___, {}, y___}] :=
	stitchPaths[x, y];

stitchPaths[{x___, {a_, u___, b_}, y___, {b_, v___, c_}, z___}] :=
	stitchPaths[{x, {a, u, b, v, c}, z}];

stitchPaths[{x___, {a_, u___, b_}, y___, {c_, v___, b_}, z___}] :=
	stitchPaths[{x, {a, u, b, Sequence @@ Reverse[{v}], c}, y, z}];

stitchPaths[{x___, {a_, u___, b_}, y___, {c_, v___, a_}, z___}] :=
	stitchPaths[{x, {c, v, b, u, a}, y, z}];

stitchPaths[{x___, {a_, u___, b_}, y___, {a_, v___, c_}, z___}] :=
	stitchPaths[{x, {c, Sequence @@ Reverse[{v}], a, u, b}, y, z}];

stitchPaths[{x___}] := {x};


(* splitPath[path, vetices]

	pre: path is a path including the given vertex
	ret: path split into segments starting with the given vertex

N.B. stitchPaths[splitPath[path, vertices]] = {path}
*)

splitPath[path_List, vertices_List] :=
	Block[{pos, segments},
		pos = Sort @ Map[FirstPosition[path, #][[1]] &, vertices];
		PrependTo[pos, 1];
		AppendTo[pos, Length[path] + 1];
		segments = Select[Partition[pos, 2, 1], #[[1]] < #[[2]] &];
		Map[path[[#[[1]];;#[[2]]-1]] &, segments]
	];

splitPath[vertex_][path_List] :=
	splitPath[path, vertex];


(* cutCycle[path, vertex]

	pre: path is a cycle of vertices
	ret: cycle cut at given vertex, so that it starts with the given vertex
*)

cutCycle[path_List, vertex_] :=
	RotateLeft[path, Position[path, vertex][[1, 1]] - 1];

cutCycle[vertex_][path_List] :=
	cutCycle[path, vertex];


(* incorporateSpur[path, vertex, edgeQ]

	pre: pathQ[path, edgeQ] and vertex is at distance 1 from this path
	ret: path with vertex incorporated as a spur
*)

spurBaseIndex[path_List, vertex_, edgeQ_] :=
	FirstPosition[path, _?(edgeQ[{#, vertex}] &), Missing["Nonexistent"], {1},Heads->False][[1]];

spur[path_List, vertex_, edgeQ_] :=
	With[{i = spurBaseIndex[path, vertex, edgeQ]}, {path[[i]], vertex}];

spurs[path_List, vertices_List, edgeQ_] :=
	Map[spur[path, #, edgeQ] &, vertices];

incorporateSpur[path_List, vertex_, edgeQ_] :=
	With[{i = spurBaseIndex[path, vertex, edgeQ]},
		Join[path[[;;i]], {vertex}, path[[i;;]]]
	];

incorporateSpurs[path_List, vertices_List, edgeQ_] :=
	Fold[incorporateSpur[#1, #2, edgeQ] &, path, vertices];


(* createZigZagPath[cycle, u, v]

	pre: Length[cycle] is even; vertices are lists
	ret: cycle obtained by combining two "parallel" copies of given cycle, to form a 'square wave',
		running from cycle[[1]]v to cycle[[-1]]v;
		the two copies are distinguished by appending u and v;
		also works for a path
*)

createZigZagPath[cycle_List, u_, v_] :=
	Block[{temp, module},
		temp = Catenate @ Transpose[{cycle, cycle}];
		module = {u, v, v, u};
		(* Length[result] is a multiple of 4 *)
		MapIndexed[Join[#1, module[[Mod[First[#2], 4, 1]]]] &, temp]
	];


(* incorporateSpurInZigZag[path, vertex, edgeQ], incorporateSpursInZigZag[path, vertices, edgeQ]

	pre: path is a zigzag path, vertex is at distance 1 from the path when dropping e trailing items
		from vertices in the path 
	ret: path with 'vertical' edge in zigzag replaced by sidestep via two connected copies of vertex
*)

incorporateSpurInZigZag[path_List, vertex_, edgeQ_, e_] :=
	Block[{i, pair},
		i = spurBaseIndex[path, vertex, edgeQ[MapAt[Drop[#, -e] &, #, 1]] &];
		pair = path[[i;;i+1]]; (* a 'vertical' edge *)
		Join[path[[;;i]], Map[Join[vertex, Take[#, -e]] &, pair], path[[i+1;;]]]
	];

incorporateSpursInZigZag[path_List, vertices_List, edgeQ_, e_] :=
	Fold[incorporateSpurInZigZag[#1, #2, edgeQ, e] &, path, vertices];


(* createSquareTube[path]

	pre: Length[path] is even; path runs from 
	ret: path obtained by combining four "parallel" copies of given path, to form a square tube,
		running from path[[1]]uu to path[[-1]vv;
		the four copies are distinguished by appending uu, uv, vu, vv
*)

createSquareTube[path_List, u_, v_] :=
	Block[{temp, module1, module2, uu, uv, vu, vv},
		temp = Catenate @ Transpose[{path, path, path, path}];
		uu = Join[u, u];
		uv = Join[u, v];
		vu = Join[v, u];
		vv = Join[v, v];
		module1 := {uu, uv, vv, vu, vu, vv, uv, uu};
		module2 := {uu, uv, vv, vu, vu, uu, uv, vv};
		Join[
			MapIndexed[Join[#1, module1[[Mod[First[#2], 8, 1]]]] &, Drop[temp, -8]],
			MapIndexed[Join[#1, module2[[Mod[First[#2], 8, 1]]]] &, Take[temp, -8]]
		]
	];


(* parallelEdgesQ[{edge1, edge2}, edgeQ]

	pre: edge1 and edge2 are two pairs of connected vertices; edgeQ is the edge relation on vertices
	ret: whether edge1 and edge2 are parallel
*)

parallelEdgesQ[{edge1_List, edge2_List}, edgeQ_] :=
	And[
		DisjointQ[edge1, edge2],
		Or @@ Map[AllTrue[Transpose[{edge1, #}], edgeQ]&, NestList[Reverse, edge2, 1]]
	];

parallelEdgesQ[edge1_List, edge2_List, edgeQ_] :=
	parallelEdgesQ[{edge1, edge2}, edgeQ];


(* parallelEdges

	pre: path1 and path2 are two paths; edgeQ is the edge relation on vertices
	ret: list with all pairs of edge pairs from path1 and path2 that are parallel
*)

parallelEdges[path1_List, path2_List, edgeQ_] :=
	Select[Tuples[{Partition[path1, 2, 1], Partition[path2, 2, 1]}], parallelEdgesQ[#, edgeQ] &];


End[ ];

EndPackage[ ]
