Graph¶

class rnamake.graph.Graph[source]¶

Bases: object

General implementation of a undirected graph. Do not call directly!

Attributes:

nodes : list of GraphNode objects: all the nodes in the tree, used for fast access by index
connections : list of GraphConnection objects: all the connections between two different nodes in the graph
level : int: the current graph level, used for quickly deleting sections of the graph
index: int: the current node index, always the length of the number of nodes in teh graph
last_node: GraphNode object: the last node added to the graph
current_node: GraphNode object: the current node during iteration
queue: PriorityQueue object: tracks which nodes to visit turning iteration
seen: List of GraphNode Objects: tracks which nodes have alaready been visited during iteration

decrease_level()[source]¶: Decreases the level of nodes to be added. default level is 0. This is useful when removing or adding a set of nodes. Think of level as a grouping mechanism

get_node(index)[source]¶

Parameters:	index (int) – the node index that you want
Returns:	GraphNode object
Raises:	exceptions.GraphIndexException
Examples:

>>> g = Graph()
>>> g.add_data(10)
#get node of index '0' which is the first one
>>> print g.get_node(0).data
10

increase_level()[source]¶: Increases the level of nodes to be added. default level is 0. This is useful when removing or adding a set of nodes. Think of level as a grouping mechanism

oldest_node()[source]¶

returns the node with the lowest index. Only used a few examples may deprecated in next verision.

Returns:	GraphNode object
Examples:

>>> g = Graph()
>>> g.add_data(10)
>>> g.add_data(5)
>>> g.add_data(15)
>>> g.oldest_node().data
10

class rnamake.graph.GraphConnection(node_1, node_2, end_index_1, end_index_2)[source]¶

Bases: object

A simple class to store a connection between two nodes in Graph classes. Never needs to be called outside Graph classes.

Param_end_index_2:
Parameters:	node_1 (GraphNode) – first node in the connection, order doesn’t matter node_2 (GraphNode) – second node in the connection end_index_1 (int) – connection position in node 1
	connection position in node 2
Attributes:

node_1: GraphNode: first node in the connection, order doesn’t matter
node_2: GraphNode: second node in the connection
end_index_1: int: connection position in node 1
end_index_2: int: connection position in node 2

disconnect()[source]¶

removes connection, gets each node to remove this connection from their connection lists.

Returns:	None

end_index(n_index)[source]¶

get the end index of a given node specified by its index

Parameters:	n_index (int) – index of the node you want to find its end_index in this connection
Returns:	end index of specified node in this connection
Return type:	int

partner(n_index)[source]¶

get other node in the connection.

Parameters:	n_index (int) – index of node you know but want to find the other node
Returns:	other node
Return type:	GraphNode

class rnamake.graph.GraphDynamic[source]¶

Bases: rnamake.graph.Graph

a Graph with dynamic connections between nodes. i.e. each node does NOT have a predefined number of connections. Each node starts with 0 connections and are added over time, there is no max to the number of connections each node can have

Attributes:

nodes : list of GraphNode objects: all the nodes in the tree, used for fast access by index
connections : list of GraphConnection objects: all the connections between two different nodes in the graph
level : int: the current graph level, used for quickly deleting sections of the graph
index: int: the current node index, always the length of the number of nodes in teh graph
last_node: GraphNode object: the last node added to the graph
current_node: GraphNode object: the current node during iteration
queue: PriorityQueue object: tracks which nodes to visit turning iteration
seen: List of GraphNode Objects: tracks which nodes have alaready been visited during iteration

Examples:

>>> g = GraphDynamic()
>>> g.add_data(0)
>>> g.add_data(1)
>>> g.add_data(2, parent_index=0)
>>> g.add_data(3, parent_index=0)

>>> len(g.get_node(0).connections)
3

add_data(data, parent_index=-1)[source]¶

add a new peice of data to the graph

Parameters:	data (can be anything) – Item to be added to graph parent_index (int) – index of node that this element should be connected too
Returns:	index of added node
Return type:	int
Raises:	exceptions.GraphIndexException

connect(i, j)[source]¶

Add a connection between two nodes. Since this is a Dynamic Graph this cannot fail. i and j can be the same

Parameters:	i (int) – index of node 1 to connect j (int) – index of node 2 to connect
Returns:	None

