[PYTHON] NetworkX memo (directed graph)

Overview

Since I recently started using NetworkX in my research, I will write a module that I think I will often use as a memo for myself.

I've just started using Python, so I don't think I can write it smartly. Also, there may be parts where the wording is wrong (methods, packages, etc.).

You can install the NetworkX package with pip. You can use pip install networkx.

Reference : http://networkx.readthedocs.io/en/stable/

Import NetworkX packages

First, import the NetworkX package. In the NetworkX documentation, it is abbreviated as nx.

python3.5

import networkx as nx

Creating a graph

Creating an empty graph

First, create an empty graph to work with the graph. In the case of a directed graph, it can be generated with DiGraph (). For undirected graphs, it is Graph ().

python3.5

Graph = nx.DiGraph()

Add node

Add nodes to the empty graph created earlier. Nodes can be added with the DiGraph.add_node () method.

python3.5

>>> Graph.add_node('hoge')
>>> Graph.add_node('fuga')

Get a list of nodes

It is DiGraph.nodes () to get the list of nodes. Alternatively, you can also output with Graph.nodes (data = True / False). If no arguments are given, the default value for data is False. If data = True is set, it will be acquired as a list of tuples consisting of a node name and a dictionary of the attributes of the node.

If it is an interactive interpreter, the list will be output just by hitting Graph.nodes (), but since it is essentially just getting the node list, if you want to output the node list during file execution, print (Graph. You have to do nodes ()) .

python3.5

>>> Graph.nodes()
['fuga', 'hoge']
>>> Graph.nodes(data=False)
['fuga', 'hoge']
>>> Graph.nodes(data=True)
[('fuga', {}), ('hoge', {})]

Add nodes at once

You can also add nodes collectively from a list or dictionary. This uses the DiGraph.add_nodes_from () method.

python3.5

>>> Graph.add_nodes_from(['foo','bar'])
>>> Graph.nodes(data=False)
['fuga', 'bar', 'hoge', 'foo']

Create a node with attributes

In the output of the node list earlier, I introduced that if you set DiGraph.nodes (data = True), a list of tuples consisting of a node name and a dictionary of the attributes of the node will be output. It is also DiGraph.add_node () to generate a node with attributes.

python3.5

>>> Graph.add_node('hoge', color = 'green')
>>> Graph.add_node('fuga', color = 'red')
>>> Graph.nodes(data=True)
[('fuga', {'color': 'red'}), ('hoge', {'color': 'green'})]

You can add as many attributes as you like.

python3.5

>>> Graph.add_node('foo', color = 'white', lang = 'en')
>>> Graph.nodes(data=True)
[('fuga', {'color': 'red'}), ('foo', {'color': 'white', 'lang': 'en'}), ('hoge', {'color': 'green'})]

Delete node

Use the DiGraph.remove_node () method to remove a node added to the graph.

python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'bar', 'foo']
>>> Graph.remove_node('bar')
>>> Graph.nodes()
['fuga', 'hoge', 'foo']

Delete nodes at once

As with adding nodes, you can remove nodes in bulk from a list or dictionary. This uses the DiGraph.remove_nodes_from () method.

python3.5

>>> e = Graph.nodes()
>>> e
['fuga', 'hoge', 'foo']
>>> Graph.remove_nodes_from(e)
>>> Graph.nodes()
[]

Add edge

We will add edges that connect nodes. Edges can be added with the DiGraph.add_edge () method. Since it is a directed graph, the first argument is start and the second argument is target.

Python3.5

>>> Graph.nodes(data=False)
['hoge', 'foo', 'fuga', 'bar']
>>> Graph.add_edge('hoge','fuga')
>>> Graph.add_edge('foo','bar')

Get edge list

It is DiGraph.edges () to get the list of edges. As with nodes, you can select to show / hide attributes with data = True / False to get the edge list.

If this is also an interactive interpreter, the list will be output just by hitting Graph.edges (), but if you want to output the list by executing the code file, you have to do print (Graph.edges ()). Is useless.

Python3.5

>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.edges(data=False)
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.edges(data=True)
[('hoge', 'fuga', {}), ('foo', 'bar', {})]

Add edges together

Edges can be added collectively from a list or dictionary as well as nodes. For edges, use the DiGraph.add_edges_from () method.

