3
Implementation of `igraph.Graph.Formula()`
5
You should use this module directly only if you have a very strong reason
6
to do so. In almost all cases, you are better off with calling
7
`igraph.Graph.Formula()`.
10
from cStringIO import StringIO
11
from igraph.datatypes import UniqueIdGenerator
18
def generate_edges(formula):
19
"""Parses an edge specification from the head of the given
20
formula part and yields the following:
22
- startpoint(s) of the edge by vertex names
23
- endpoint(s) of the edge by names or an empty list if the vertices are isolated
24
- a pair of bools to denote whether we had arrowheads at the start and end vertices
27
yield [], [""], [False, False]
30
name_tokens = set([token.NAME, token.NUMBER, token.STRING])
32
start_names, end_names, arrowheads = [], [], [False, False]
33
parsing_vertices = True
35
# Tokenize the formula
36
token_gen = tokenize.generate_tokens(StringIO(formula).next)
37
for token_type, tok, (_, start_char), (_, end_char), _ in token_gen:
38
# Do the state transitions
40
if tok in edge_chars and token_type == token.OP:
41
parsing_vertices = False
42
# Check the edge we currently have
43
if start_names and end_names:
44
# We have a whole edge
45
yield start_names, end_names, arrowheads
46
start_names, end_names, arrowheads = end_names, [], [False, False]
48
if tok not in edge_chars:
49
parsing_vertices = True
52
# We are parsing vertex names at the moment
53
if token_type in name_tokens:
54
# We found a vertex name
55
if token_type == token.STRING:
56
end_names.append(eval(tok))
58
end_names.append(str(tok))
59
elif tok == ":" and token_type == token.OP:
60
# Separating semicolon between vertex names, we just go on
62
elif token_type == token.ENDMARKER:
63
# End markers are fine
66
raise SyntaxError, "invalid token found in edge specification: %s" % formula
68
# We are parsing an edge operator
69
if tok == "<": arrowheads[0] = True
70
elif tok == ">": arrowheads[1] = True
71
elif tok == "<>": arrowheads = [True, True]
76
yield start_names, end_names, arrowheads
79
def Formula(klass, formula = None, attr = "name"):
80
"""Graph.Formula(formula = None, attr = "name")
82
Generates a graph from a graph formula
84
A graph formula is a simple string representation of a graph.
85
It is very handy for creating small graphs quickly. The string
86
consists of vertex names separated by edge operators. An edge
87
operator is a sequence of dashes (C{-}) that may or may not
88
start with an arrowhead (C{<} at the beginning of the sequence
89
or C{>} at the end of the sequence). The edge operators can
90
be arbitrarily long, i.e., you may use as many dashes to draw
91
them as you like. This makes a total of four different edge
94
- C{-----} makes an undirected edge
95
- C{<----} makes a directed edge pointing from the vertex
96
on the right hand side of the operator to the vertex on
98
- C{---->} is the opposite of C{<----}
99
- C{<--->} creates a mutual directed edge pair between
102
If you only use the undirected edge operator (C{-----}),
103
the graph will be undirected. Otherwise it will be directed.
104
Vertex names used in the formula will be assigned to the
105
C{name} vertex attribute of the graph.
107
Some simple examples:
109
>>> print Graph.Formula() # empty graph
110
Undirected graph (|V| = 0, |E| = 0)
111
>>> g = Graph.Formula("A-B") # undirected graph
115
Undirected graph (|V| = 2, |E| = 1)
117
>>> g2 = Graph.Formula("A-----------B")
120
>>> g = Graph.Formula("A ---> B") # directed graph
124
Directed graph (|V| = 2, |E| = 1)
126
If you have may disconnected componnets, you can separate them
127
with commas. You can also specify isolated vertices:
129
>>> g = Graph.Formula("A--B, C--D, E--F, G--H, I, J, K")
130
>>> print ", ".join(g.vs["name"])
131
A, B, C, D, E, F, G, H, I, J, K
132
>>> g.clusters().membership
133
[0, 0, 1, 1, 2, 2, 3, 3, 4, 5, 6]
135
The colon (C{:}) operator can be used to specify vertex sets.
136
If an edge operator connects two vertex sets, then every vertex
137
from the first vertex set will be connected to every vertex in
140
>>> g = Graph.Formula("A:B:C:D --- E:F:G")
141
>>> g.isomorphic(Graph.Full_Bipartite(4, 3))
144
Note that you have to quote vertex names if they include spaces
145
or special characters:
147
>>> g = Graph.Formula('"this is" +- "a silly" -+ "graph here"')
149
['this is', 'a silly', 'graph here']
151
@param formula: the formula itself
152
@param attr: name of the vertex attribute where the vertex names
154
@return: the constructed graph:
157
# If we have no formula, return an empty graph
158
if formula is None: return klass(0, vertex_attrs = {attr: []})
160
vertex_ids, edges, directed = UniqueIdGenerator(), [], False
161
# Loop over each part in the formula
162
for part in formula.split(","):
163
# Drop newlines from the part
164
part = part.strip().replace("\n", "").replace("\t", "")
165
# Parse the first vertex specification from the formula
166
for start_names, end_names, arrowheads in generate_edges(part):
167
start_ids = [vertex_ids[name] for name in start_names]
168
end_ids = [vertex_ids[name] for name in end_names]
169
if not arrowheads[0] and not arrowheads[1]:
170
# This is an undirected edge. Do we have a directed graph?
173
edges.extend([(id1, id2) for id1 in start_ids for id2 in end_ids])
175
# This is a directed edge
178
edges.extend([(id1, id2) for id1 in start_ids for id2 in end_ids])
180
edges.extend([(id2, id1) for id1 in start_ids for id2 in end_ids])
182
# Grab the vertex names into a list
183
names = sorted(((v, k) for k, v in vertex_ids._ids.iteritems()))
184
names = [k for _, k in names]
185
# Construct and return the graph
186
return klass(len(names), edges, directed, vertex_attrs={attr: names})
added
removed
igraph/formula.py
