# Functions to construct graphs.

### Description

Functions to construct graphs- see details below.

### Usage

1 2 3 4 5 6 7 8 9 10 11 12 | ```
knn_graph(g, k = 2)
dn_graph(g, d = 1, test=`<=`)
mk_binary_graph(n,sep="",delta=1,test=`==`)
mk_hypercube_graph(n,sep="")
mk_line_graph(g,sep="-")
kspace_graph(n,m, link=NULL,sep="-")
graph_product(g,h, type="cartesian",sep="-")
graph_compose(g,h,sep="-")
graph_sum(g,h,combineWeight=`+`)
bipartite_graph(n1,n2)
iterated_line_graph(g,sep="-")
``` |

### Arguments

`g` |
a graph |

`h` |
a graph |

`n` |
a positive integer, or a character vector. |

`k` |
a positive integer |

`d` |
an edge weight |

`test` |
used to select edges. |

`sep` |
used to form node names of new graph. |

`m` |
subsets of size m are nodes of kneser graph. |

`link` |
A positive number or NULL. If NULL, the returned graph is complete. Otherwise edges for subsets sharing link elements. |

`type` |
the type of graph product, one of "cartesian", "strong" or "tensor" |

`n1` |
a character vector. |

`n2` |
a character vector. |

`delta` |
used to select edges. |

`combineWeight` |
used to combine weights. |

### Details

knn_graph- returns a symmetric k nearest neighbour graph

dn_graph- returns a graph formed from g where edges of satisfy test(weight, d). The default retains edges whose weight are 1 are less. Nodes with no edges are also removed.

mk_hypercube_graph- returns a hypercube graph with $2^n$ nodes

mk_binary_graph(n,sep="",delta=1,test='==') - returns a graph with $2^n$ nodes. Undirected edges join nodes A and B whose binary vectors satisfy *a_i ≤q b_i$,$i=1, …, n* and test(*∑(b_i - a_i)*, delta) is true.

mk_line_graph- returns the line graph of g

kspace_graph- returns a graph where nodes are subsets of size m from n. Edges are connect nodes whose subsets share link elements. The standard kneser graph has link=0. When link is NULL, returned graph is complete.

graph_product(g,h, type="cartesian",sep="-")- returns the graph product of g and h.

graph_compose(g,h,sep="-")- returns the graph composition of g and h.

bipartite_graph(n1,n2)- returns the complete bipartite graph with node sets n1 and n2.

graph_sum(g,h,combineWeight='+')- returns a graph whose nodes and edges are the union of those in g and h. Weights of common edges are combined using combineWeight.

iterated_line_graph- returns the iterated line graph of g, with compression of nodes as described in the reference Hurley and Oldford(2008) given below.

### Author(s)

C.B. Hurley and R.W. Oldford

### References

See any Graph Theory text. Also C.B. Hurley and R.W. Oldford, Graphs as navigational infrastructure for high dimensional data spaces. 2008 submitted.

### Examples

1 2 | ```
# See the demo file nav.R
``` |