Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/galaxy/util/simplegraph.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"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())}