| Title: | A package providing hypergraph data structures |
|---|---|
| Description: | A package that implements some simple capabilities for representing and manipulating hypergraphs. |
| Authors: | Seth Falcon, Robert Gentleman |
| Maintainer: | Bioconductor Package Maintainer <[email protected]> |
| License: | Artistic-2.0 |
| Version: | 1.77.0 |
| Built: | 2024-07-03 05:16:47 UTC |
| Source: | https://github.com/bioc/hypergraph |
A convenience constructor for DirectedHyperedge-class
objects
DirectedHyperedge(head, tail, label = "")DirectedHyperedge(head, tail, label = "")
head |
Character vector of nodes that are part of the head of the hyperedge |
tail |
Character vector of nodes that part of the tail of the hyperedge |
label |
A character string describing the directed hyperedge |
An object of class DirectedHyperedge-class
Seth Falcon
DirectedHyperedge-class
Hyperedge-class
Hypergraph-class
This class represents directed hyperedges in a
Hypergraph-class. A directed hyperedge consists of two
disjount sets of nodes, those in the tail and those in the head of the
hyperedge. Directed hyperedges are sometimes called hyperarcs.
Objects can be created by calls of the form new("DirectedHyperedge", head, tail, label).
You can also use the convenience function DirectedHyperedge.
tail:Character vector of nodes in the tail of the hyperedge
head:Character vector of nodes in the head of the hyperege
label:Character string describing the directed hyperedge
Class "Hyperedge", directly.
signature(x = "DirectedHyperedge"): Return a
vector containing the nodes in the head of the hyperedge
signature(x = "DirectedHyperedge"): Return a
vector containing the nodes in the tail of the hyperedge
signature(.Object = "DirectedHyperedge"):
Create a new instance.
signature(object = "DirectedHyperedge"): Return
a vector containing all nodes present in the hyperedge.
signature(object = "DirectedHyperedge"): Print me
signature(.Object = "DirectedHyperedge"):
Return a Hyperedge-class object that results from
coercing to an undirected hyperedge.
Seth Falcon
DirectedHyperedge
Hyperedge
Hyperedge-class
Hypergraph-class
head <- LETTERS[1:4] tail <- LETTERS[19:21] label <- "Directed hyperedge" dhe <- new("DirectedHyperedge", head=head, tail=tail, label=label)head <- LETTERS[1:4] tail <- LETTERS[19:21] label <- "Directed hyperedge" dhe <- new("DirectedHyperedge", head=head, tail=tail, label=label)
A convenience constructor for Hyperedge-class objects
Hyperedge(nodes, label = "")Hyperedge(nodes, label = "")
nodes |
Character vector of nodes that are part of the hyperedge |
label |
A character string describing the hyperedge |
An object of class Hyperedge-class
Seth Falcon
Hyperedge-class
Hypergraph-class
A Hyperedge object represents a hyperedge in a hypergraph, that is, a subset of the nodes of a hypergraph.
Objects can be created by calls of the form new("Hyperedge",
nodes, label).
You can also use the convenience function Hyperedge to create
instances. This is especially useful for creating a list of
Hyperedge instances using lapply.
head:A vector of mode "character" containing
the node labels that are a part of the hyperedge
label:An arbitrary "character" string
describing this hyperedge
signature(.Object = "Hyperedge"): Create an
instance
signature(object = "Hyperedge"): Return the
value of the label slot
signature(object = "Hyperedge", value =
"character"): Set the label slot.
signature(object = "Hyperedge"): Return a
vector containing the nodes in the hyperedge
signature(object = "Hyperedge"): Print a textual
summary of the hyperedge
Seth Falcon
Hyperedge
Hypergraph-class
DirectedHyperedge-class
nodes <- LETTERS[1:4] label <- "Simple hyperedge" ## Use the convenience constructor he <- Hyperedge(nodes, label)nodes <- LETTERS[1:4] label <- "Simple hyperedge" ## Use the convenience constructor he <- Hyperedge(nodes, label)
A convenience constructor for link{Hypergraph-class} objects
Hypergraph(nodes, hyperedges)Hypergraph(nodes, hyperedges)
nodes |
A vector of nodes (character) |
hyperedges |
A list of |
An object of class Hypergraph-class
Seth Falcon
Hypergraph-class
Hyperedge-class
DirectedHyperedge-class
A hypergraph consists of a set of nodes and a set of hyperedges. Each hyperedge is a subset of the node set. This class provides a representation of a hypergraph that is (hopefully) useful for computing.
Objects can be created by calls of the form new("Hypergraph", nodes, hyperedges).
You can also use the convenience function Hypergraph. The
nodes argument should be a character vector of distinct labels
representing the nodes of the hypergraph. The hyperedges
argument must be a list of Hyperedge-class objects.
nodes:A "character" vector specifying the nodes
hyperedges:A "list" of
Hyperedge-class objects
signature(.Object = "Hypergraph"): Return
the list of Hyperedge objects
signature(.Object = "Hypergraph"): Return
a character vector of labels for the Hyperedge objects in the
hypergraph.
signature(.Object = "Hypergraph"): Return the
incidence matrix representation of this hypergraph
signature(.Object = "matrix"): Return the
hypergraph representation of this incidence matrix
signature(.Object = "Hypergraph"): Create
an instance
signature(object = "Hypergraph"): Return the
vector of nodes (character vector)
signature(object = "Hypergraph"): Return the
number of nodes in the hypergraph
signature(.Object = "Hypergraph"): Return
the graphNEL representation of the hypergraph (a bipartite
graph)
Seth Falcon
Hyperedge-class
DirectedHyperedge-class
graphNEL-class
nodes <- LETTERS[1:4] hEdges <- lapply(list("A", LETTERS[1:2], LETTERS[3:4]), "Hyperedge") hg <- new("Hypergraph", nodes=nodes, hyperedges=hEdges)nodes <- LETTERS[1:4] hEdges <- lapply(list("A", LETTERS[1:2], LETTERS[3:4]), "Hyperedge") hg <- new("Hypergraph", nodes=nodes, hyperedges=hEdges)
Find all the k-cores in a hypergraph
kCoresHypergraph(hg)kCoresHypergraph(hg)
hg |
an instance of the |
A k-core in a hypergraph is a maximal subhypergraph where (a) no hyperedge
is contained in another, and (b) each node is adjacent to at least k
hyperedges in the subgraph.
The implementation is based on the algorithm by E. Ramadan, A. Tarafdar, A. Pothen, 2004.
A vector of the core numbers for all the nodes in g.
Li Long <[email protected]>
A hypergraph model for the yeast protein complex network, Ramadan, E. Tarafdar, A. Pothen, A., Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International.
# to turn the snacoreex.gxl (from RBGL package) graph to a hypergraph # this is a rough example kc_hg_n <- c("A", "C", "B", "E", "F", "D", "G", "H", "J", "K", "I", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U") kc_hg_e <- list(c("A", "C"), c("B", "C"), c("C", "E"), c("C", "F"), c("E", "D"), c("E", "F"), c("D", "G"), c("D", "H"), c("D", "J"), c("H", "G"), c("H", "J"), c("G", "J"), c("J", "M"), c("J", "K"), c("M", "K"), c("M", "O"), c("M", "N"), c("K", "N"), c("K", "F"), c("K", "I"), c("K", "L"), c("F", "I"), c("I", "L"), c("F", "L"), c("P", "Q"), c("Q", "R"), c("Q", "S"), c("R", "T"), c("S", "T")) kc_hg_he <- lapply(kc_hg_e, "Hyperedge") kc_hg <- new("Hypergraph", nodes=kc_hg_n, hyperedges=kc_hg_he) kCoresHypergraph(kc_hg)# to turn the snacoreex.gxl (from RBGL package) graph to a hypergraph # this is a rough example kc_hg_n <- c("A", "C", "B", "E", "F", "D", "G", "H", "J", "K", "I", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U") kc_hg_e <- list(c("A", "C"), c("B", "C"), c("C", "E"), c("C", "F"), c("E", "D"), c("E", "F"), c("D", "G"), c("D", "H"), c("D", "J"), c("H", "G"), c("H", "J"), c("G", "J"), c("J", "M"), c("J", "K"), c("M", "K"), c("M", "O"), c("M", "N"), c("K", "N"), c("K", "F"), c("K", "I"), c("K", "L"), c("F", "I"), c("I", "L"), c("F", "L"), c("P", "Q"), c("Q", "R"), c("Q", "S"), c("R", "T"), c("S", "T")) kc_hg_he <- lapply(kc_hg_e, "Hyperedge") kc_hg <- new("Hypergraph", nodes=kc_hg_n, hyperedges=kc_hg_he) kCoresHypergraph(kc_hg)
Conveniently create lists of Hyperedge-class instances.
l2hel(e)l2hel(e)
e |
A list of character vectors. Each element of the list represents a hyperedge and the character vector value specifies the nodes of the hypergraph that are part of the hyperedge. The names of the list elements, if found, will be used as the label for the corresponding Hyperedge object. |
A list of Hyperedge-class objects. If the list e did
not have names, the labels of the Hyperedges will be set to its index
in the list coerced to character.
Seth Falcon
Hyperedge-class
Hypergraph-class
edges <- list("e1"="A", "e2"=c("A", "B"), "e3"=c("C", "D")) hEdgeList <- l2hel(edges)edges <- list("e1"="A", "e2"=c("A", "B"), "e3"=c("C", "D")) hEdgeList <- l2hel(edges)
Approximate minimum weight vertex cover in a hypergraph
vCoverHypergraph(hg, vW=rep(1, numNodes(hg)))vCoverHypergraph(hg, vW=rep(1, numNodes(hg)))
hg |
an instance of the |
vW |
vertex weights |
Hypergraph g has non-negative weights on its vertices.
The minimum weight vertex cover problem is to find a subset of vertices C
such that C includes at least one vertex from each hyperedge and the sum of
the weights of the vertices in C is minimum. This problem is NP-hard.
We implement the greedy algorithm to approximate near-optimal solution, proposed by E. Ramadan, A. Tarafdar, A. Pothen, 2004.
A list of vertices from hypergraph g.
Li Long <[email protected]>
A hypergraph model for the yeast protein complex network, Ramadan, E. Tarafdar, A. Pothen, A., Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International.
# to turn the snacoreex.gxl graph (from RBGL package) to a hypergraph # this is a rough example kc_hg_n <- c("A", "C", "B", "E", "F", "D", "G", "H", "J", "K", "I", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U") kc_hg_e <- list(c("A", "C"), c("B", "C"), c("C", "E"), c("C", "F"), c("E", "D"), c("E", "F"), c("D", "G"), c("D", "H"), c("D", "J"), c("H", "G"), c("H", "J"), c("G", "J"), c("J", "M"), c("J", "K"), c("M", "K"), c("M", "O"), c("M", "N"), c("K", "N"), c("K", "F"), c("K", "I"), c("K", "L"), c("F", "I"), c("I", "L"), c("F", "L"), c("P", "Q"), c("Q", "R"), c("Q", "S"), c("R", "T"), c("S", "T")) kc_hg_he <- lapply(kc_hg_e, "Hyperedge") kc_hg <- new("Hypergraph", nodes=kc_hg_n, hyperedges=kc_hg_he) vCoverHypergraph(kc_hg)# to turn the snacoreex.gxl graph (from RBGL package) to a hypergraph # this is a rough example kc_hg_n <- c("A", "C", "B", "E", "F", "D", "G", "H", "J", "K", "I", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U") kc_hg_e <- list(c("A", "C"), c("B", "C"), c("C", "E"), c("C", "F"), c("E", "D"), c("E", "F"), c("D", "G"), c("D", "H"), c("D", "J"), c("H", "G"), c("H", "J"), c("G", "J"), c("J", "M"), c("J", "K"), c("M", "K"), c("M", "O"), c("M", "N"), c("K", "N"), c("K", "F"), c("K", "I"), c("K", "L"), c("F", "I"), c("I", "L"), c("F", "L"), c("P", "Q"), c("Q", "R"), c("Q", "S"), c("R", "T"), c("S", "T")) kc_hg_he <- lapply(kc_hg_e, "Hyperedge") kc_hg <- new("Hypergraph", nodes=kc_hg_n, hyperedges=kc_hg_he) vCoverHypergraph(kc_hg)