Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Solving a graph issue with Python

I have one situation and I would like to approach this problem with Python, but unfortunately I don't have enough knowledge about the graphs. I found one library which seems very suitable for this relatively simple task, networkx, but I am having issues doing exact things I want, which should be fairly simple.

I have a list of nodes, which can have different types, and two "classes" of neighbors, upwards and downwards. The task is to find paths between two target nodes, with some constraints in mind:

  • only nodes of specific type can be traversed, i.e. if starting nodes are of type x, any node in the path has to be from another set of paths, y or z
  • if a node has a type y, it can be passed through only once
  • if a node has type z, it can be passed through twice
  • in case a node of type z is visited, the exit has to be from the different class of neighbor, i.e. if its visited from upwards, the exit has to be from downwards

So, I tried some experimentation but I, as said, have struggled. First, I am unsure what type of graph this actually represents? Its not directional, since it doesn't matter if you go from node 1 to node 2, or from node 2 to node 1 (except in that last scenario, so that complicates things a bit...). This means I can't just create a graph which is simply multidirectional, since I have to have that constraint in mind. Second, I have to traverse through those nodes, but specify that only nodes of specific type have to be available for path. Also, in case the last scenario happens, I have to have in mind the entry and exit class/direction, which puts it in somewhat directed state.

Here is some sample mockup code:

import networkx as nx

G=nx.DiGraph()
G.add_node(1, type=1)
G.add_node(2, type=2)
G.add_node(3, type=3)
G.add_edge(1,2, side="up")
G.add_edge(1,3, side="up")
G.add_edge(2,1, side="down")
G.add_edge(2,3, side="down")
for path in nx.all_simple_paths(G,1,3):
    print path

The output is fairly nice, but I need these constraints. So, do you have some suggestions how can I implement these, or give me some more guidance regarding understanding this type of problem, or suggest a different approach or library for this problem? Maybe a simple dictionary based algorithm would fit this need?

Thanks!

like image 469
wont_compile Avatar asked Dec 10 '13 11:12

wont_compile


People also ask

How do you connect graphs in Python?

To find the connected components of a graph, you can simply use a depth-first search. Start at any node and follow edges until you can't reach any more nodes without hitting duplicates. This is the first connected component. Then start at any node you haven't touched yet and repeat.

How is a graph represented in Python?

Graphs in Python can be represented in several different ways. The most notable ones are adjacency matrices, adjacency lists, and lists of edges. In this guide, we'll cover all of them. When implementing graphs, you can switch between these types of representations at your leisure.

Is there a graph module in Python?

python-graph (dist: python-graph-core, mod: pygraph) is a library for working with graphs in Python. This software provides a suitable data structure for representing graphs and a whole set of important algorithms.


1 Answers

You might be able to use the all_simple_paths() function for your problem if you construct your graph differently. Simple paths are those with no repeated nodes. So for your constraints here are some suggestions to build the graph so you can run that algorithm unmodified.

  • only nodes of specific type can be traversed, i.e. if starting nodes are of type x, any node in the path has to be from another set of paths, y or z

Given a starting node n, remove all other nodes with that type before you find paths.

  • if a node has a type y, it can be passed through only once

This is the definition of simple paths so it is automatically satisfied.

  • if a node has type z, it can be passed through twice

For every node n of type z add a new node n2 with the same edges as those pointing to and from n.

  • in case a node of type z is visited, the exit has to be from the different class of neighbor, i.e. if its visited from upwards, the exit has to be from downwards

If the edges are directed as you propose then this could be satisfied if you make sure the edges to z are all the same direction - e.g. in for up and out for down...

like image 125
Aric Avatar answered Sep 28 '22 08:09

Aric