decrease_level()¶: Decreases the level of nodes to be added. default level is 0. This is useful when removing or adding a set of nodes. Think of level as a grouping mechanism

get_node(index)¶

Parameters:	index (int) – the node index that you want
Returns:	GraphNode object
Raises:	exceptions.GraphIndexException
Examples:

>>> g = Graph()
>>> g.add_data(10)
#get node of index '0' which is the first one
>>> print g.get_node(0).data
10

increase_level()¶: Increases the level of nodes to be added. default level is 0. This is useful when removing or adding a set of nodes. Think of level as a grouping mechanism

oldest_node()¶

returns the node with the lowest index. Only used a few examples may deprecated in next verision.

Returns:	GraphNode object
Examples:

>>> g = Graph()
>>> g.add_data(10)
>>> g.add_data(5)
>>> g.add_data(15)
>>> g.oldest_node().data
10

class rnamake.graph.GraphNode(data, index, level, n_connections=0)[source]¶

Bases: object

An abstract class to define the behavior of a graph node or an element of data that has connectivity relationships to other elements of data of the same type. This class is never called directly.

Parameters:

data (anything) – The element that you wish to store in the graph
index (int) – The way for you to find this element of data again through Graph.get_node()
level (int) – A way of grouping nodes together, increasing the level and then removing all nodes of a given level is a quick way to batch remove nodes
n_connections (int) – The number of connections this node can have, in GraphDynamic this does nothing.

Attributes:

data : anything: The element of data being stored in graph
index: int: The way for you to find this element of data again through Graph.get_node()
level: int: A way of grouping nodes together, increasing the level and then removing all nodes of a given level is a quick way to batch remove nodes
connections: list of GraphConnections: the connections the node has with other nodes

available_children_pos()[source]¶

gets all of the connection positions that are not filled yet for this node

Returns:	a list of end positions not yet filled
Return type:	list of ints

available_pos(pos)[source]¶

check to see if specific connection position is filled

Parameters:	pos (int) – position to check within interal connctions member
Returns:	returns 1 if not filled and 0 is filled
Return type:	int

connected(n)[source]¶

check to see if another node is connected to this one. If so will return the GraphConnection object that they share. If not will return None.

Parameters:	n (GraphNode) – other GraphNode object
Returns:	Will return GraphConnection they share if connected if not will return None
Return type:	GraphConnection

parent()[source]¶

A way to find the oldest node the current node is connected to. This is usually the parent node but this is not always 100% true. If is connected to no other nodes will return None.

Returns:	the oldest node the current one is connected too
Return type:	GraphNode

parent_index()[source]¶

Gets the end index of the connected node that is the oldest.

Returns:	end index of oldest connected node.
Return type:	int

class rnamake.graph.GraphNodeDynamic(data, index, level)[source]¶

Bases: rnamake.graph.GraphNode

A GraphNode container that is specific for GraphDyanmic graphs. That is it can be connected to an unlimited number of other nodes. There is no reason to instantiate this class outside GraphDynamic.

Parameters:	data (anything) – The element that you wish to store in the graph index (int) – The way for you to find this element of data again through `Graph.get_node()` level (int) – A way of grouping nodes together, increasing the level and then removing all nodes of a given level is a quick way to batch remove nodes
Attributes:

data : anything: The element of data being stored in graph
index: int: The way for you to find this element of data again through Graph.get_node()
level: int: A way of grouping nodes together, increasing the level and then removing all nodes of a given level is a quick way to batch remove nodes
connections: list of GraphConnections: the connections the node has with other nodes

add_connection(c)[source]¶

adds a connection to another graph node

Parameters:	c (GraphConnection) – a connection to another node
Returns:	None

available_children_pos()¶

gets all of the connection positions that are not filled yet for this node

Returns:	a list of end positions not yet filled
Return type:	list of ints

available_pos(pos)¶

check to see if specific connection position is filled

Parameters:	pos (int) – position to check within interal connctions member
Returns:	returns 1 if not filled and 0 is filled
Return type:	int

connected(n)¶

check to see if another node is connected to this one. If so will return the GraphConnection object that they share. If not will return None.

Parameters:	n (GraphNode) – other GraphNode object
Returns:	Will return GraphConnection they share if connected if not will return None
Return type:	GraphConnection

parent()¶

A way to find the oldest node the current node is connected to. This is usually the parent node but this is not always 100% true. If is connected to no other nodes will return None.

