2
$\begingroup$

Suppose I have a graph formed by 3 vertices and 4 lines. {4 <-> 1, 1 <-> 3, 3 <-> 4, 1 <-> 3} Let the line numbers be {1,2,3,4}. Now lines 2&4 are parallel lines.

Suppose I have a graph with 5000 vertices and 5500 lines.Assuming there are 300 parallel lines in the graph,how would you identify them along with line numbers? In other words, how would you identify such parallel lines and its corresponding line numbers in a big graph?

$\endgroup$
5
  • $\begingroup$ Could you clarify how you define parallel in this context? $\endgroup$
    – MarcoB
    Jul 1 '18 at 5:49
  • 2
    $\begingroup$ @MarcoB "Parallel edges" typically refers to edges connecting the same vertices. $\endgroup$
    – Szabolcs
    Jul 1 '18 at 6:13
  • 1
    $\begingroup$ What are you actually trying to do? IGraph/M has several tools that help in dealing with multigraphs. E.g., IGWeightedSimpeGraph will merge parallel edges and sum their weights. $\endgroup$
    – Szabolcs
    Jul 1 '18 at 6:19
  • $\begingroup$ @Szabolcs thank you for the clarification. I wasn’t aware of that. $\endgroup$
    – MarcoB
    Jul 1 '18 at 6:23
  • $\begingroup$ @Szabolcs If I assign line numbers to every line, and form a graph and that graph has parallel lines, I want to get only the numbers of parallel lines $\endgroup$
    – no-one
    Jul 1 '18 at 6:34
2
$\begingroup$

You can identify the indices of parallel edges using

GroupBy[
  Thread[
    Range@EdgeCount[g] -> (Sort /@ EdgeList[g])
  ],
  Last -> First
]


(* <|1 \[UndirectedEdge] 4 -> {1}, 1 \[UndirectedEdge] 3 -> {2, 4}, 3 \ [UndirectedEdge] 4 -> {3}|> *)
$\endgroup$
0
$\begingroup$

Here is a solution based on Tally for obtaining the edges that have parallels:

edgeRules = {4 <-> 1, 1 <-> 3, 4 <-> 3, 3 <-> 1, 4 <-> 3, 3 <-> 4};
g = Graph[edgeRules];

parallelEdges = 
 First /@ Select[Tally[Sort /@ EdgeList[g]], Last[#] > 1 &]

(*  {1 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4}  *)

That is simple enough, but it gets a little more complicated if we want the position of the edges in the original edgeRules. We could do something like this:

lineNumbers = Flatten[Union[Position[edgeRules, #],
     Position[edgeRules, Reverse[#]]]] & /@
  TwoWayRule @@@ parallelEdges    

(*  {{2, 4}, {3, 5, 6}}  *)

And retrieve the original rules that generated the parallel edges like this:

parallelRules = Part[edgeRules, #] & /@ lineNumbers

{{1 <-> 3, 3 <-> 1}, {4 <-> 3, 4 <-> 3, 3 <-> 4}}
$\endgroup$
0
$\begingroup$
edges = {4 <-> 1, 1 <-> 3, 3 <-> 4, 3 <-> 1} ;
Select[Length @ # >= 2 &] @ GatherBy[Range @ Length @ edges, Sort @ edges[[#]]&]

{{2, 4}}

Also

Select[Length @ # >= 2 &] @ Values @ 
  GroupBy[edges, (Sort @ # &) -> (Flatten[Position[edges, #]]&), First[#]&]

ac = ArrayComponents[Sort /@ edges];
Select[Length@# >= 2 &]@ Values@GroupBy[Range@Length@edges, ac[[#]] &] 

both give

{{2, 4}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.