summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichele Borassi <michele.borassi@imtlucca.it>2015-07-28 18:30:54 +0200
committerMichele Borassi <michele.borassi@imtlucca.it>2015-07-28 18:30:54 +0200
commitfacc0faa1906a9f5744de908915163aab575722a (patch)
tree5d89a0e8fb894cc71a563cc877ca2cdfe0e87474
parentCheck that libxml2 is installed (diff)
Conversion of graph name, edge labels, vertex name, and edge weight
-rw-r--r--src/sage/graphs/digraph.py87
-rw-r--r--src/sage/graphs/generic_graph.py118
-rw-r--r--src/sage/graphs/graph.py70
3 files changed, 244 insertions, 31 deletions
diff --git a/src/sage/graphs/digraph.py b/src/sage/graphs/digraph.py
index 4af5254..4d453b7 100644
--- a/src/sage/graphs/digraph.py
+++ b/src/sage/graphs/digraph.py
@@ -254,7 +254,9 @@ class DiGraph(GenericGraph):
``convert_empty_dict_labels_to_None`` to ``False`` (it is
``True`` by default).
- - ``igraph`` - data must be an igraph Graph.
+ - ``igraph`` - data must be an igraph directed Graph. In this case,
+ vertex and edge labels are also converted, and the graph name is
+ deduced, if available, as shown by the following examples.
- ``boundary`` - a list of boundary vertices, if
empty, digraph is considered as a 'graph without boundary'
@@ -402,12 +404,34 @@ class DiGraph(GenericGraph):
sage: DiGraph(g)
Digraph on 5 vertices
- #. An igraph Graph::
-
- sage: import igraph # optional - python_igraph
- sage: g = igraph.Graph([(0,1),(1,2),(0,2)], directed = True) # optional - python_igraph
- sage: DiGraph(g) # optional - python_igraph
- Digraph on 3 vertices
+ #. An igraph directed Graph (see also
+ :meth:`~sage.graphs.generic_graph.GenericGraph.igraph_graph`)::
+
+ sage: import igraph # optional - python_igraph
+ sage: g = igraph.Graph([(0,1),(0,2)], directed=True) # optional - python_igraph
+ sage: DiGraph(g) # optional - python_igraph
+ Digraph on 3 vertices
+
+ If the igraph Graph has a vertex attribute ``'name'``, this attribute is
+ used as vertex name::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], directed=True, vertex_attrs={'name':['a','b','c']}) # optional - python_igraph
+ sage: DiGraph(g).vertices() # optional - python_igraph
+ ['a', 'b', 'c']
+
+ If the igraph Graph has edge attributes, they are used for edge labels::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], directed=True, edge_attrs={'weight':[1,3]}) # optional - python_igraph
+ sage: DiGraph(g).edges() # optional - python_igraph
+ [(0, 1, {'weight': 1}), (0, 2, {'weight': 3})]
+
+ However, if there is only one attribute named ``'label'``, that attribute
+ is used as the label (so that, if we make a back and forth conversion,
+ labels do not change)::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], directed=True, edge_attrs={'label':[1,3]}) # optional - python_igraph
+ sage: DiGraph(g).edges() # optional - python_igraph
+ [(0, 1, 1), (0, 2, 3)]
TESTS::
@@ -453,15 +477,6 @@ class DiGraph(GenericGraph):
True
sage: type(J_imm._backend) == type(G_imm._backend)
True
-
- If the input is an undirected igraph graph, the output is transformed into
- a directed graph::
-
- sage: import igraph # optional - python_igraph
- sage: G = igraph.Graph([(0,1),(1,2),(0,2)], directed = False) # optional - python_igraph
- sage: H = DiGraph(G) # optional - python_igraph
- sage: H.edges(labels=False) # optional - python_igraph
- [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
"""
_directed = True
@@ -553,12 +568,20 @@ class DiGraph(GenericGraph):
sage: copy(g) is g # copy is mutable again
False
- TESTS::
+ Unknown input format::
sage: DiGraph(4,format="HeyHeyHey")
Traceback (most recent call last):
...
ValueError: Unknown input format 'HeyHeyHey'
+
+ Sage DiGraph from igraph undirected graph::
+
+ sage: import igraph
+ sage: DiGraph(igraph.Graph()) # optional - python_igraph
+ Traceback (most recent call last):
+ ...
+ ValueError: The input is an undirected igraph network, and you are creating a directed Sage network
"""
msg = ''
GenericGraph.__init__(self)
@@ -881,10 +904,34 @@ class DiGraph(GenericGraph):
self.add_vertices(data.nodes())
self.add_edges((u,v,r(l)) for u,v,l in data.edges_iter(data=True))
elif format == 'igraph':
- self.add_vertices(range(data.vcount()))
- self.add_edges(data.get_edgelist())
if not data.is_directed():
- self.add_edges(((w,v) for (v,w) in data.get_edgelist()))
+ raise ValueError("The input is an undirected igraph network, " +
+ "and you are creating a directed Sage network")
+ try:
+ self.name(data['name'])
+ except Exception:
+ pass
+
+ if 'name' in data.vertex_attributes():
+ vs = data.vs()
+ self.add_vertices(vs['name'])
+
+ if len(data.edge_attributes()) == 1 and data.edge_attributes()[0] == 'label':
+ self.add_edges([(vs[e.source]['name'], vs[e.target]['name'], e['label']) for e in data.es()])
+ elif len(data.edge_attributes()) > 0:
+ self.add_edges([(vs[e.source]['name'], vs[e.target]['name'], e.attributes()) for e in data.es])
+ else:
+ self.add_edges([(vs[e.source]['name'], vs[e.target]['name']) for e in data.es])
+ else:
+ self.add_vertices(range(data.vcount()))
+
+ if len(data.edge_attributes()) == 1 and data.edge_attributes()[0] == 'label':
+ self.add_edges([(e.source, e.target, e['label']) for e in data.es()])
+ elif len(data.edge_attributes()) > 0:
+ self.add_edges([(e.source, e.target, e.attributes()) for e in data.es()])
+ else:
+ self.add_edges(data.get_edgelist())
+
elif format == 'int':
if weighted is None: weighted = False
self.allow_loops(True if loops else False,check=False)
diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
index b06afb0..3367657 100644
--- a/src/sage/graphs/generic_graph.py
+++ b/src/sage/graphs/generic_graph.py
@@ -1311,30 +1311,134 @@ class GenericGraph(GenericGraph_pyx):
N.add_edge(u,v,weight=l)
return N
- def igraph_graph(self):
+ def igraph_graph(self, weight_function=None, vertex_labels=False, edge_labels=False):
r"""
Converts the graph into an igraph graph.
+ If present, the name of this graph is added as a graph attribute
+ ``'name'`` to the output graph. Optionally, we can define a weight and
+ we can transform vertex and edge labels into igraph vertex and edge
+ attributes.
+
For more information on the Python version of igraph, see
http://igraph.org/python/.
+
+ INPUT:
+
+ - ``weight_function`` (function) - a function that inputs an edge
+ ``(u, v, l)`` and outputs its weight. If provided, the weight obtained
+ is stored as an attribute of the edges of the igraph network, named
+ ``'weight'``. As a consequence, igraph will consider this graph
+ weighted.
+
+ - ``vertex_labels`` (boolean) - if True, we add a vertex attribute
+ ``'name'`` to the output graph, which is equal to the vertex name in
+ Sage. If False, the igraph network will have no vertex attribute.
+
+ - ``edge_labels`` (boolean) - if True, the Sage edge labels are stored
+ inside an igraph edge attribute named ``'label'``.
- EXAMPLES::
+ EXAMPLES:
+
+ Standard conversion::
sage: G = graphs.TetrahedralGraph() # optional - python_igraph
sage: H = G.igraph_graph() # optional - python_igraph
sage: H.summary() # optional - python_igraph
- 'IGRAPH U--- 4 6 -- '
+ 'IGRAPH U--- 4 6 -- Tetrahedron\n+ attr: name (g)'
sage: G = digraphs.Path(3) # optional - python_igraph
sage: H = G.igraph_graph() # optional - python_igraph
sage: H.summary() # optional - python_igraph
- 'IGRAPH D--- 3 2 -- '
+ 'IGRAPH D--- 3 2 -- Path\n+ attr: name (g)'
+
+ Adding a weight::
+
+ sage: G = Graph([(1,2,{'w':1}),(2,3,{'w':2})]) # optional - python_igraph
+ sage: H = G.igraph_graph(weight_function=lambda e:e[2]['w']) # optional - python_igraph
+ sage: H.is_weighted() # optional - python_igraph
+ True
+ sage: H.es['weight'] # optional - python_igraph
+ [1, 2]
+
+ Edge labeled graphs::
+
+ sage: H = G.igraph_graph(edge_labels = True) # optional - python_igraph
+ sage: H.es['label'] # optional - python_igraph
+ [{'w': 1}, {'w': 2}]
+
+ Vertex labeled graphs::
+
+ sage: G = graphs.GridGraph([2,2]) # optional - python_igraph
+ sage: H = G.igraph_graph(vertex_labels=True) # optional - python_igraph
+ sage: H.vs()['name'] # optional - python_igraph
+ [(0, 0), (0, 1), (1, 0), (1, 1)]
+
+ TESTS:
+
+ Converting a DiGraph back and forth::
+
+ sage: G = DiGraph([('a','b',{'w':1}),('b','c',{'w':2})]) # optional - python_igraph
+ sage: H = DiGraph(G.igraph_graph(vertex_labels=True, edge_labels=True)) # optional - python_igraph
+ sage: G == H # optional - python_igraph
+ True
+ sage: G.edges() == H.edges() # optional - python_igraph
+ True
+ sage: H = DiGraph(G.igraph_graph(edge_labels=True)) # optional - python_igraph
+ sage: G == H # optional - python_igraph
+ False
+
+ When checking for equality, edge labels are not taken into account::
+
+ sage: H = DiGraph(G.igraph_graph(vertex_labels=True)) # optional - python_igraph
+ sage: G == H # optional - python_igraph
+ True
+ sage: G.edges() == H.edges() # optional - python_igraph
+ False
+
+ Converting a Graph back and forth::
+
+ sage: G = Graph([('a','b',{'w':1}),('b','c',{'w':2})]) # optional - python_igraph
+ sage: H = Graph(G.igraph_graph(vertex_labels=True, edge_labels=True)) # optional - python_igraph
+ sage: G == H # optional - python_igraph
+ True
+ sage: G.edges() == H.edges() # optional - python_igraph
+ True
+ sage: H = Graph(G.igraph_graph(edge_labels=True)) # optional - python_igraph
+ sage: G == H # optional - python_igraph
+ False
+
+ When checking for equality, edge labels are not taken into account::
+
+ sage: H = Graph(G.igraph_graph(vertex_labels=True)) # optional - python_igraph
+ sage: G == H # optional - python_igraph
+ True
+ sage: G.edges() == H.edges() # optional - python_igraph
+ False
"""
try:
import igraph
v_to_int = {v:i for i,v in enumerate(self.vertices())}
- edgelist = [(v_to_int[v],v_to_int[w])
- for v,w in self.edges(labels=False)]
- return igraph.Graph(self.num_verts(), edgelist, directed=self.is_directed())
+ edges = [(v_to_int[v], v_to_int[w]) for v,w in self.edge_iterator(labels=False)]
+
+ if vertex_labels:
+ vertex_attrs = {'name':[v for i,v in enumerate(self.vertices())]}
+ else:
+ vertex_attrs = {}
+
+ if weight_function:
+ edge_attrs = {'weight':[weight_function(e) for e in self.edge_iterator()]}
+ else:
+ edge_attrs = {}
+
+ if edge_labels:
+ edge_attrs['label'] = [l for _,_,l in self.edge_iterator()]
+
+ return igraph.Graph(n = self.num_verts(),
+ edges = edges,
+ directed=self.is_directed(),
+ graph_attrs = {'name':self.name()},
+ vertex_attrs = vertex_attrs,
+ edge_attrs = edge_attrs)
except ImportError:
raise ImportError("The package igraph is not available. To " +
"install it, run Sage with option -i " +
diff --git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py
index 08be7ec..a06a58c 100644
--- a/src/sage/graphs/graph.py
+++ b/src/sage/graphs/graph.py
@@ -338,6 +338,13 @@ examples are covered here.
sage: g
Graph on 5 vertices
+- an igraph Graph::
+
+ sage: import igraph # optional - python_igraph
+ sage: g = Graph(igraph.Graph([(1,3),(3,2),(0,2)])) # optional - python_igraph
+ sage: g # optional - python_igraph
+ Graph on 4 vertices
+
Generators
----------
@@ -690,7 +697,9 @@ class Graph(GenericGraph):
``convert_empty_dict_labels_to_None`` to ``False`` (it is
``True`` by default).
- - ``igraph`` - data must be an igraph Graph.
+ - ``igraph`` - data must be an igraph Graph. In this case, vertex and
+ edge labels are also converted, and the graph name is deduced, if
+ available, as shown by the following examples.
- ``boundary`` - a list of boundary vertices, if
empty, graph is considered as a 'graph without boundary'
@@ -957,12 +966,34 @@ class Graph(GenericGraph):
sage: DiGraph(g)
Digraph on 5 vertices
- #. An igraph graph::
+ #. An igraph Graph (see also
+ :meth:`~sage.graphs.generic_graph.GenericGraph.igraph_graph`)::
sage: import igraph # optional - python_igraph
sage: g = igraph.Graph([(0,1),(0,2)]) # optional - python_igraph
sage: Graph(g) # optional - python_igraph
Graph on 3 vertices
+
+ If the igraph Graph has a vertex attribute ``'name'``, this attribute is
+ used as vertex name::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], vertex_attrs={'name':['a','b','c']}) # optional - python_igraph
+ sage: Graph(g).vertices() # optional - python_igraph
+ ['a', 'b', 'c']
+
+ If the igraph Graph has edge attributes, they are used for edge labels::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], edge_attrs={'weight':[1,3]}) # optional - python_igraph
+ sage: Graph(g).edges() # optional - python_igraph
+ [(0, 1, {'weight': 1}), (0, 2, {'weight': 3})]
+
+ However, if there is only one attribute named ``'label'``, that attribute
+ is used as the label (so that, if we make a back and forth conversion,
+ labels do not change)::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], edge_attrs={'label':[1,3]}) # optional - python_igraph
+ sage: Graph(g).edges() # optional - python_igraph
+ [(0, 1, 1), (0, 2, 3)]
By default, graphs are mutable and can thus not be used as a dictionary
key::
@@ -990,6 +1021,11 @@ class Graph(GenericGraph):
Traceback (most recent call last):
...
ValueError: Unknown input format 'HeyHeyHey'
+
+ sage: Graph(igraph.Graph(directed=True)) # optional - python_igraph
+ Traceback (most recent call last):
+ ...
+ ValueError: The input is a directed igraph network, and you are creating an undirected Sage network
"""
_directed = False
@@ -1400,8 +1436,34 @@ class Graph(GenericGraph):
self.add_vertices(data.nodes())
self.add_edges((u,v,r(l)) for u,v,l in data.edges_iter(data=True))
elif format == 'igraph':
- self.add_vertices(range(data.vcount()))
- self.add_edges(data.get_edgelist())
+ if data.is_directed():
+ raise ValueError("The input is a directed igraph network, and" +
+ " you are creating an undirected Sage network")
+ try:
+ self.name(data['name'])
+ except Exception:
+ pass
+
+ if 'name' in data.vertex_attributes():
+ vs = data.vs()
+ self.add_vertices(vs['name'])
+
+ if len(data.edge_attributes()) == 1 and data.edge_attributes()[0] == 'label':
+ self.add_edges([(vs[e.source]['name'], vs[e.target]['name'], e['label']) for e in data.es()])
+ elif len(data.edge_attributes()) > 0:
+ self.add_edges([(vs[e.source]['name'], vs[e.target]['name'], e.attributes()) for e in data.es])
+ else:
+ self.add_edges([(vs[e.source]['name'], vs[e.target]['name']) for e in data.es])
+ else:
+ self.add_vertices(range(data.vcount()))
+
+ if len(data.edge_attributes()) == 1 and data.edge_attributes()[0] == 'label':
+ self.add_edges([(e.source, e.target, e['label']) for e in data.es()])
+ elif len(data.edge_attributes()) > 0:
+ self.add_edges([(e.source, e.target, e.attributes()) for e in data.es()])
+ else:
+ self.add_edges(data.get_edgelist())
+
elif format == 'rule':
f = data[1]
verts = data[0]