Returns:	the oldest node the current one is connected too
Return type:	GraphNode

parent_index()¶

Gets the end index of the connected node that is the oldest.

Returns:	end index of oldest connected node.
Return type:	int

remove_connection(c)[source]¶

removes a connection to another node

Parameters:	c (GraphConnection) – a connection to another node
Returns:	None

class rnamake.graph.GraphNodeStatic(data, index, level, n_children)[source]¶

Bases: rnamake.graph.GraphNode

A GraphNode container that is specific for GraphStatic graphs. That is it can be connected to an unlimited number of other nodes. There is no reason to instantiate this class outside GraphStatic.

Parameters:

data (anything) – The element that you wish to store in the graph
index (int) – The way for you to find this element of data again through Graph.get_node()
level (int) – A way of grouping nodes together, increasing the level and then removing all nodes of a given level is a quick way to batch remove nodes
n_connections (int) – The number of connections this node can have.

Attributes:

data : anything: The element of data being stored in graph
index: int: The way for you to find this element of data again through Graph.get_node()
level: int: A way of grouping nodes together, increasing the level and then removing all nodes of a given level is a quick way to batch remove nodes
connections: list of GraphConnections: the connections the node has with other nodes

add_connection(c, pos)[source]¶

Add a new connection at a specific position in connection list

Parameters:	c (GraphConnection) – the new connection pos (int) – the position to be added
Returns:	None

available_children_pos()¶

gets all of the connection positions that are not filled yet for this node

Returns:	a list of end positions not yet filled
Return type:	list of ints

available_pos(pos)¶

check to see if specific connection position is filled

Parameters:	pos (int) – position to check within interal connctions member
Returns:	returns 1 if not filled and 0 is filled
Return type:	int

connected(n)¶

check to see if another node is connected to this one. If so will return the GraphConnection object that they share. If not will return None.

Parameters:	n (GraphNode) – other GraphNode object
Returns:	Will return GraphConnection they share if connected if not will return None
Return type:	GraphConnection

copy()[source]¶

deep copies graph node and also tries to deep copy data. Will work if data element has a function copy().

Returns:	a deep copy of node
Return type:	GraphNodeStatic

parent()¶

A way to find the oldest node the current node is connected to. This is usually the parent node but this is not always 100% true. If is connected to no other nodes will return None.

Returns:	the oldest node the current one is connected too
Return type:	GraphNode

parent_index()¶

Gets the end index of the connected node that is the oldest.

Returns:	end index of oldest connected node.
Return type:	int

remove_connection(c)[source]¶

Remove a connection at a specific position in connection list

Parameters:	c (GraphConnection) – the connection to remove
Returns:	None

class rnamake.graph.GraphStatic[source]¶

Bases: rnamake.graph.Graph

a Graph with static connections between nodes. i.e. each node HAS a predefined number of connections. This is useful for constructing graphs of Motifs and Secondary Structure elements which have predefined ends.

Attributes:

nodes : list of GraphNode objects: all the nodes in the tree, used for fast access by index
connections : list of GraphConnection objects: all the connections between two different nodes in the graph
level : int: the current graph level, used for quickly deleting sections of the graph
index: int: the current node index, always the length of the number of nodes in teh graph
last_node: GraphNode object: the last node added to the graph
current_node: GraphNode object: the current node during iteration
queue: PriorityQueue object: tracks which nodes to visit turning iteration
seen: List of GraphNode Objects: tracks which nodes have alaready been visited during iteration

Examples:

>>> g = graph.GraphStatic()
# legend
# N0 = Node 0
# N0C0 = Connection 0 of Node 0
# add first node with 2 possible connection
>>> g.add_data(0, n_children=2)
#          N0
#    N0C0 /  \  N0C1
#        /    \
#     None     None
# add new node, connected to node 0. This new node: node 1 is connected
# to node 0 using the connnection in the 0th position on both node 0 and
# node 1. Do not need to specifiy parent_index=0 since adds to last node
# without specifying
# g.add_data(1, parent_index=0, parent_pos=0, child_pos=0, n_children=2)
# means the same thing
>>> g.add_data(1, parent_pos=0, child_pos=0, n_children=2)
#          N0
#    N0C0 /  \  N0C1
#    N1C0/    \
#       N1   None
#   N1C1|
#       |
#      None
# add new node, connected to node 0.
>>> g.add_data(2, parent_index=0, parent_pos=1, child_pos=0, n_children=2)
#          N0
#    N0C0 /  \  N0C1
#    N1C0/    \ N2C0
#       N1    N2
#   N1C1|      |N2C1
#       |      |
#      None   None
>>> g.connect(1, 2, 1, 1)
#          N0
#    N0C0 /  \  N0C1
#    N1C0/    \ N2C0
#       N1----N2
#      N1C1  N2C1