Python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'foo', 'bar']
>>> Graph.add_edges_from([('hoge','fuga'),('foo','bar')])
>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]

Add an edge with an attribute

Of course, you can also add attributes to edges. Rather, it may be more common to add attributes to edges. You can now realize a weighted graph.

By the way, in the case of a weighted graph, if you set the weight with weight, it is easy because the default value of the key is often weight when searching for a route later. Edges with attributes are also DiGraph.add_edge ().

Python3.5

>>> Graph.add_edge('foo', 'hoge', weight=0.7)
>>> Graph.add_edge('bar', 'fuga', weight=0.7)
>>> Graph.edges(data=True)
[('foo', 'hoge', {'weight': 0.7}), ('bar', 'fuga', {'weight': 0.7})]

Add weighted edges together

Since there are many situations to create a weighted graph, NetworkX has a DiGraph.add_weighted_edges_from () method to make it easier to add weighted edges.

In ʻadd_edges_from (), edges are added together from the 2-tuple list of (start point, end point). ʻAdd_weighted_edges_from () adds weighted edges together from the 3-tuple list of (start, end, weight).

python3.5

>>> Graph.add_weighted_edges_from([('hoge','fuga',0.4),('foo','bar',0.2)])
>>> Graph.edges(data=True)
[('hoge', 'fuga', {'weight': 0.4}), ('foo', 'bar', {'weight': 0.2})]

Unless otherwise specified, the weight key is set with weight. However, if you want to specify the weight with a key other than weight, you can change it. In that case, set the key as follows.

python3.5

>>> Graph.add_weighted_edges_from([('hoge','fuga',0.4),('foo','bar',0.2)],weight='omomi')
>>> Graph.edges(data=True)
[('hoge', 'fuga', {'omomi': 0.4}), ('foo', 'bar', {'omomi': 0.2})]

Delete edge

Use the DiGraph.remove_edge () method to remove the edge added to the graph.

python3.5

>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edge('hoge','fuga')
>>> Graph.edges()
[('foo', 'bar')]

Delete edges at once

As with adding edges, you can also remove edges in bulk from a list or dictionary. This uses the DiGraph.remove_edges_from () method.

python3.5

>>> e = Graph.edges()
>>> e
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edges_from(e)
>>> Graph.edges()
[]

Delete all nodes and edges

If you want to delete all the added nodes and edges and return to an empty graph, use the DiGraph.clear () method.

python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'bar', 'foo']
>>> Graph.edges()
[('fuga', 'foo'), ('hoge', 'fuga'), ('bar', 'hoge'), ('foo', 'bar')]
>>> Graph.clear()
>>> Graph.nodes()
[]
>>> Graph.edges()
[]

Route search

The graph is now created. NetworkX also includes various route search algorithms, making route search easy. In my research, it is necessary to acquire all the routes from the start point to the end point, so I will write this first.

Acquisition of all routes

This time, assuming the following graph as a sample, we will search the entire route from the node of ʻato the node ofc`.

In the case of route search, the shortest route is often found, but NetworkX also has a module that acquires all routes, which is nx.all_simple_paths (G, source, target, cutoff = None). cutoff is the depth at which the search is stopped, and if this is specified, only routes with a length less than or equal to cutoff will be returned. Not specified by default.

I wrote the following code to get all the routes.

allpaths.py

import networkx as nx

Graph = nx.DiGraph()

Graph.add_nodes_from(['a','b','c','d'])

Graph.add_edges_from([('a','b'),('a','c'),('a','d'),('b','c'),('b','d'),('d','c')])

print('all paths')
for path in nx.all_simple_paths(Graph, source='a', target='c'):
    print(path)

The following execution results.

Execution result

all paths
['a', 'b', 'c']
['a', 'b', 'd', 'c']
['a', 'c']
['a', 'd', 'c']

It was confirmed that all routes could be acquired.

Shortest path search

The shortest path search module implements various algorithms, including Dijkstra's algorithm, Floyd-Warshall's algorithm, and Bellman-Ford algorithm (I don't know what kind of algorithm it is because I don't know the graph at all). The subject of my research interest is not the shortest path, so I will add it if my energy continues in the future.

By the way, the reference of the shortest path search module is here.