(* :Title: Graph Families *)

(* :Context: "GrafPack`GraphFamilies`" *)

(* :Authors:
	D. Andrén, P.H. Lundow (editor), K. Markström
	Department of Mathematics
	Umea University
	S-901 87 Umea
	Sweden
	Bug reports to per.hakan.lundow@math.umu.se
*)
(* :Summary:
	This package contains functions returning graphs from some
	standard families of graphs.
*)
(* :History:
	991221 Cyclic moved.
*)
(* :Mathematica Version: 3.0 *)
(* :Keywords: *)
(* :Limitations: *)
(* :Discussion: *)

BeginPackage["GrafPack`GraphFamilies`",
	{
	    "GrafPack`Combinatorics`",
	    "GrafPack`Basics`"
	}
]

CompleteGraph::usage =
	"CompleteGraph[n] returns a complete graph on n vertices.
	CompleteGraph[n1, n2,.., nk] returns a complete k-partite graph on
	n1+n2+..+nk vertices."

Cycle::usage =
	"Cycle[n] returns a cycle on vertices."

EmptyGraph::usage =
	"EmptyGraph[n] returns an empty graph on n vertices."

GridGraph::usage =
	"GridGraph[n1, n2,.., nk] returns an n1 x n2 x .. x nk grid graph,
	i.e. the cartesian product of Path[n1], Path[n2],.., Path[nk].
	GridGraph[n1, n2,.., nk, {i1, i2,.., il}] replaces Path[nij] with
	Cycle[nij]. GridGraph[n1, n2, nk, Cyclic] returns the cartesian product
	of Cycle[n1], Cycle[n2],.., Cycle[nk]."

Hypercube::usage =
	"Hypercube[n] returns the n-dimensional hypercube, or, the n-cube."

Path::usage =
	"Path[n] returns a path on n vertices."

RandomGraph::usage =
	"RandomGraph[n, p] returns a random labelled graph on n vertices with
	edge probability p, where p is a Real number. RandomGraph[n, m] returns
	a random labelled graph on n vertices and m edges.
	RandomGraph[n1, n2,.., nk, p] returns a random labelled subgraph of
	CompleteGraph[n1, n2,.., nk] with edge probability p.
	RandomGraph[n1, n2,.., nk, m] returns a random labelled subgraph of
	CompleteGraph[n1, n2,.., nk] on m edges."

RandomTree::usage =
	"RandomTree[n] returns a random labelled tree on n vertices."

Begin["`Private`"]

protected = Unprotect[]

definitions = {
    CompleteGraph, Cycle, EmptyGraph, GridGraph, Hypercube, Path,
	RandomGraph, RandomTree
}

Scan[Unprotect, definitions]


CompleteGraph[n_Integer] := Graph[1 - IdentityMatrix[n], CircularEmbedding[n]]

CompleteGraph[n__Integer?Positive] :=
	Module[{a, b={n}, c=2*Pi/Length[{n}], m=Plus[n]},
		Graph[
			Apply[Join,
				MapThread[
					(a = Join[
						Table[1, {#1}],
						Table[0, {#2}],
						Table[1, {m - #1 - #2}]
					];
					Table[a, {#2}])&,
					{FoldList[Plus, 0, Drop[b, -1]], b}
				]
			],
			CircularEmbedding[n]
		]
	]


Cycle[n_Integer] :=
	Module[{i, a=ReplacePart[Table[0, {n}], 1, {{2}, {-1}}]},
		Graph[
			Table[RotateRight[a, i], {i, 0, n-1}],
			CircularEmbedding[n]
		]
	] /; n > 2


EmptyGraph[n_Integer] := Graph[Table[0, {n}, {n}], CircularEmbedding[n]]


GridGraph[n__Integer?Positive] := 
	GraphProduct[Apply[Sequence, Map[Path, {n}]]]

GridGraph[n__Integer?Positive, a_List] :=
	GraphProduct[
		Apply[Sequence,
			MapThread[
				#1[#2]&,
				{
					ReplacePart[
						Table[Path, {Length[{n}]}],
						Cycle,
						Map[List, a]
					],
					{n}
				}
			]
		]
	]

GridGraph[n__Integer?Positive, Cyclic] :=
	GraphProduct[Apply[Sequence, Map[Cycle, {n}]]]


Hypercube[0] := Path[1]

Hypercube[n_Integer?Positive] := GraphProduct[Hypercube[n-1], Path[2]]


Path[n_Integer?NonNegative] := 
	FromEdges[
		Partition[Range[n], 2, 1],
		LinearEmbedding[n]
	]


RandomGraph[0, _Real] := Graph[{}, {}]

RandomGraph[n_Integer, p_Real] :=
	Module[{adj, i},
		adj = Table[
			Join[
				Table[0, {i}],
				Table[Random[Integer], {n - i}]
			],
			{i, n}
		];
		Graph[adj + Transpose[adj], CircularEmbedding[n]]
	] /; p == 0.5

RandomGraph[n_Integer, p_Real] :=
	Module[{adj, i},
		adj = Table[
			Join[
				Table[0, {i}],
				Table[If[Random[] < p, 1, 0], {n - i}]
			],
			{i, n}
		];
		Graph[adj + Transpose[adj], CircularEmbedding[n]]
	] /; 0.0 <= p <= 1.0

RandomGraph[n__Integer, p_Real] :=
	Module[{a={n}, adj, m=Plus[n]},
		adj = Apply[Join,
			MapThread[
				Table[
					Join[
						Table[0, {#1+#2}],
						Table[If[Random[] < p, 1, 0], {m - #1 - #2}]
					],
					{#2}
				]&,
				{FoldList[Plus, 0, Drop[a, -1]], a}
			]
		];
		Graph[adj + Transpose[adj], CircularEmbedding[n]]
	] /; 0.0 <= p <= 1.0

RandomGraph[n_Integer, m_Integer?NonNegative] :=
	FromEdges[RandomSubset[Subsets[n, 2], m], n] /; m <= Binomial[n, 2]

RandomGraph[n__Integer?Positive, m_Integer] :=
	FromEdges[
		RandomSubset[
			Flatten[
				Map[
					CartesianProduct[Apply[Sequence, #]]&,
					Subsets[
						Plus[
							Map[Range, {n}],
							FoldList[Plus, 0, Drop[{n}, -1]]
						],
						2
					]
				],
				1
			],
			m
		],
		CircularEmbedding[n]
	]


RandomTree[0] := Graph[{}, {}]

RandomTree[1] := FromEdges[{}, 1]

RandomTree[n_Integer?Positive] :=
	CircularEmbedding[CodeToTree[Table[Random[Integer, {1, n}], {n - 2}]]]


Protect[Evaluate[protected]]

Scan[Protect, definitions]

End[]

EndPackage[]