add_data(data, parent_index=-1, parent_pos=-1, child_pos=-1, n_children=1, orphan=0, index=-1)[source]¶

Adds a new node to the graph given specfied data.

Parameters:	data (anything) – element to add to graph parent_index (int) – index of parent to connect to, optional parent_pos (int) – connection position to connect to parent, optional child_pos (int) – connection position on new node to be created, optional n_children (int) – number of connections new node will have, optional orphan (int) – whether node will not be connected to any other node. default new nodes are connected to the last node added. if orphan=1 this will not happen index (int) – overrides internal index and set node to specific index value, this is rarely used other then copying an entire graph
Returns:	index of new node
Return type:	int
Raises:	exceptions.GraphIndexException, exceptions.GraphInvalidEndException, exceptions.GraphException
Examples:

>>> g = graph.GraphStatic()
# legend
# N0 = Node 0
# N0C0 = Connection 0 of Node 0
# add first node with 2 possible connection
>>> g.add_data(0, n_children=2)
#          N0
#    N0C0 /  \  N0C1
#        /    \
#     None     None
# add new node, connected to node 0. This new node: node 1 is connected
# to node 0 using the connnection in the 0th position on both node 0 and
# node 1. Do not need to specifiy parent_index=0 since adds to last node
# without specifying
# g.add_data(1, parent_index=0, parent_pos=0, child_pos=0, n_children=2)
# means the same thing
>>> g.add_data(1, parent_pos=0, child_pos=0, n_children=2)
#          N0
#    N0C0 /  \  N0C1
#    N1C0/    \
#       N1   None
#   N1C1|
#       |
#      None

check_pos_is_value(n, pos, error=1)[source]¶

checks to see if a given node has a free end to connect to

Parameters:	n (GraphNodeStatic) – the node to check pos (int) – the end position to check error (int) – whether an error should be returned if end is not free, default=1, will error
Returns:	free end pos

connect(i, j, i_pos, j_pos)[source]¶

Connects two nodes together given a specific end index

Parameters:	i – index of node i j – index of node j i_pos – end pos of node i j_pos – end pos of node j
Returns:	None

copy()[source]¶

creates a deep copy of the graph tries to create a copy of the data held in each node

Returns:	copy of graph
Return type:	GraphStatic

decrease_level()¶: Decreases the level of nodes to be added. default level is 0. This is useful when removing or adding a set of nodes. Think of level as a grouping mechanism

get_availiable_pos(n, pos)[source]¶

checks to see if a given node has a free end position will return and error if it doesn’t

Parameters:	n (GraphNodeStatic) – the graph node in question pos (int) – the end position (connection point)
Returns:	returns a list of positions if successful

get_node(index)¶

Parameters:	index (int) – the node index that you want
Returns:	GraphNode object
Raises:	exceptions.GraphIndexException
Examples:

>>> g = Graph()
>>> g.add_data(10)
#get node of index '0' which is the first one
>>> print g.get_node(0).data
10

increase_level()¶: Increases the level of nodes to be added. default level is 0. This is useful when removing or adding a set of nodes. Think of level as a grouping mechanism

oldest_node()¶

returns the node with the lowest index. Only used a few examples may deprecated in next verision.

Returns:	GraphNode object
Examples:

>>> g = Graph()
>>> g.add_data(10)
>>> g.add_data(5)
>>> g.add_data(15)
>>> g.oldest_node().data
10

remove_node(index)[source]¶

removes a node with a given index

Parameters:	index (int) – the index of the node you want to remove
Returns:	None
Raises:	exceptions.GraphIndexException

remove_node_level(level=None)[source]¶

remove all nodes with a given level, this is useful if you are unsure how many nodes have been added from a given point. if level is not specified level will be set to current level

Parameters:	level (int) – the node minimum node level you want to remove
Returns:	None