Path finder for network link wiring - follow-up

user_7612031 0
Viewed 275

See the initial post on code review

Thanks to @Graipher who proposed the library called networkx in Python for answering my question. My code is now improved and cleaner:

# Path finder improved

class Edge:
  # An Edge is a link (physical, radio, logical) between two assets/nodes/vertices
  def __init__(self, sku, e1, e2, re1, re2):
    # The SKU is the unique ID of the edge
    # An edge two vertices that can be inversable (undirected edge)
    self.sku = sku
    self.sku_endpoint_1 = e1
    self.sku_endpoint_2 = e2
    self.reverse_sku_endpoint_1 = re1
    self.reverse_sku_endpoint_2 = re2

# We can instanciante a edge like that

edge1 = Edge("Edge1","A", "B", "B", "A")
edge2 = Edge("Edge2","B", "C", "C", "B")
edge3 = Edge("Edge3","A", "C", "C", "A")
edge4 = Edge("Edge4","C", "D", "D", "C")
edge5 = Edge("Edge5","B", "E", "E", "B")
edge6 = Edge("Edge6","D", "E", "E", "D")

edges = [edge1, edge2, edge3, edge4, edge5, edge6]

# And then we can find all paths using @Graipher method

def solve(edges, source, target):
  g = nx.Graph()  # bi-directional edges.
  for edge in edges: 
    g.add_edge(edge.sku_endpoint_1, edge.sku_endpoint_2, sku=edge.sku)
  paths = nx.all_simple_paths(g, source=source, target=target)
  index = 0
  paths_dict = {}
  # Creating the dict of paths with only the edgesku
  for path in map(nx.utils.pairwise, paths):
    paths_dict[index] = []
    for edge in path:
        paths_dict[index].append(g.edges[edge]["sku"])
    index+=1
  return paths_dict

But now, what about finding all paths with repeated nodes, but without repeating the same edge? I now see that the networkx library is explicitly not repeating nodes while searching paths...

But consider the following graph:

g.add_edges_from([("A", "B", {"sku": "Edge1"}),
                  ("B", "C", {"sku": "Edge2"}),
                  ("A", "C", {"sku": "Edge3"}),
                  ("C", "D", {"sku": "Edge4"}),
                  ("B", "E", {"sku": "Edge5"}),
                  ("D", "E", {"sku": "Edge6"}),
                  ("C", "E", {"sku": "Edge7"})]

The graph we see looks like that:

enter image description here

When we want to find all paths from A to D we also want find a path even if it uses an already discovered node (here it's C). The only rule we want is, not add a path that has the same edge aleady used (to prevent an infinite loop).

In this example one path that matching these rules for A to D is:

 A->C : "Edge3"
 C->E : "Edge7"
 E->B : "Edge5"
 B->C : "Edge2"
 C->D : "Edge4"

Is there a way to do that with this library? Because with my code (see previous post on codereview) I was able to find these paths. But that's not very optimised because the program searches ALL paths and only then I remove duplicated and non meaningful paths.

python
2 Answers

Here is an attempt, but it's not so great since it doesn't track back all the way to 'a' and re-search all paths via a -> c etc...

If you swap the order of ['b', 'c'] you will get the example path you specified in your question here... Not ideal since it doesn't scale, but hopefully this might show you where I'm headed with this...

graph = {
  'a': ['b','c'],
  'b': ['a', 'c', 'e'],
  'c': ['a','b','d','e'],
  'd': ['c','e'],
  'e': ['b','c','d']
}

def non_simple_paths(g, u, v):
  from collections import defaultdict
  paths = []
  path = []
  edges_used = defaultdict(bool)

  def dfs(g, u, v):

    for n in g[u]:
      e = (u, n)
      re = (n,u)

      if edges_used[re] or edges_used[e]:
        continue
      
      elif v in e:
        c = path[:]
        c.append(e)
        paths.append(c)
        edges_used[e] = True
        edges_used[re] = True
    
      else:
        path.append(e)
        edges_used[e] = True
        edges_used[re] = True
        dfs(g, n, v)

    if path:
      path.pop() # going back to parent

    return

  dfs(g, u, v)
  return paths
  

# ================================
ps = non_simple_paths(graph, 'a', 'd')
print(ps)
user_55547890

I thought a while about this interesting problem, but unfortunately don’t have a great answer.

1. Approach

My first approach was based on the following observation (I’m calling the the paths you are looking for edge-simple):

  1. Each simple path is obviously edge-simple.
  2. Each edge-simple graph can be reduced to a simple path by removing the cycles (loops) between multiple nodes.

To illustrate the 2. point, look at the path you used as an example path A-C-E-B-C-D. It has the node C twice, and, after removing the corresponding cycle C-E-B-C, it is simple: A-C-D.

My idea was to use the simple paths between two nodes as a basis for the edge-simple ones

simple_paths = list(nx.all_simple_paths(G, 'A', 'D'))

and add cycles to the nodes it contains (here constructed via the (full) corresponding directed graph)

H = nx.DiGraph()
H.add_edges_from(list(G.edges) + [(edge[1], edge[0]) for edge in G.edges])
cycles_basis = [cycle for cycle in nx.simple_cycles(H) if len(cycle) > 2]

But I got lost on the way through the second part ...

2. Approach

I ended up with a second approach that resembles the one given by @JordanSimba:

import networkx as nx

def remove_edge(G, node1, node2):
    return G.edge_subgraph(list(set(G.edges)
                                .difference({(node1, node2), (node2, node1)})))

def all_edge_simple_paths(G, source, target):
    paths = []
    if source == target:
        paths.append([source])
    for node in G[source]:
        G_sub = remove_edge(G, source, node)
        if node in G_sub.nodes and target in G_sub.nodes:
            paths.extend([[source] + path
                          for path in all_edge_simple_paths(G_sub, node, target)])
        else:
            if node == target:
                paths.append([source, target])
    return paths

With your graph

G = nx.Graph()
G.add_edges_from([('A', 'B'), ('B', 'C'), ('A', 'C'), ('C', 'D'), ('B', 'E'),
                  ('D', 'E'), ('C', 'E')])

the result (all_edge_simple_paths(G, 'A', 'D')) is

[['A', 'B', 'C', 'D'],
 ['A', 'B', 'C', 'E', 'D'],
 ['A', 'B', 'E', 'D'],
 ['A', 'B', 'E', 'C', 'D'],
 ['A', 'C', 'B', 'E', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D'],
 ['A', 'C', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D'],
 ['A', 'C', 'E', 'D']]

If a small cycle gets added onto node D

G.add_edges_from([('D', 'F'), ('F', 'G'), ('G', 'D')])

the results includes it (both directions through the cycle)

[['A', 'B', 'C', 'D'],
 ['A', 'B', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'B', 'C', 'E', 'D'],
 ['A', 'B', 'C', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'C', 'E', 'D', 'G', 'F', 'D'],
 ['A', 'B', 'E', 'D'],
 ['A', 'B', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'E', 'D', 'G', 'F', 'D'],
 ['A', 'B', 'E', 'C', 'D'],
 ['A', 'B', 'E', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'B', 'E', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'B', 'E', 'D'],
 ['A', 'C', 'B', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'B', 'E', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'B', 'E', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'D'],
 ['A', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'E', 'B', 'C', 'D', 'G', 'F', 'D'],
 ['A', 'C', 'E', 'D'],
 ['A', 'C', 'E', 'D', 'F', 'G', 'D'],
 ['A', 'C', 'E', 'D', 'G', 'F', 'D']]

To be honest: I’m not 100% sure it works correctly (for all situations). I just don't have the time for extensive testing. And the number of paths grows rapidly with increasing graph size, which makes it hard to keep track on what's going on.

And I have serious doubts regarding the efficiency. Someone pointed out to me recently that working with the subgraph view could slow things down. So maybe only a lower level implementation might produce the speed you’re looking for.

But maybe it helps.

user_143112630
Related