summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRelease Manager <release@sagemath.org>2015-08-07 20:40:12 +0200
committerVolker Braun <vbraun.name@gmail.com>2015-08-07 20:40:12 +0200
commit6dbe2aae777652714d18d728a2c3db6e6af895ff (patch)
tree65221464f8e3cc67c69401445659548416769b38
parentTrac #18953: Replace pipestatus by build/bin/sage-logger (diff)
parentCorrected doc and error message if igraph is not installed (diff)
Trac #18929: Include igraph library
Include igraph library ![1] in Sagemath, so that we can use its algorithms. Add routines to convert Sage graphs into igraph and viceversa. The input files are available through the following links: * for igraph.tar.gz: igraph.org/nightly/get/c/igraph-0.7.1.tar.gz * for python-igraph.tar.gz: igraph.org/nightly/get/python/python- igraph-0.7.0.tar.gz The modified files (with script spkg_src) are available through the following links: * for igraph.tar.gz (the same as the previous one): !https://drive.goog le.com/file/d/0B5D_YOccuV6xNFFUYnZFYzg0bkk/view?usp=sharing * for python-igraph.tar.gz (we had to replace - with _ in the filename and in a folder): !https://drive.google.com/file/d/0B5D_YOccuV6xcURsT1Bp LUpqZ0E/view?usp=sharing If we manage to include igraph, we will have access to 62 algorithms on graphs: 29 of them are not available in Sage, yet ![2]. ![1]http://igraph.org/python/ ![2] https://docs.google.com/spreadsheets/d/1Iu1hkQtRn9J- sgfZbQTu2RoXzyjoMEWP5-cm3nAwnWE/edit#gid=0 URL: http://trac.sagemath.org/18929 Reported by: borassi Ticket author(s): Michele Borassi Reviewer(s): Nathann Cohen, David Coudert
-rw-r--r--build/pkgs/igraph/SPKG.txt27
-rw-r--r--build/pkgs/igraph/checksums.ini4
-rw-r--r--build/pkgs/igraph/package-version.txt1
-rw-r--r--build/pkgs/igraph/spkg-check4
-rw-r--r--build/pkgs/igraph/spkg-install27
-rw-r--r--build/pkgs/igraph/type1
-rw-r--r--build/pkgs/python_igraph/SPKG.txt27
-rw-r--r--build/pkgs/python_igraph/checksums.ini4
-rw-r--r--build/pkgs/python_igraph/dependencies5
-rw-r--r--build/pkgs/python_igraph/package-version.txt1
-rw-r--r--build/pkgs/python_igraph/spkg-check4
-rw-r--r--build/pkgs/python_igraph/spkg-install15
-rwxr-xr-xbuild/pkgs/python_igraph/spkg-src46
-rw-r--r--build/pkgs/python_igraph/type1
-rw-r--r--src/sage/graphs/digraph.py64
-rw-r--r--src/sage/graphs/generic_graph.py137
-rw-r--r--src/sage/graphs/graph.py67
17 files changed, 432 insertions, 3 deletions
diff --git a/build/pkgs/igraph/SPKG.txt b/build/pkgs/igraph/SPKG.txt
new file mode 100644
index 0000000..faf25d2
--- /dev/null
+++ b/build/pkgs/igraph/SPKG.txt
@@ -0,0 +1,27 @@
+= igraph =
+
+== Description ==
+
+igraph is a library for creating and manipulating graphs.
+It is intended to be as powerful (ie. fast) as possible to enable the
+analysis of large graphs.
+
+== License ==
+
+GPL version 2
+
+== SPKG Maintainers ==
+
+* Michele Borassi
+
+== Upstream Contact ==
+
+http://igraph.org/c/
+
+== Dependencies ==
+
+* python
+* readline
+* gcc
+
+== Special Update/Build Instructions ==
diff --git a/build/pkgs/igraph/checksums.ini b/build/pkgs/igraph/checksums.ini
new file mode 100644
index 0000000..f826586
--- /dev/null
+++ b/build/pkgs/igraph/checksums.ini
@@ -0,0 +1,4 @@
+tarball=igraph-VERSION.tar.gz
+sha1=2cf3528a60c52810a3d5ed9f117692f8f639aac1
+md5=4f6e7c16b45fce8ed423516a9786e4e8
+cksum=2372626349
diff --git a/build/pkgs/igraph/package-version.txt b/build/pkgs/igraph/package-version.txt
new file mode 100644
index 0000000..7deb86f
--- /dev/null
+++ b/build/pkgs/igraph/package-version.txt
@@ -0,0 +1 @@
+0.7.1 \ No newline at end of file
diff --git a/build/pkgs/igraph/spkg-check b/build/pkgs/igraph/spkg-check
new file mode 100644
index 0000000..35f04fc
--- /dev/null
+++ b/build/pkgs/igraph/spkg-check
@@ -0,0 +1,4 @@
+#!/usr/bin/env bash
+
+cd src
+$MAKE check
diff --git a/build/pkgs/igraph/spkg-install b/build/pkgs/igraph/spkg-install
new file mode 100644
index 0000000..5d0ae62
--- /dev/null
+++ b/build/pkgs/igraph/spkg-install
@@ -0,0 +1,27 @@
+#!/usr/bin/env bash
+
+if gcc -lxml2 2>&1 | grep -q 'cannot find -lxml2'; then
+ echo "
+You need libxml2 to run igraph. On Ubuntu and Debian Linux, installing the build-essential and the libxml2-dev packages is sufficient."
+ exit 1
+fi
+
+cd src
+
+./configure --prefix="$SAGE_LOCAL" --libdir="$SAGE_LOCAL/lib"
+if [ $? -ne 0 ]; then
+ echo >&2 "Error configuring igraph."
+ exit 1
+fi
+
+$MAKE
+if [ $? -ne 0 ]; then
+ echo >&2 "Error building igraph."
+ exit 1
+fi
+
+$MAKE -j1 install
+if [ $? -ne 0 ]; then
+ echo >&2 "Error installing igraph."
+ exit 1
+fi
diff --git a/build/pkgs/igraph/type b/build/pkgs/igraph/type
new file mode 100644
index 0000000..134d9bc
--- /dev/null
+++ b/build/pkgs/igraph/type
@@ -0,0 +1 @@
+optional
diff --git a/build/pkgs/python_igraph/SPKG.txt b/build/pkgs/python_igraph/SPKG.txt
new file mode 100644
index 0000000..ef07b8b
--- /dev/null
+++ b/build/pkgs/python_igraph/SPKG.txt
@@ -0,0 +1,27 @@
+= python-igraph =
+
+== Description ==
+
+igraph is a library for creating and manipulating graphs.
+It is intended to be as powerful (ie. fast) as possible to enable the
+analysis of large graphs.
+
+== License ==
+
+GPL version 2
+
+== SPKG Maintainers ==
+
+* Michele Borassi
+
+== Upstream Contact ==
+
+http://igraph.org/python/
+
+== Dependencies ==
+
+* python
+* readline
+* igraph
+
+== Special Update/Build Instructions ==
diff --git a/build/pkgs/python_igraph/checksums.ini b/build/pkgs/python_igraph/checksums.ini
new file mode 100644
index 0000000..e1bf34b
--- /dev/null
+++ b/build/pkgs/python_igraph/checksums.ini
@@ -0,0 +1,4 @@
+tarball=python_igraph-VERSION.tar.gz
+sha1=3a01e98962d96061e5f2383445c7f7a86b2759cc
+md5=088e816732d02b84119183e3d82a9deb
+cksum=680376365
diff --git a/build/pkgs/python_igraph/dependencies b/build/pkgs/python_igraph/dependencies
new file mode 100644
index 0000000..a23b62d
--- /dev/null
+++ b/build/pkgs/python_igraph/dependencies
@@ -0,0 +1,5 @@
+$(INST)/$(IGRAPH)
+
+----------
+All lines of this file are ignored except the first.
+It is copied by SAGE_ROOT/build/make/install into SAGE_ROOT/build/make/Makefile.
diff --git a/build/pkgs/python_igraph/package-version.txt b/build/pkgs/python_igraph/package-version.txt
new file mode 100644
index 0000000..bcaffe1
--- /dev/null
+++ b/build/pkgs/python_igraph/package-version.txt
@@ -0,0 +1 @@
+0.7.0 \ No newline at end of file
diff --git a/build/pkgs/python_igraph/spkg-check b/build/pkgs/python_igraph/spkg-check
new file mode 100644
index 0000000..4172cc7
--- /dev/null
+++ b/build/pkgs/python_igraph/spkg-check
@@ -0,0 +1,4 @@
+#!/usr/bin/env bash
+
+cd src
+python setup.py check
diff --git a/build/pkgs/python_igraph/spkg-install b/build/pkgs/python_igraph/spkg-install
new file mode 100644
index 0000000..684a838
--- /dev/null
+++ b/build/pkgs/python_igraph/spkg-install
@@ -0,0 +1,15 @@
+#!/usr/bin/env bash
+
+cd src
+
+python setup.py build
+if [ $? -ne 0 ]; then
+ echo >&2 "Error building python_igraph."
+ exit 1
+fi
+
+python setup.py install
+if [ $? -ne 0 ]; then
+ echo >&2 "Error installing python_igraph."
+ exit 1
+fi
diff --git a/build/pkgs/python_igraph/spkg-src b/build/pkgs/python_igraph/spkg-src
new file mode 100755
index 0000000..a5ff069
--- /dev/null
+++ b/build/pkgs/python_igraph/spkg-src
@@ -0,0 +1,46 @@
+#!/usr/bin/env bash
+
+# This script must be run from folder SAGE_ROOT. It modifies the file
+# python-igraph-0.7.0.tar.gz into python_igraph-0.7.0.tar.gz, and it modifies
+# the name of the top folder accordingly.
+
+
+if [ -z "$SAGE_ROOT" -o -z "$SAGE_DISTFILES" ]; then
+ echo >&2 "\$SAGE_ROOT or \$SAGE_DISTFILES undefined ... exiting";
+ echo >&2 "Maybe run 'sage -sh'?"
+ exit 1
+fi
+
+PKG_DIR="$SAGE_ROOT/build/pkgs/python_igraph/"
+VERSION=$(cat "$PKG_DIR/package-version.txt")
+PYTHONIGRAPH=python-igraph-$VERSION
+PYTHONIGRAPHMOD=python_igraph-$VERSION
+
+set -e
+shopt -s extglob
+
+if [ -e $SAGE_ROOT/upstream/$PYTHONIGRAPHMOD-$VERSION.tar.gz ]
+then
+ echo "The modified .tar file already exists."
+ exit
+fi
+
+# work in a temporary directory
+cd $(mktemp -d)
+
+mkdir src
+cd src
+
+tar xzf <( curl -L "igraph.org/nightly/get/python/$PYTHONIGRAPH.tar.gz" )
+
+if [ -e $PYTHONIGRAPH ]
+then
+ mv $PYTHONIGRAPH $PYTHONIGRAPHMOD
+ tar -zcf $PYTHONIGRAPHMOD.tar.gz $PYTHONIGRAPHMOD
+ mv $PYTHONIGRAPHMOD.tar.gz $SAGE_ROOT/upstream/python_igraph-$VERSION.tar.gz
+ echo "Correctly downloaded/modified input file."
+else
+ echo "Cannot find file $PYTHONIGRAPH.tar.gz."
+fi
+cd ..
+rm -rf src \ No newline at end of file
diff --git a/build/pkgs/python_igraph/type b/build/pkgs/python_igraph/type
new file mode 100644
index 0000000..134d9bc
--- /dev/null
+++ b/build/pkgs/python_igraph/type
@@ -0,0 +1 @@
+optional
diff --git a/src/sage/graphs/digraph.py b/src/sage/graphs/digraph.py
index cf6b583..56dfd3a 100644
--- a/src/sage/graphs/digraph.py
+++ b/src/sage/graphs/digraph.py
@@ -206,6 +206,8 @@ class DiGraph(GenericGraph):
#. A NetworkX digraph
+ #. An igraph Graph (see http://igraph.org/python/)
+
- ``pos`` - a positioning dictionary: for example, the
spring layout from NetworkX for the 5-cycle is::
@@ -252,6 +254,8 @@ class DiGraph(GenericGraph):
``convert_empty_dict_labels_to_None`` to ``False`` (it is
``True`` by default).
+ - ``igraph`` - data must be an igraph directed Graph.
+
- ``sparse`` (boolean) -- ``sparse=True`` is an alias for
``data_structure="sparse"``, and ``sparse=False`` is an alias for
``data_structure="dense"``.
@@ -395,6 +399,31 @@ class DiGraph(GenericGraph):
sage: DiGraph(g)
Digraph on 5 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 ``vertex_labels`` is ``True``, the names of the vertices are given by
+ the vertex attribute ``'name'``, if available::
+
+ 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']
+ sage: g = igraph.Graph([(0,1),(0,2)], directed=True, vertex_attrs={'label':['a','b','c']}) # optional - python_igraph
+ sage: DiGraph(g).vertices() # optional - python_igraph
+ [0, 1, 2]
+
+ If the igraph Graph has edge attributes, they are used as edge labels::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], directed=True, edge_attrs={'name':['a','b'], 'weight':[1,3]}) # optional - python_igraph
+ sage: DiGraph(g).edges() # optional - python_igraph
+ [(0, 1, {'name': 'a', 'weight': 1}), (0, 2, {'name': 'b', 'weight': 3})]
+
+
TESTS::
sage: DiGraph({0:[1,2,3], 2:[4]}).edges()
@@ -433,7 +462,6 @@ class DiGraph(GenericGraph):
True
sage: type(J_imm._backend) == type(G_imm._backend)
True
-
"""
_directed = True
@@ -525,12 +553,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 # optional - python_igraph
+ sage: DiGraph(igraph.Graph()) # optional - python_igraph
+ Traceback (most recent call last):
+ ...
+ ValueError: A *directed* igraph graph was expected. To build an undirected graph, call the Graph constructor.
"""
msg = ''
GenericGraph.__init__(self)
@@ -604,6 +640,17 @@ class DiGraph(GenericGraph):
format = 'NX'
elif isinstance(data, (networkx.DiGraph, networkx.MultiDiGraph)):
format = 'NX'
+ if (format is None and
+ hasattr(data, 'vcount') and
+ hasattr(data, 'get_edgelist')):
+ try:
+ import igraph
+ except ImportError:
+ raise ImportError("The data seems to be a igraph object, but "+
+ "igraph is not installed in Sage. To install "+
+ "it, run 'sage -i python_igraph'")
+ if format is None and isinstance(data, igraph.Graph):
+ format = 'igraph'
if format is None and isinstance(data, (int, Integer)):
format = 'int'
if format is None and data is None:
@@ -841,6 +888,19 @@ class DiGraph(GenericGraph):
self.allow_loops(loops,check=False)
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':
+ if not data.is_directed():
+ raise ValueError("A *directed* igraph graph was expected. To "+
+ "build an undirected graph, call the Graph "
+ "constructor.")
+
+ self.add_vertices(range(data.vcount()))
+ self.add_edges([(e.source, e.target, e.attributes()) for e in data.es()])
+
+ if vertex_labels and 'name' in data.vertex_attributes():
+ vs = data.vs()
+ self.relabel({v:vs[v]['name'] for v in self})
+
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 ee53a92..932d3b3 100644
--- a/src/sage/graphs/generic_graph.py
+++ b/src/sage/graphs/generic_graph.py
@@ -12,6 +12,7 @@ can be applied on both. Here is what it can do:
:delim: |
:meth:`~GenericGraph.networkx_graph` | Create a new NetworkX graph from the Sage graph
+ :meth:`~GenericGraph.igraph_graph` | Create a new igraph graph from the Sage graph
:meth:`~GenericGraph.to_dictionary` | Create a dictionary encoding the graph.
:meth:`~GenericGraph.copy` | Return a copy of the graph.
:meth:`~GenericGraph.export_to_file` | Export the graph to a file.
@@ -1306,6 +1307,142 @@ class GenericGraph(GenericGraph_pyx):
N.add_edge(u,v,weight=l)
return N
+ def igraph_graph(self, vertex_attrs={}, edge_attrs={}):
+ r"""
+ Converts the graph into an igraph graph.
+
+ Optionally, it is possible to add vertex attributes and edge attributes
+ to the output graph.
+
+ .. NOTE::
+
+ This routine needs the optional package igraph to be installed:
+ to do so, it is enough to
+ run ``sage -i igraph`` followed by ``sage -i python_igraph``. For
+ more information on the Python version of igraph, see
+ http://igraph.org/python/.
+
+ INPUT:
+
+ - ``vertex_attrs`` (dictionary) - a dictionary where the key is a string
+ (the attribute name), and the value is an iterable containing in
+ position i the label of the ith vertex (see
+ http://igraph.org/python/doc/igraph.Graph-class.html#__init__ for
+ more information).
+
+ - ``edge_attrs`` (dictionary) - a dictionary where the key is a string
+ (the attribute name), and the value is an iterable containing in
+ position i the label of the ith edge in the list outputted by
+ ``self.edges()`` (see
+ http://igraph.org/python/doc/igraph.Graph-class.html#__init__
+ for more information).
+
+ .. NOTE::
+
+ In igraph, a graph is weighted if the edge labels have attribute
+ ``weight``. Hence, to create a weighted graph, it is enough to add
+ this attribute.
+
+ 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 -- '
+ 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 -- '
+
+ Adding edge attributes::
+
+ sage: G = Graph([(1,2,'a'),(2,3,'b')]) # optional - python_igraph
+ sage: H = G.igraph_graph(edge_attrs = {'label':[e[2] for e in G.edges()]}) # optional - python_igraph
+ sage: H.es['label'] # optional - python_igraph
+ ['a', 'b']
+
+
+ If edges have an attribute ``weight``, the igraph graph is considered
+ weighted::
+
+ sage: G = Graph([(1,2,{'weight':1}),(2,3,{'weight':2})]) # optional - python_igraph
+ sage: H = G.igraph_graph(edge_attrs = {'weight':[e[2]['weight'] for e in G.edges()]}) # optional - python_igraph
+ sage: H.is_weighted() # optional - python_igraph
+ True
+ sage: H.es['weight'] # optional - python_igraph
+ [1, 2]
+
+ Adding vertex attributes::
+
+ sage: G = graphs.GridGraph([2,2]) # optional - python_igraph
+ sage: H = G.igraph_graph(vertex_attrs={'name':G.vertices()}) # 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: vertex_attrs={'name':G.vertices()} # optional - python_igraph
+ sage: edge_attrs={'w':[e[2]['w'] for e in G.edges()]} # optional - python_igraph
+ sage: H = DiGraph(G.igraph_graph(vertex_attrs, edge_attrs)) # 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_attrs=edge_attrs)) # 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_attrs)) # 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: vertex_attrs={'name':G.vertices()} # optional - python_igraph
+ sage: edge_attrs={'w':[e[2]['w'] for e in G.edges()]} # optional - python_igraph
+ sage: H = Graph(G.igraph_graph(vertex_attrs, edge_attrs)) # 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_attrs=edge_attrs)) # 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_attrs)) # optional - python_igraph
+ sage: G == H # optional - python_igraph
+ True
+ sage: G.edges() == H.edges() # optional - python_igraph
+ False
+ """
+ try:
+ import igraph
+ except ImportError:
+ raise ImportError("The package igraph is not available. To " +
+ "install it, run 'sage -i igraph' followed by " +
+ "'sage -i python_igraph'.")
+
+ v_to_int = {v:i for i,v in enumerate(self.vertices())}
+ edges = [(v_to_int[v], v_to_int[w]) for v,w in self.edge_iterator(labels=False)]
+
+ return igraph.Graph(n = self.num_verts(),
+ edges = edges,
+ directed=self.is_directed(),
+ vertex_attrs = vertex_attrs,
+ edge_attrs = edge_attrs)
+
def to_dictionary(self, edge_labels=False, multiple_edges=False):
r"""
Returns the graph as a dictionary.
diff --git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py
index 1d3eef2..12b90b8 100644
--- a/src/sage/graphs/graph.py
+++ b/src/sage/graphs/graph.py
@@ -337,6 +337,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
----------
@@ -626,6 +633,8 @@ class Graph(GenericGraph):
#. A NetworkX graph
+ #. An igraph graph (see http://igraph.org/python/)
+
- ``pos`` - a positioning dictionary: for example, the
spring layout from NetworkX for the 5-cycle is::
@@ -688,6 +697,8 @@ class Graph(GenericGraph):
``convert_empty_dict_labels_to_None`` to ``False`` (it is
``True`` by default).
+ - ``igraph`` - data must be an `igraph <http://igraph.org/>`__ graph.
+
- ``sparse`` (boolean) -- ``sparse=True`` is an alias for
``data_structure="sparse"``, and ``sparse=False`` is an alias for
``data_structure="dense"``.
@@ -950,6 +961,30 @@ class Graph(GenericGraph):
sage: DiGraph(g)
Digraph on 5 vertices
+ #. 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 ``vertex_labels`` is ``True``, the names of the vertices are given by
+ the vertex attribute ``'name'``, if available::
+
+ 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']
+ sage: g = igraph.Graph([(0,1),(0,2)], vertex_attrs={'label':['a','b','c']}) # optional - python_igraph
+ sage: Graph(g).vertices() # optional - python_igraph
+ [0, 1, 2]
+
+ If the igraph Graph has edge attributes, they are used as edge labels::
+
+ sage: g = igraph.Graph([(0,1),(0,2)], edge_attrs={'name':['a','b'], 'weight':[1,3]}) # optional - python_igraph
+ sage: Graph(g).edges() # optional - python_igraph
+ [(0, 1, {'name': 'a', 'weight': 1}), (0, 2, {'name': 'b', 'weight': 3})]
+
By default, graphs are mutable and can thus not be used as a dictionary
key::
@@ -976,6 +1011,12 @@ 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: An *undirected* igraph graph was expected. To build an directed graph, call the DiGraph constructor.
+
"""
_directed = False
@@ -1155,9 +1196,20 @@ class Graph(GenericGraph):
import networkx
if isinstance(data, (networkx.DiGraph, networkx.MultiDiGraph)):
data = data.to_undirected()
- format = 'NX'
elif isinstance(data, (networkx.Graph, networkx.MultiGraph)):
format = 'NX'
+
+ if (format is None and
+ hasattr(data, 'vcount') and
+ hasattr(data, 'get_edgelist')):
+ try:
+ import igraph
+ except ImportError:
+ raise ImportError("The data seems to be a igraph object, but "+
+ "igraph is not installed in Sage. To install "+
+ "it, run 'sage -i python_igraph'")
+ if format is None and isinstance(data, igraph.Graph):
+ format = 'igraph'
if format is None and isinstance(data, (int, Integer)):
format = 'int'
if format is None and data is None:
@@ -1368,6 +1420,19 @@ class Graph(GenericGraph):
self.allow_multiple_edges(multiedges, check=False)
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':
+ if data.is_directed():
+ raise ValueError("An *undirected* igraph graph was expected. "+
+ "To build an directed graph, call the DiGraph "+
+ "constructor.")
+
+ self.add_vertices(range(data.vcount()))
+ self.add_edges([(e.source, e.target, e.attributes()) for e in data.es()])
+
+ if vertex_labels and 'name' in data.vertex_attributes():
+ vs = data.vs()
+ self.relabel({v:vs[v]['name'] for v in self})
+
elif format == 'rule':
f = data[1]
verts = data[0]