11

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!

Improve this question
4
  • 1
    It's hard to understand what you want. Can you give some context for the problem? What do the different kinds of nodes represent? Do you want all paths between two nodes, or just the shortest? How fast does it have to be? ("all paths" is probably gonna push it to exponential time just in printing the output) Commented Dec 12, 2013 at 23:35
  • Lets say nodes represent cities, or stations, some kind of location which has a specific "type", which denotes its size or some other limiting factor. There are three types of those nodes. All paths should be there, not only the shortest one. Speed is irrelevant factor, but I woulnd like to wait for an hours to parse through some nodes :) I will test this with quite small data, under 100 nodes, so speed should definitely not be an issue. Commented Dec 13, 2013 at 8:50
  • I don't entirely understand the constraints. Can nodes of type x be passed through just once or arbitrarily many times? Are connections between the nodes entirely based on the three classes, or is there additional structure to be concerned about? Commented Dec 13, 2013 at 10:58
  • Type X nodes are just a starting and ending point, no path can't contain them besides in those two states. Connections between have that additional "side", upwards and downwards, which is relevant in the final constraint. Other than that, and the type of the actual node, there are no other additional things that are used to describe nodes/connections. Regarding the node y requirement, a node can appear only once, but multiple y nodes can appear in the path. So, two y's are OK, but they have to be different nodes. Similar is with type z, but the same node can be passed through twice. Commented Dec 14, 2013 at 23:56

3 Answers 3

Reset to default
7
+50

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...

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I was trying to solve this using graph gadgets too, but the problem is the up/down edges. If you have in for up and out for down, then you won't find any paths which arrive using a down edge and depart using an up one. If you duplicate the z nodes again so that you can have one with up/in and one with up/out, you can't constrain it so that each z node is passed through twice.
I see. You might have to modify the simple_paths algorithm to keep track of how many times you visit each type of node in that case.
Each node z "can be passed through twice". It doesn't ask you to traverse through node z exactly twice.
Hey, this is helpful and since it got the most upvotes I awarded the bounty, so great job :) However, I had to code my own solution, some insight from your answers helped, and I will post my answer soon and show how I managed to do this. I completely avoided usage of network x and did some "tricks", and it seems like a correct solution. And a small comment, regarding the type x node being visited only once, there are some "subsets" of that type, lets say 1-2-3 which are of that first type, but also are differentiated.
5

The best way to do this I think is by calculating all valid paths of length at most k between the source S and every other node, then using that information to calculate all valid paths of length at most k+1. You then just repeat this until you get a fixed point where no paths are modified.

In practice, this means you should set up a list of paths at each node. At each step, you take each node U in turn and look at the paths that, in the previous step, terminated at some neighbour V of U. If any of those paths can be extended to be a new, distinct path to U, extend it and add it to U's list.

If when you execute a step you find no new paths, that's your termination state. You can then check the list of paths at the target node T.

Pseudocode (in a very loose C# formalism):

var paths = graph.nodes.ToDictionary(node => node, node => new List<List<node>>())
paths[S].Add(new List<node> {S}) // The trivial path that'll start us off.


bool notAFixedPoint = true;

while (notAFixedPoint)
{
    notAFixedPoint = false // Assume we're not gonna find any new paths.

    foreach (var node in graph)
    {
        var pathsToNode = paths[node]

        foreach (var neighbour in node.Neighbours)
        {
            var pathsToNeighbour = paths[neighbour]

            // ExtendPaths is where all the logic about how to recognise a valid path goes.
            var newPathsToNode = ExtendPaths(pathsToNeighbour, node)

            // The use of "Except" here is for expository purposes. It wouldn't actually work,
            // because collections in most languages are compared by reference rather than by value.
            if (newPathsToNode.Except(pathsToNode).IsNotEmpty())
            {
                // We've found some new paths, so we can't terminate yet.
                notAFixedPoint = true 

                pathsToNode.AddMany(newPathsToNode)
            }
        }
    }
}

return paths[T]
Improve this answer

2 Comments

So, for the first portion, I would make paths from source S to its neighbors, and have a length of k. Then, at length k+1, this will add paths from nodes that are adjacent to the nodes connected to the source, and in that way give me the paths from source up to those nodes. And iterate this until I get the target node in the result? How can I know how to stop, since multiple paths might be possible. Could you guide me a bit with some pseudo code, I really don't have a lot of experience with writing this kind of stuff. Thanks!
Thanks for the input and your insight, I spent some more time with this and arrived at solution from a different angle, the other portion besides this pseudocode of yours are the constrains, which were "the key" of this issue.
-1

This looks like an optimization problem to me -- look up "Traveling Salesman" for a classic example that is somewhat close to what you want to do.

I've had good luck using "simulated annealing" for optimization problems, but you might also take a look at "genetic algorithms".

Improve this answer

2 Comments

I don't think a genetic algorithm fits this problem at all, unfortunately. The mutations and crossovers would probably very seldom result in something that is actually a solution.
I agree, I had to code this a bit differently that I was expecting it would be, I will post my answer soon for further reference.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.