I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I want to find its longest directed trails (a directed trail is a directed walk in which all edges are distinct). I.e., I'm looking for long walks with repeated nodes, but distinct edges.
Note that this is an NP-hard problem. Otherwise, I would have asked for the longest trails, not merely long trails.
My graph has no weights and it is weakly connected (that is, if each edge were converted to an undirected edge, that undirected graph would be connected).
I define walk/trail/path length as the number of edges in the walk.
My current program is based on traversing the graph in a DFS-like manner. If allowed to run for, e.g., half an hour, it produces trails of less than satisfactory length, and I know that longer trails should be possible in that time budget.
Note that this problem is quite similar to the problem of finding the longest path of a directed graph, but with each edge having a max allowed visits number associated with it, equal to the cardinality of the corresponding edge set in the multidigraph.
In fact, it's possible to transform my problem to the longest path problem by producing the line graph of my graph and then finding its longest paths. However, I'm hoping for a smarter, more efficient solution.
The reason I'm mentioning the digraph longest path problem is that there are certain smart solutions to that problem, but they don't seem to translate to my multidigraph longest trail problem, sadly. In particular, I'm thinking of Miguel Raggi's Arxiv paper, finding long simple paths in a weighted digraph using pseudo-topological orderings. Those and other solutions are based on finding the longest path of a DAG subgraph (or, equivalently, some feedback arc set), which seems inapplicable to my problem (unless I do the mentioned line graph transformation), but I'd be happy for somebody here to prove me wrong.
What am I looking for, then?
Either of these two:
- some method of finding long trails in my multidigraph, smarter than the naive approach.
- some method of finding long paths in my multidigraph's line graph; but it should be more efficient than just looking for an arbitrary digraph's longest paths, i.e., it should take into account the fact that the graph that is being searched through is a line graph.
Some characteristics of my graph
It's got around 500 nodes and around 20000 edges. If the multiple edges are accounted for, the graph's got around 160000 edges.
Some characteristics of my graph's condensation
I don't know if the info on the condensation is relevant, but it might be. See the Wikipedia page for strongly connected components for definitions and examples of graph condensations.
There are less than 200 strongly connected components (equivalently, the condensation has less than 200 nodes), and the condensation's got around 220 edges. One of the SCCs consists of more than 300 original nodes, while every other SCC has only a single original node.
Info about node in-degree and out-degree over all nodes
This too is of dubious importance, but it may be useful. The images are just thumbnails that link to the full-sized plots (made with Vega-Lite):
Note about the scatterplots: each point in the scatterplots is "transparent" so that if there's only one data point in the same point of the plot it's displayed less prominently than if there are multiple in the same position.