Constructions for cographs and endographs of finite functions

Introduction

This Mathematica notebook is licensed under a MouseOver .

It provides examples of  cographs and endographs of functions on finite sets.  

The notebook is still rough and incomplete.  It will be revised from time to time.  I hope anyone interested will feel free to improve this work and to use it in their own publications and coursework.

Charles Wells

Utilities

Options[op]={Background->White,FontFamily->"Arial",FontWeight->Bold,FontSlant->Plain}

op[x_,loc_]:=Text[Style[x,14,Bold,Background->White],loc]

op["x",{0,1}]

Making endographs

MakeFunctionRule[f_,n_]:=#->f[#]&/@ Table[k,{k,0,n-1}]

MakeRule[f_,l_]:=#->f[#]&/@l

Endograph[rule_,size_]:=GraphPlot[rule,VertexLabeling->True, DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,0.2(200/size)]&),PlotStyle->Directive[Arrowheads[Small]],VertexRenderingFunction->(op[#2,#1]&),ImageSize->size]

Endograph[rule_,size_,vtc_]:=GraphPlot[rule,VertexLabeling->True, DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,0.25(200/size)]&),PlotStyle->Directive[Arrowheads[Small]],
VertexCoordinateRules->vtc,VertexRenderingFunction->(op[#2,#1]&),ImageSize->size]

Endograph[rule_,size_,vtc_,gap_]:=GraphPlot[rule,VertexLabeling->True, DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,gap]&),PlotStyle->Directive[Arrowheads[Small]],
VertexCoordinateRules->vtc,VertexRenderingFunction->(op[#2,#1]&),ImageSize->size]

Making cographs

Basic example

This example will be used for testing the constructions. Names with lowercase are just for this example.  Names beginning with uppercase are permanent tools for the construction of the main function, Cograph.

f[a]:=c;f[b]:=a;f[c]:=c;f[d]:=b;f[e]:=d

BEsourcelist:={a,b,c,d,e};BEtargetlist:={a,b,c,d}

This particular choice of locations produces a column of addresses.

BEsourcelocs:={{1,5},{1,4},{1,3},{1,2},{1,1}}

BEtargetlocs:={{2,4.4},{2,3.5},{2,2.5},{2,1.5}}

Other possibilities, such as rows, may also be suitable:

BErowsourcelocs:={{1,1},{2,1},{3,1},{4,1},{5,1}}

BErowtargetlocs:={{1.5,0},{2.5,0},{3.5,0},{4.5,0}}

Preliminary functions

SetLocs

SetLocs associates each source and target element with a location

SetLocs[source_,locs_]:={source,locs}//Transpose

sourceplacement attaches elements of the sourcelist to locations in sourcelocs in the order they occur in each list. By writing out the placement functions by hand you can arrange them in any way you want.

Applied to Basic Example

sourceplacement:=SetLocs[BEsourcelist,BEsourcelocs]

sourceplacement

targetplacement:=SetLocs[BEtargetlist,BEtargetlocs]

targetplacement

DisplayNodes

DisplayNodes formats the nodes, resulting in a list which Graphics uses to display them.

DisplayNodes[list_,locs_]:=MapThread[op,{list,locs}]

Applied to Basic Example

sourcecol:=DisplayNodes[BEsourcelist,BEsourcelocs]

sourcecol

targetcol:=DisplayNodes[BEtargetlist,BEtargetlocs]

targetcol

Show[
Graphics[Flatten[{{sourcecol},{targetcol}}],
ImageSize->50,AspectRatio->3]]

ArrowSourceLoc and ArrowTargetLoc

arrowsource[chr_,slist_]:=Position[slist,chr][[1]][[1]]

ArrowSourceLoc[chr_,slist_,slocs_]:=slocs[[arrowsource[chr,slist]]]

arrowtarget[chr_,func_,slist_,tlist_]:=Position[tlist,func[chr]][[1]][[1]]

ArrowTargetLoc[chr_,func_,slist_,tlist_,tlocs_]:=tlocs[[arrowtarget[chr,func,slist,tlist]]]

Applied to Basic Example

ArrowTargetLoc[a,f,BEsourcelist,BEtargetlist,BEtargetlocs]

f[a]:=c;f[b]:=a;f[c]:=c;f[d]:=b;f[e]:=d (*unevaluated reminder of our example function*)

BEsourcelocs:={{1,5},{1,4},{1,3},{1,2},{1,1}}

BEtargetlocs:={{2,4},{2,3},{2,2},{2,1}}

ArrowList

ArrowList[func_,slist_,tlist_,slocs_,tlocs_,gap_]:=
Arrow[{ArrowSourceLoc[#,slist,slocs],ArrowTargetLoc[#,func,slist,tlist,tlocs]},gap]&/@slist

Applied to Basic Example

ArrowList[f,BEsourcelist,BEtargetlist,BEsourcelocs,BEtargetlocs,.03]

Definition of Cograph

Cograph[func_,slist_,tlist_,slocs_,tlocs_,gap_]:=
Graphics[{Arrowheads->Small,DisplayNodes[slist,slocs] ~Join~DisplayNodes[tlist,tlocs]~Join~ArrowList[func,slist,tlist,slocs,tlocs,gap]}]

Cograph of the Basic Example

Show[
Cograph[f,BEsourcelist,BEtargetlist,BErowsourcelocs,BErowtargetlocs,Scaled[.0005]],ImageSize->100,AspectRatio->.5]

Show[
Cograph[f,BEsourcelist,BEtargetlist,BEsourcelocs,BEtargetlocs,Scaled[.0005]],ImageSize->50,AspectRatio->3]

Alternative ordering

An alternative ordering of the nodes makes a clearer picture of how the function behaves. Note that the sourcelocs and targetlocs are the same.

f2[a]:=c;f2[b]:=a;f2[c]:=c;f2[d]:=b;f2[e]:=d

sourcelist2:={c,a,b,d,e};targetlist2:={c,a,b,d}

Show[
Cograph[f2,sourcelist2,targetlist2,BEsourcelocs,BEtargetlocs,Scaled[.0005]],ImageSize->50,AspectRatio->3]

Horizontal cograph

rearrcograph:=Show[
Cograph[f2,sourcelist2,targetlist2,{{5,1},{4,1},{3,1},{2,1},{1,1}},{{4.5,0},{3.5,0},{2.5,0},{1.5,0}},Scaled[.0007]],ImageSize->150,AspectRatio->.3]

rearrcograph

Export["W:\\www\\MM\\Mathematica\\Function Representations\\rearrcograph.png",rearrcograph];

Export["W:\\www\\MM\\Mathematica\\Function Representations\\rearrcograph.gif",rearrcograph];

Export["rearrcograph.png",rearrcograph];

Export["rearrcograph.gif",rearrcograph];

An endograph showing the same example

MakeFunctionRule[f_,n_]:=#->f[#]&/@ Table[k,{k,0,n-1}]

MakeRule[f_,l_]:=#->f[#]&/@l

MakeRule[f2,{c,a,b,d,e}]

Endograph[{c->c,a->c,b->a,d->b,e->d},300]

Examples

Example 1

Remove[f,f1,g]

Endographs of g

g[n_]:=Mod[n^2+1,11]

g[#]&/@{0,1,2,3,4,5,6,7,8,9,10,11,12}

MakeFunctionRule[g,13]

Endograph[MakeFunctionRule[g,13],250]

lyout={6->{1,0},7->{0,0},4->{2,0},5->{3,0},9->{3,1},2->{4,0},10->{5,-.66},3->{6,-.33},8->{6,-1.33},1->{5,.66},0->{6,1.33},11->{6,.33},12->{4,1}};

Endograph[MakeFunctionRule[g,13],300,lyout]

Cographs of g

mod12list={0,1,2,3,4,5,6,7,8,9,10,11,12}

sourcelocsEx1:={0,#}&/@mod12list//Reverse

sourcelocsEx1

targetlocsEx1:={1,#}&/@mod12list//Reverse

targetlocsEx1

g[8]

Show[
Cograph[g,{0,1,2,3,4,5,6,7,8,9,10,11,12},{0,1,2,3,4,5,6,7,8,9,10,11,12},{{0,12},{0,11},{0,10},{0,9},{0,8},{0,7},{0,6},{0,5},{0,4},{0,3},{0,2},{0,1},{0,0}},{{1,12},{1,11},{1,10},{1,9},{1,8},{1,7},{1,6},{1,5},{1,4},{1,3},{1,2},{1,1},{1,0}},
Scaled[.0009]],ImageSize->70,AspectRatio->6]

Horizontal cograph

{1,#}&/@mod12list

{0,#}&/@mod12list

Show[
Cograph[g,mod12list,mod12list,{{0,1},{1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{7,1},{8,1},{9,1},{10,1},{11,1},{12,1}},{{0,0},{1,0},{2,0},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0},{9,0},{10,0},{11,0},{12,0}},
Scaled[.0009]],ImageSize->370,AspectRatio->.2]

Cograph of g with rearranged domain

Show[
Cograph[g,{7,6,4,5,9,2,12,10,1,8,3,0,11},{7,6,4,5,9,2,12,10,1,8,3,0,11},{{0,12},{0,11},{0,10},{0,9},{0,8},{0,7},{0,6},{0,5},{0,4},{0,3},{0,2},{0,1},{0,0}},{{1,12},{1,11},{1,10},{1,9},{1,8},{1,7},{1,6},{1,5},{1,4},{1,3},{1,2},{1,1},{1,0}},
Scaled[.0009]],ImageSize->70,AspectRatio->6]

Horizontal rearranged cograph

{#,0}&/@mod12list

{#,1}&/@mod12list

Show[
Cograph[g,{7,6,4,5,9,2,12,10,1,8,3,0,11},{7,6,4,5,9,2,12,10,1,8,3,0,11},{{0,1},{1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{7,1},{8,1},{9,1},{10,1},{11,1},{12,1}},{{0,0},{1,0},{2,0},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0},{9,0},{10,0},{11,0},{12,0}},
Scaled[.0005]],ImageSize->370,AspectRatio->.2]

Example 2: A permutation

Remove[g,h,p]

p[0]:=0;p[1]:=2;p[2]:=1;p[3]:=4;p[4]:=5;p[5]:=3;p[6]:=7;p[7]:=8;p[8]:=9;p[9]:=6;

MakeFunctionRule[p,10]

Endograph

endographperm:=Endograph[{0->0,1->2,2->1,3->4,4->5,5->3,6->7,7->8,8->9,9->6},180]

endographperm

Export["W:\\www\\MM\\Mathematica\\Function Representations\\endographperm.png",endographperm]

Cograph

{#,1}&/@{1,2,3,4,5,6,7,8,9,10}

{#,0}&/@{1,2,3,4,5,6,7,8,9,10}

cographperm:=Show[
Cograph[p,{0,1,2,3,4,5,6,7,8,9},{0,1,2,3,4,5,6,7,8,9},{{1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{7,1},{8,1},{9,1},{10,1}},{{1,0},{2,0},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0},{9,0},{10,0}},
Scaled[.0006]],ImageSize->300,AspectRatio->.2]

cographperm

Export["W:\\www\\MM\\Mathematica\\Function Representations\\cographperm.png",cographperm]

Example 3

Remove[p]

h[0]:=2;h[1]:=2;h[2]:=3;h[3]:=3;h[4]:=15;h[5]:=7;h[6]:=7;h[7]:=15;h[8]:=16;h[9]:=10;h[10]:=14;h[11]:=13;h[12]:=14;h[13]:=14;h[14]:=17;h[15]:=16;h[16]:=17;h[17]:=15

Endograph

hrule=MakeFunctionRule[h,18]

Endograph[hrule,300]

hlayout={3->{-.3,-1},2->{-.3,0},0->{-.8,1},1->{.3,1},5->{1,.6},6->{1,-.6},7->{2,0},15->{3,0},4->{3,1},16->{3.5,-1},8->{3.5,-2},17->{4,0},14->{5,0},12->{5,1},13->{6,.6},10->{6,-.7},9->{7,-1.6},11->{7,1.3}};

bigendo:=Endograph[hrule,300,hlayout]

Export["W:\\www\\MM\Mathematica\\Function Representations\\bigendo.png",bigendo]

Cograph

Not rearranged

{#,1}&/@Table[i,{i,0,17}]

{#,0}&/@Table[i,{i,0,17}]

Show[
Cograph[h,Table[i,{i,0,17}],Table[i,{i,0,17}],{#,1}&/@Table[i,{i,0,17}],{#,0}&/@Table[i,{i,0,17}],
Scaled[.0010]],ImageSize->400,AspectRatio->.2]

Rearranged

h[0]:=2;h[1]:=2;h[2]:=3;h[3]:=3;h[4]:=15;h[5]:=7;h[6]:=7;h[7]:=15;h[8]:=16;h[9]:=10;h[10]:=14;h[11]:=13;h[12]:=14;h[13]:=14;h[14]:=17;h[15]:=16;h[16]:=17;h[17]:=15

hdomrearr={0,1,2,3,5,6,7,4,8,15,16,17,14,10,12,13,9,11};

Show[
Cograph[h,hdomrearr,hdomrearr,{#,1}&/@Table[i,{i,0,17}],{#,0}&/@Table[i,{i,0,17}],
Scaled[.0010]],ImageSize->400,AspectRatio->.2]

Example 4

Remove[h]

Endograph

newrule:={0->2,1->2,2->3,3->4,4->3,5->4,6->3,7->5,8->16,9->16,10->14,11->13,12->15,13->14,14->17,15->16,16->17,17->15}

Endograph[newrule,300]

newlayout={0->{0,-.3},1->{0,.3},2->{1,0},3->{2,0},4->{3,0},5->{4,0},6->{2,1},7->{5,0},8->{0.5,-2},9->{2.5,-2},10->{4,-1.6},11->{5,-1},12->{0,-1},13->{4,-1},14->{3,-1},15->{1,-1},16->{1.5,-2},17->{2,-1}}

bigendo2:=Endograph[newrule,390,newlayout,Scaled[.0008]]

bigendo2

Export["W:\\www\\MM\\Mathematica\\Function Representations\\bigendo.png",bigendo2]

Example 5 : a tree

t[1]:=4;t[2]:=4;t[3]:=6;t[4]:=4;t[5]:=2;t[6]:=4;t[7]:=2;t[8]:=7;t[9]:=7;t[0]:=6

Endograph

trule=MakeFunctionRule[t,10]

treeex:=Endograph[trule,280]

treeex

Export["W:\\www\\MM\\Mathematica\\Function Representations\\treeex.png",treeex]

Cograph

Show[
Cograph[t,Table[i,{i,0,9}],Table[i,{i,0,9}],{#,1}&/@Table[i,{i,0,9}],{#,0}&/@Table[i,{i,0,9}],
Scaled[.0010]],ImageSize->300,AspectRatio->.2]

tdomrearr={9,8,7,5,2,4,1,6,0,3};

Show[
Cograph[t,tdomrearr,tdomrearr,{#,1}&/@Table[i,{i,0,9}],{#,0}&/@Table[i,{i,0,9}],
Scaled[.0010]],ImageSize->300,AspectRatio->.2]

Example 6

For any endofunction of a finite field of order q,  x^(q-2) is a permutation.

xp[n_]:=Mod[n^15,17]

Endograph[MakeFunctionRule[xp,17],250]

xp2[n_]:=Mod[n^15+5n^14-n^10,17]

Endograph[MakeFunctionRule[xp2,17],350]

xp3[n_]:=Mod[n^14,17]

Endograph[MakeFunctionRule[xp3,17],250]

xp4[n_]:=Mod[n^14+10,17]

Endograph[MakeFunctionRule[xp4,17],250]

xp5[n_]:=Mod[6n+5,17]

Endograph[MakeFunctionRule[xp5,17],300]

xp6[n_]:=Mod[6n^2+5,17]

Endograph[MakeFunctionRule[xp6,17],330]

Other notations

Table

tableop[x_]:=Style[x,16]

grid1:=Show[
Graphics[{Text[Grid[{{tableop[a],tableop[c]},{tableop[b],tableop[a]},{tableop[c],tableop[c]},{tableop[d],tableop[b]},{tableop[e],tableop[d]}},Frame->All],{0,0}]
}
],ImageSize->80]

grid1

Export["W:\\www\\MM\\Mathematica\\Function Representations\\grid1.png",grid1]

grid2:=
Text[Grid[{{tableop["Albert Singlestone"],tableop["Personnel"]},{tableop["Eva Peron"],tableop["Information Services"]},{tableop["Minnie Tonka"],tableop["Head Office"]},{tableop["Theodore Rosefield"],tableop["Personnel"]},{tableop["Roy Roget"],tableop["Head Office"]}},Alignment->Left,Frame->All]]

grid2

Export["W:\\www\\MM\\Mathematica\\Function Representations\\grid2.png",grid2]

"W:\\www\\MM\\Mathematica\\Function Representations\\grid2.png"

{320,200}1.1