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