Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/galaxy/util/simplegraph.py @ 0:26e78fe6e8c4 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
author shellac
date Sat, 02 May 2020 07:14:21 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:26e78fe6e8c4
1 """
2 Fencepost-simple graph structure implementation.
3 """
4 # Currently (2013.7.12) only used in easing the parsing of graph datatype data.
5
6 from collections import OrderedDict
7
8
9 class SimpleGraphNode(object):
10 """
11 Node representation.
12 """
13
14 def __init__(self, index, **data):
15 """
16 :param index: index of this node in some parent list
17 :type index: int
18 :param data: any extra data that needs to be saved
19 :type data: (variadic dictionary)
20 """
21 # a bit application specific (could be 'id')
22 self.index = index
23 self.data = data
24
25
26 class SimpleGraphEdge(object):
27 """
28 Edge representation.
29 """
30
31 def __init__(self, source_index, target_index, **data):
32 """
33 :param source_index: index of the edge's source node in some parent list
34 :type source_index: int
35 :param target_index: index of the edge's target node in some parent list
36 :type target_index: int
37 :param data: any extra data that needs to be saved
38 :type data: (variadic dictionary)
39 """
40 self.source_index = source_index
41 self.target_index = target_index
42 self.data = data
43
44
45 class SimpleGraph(object):
46 """
47 Each node is unique (by id) and stores its own index in the node list/odict.
48 Each edge is represented as two indeces into the node list/odict.
49 Both nodes and edges allow storing extra information if needed.
50
51 Allows:
52 multiple edges between two nodes
53 self referential edges (an edge from a node to itself)
54
55 These graphs are not specifically directed but since source and targets on the
56 edges are listed - it could easily be used that way.
57 """
58
59 def __init__(self, nodes=None, edges=None):
60 # use an odict so that edge indeces actually match the final node list indeces
61 self.nodes = nodes or OrderedDict()
62 self.edges = edges or []
63
64 def add_node(self, node_id, **data):
65 """
66 Adds a new node only if it doesn't already exist.
67 :param node_id: some unique identifier
68 :type node_id: (hashable)
69 :param data: any extra data that needs to be saved
70 :type data: (variadic dictionary)
71 :returns: the new node
72 """
73 if node_id in self.nodes:
74 return self.nodes[node_id]
75 node_index = len(self.nodes)
76 new_node = SimpleGraphNode(node_index, **data)
77 self.nodes[node_id] = new_node
78 return new_node
79
80 def add_edge(self, source_id, target_id, **data):
81 """
82 Adds a new node only if it doesn't already exist.
83 :param source_id: the id of the source node
84 :type source_id: (hashable)
85 :param target_id: the id of the target node
86 :type target_id: (hashable)
87 :param data: any extra data that needs to be saved for the edge
88 :type data: (variadic dictionary)
89 :returns: the new node
90
91 ..note: that, although this will create new nodes if necessary, there's
92 no way to pass `data` to them - so if you need to assoc. more data with
93 the nodes, use `add_node` first.
94 """
95 # adds target_id to source_id's edge list
96 # adding source_id and/or target_id to nodes if not there already
97 if source_id not in self.nodes:
98 self.add_node(source_id)
99 if target_id not in self.nodes:
100 self.add_node(target_id)
101 new_edge = SimpleGraphEdge(self.nodes[source_id].index, self.nodes[target_id].index, **data)
102 self.edges.append(new_edge)
103 return new_edge
104
105 def gen_node_dicts(self):
106 """
107 Returns a generator that yields node dictionaries in the form:
108 { 'id': <the nodes unique id>, 'data': <any additional node data> }
109 """
110 for node_id, node in self.nodes.items():
111 yield {'id': node_id, 'data': node.data}
112
113 def gen_edge_dicts(self):
114 """
115 Returns a generator that yields node dictionaries in the form::
116
117 {
118 'source': <the index of the source node in the graph's node list>,
119 'target': <the index of the target node in the graph's node list>,
120 'data' : <any additional edge data>
121 }
122 """
123 for edge in self.edges:
124 yield {'source': edge.source_index, 'target': edge.target_index, 'data': edge.data}
125
126 def as_dict(self):
127 """
128 Returns a dictionary of the form::
129
130 { 'nodes': <a list of node dictionaries>, 'edges': <a list of node dictionaries> }
131 """
132 return {'nodes': list(self.gen_node_dicts()), 'edges': list(self.gen_edge_dicts())}