"""
.. module:: undirected_hypergraph
:synopsis: Defines UndirectedHypergraph class for the basic properties
of an undirected hypergraph, along with the relevant structures
regarding nodes, hyperedges, adjacency, etc.
"""
import copy
[docs]class UndirectedHypergraph(object):
"""
The UndirectedHypergraph class provides an undirected hypergraph object
and associated functions for basic properties of undirected hypergraphs.
An undirected hypergraph contains nodes and undirected hyperedges. Each
undirected hyperedge simply connects a set of nodes. An undirected
hypergraph is a special case of an undirected graph, where each edge
connects exactly 2 nodes. The set of nodes cannot be empty.
A node is simply any hashable type. See "add_node" or "add_nodes" for
more details.
An undirected hyperedge is any iterable container of nodes.
This class assigns (upon adding) and refers to each hyperedge by an
internal ID. See "add_hyperedge" or "add_hyperedges" for more details.
Self-loops and parallel (multi-) hyperedges are not allowed.
:note: This class uses several data structures to store a undirected
hypergraph. Since these structures must stay in sync (see: __init__),
we highly recommend that only the public methods be used for accessing
and modifying the hypergraph.
Examples:
Create an empty undirected hypergraph (no nodes or hyperedges).
>>> H = UndirectedHypergraph()
Add nodes (with or without attributes) to the hypergraph
one at a time (see: add_node) or several at a time (see: add_nodes).
>>> H.add_nodes(["A", "B", "C", "D"], {color: "black"})
Add hyperedges to the hypergraph one at a time (see: add_hyperedge)
or several at a time (see: add_hyperedges).
>>> H.add_hyperedges(["A", "B"], ("A", "C", "D"))
Update attributes of existing nodes and hyperedges by simulating adding the
node or hyperedge again, with the [potentially new] attribute appended.
>>> H.add_node("A", label="sink")
>>> H.add_hyperedge(["A", "C", "D"], weight=5)
"""
def __init__(self):
"""
Constructor for the UndirectedHypergraph class.
Initializes all internal data structures used for the rapid
execution of most of the fundamental hypergraph queries.
"""
# _node_attributes: a dictionary mapping a node (any hashable type)
# to a dictionary of attributes of that node.
#
# Provides O(1) time access to the attributes of a node.
#
# Used in the implementation of methods such as add_node and
# get_node_attributes.
#
self._node_attributes = {}
# _hyperedge_attributes: a dictionary mapping a hyperedge ID
# (initially created by the call to add_hyperedge or add_hyperedges)
# to a dictionary of attributes of that hyperedge.
# Given a hyperedge ID, _hyperedge_attributes[hyperedge_id] stores
# the nodes of the hyperedge as specified by the user (as "nodes")
# and the weight of the hyperedge (as "weight").
# For internal purposes, it also stores the frozenset version of
# the nodes (as "_frozen_nodes").
#
# Provides O(1) time access to the attributes of a hyperedge.
#
# Used in the implementation of methods such as add_hyperedge and
# get_hyperedge_attributes.
#
self._hyperedge_attributes = {}
# The star of a node is the set of hyperedges such that the
# node is a member of.
#
# _star: a dictionary mapping a node to the set of hyperedges
# that are in that node's star.
#
# Provides O(1) time access to a reference to the set of hyperedges
# that a node is a member of.
#
# Used in the implementation of methods such as add_node and
# remove_hyperedge.
#
self._star = {}
# _node_set_to_hyperedge: a dictionary mapping a set of nodes to the ID
# of the hyperedge they compose. We represent the node set by a
# frozenset, so that the structure is hashable.
#
# Provides O(1) time access to the ID of the hyperedge that
# a specific frozenset of nodes composes.
#
self._node_set_to_hyperedge = {}
# _current_hyperedge_id: an int representing the hyperedge ID that
# was most recently assigned by the class (since users don't
# name/ID their own hyperedges); hyperedges being added are issued
# ID "e"+_current_hyperedge_id.
#
# Since the class takes responsibility for giving hyperedges
# their IDs (i.e. a unique identifier; could be alternatively viewed
# as a unique name, label, etc.), the class keeps track of the issued
# IDs. A consecutive issuing of integer IDs to the hyperedges is a
# simple strategy to ensure their uniqueness while allowing for
# readability.
#
# e.g., _current_hyperedge_id = 4 implies that 4 hyperedges have
# been added to the hypergraph, and that "e4" was the most recently
# assigned hyperedge.
#
# Note: An hyperedge, once added, will receive a unique ID. If this
# hyperedge is removed and subsequently re-added, it will not receive
# the same ID as it was issued when it was originally added.
#
self._current_hyperedge_id = 0
def _combine_attribute_arguments(self, attr_dict, attr):
# Note: Code & comments unchanged from DirectedHypergraph
"""Combines attr_dict and attr dictionaries, by updating attr_dict
with attr.
:param attr_dict: dictionary of attributes of the node.
:param attr: keyword arguments of attributes of the node;
attr's values will override attr_dict's values
if both are provided.
:returns: dict -- single dictionary of [combined] attributes.
:raises: AttributeError -- attr_dict argument must be a dictionary.
"""
# If no attribute dict was passed, treat the keyword
# arguments as the dict
if attr_dict is None:
attr_dict = attr
# Otherwise, combine the passed attribute dict with
# the keyword arguments
else:
try:
attr_dict.update(attr)
except AttributeError:
raise AttributeError("attr_dict argument \
must be a dictionary.")
return attr_dict
[docs] def has_node(self, node):
# Note: Code & comments unchanged from DirectedHypergraph
"""Determines if a specific node is present in the hypergraph.
:param node: reference to the node whose presence is being checked.
:returns: bool -- true iff the node exists in the hypergraph.
"""
return node in self._node_attributes
[docs] def add_node(self, node, attr_dict=None, **attr):
"""Adds a node to the graph, along with any related attributes
of the node.
:param node: reference to the node being added.
:param attr_dict: dictionary of attributes of the node.
:param attr: keyword arguments of attributes of the node;
attr's values will override attr_dict's values
if both are provided.
:note: Following the NetworkX model, we allow both a dictionary
of attributes to be passed in by the user as well as key-value
pairs of attributes to be passed in by the user to provide
greater flexibility. This pattern is followed in methods such
as add_nodes, add_hyperedge, and add_hyperedges.
Examples:
::
>>> H = UndirectedHypergraph()
>>> attributes = {label: "positive"}
>>> H.add_node("A", attributes)
>>> H.add_node("B", label="negative")
>>> H.add_node("C", attributes, root=True)
"""
attr_dict = self._combine_attribute_arguments(attr_dict, attr)
# If the node hasn't previously been added, add it along
# with its attributes
if not self.has_node(node):
self._node_attributes[node] = attr_dict
self._star[node] = set()
# Otherwise, just update the node's attributes
else:
self._node_attributes[node].update(attr_dict)
[docs] def add_nodes(self, nodes, attr_dict=None, **attr):
# Note: Code & comments unchanged from DirectedHypergraph
"""Adds multiple nodes to the graph, along with any related attributes
of the nodes.
:param nodes: iterable container to either references of the nodes
OR tuples of (node reference, attribute dictionary);
if an attribute dictionary is provided in the tuple,
its values will override both attr_dict's and attr's
values.
:param attr_dict: dictionary of attributes shared by all the nodes.
:param attr: keyword arguments of attributes of the node;
attr's values will override attr_dict's values
if both are provided.
See also:
add_node
Examples:
::
>>> H = UndirectedHypergraph()
>>> attributes = {label: "positive"}
>>> node_list = ["A",
("B", {label="negative"}),
("C", {root=True})]
>>> H.add_nodes(node_list, attributes)
"""
attr_dict = self._combine_attribute_arguments(attr_dict, attr)
for node in nodes:
# Note: This won't behave properly if the node is actually a tuple
if type(node) is tuple:
# See ("B", {label="negative"}) in the documentation example
new_node, node_attr_dict = node
# Create a new dictionary and load it with node_attr_dict and
# attr_dict, with the former (node_attr_dict) taking precedence
new_dict = attr_dict.copy()
new_dict.update(node_attr_dict)
self.add_node(new_node, new_dict)
else:
# See "A" in the documentation example
self.add_node(node, attr_dict.copy())
[docs] def remove_node(self, node):
"""Removes a node and its attributes from the hypergraph. Removes
every hyperedge that contains this node.
:param node: reference to the node being added.
:raises: ValueError -- No such node exists.
Examples:
::
>>> H = UndirectedHypergraph()
>>> H.add_node("A", label="positive")
>>> H.remove_node("A")
"""
if not self.has_node(node):
raise ValueError("No such node exists.")
# Loop over every hyperedge in the star of the node;
# i.e., over every hyperedge that contains the node
for hyperedge_id in self._star[node]:
frozen_nodes = \
self._hyperedge_attributes[hyperedge_id]["__frozen_nodes"]
# Remove the node set composing the hyperedge
del self._node_set_to_hyperedge[frozen_nodes]
# Remove this hyperedge's attributes
del self._hyperedge_attributes[hyperedge_id]
# Remove node's star
del self._star[node]
# Remove node's attributes dictionary
del self._node_attributes[node]
[docs] def remove_nodes(self, nodes):
# Note: Code unchanged from DirectedHypergraph
"""Removes multiple nodes and their attributes from the graph. If
the nodes are part of any hyperedges, those hyperedges are removed
as well.
:param nodes: iterable container to either references of the nodes
OR tuples of (node reference, attribute dictionary);
if an attribute dictionary is provided in the tuple,
its values will override both attr_dict's and attr's
values.
See also:
remove_node
Examples:
::
>>> H = UndirectedHypergraph()
>>> attributes = {label: "positive"}
>>> node_list = ["A",
("B", {label="negative"}),
("C", {root=True})]
>>> H.add_nodes(node_list, attributes)
>>> H.remove_nodes(["A", "B", "C"])
"""
for node in nodes:
self.remove_node(node)
[docs] def get_node_set(self):
# Note: Code and comments unchanged from DirectedHypergraph
"""Returns the set of nodes that are currently in the hypergraph.
:returns: set -- all nodes currently in the hypergraph
"""
return set(self._node_attributes.keys())
[docs] def node_iterator(self):
# Note: Code and comments unchanged from DirectedHypergraph
"""Provides an iterator over the nodes.
"""
return iter(self._node_attributes)
[docs] def get_node_attribute(self, node, attribute_name):
# Note: Code and comments unchanged from DirectedHypergraph
"""Given a node and the name of an attribute, get a copy
of that node's attribute.
:param node: reference to the node to retrieve the attribute of.
:param attribute_name: name of the attribute to retrieve.
:returns: attribute value of the attribute_name key for the
specified node.
:raises: ValueError -- No such node exists.
:raises: ValueError -- No such attribute exists.
"""
if not self.has_node(node):
raise ValueError("No such node exists.")
elif attribute_name not in self._node_attributes[node]:
raise ValueError("No such attribute exists.")
else:
return copy.\
copy(self._node_attributes[node][attribute_name])
[docs] def get_node_attributes(self, node):
# Note: Code and comments unchanged from DirectedHypergraph
"""Given a node, get a dictionary with copies of that node's
attributes.
:param node: reference to the node to retrieve the attributes of.
:returns: dict -- copy of each attribute of the specified node.
:raises: ValueError -- No such node exists.
"""
if not self.has_node(node):
raise ValueError("No such node exists.")
attributes = {}
for attr_name, attr_value in self._node_attributes[node].items():
attributes[attr_name] = copy.copy(attr_value)
return attributes
def _assign_next_hyperedge_id(self):
# Note: Code and comments unchanged from DirectedHypergraph
"""Returns the next [consecutive] ID to be assigned
to a hyperedge.
:returns: str -- hyperedge ID to be assigned.
"""
self._current_hyperedge_id += 1
return "e" + str(self._current_hyperedge_id)
[docs] def add_hyperedge(self, nodes, attr_dict=None, **attr):
"""Adds a hyperedge to the hypergraph, along with any related
attributes of the hyperedge.
This method will automatically add any node from the node set
that was not in the hypergraph.
A hyperedge without a "weight" attribute specified will be
assigned the default value of 1.
:param nodes: iterable container of references to nodes in the
hyperedge to be added.
:param attr_dict: dictionary of attributes of the hyperedge being
added.
:param attr: keyword arguments of attributes of the hyperedge;
attr's values will override attr_dict's values
if both are provided.
:returns: str -- the ID of the hyperedge that was added.
:raises: ValueError -- nodes arguments cannot be empty.
Examples:
::
>>> H = UndirectedHypergraph()
>>> x = H.add_hyperedge(["A", "B", "C"])
>>> y = H.add_hyperedge(("A", "D"), weight=2)
>>> z = H.add_hyperedge(set(["B", "D"]), {color: "red"})
"""
attr_dict = self._combine_attribute_arguments(attr_dict, attr)
# Don't allow empty node set (invalid hyperedge)
if not nodes:
raise ValueError("nodes argument cannot be empty.")
# Use frozensets for node sets to allow for hashable keys
frozen_nodes = frozenset(nodes)
is_new_hyperedge = not self.has_hyperedge(frozen_nodes)
if is_new_hyperedge:
# Add nodes to graph (if not already present)
self.add_nodes(frozen_nodes)
# Create new hyperedge name to use as reference for that hyperedge
hyperedge_id = self._assign_next_hyperedge_id()
# For each node in the node set, add hyperedge to the node's star
for node in frozen_nodes:
self._star[node].add(hyperedge_id)
# Add the hyperedge ID as the hyperedge that the node set composes
self._node_set_to_hyperedge[frozen_nodes] = hyperedge_id
# Assign some special attributes to this hyperedge. We assign
# a default weight of 1 to the hyperedge. We also store the
# original node set in order to return them exactly as the
# user passed them into add_hyperedge.
self._hyperedge_attributes[hyperedge_id] = \
{"nodes": nodes, "__frozen_nodes": frozen_nodes, "weight": 1}
else:
# If its not a new hyperedge, just get its ID to update attributes
hyperedge_id = self._node_set_to_hyperedge[frozen_nodes]
# Set attributes and return hyperedge ID
self._hyperedge_attributes[hyperedge_id].update(attr_dict)
return hyperedge_id
[docs] def add_hyperedges(self, hyperedges, attr_dict=None, **attr):
"""Adds multiple hyperedges to the graph, along with any related
attributes of the hyperedges.
If any node of a hyperedge has not previously been added to the
hypergraph, it will automatically be added here.
Hyperedges without a "weight" attribute specified will be
assigned the default value of 1.
:param hyperedges: iterable container to references of the node sets
:param attr_dict: dictionary of attributes shared by all
the hyperedges being added.
:param attr: keyword arguments of attributes of the hyperedges;
attr's values will override attr_dict's values
if both are provided.
:returns: list -- the IDs of the hyperedges added in the order
specified by the hyperedges container's iterator.
See also:
add_hyperedge
Examples:
::
>>> H = UndirectedHypergraph()
>>> hyperedge_list = (["A", "B", "C"],
("A", "D"),
set(["B", "D"]))
>>> hyperedge_ids = H.add_hyperedges(hyperedge_list)
"""
attr_dict = self._combine_attribute_arguments(attr_dict, attr)
hyperedge_ids = []
for nodes in hyperedges:
hyperedge_id = self.add_hyperedge(nodes, attr_dict.copy())
hyperedge_ids.append(hyperedge_id)
return hyperedge_ids
[docs] def remove_hyperedge(self, hyperedge_id):
"""Removes a hyperedge and its attributes from the hypergraph.
:param hyperedge_id: ID of the hyperedge to be removed.
:raises: ValueError -- No such hyperedge exists.
Examples:
::
>>> H = UndirectedHypergraph()
>>> hyperedge_list = (["A", "B", "C"],
("A", "D"),
set(["B", "D"]))
>>> hyperedge_ids = H.add_hyperedges(hyperedge_list)
>>> H.remove_hyperedge(hyperedge_ids[0])
>>> BD_id = H.get_hyperedge_id(set(["B", "D"]))
>>> H.remove_hyperedge(BD_id)
"""
if not self.has_hyperedge_id(hyperedge_id):
raise ValueError("No such hyperedge exists.")
frozen_nodes = \
self._hyperedge_attributes[hyperedge_id]["__frozen_nodes"]
# Remove this hyperedge from the star of every node in the hyperedge
for node in frozen_nodes:
self._star[node].remove(hyperedge_id)
# Remove this set as the composer of the hyperedge
del self._node_set_to_hyperedge[frozen_nodes]
# Remove hyperedge's attributes dictionary
del self._hyperedge_attributes[hyperedge_id]
[docs] def remove_hyperedges(self, hyperedge_ids):
# Note: Code unchanged from DirectedHypergraph
"""Removes a set of hyperedges and their attributes from
the hypergraph.
:param hyperedge_ids: iterable container of IDs of the hyperedges
to be removed.
:raises: ValueError -- No such hyperedge exists.
See also:
remove_hyperedge
Examples:
::
>>> H = UndirectedHypergraph()
>>> hyperedge_list = (["A", "B", "C"],
("A", "D"),
set(["B", "D"]))
>>> hyperedge_ids = H.add_hyperedges(hyperedge_list)
>>> H.remove_hyperedges(hyperedge_ids)
"""
for hyperedge_id in hyperedge_ids:
self.remove_hyperedge(hyperedge_id)
[docs] def has_hyperedge(self, nodes):
# Note: Code and comments unchanged from DirectedHypergraph
"""Given a set of nodes, returns whether there is a hyperedge in the
hypergraph that is precisely composed of those nodes.
:param nodes: iterable container of references to nodes in the
hyperedge being checked.
:returns: bool -- true iff a hyperedge exists composed of the
specified nodes.
"""
frozen_nodes = frozenset(nodes)
return frozen_nodes in self._node_set_to_hyperedge
[docs] def has_hyperedge_id(self, hyperedge_id):
# Note: Code and comments unchanged from DirectedHypergraph
"""Determines if a hyperedge referenced by hyperedge_id
exists in the hypergraph.
:param hyperedge_id: ID of the hyperedge whose existence is
being checked.
:returns: bool -- true iff a hyperedge exists that has id hyperedge_id.
"""
return hyperedge_id in self._hyperedge_attributes
[docs] def get_hyperedge_id_set(self):
# Note: Code and comments unchanged from DirectedHypergraph
"""Returns the set of IDs of hyperedges that are currently
in the hypergraph.
:returns: set -- all IDs of hyperedges currently in the hypergraph
"""
return set(self._hyperedge_attributes.keys())
[docs] def hyperedge_id_iterator(self):
# Note: Code and comments unchanged from DirectedHypergraph
"""Provides an iterator over the list of hyperedge IDs.
"""
return iter(self._hyperedge_attributes)
[docs] def get_hyperedge_id(self, nodes):
"""From a set of nodes, returns the ID of the hyperedge that this
set comprises.
:param nodes: iterable container of references to nodes in the
the hyperedge to be added
:returns: str -- ID of the hyperedge that has that the specified
node set comprises.
:raises: ValueError -- No such hyperedge exists.
Examples:
::
>>> H = UndirectedHypergraph()
>>> hyperedge_list = (["A", "B", "C"],
("A", "D"),
set(["B", "D"]))
>>> hyperedge_ids = H.add_hyperedges(hyperedge_list)
>>> x = H.get_hyperedge_id(["A", "B", "C"])
"""
frozen_nodes = frozenset(nodes)
if not self.has_hyperedge(frozen_nodes):
raise ValueError("No such hyperedge exists.")
return self._node_set_to_hyperedge[frozen_nodes]
[docs] def get_hyperedge_attribute(self, hyperedge_id, attribute_name):
# Note: Code unchanged from DirectedHypergraph
"""Given a hyperedge ID and the name of an attribute, get a copy
of that hyperedge's attribute.
:param hyperedge_id: ID of the hyperedge to retrieve the attribute of.
:param attribute_name: name of the attribute to retrieve.
:returns: attribute value of the attribute_name key for the
specified hyperedge.
:raises: ValueError -- No such hyperedge exists.
:raises: ValueError -- No such attribute exists.
Examples:
::
>>> H = UndirectedHypergraph()
>>> hyperedge_list = (["A", "B", "C"],
("A", "D"),
set(["B", "D"]))
>>> hyperedge_ids = H.add_hyperedges(hyperedge_list)
>>> attribute = H.get_hyperedge_attribute(hyperedge_ids[0])
"""
if not self.has_hyperedge_id(hyperedge_id):
raise ValueError("No such hyperedge exists.")
elif attribute_name not in self._hyperedge_attributes[hyperedge_id]:
raise ValueError("No such attribute exists.")
else:
return copy.\
copy(self._hyperedge_attributes[hyperedge_id][attribute_name])
[docs] def get_hyperedge_attributes(self, hyperedge_id):
"""Given a hyperedge ID, get a dictionary of copies of that hyperedge's
attributes.
:param hyperedge_id: ID of the hyperedge to retrieve the attributes of.
:returns: dict -- copy of each attribute of the specified hyperedge_id
(except the private __frozen_nodes entry).
:raises: ValueError -- No such hyperedge exists.
"""
if not self.has_hyperedge_id(hyperedge_id):
raise ValueError("No such hyperedge exists.")
dict_to_copy = self._hyperedge_attributes[hyperedge_id].items()
attributes = {}
for attr_name, attr_value in dict_to_copy:
if attr_name != "__frozen_nodes":
attributes[attr_name] = copy.copy(attr_value)
return attributes
[docs] def get_hyperedge_nodes(self, hyperedge_id):
"""Given a hyperedge ID, get a copy of that hyperedge's nodes.
:param hyperedge_id: ID of the hyperedge to retrieve the nodes from.
:returns: a copy of the container of nodes that the user provided
for the hyperedge referenced as hyperedge_id.
"""
return self.get_hyperedge_attribute(hyperedge_id, "nodes")
[docs] def get_hyperedge_weight(self, hyperedge_id):
# Note: Code and comments unchanged from DirectedHypergraph
"""Given a hyperedge ID, get that hyperedge's weight.
:param hyperedge: ID of the hyperedge to retrieve the weight from.
:returns: int -- the weight of the hyperedge referenced as
hyperedge_id.
"""
return self.get_hyperedge_attribute(hyperedge_id, "weight")
[docs] def get_star(self, node):
"""Given a node, get a copy of that node's star, that is, the set of
hyperedges that the node belongs to.
:param node: node to retrieve the star of.
:returns: set -- set of hyperedge_ids for the hyperedges
in the node's star.
:raises: ValueError -- No such node exists.
"""
if node not in self._node_attributes:
raise ValueError("No such node exists.")
return self._star[node].copy()
[docs] def copy(self):
# Note: Code unchanged from DirectedHypergraph
"""Creates a new UndirectedHypergraph object with the same node and
hyperedge structure.
Copies of the nodes' and hyperedges' attributes are stored
and used in the new hypergraph.
:returns: UndirectedHypergraph -- a new hypergraph that is a copy of
the current hypergraph
"""
return self.__copy__()
def __copy__(self):
"""Creates a new UndirectedHypergraph object with the same node and
hyperedge structure.
Copies of the nodes' and hyperedges' attributes are stored
and used in the new hypergraph.
:returns: UndirectedHypergraph -- a new hypergraph that is a copy of
the current hypergraph
"""
new_H = UndirectedHypergraph()
# Loop over every node and its corresponding attribute dict
# in the original hypergraph's _node_attributes dict
for node, attr_dict in self._node_attributes.items():
# Create a new dict for that node to store that node's attributes
new_H._node_attributes[node] = {}
# Loop over each attribute of that node in the original hypergraph
# and, for each key, copy the corresponding value into the new
# hypergraph's dictionary using the same key
for attr_name, attr_value in attr_dict.items():
new_H._node_attributes[node][attr_name] = \
copy.copy(attr_value)
# Loop over every hyperedge_id and its corresponding attribute dict
# in the original hypergraph's _hyperedge_attributes dict
for hyperedge_id, attr_dict in self._hyperedge_attributes.items():
# Create a new dict for that node to store that node's attributes
new_H._hyperedge_attributes[hyperedge_id] = {}
# Loop over each attribute of that hyperedge in the original
# hypergraph and, for each key, copy the corresponding value
# the new hypergraph's dictionary
for attr_name, attr_value in attr_dict.items():
new_H.\
_hyperedge_attributes[hyperedge_id][attr_name] = \
copy.copy(attr_value)
# Copy the original hypergraph's nodes' stars
new_H._star = self._star.copy()
for node in self._node_attributes.keys():
new_H._star[node] = self._star[node].copy()
# Copy the original hypergraph's composed hyperedges
for frozen_nodes, hyperedge_id in self._node_set_to_hyperedge.items():
new_H._node_set_to_hyperedge[frozen_nodes] = \
copy.copy(hyperedge_id)
# Start assigning edge labels at the same
new_H._current_hyperedge_id = self._current_hyperedge_id
return new_H
# TODO: make reading more extensible (attributes, variable ordering, etc.)
[docs] def read(self, file_name, delim=',', sep='\t'):
"""Reads an undirected hypergraph from a file, where nodes are
represented as strings.
Each column is separated by "sep", and the individual nodes are
delimited by "delim".
The header line is currently ignored, but columns should be of
the format:
node1[delim]..nodeM[sep]weight
As a concrete example, an arbitrary line with delim=',' and
sep=' ' (4 spaces) may look like:
::
x1,x2,x3,x5 12
which defines a hyperedge of weight 12 from a node set containing
nodes "x1", "x2", "x3", and "x5".
"""
in_file = open(file_name, 'r')
# Skip the header line
in_file.readline()
line_number = 2
for line in in_file.readlines():
line = line.strip()
# Skip empty lines
if not line:
continue
words = line.split(sep)
if not (1 <= len(words) <= 2):
raise \
IOError("Line {} ".format(line_number) +
"contains {} ".format(len(words)) +
"columns -- must contain only 1 or 2.")
nodes = set(words[0].split(delim))
if len(words) == 2:
weight = float(words[1].split(delim)[0])
else:
weight = 1
self.add_hyperedge(nodes, weight=weight)
line_number += 1
in_file.close()
# TODO: make writing more extensible (attributes, variable ordering, etc.)
[docs] def write(self, file_name, delim=',', sep='\t'):
"""Writes an undirected hypergraph from a file, where nodes are
represented as strings.
Each column is separated by "sep", and the individual nodes are
delimited by "delim".
The header line is currently ignored, but columns should be of
the format:
node1[delim]..nodeM[sep]node1[delim]..nodeN[sep]weight
As a concrete example, an arbitrary line with delim=',' and
sep=' ' (4 spaces) may look like:
::
x1,x2,x3,x5 12
which defines a hyperedge of weight 12 from a node set containing
nodes "x1", "x2", "x3", and "x5".
"""
out_file = open(file_name, 'w')
# write first header line
out_file.write("nodes" + sep + "weight\n")
for hyperedge_id in self.get_hyperedge_id_set():
line = ""
# Write each node to the line, separated by delim
for node in self.get_hyperedge_nodes(hyperedge_id):
line += node + delim
# Remove last (extra) delim
line = line[:-1]
# Write the weight to the line and end the line
line += sep + str(self.get_hyperedge_weight(hyperedge_id)) + "\n"
out_file.write(line)
out_file.close()