Java에서 무향 그래프의 가장자리

무 방향 그래프의 가장자리를 나타 내기 위해 Java 클래스를 작성한다고 가정 해 보겠습니다. 이 클래스 Edge에는 두 개의 정점 to과 from이 포함되어 있습니다.Java에서 무향 그래프의 가장자리

 
class Edge<Vertex> { 

    private final Vertex to, from 

    public Edge(Vertex to, Vertex from) { 
    this.to = to; 
    this.from = from; 
    } 
    ... // getters, equals, hashCode ... 
}

분명히 e1 = new Edge(v1, v2) 및 e2 = new Edge(v2, v1) 실제로 무향 그래프와 동일하다. 그것은 의미가 있습니까? 이 요구 사항을 충족시키기 위해 클래스 Edge을 어떻게 구현하겠습니까?

출처

2012-12-17 Michael

지향 에지와 무향 에지 모두에이 구현을 사용 하시겠습니까? 나는 그것을 재고 할 것이다. – bowmore

글쎄, 내 머리 위로의의 naivest 방법은 다음과 같습니다

분명히

protected boolean checkIfSameEdge(Vertex to, Vertex from) { 
    if(to.equals(this.from) && from.equals(this.to) || to.equals(this.to) && from.equals(this.from)) { 
    return true; 
    return false; 
}

당신은 아마도 노드가 스칼라 값의 일종을 포함 equals 및

출처

2012-12-17 16:51:00 noMAD

또한 : http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html –

hashcode 오버라이드 (override) 할 것 - 종류 이 값에 기반한 매개 변수 (compareTo 메소드 사용) 및 팩토리를 사용하여 새 인스턴스를 작성하거나 기존 인스턴스를 리턴하십시오.

출처

2012-12-17 16:58:24 symcbean

고유 식별자를 기반으로 생성자의 정점을 정렬합니다. 이 방법은 순서에 관계없이 일관되게 저장됩니다.

이러한 객체와 상호 작용하는 모든 코드가 equals의 구현뿐만 아니라 동일하게 처리하므로 noMAD의 솔루션보다 바람직합니다.

또한 클래스 멤버 to과 from을 호출하는 것은 유향 그래프처럼 들리므로 혼란 스럽습니다. vertex1 및 vertex2과 같이 좀 더 일반적인 이름으로 바꿀 것입니다.

public Edge(Vertex x, Vertex y) { 
     if (vertex2.getId() > vertex1.getId()) { 
      this.vertex1 = x; 
      this.vertex2 = y; 
     } else { 
      this.vertex1 = y; 
      this.vertex2 = x; 
     } 
    }

출처

2012-12-17 16:59:05 dbyrne

저는이 솔루션을 좋아하지만'Vertex'에는 몇 가지 비교 가능한'Id'가 있다고 가정합니다. 그러나 수학 그래프는 그것을 가정하지 않습니다. – Michael

사실 내 Edge 클래스에서이 논리를하지 않았을하지만 이러한 Graph 클래스로 오버 보는 클래스의 오히려 어떤 종류. 그 이유는 Edge이 정점이 2 개인 객체 일 뿐이 기 때문입니다. 그래프의 나머지 가장자리에 대해서는 아무 것도 모릅니다.

그래서 유목민의 대답 @에 확장, 사실은 내 Graph 클래스에서 자신의 checkIfSameEdge 방법을 둘 것 :

public class Graph { 
    private List<Edge> edges; 
    .... 
    public void addEdge(Edge e) { 
     for (Edge edge : edges) { 
      if (isSameEdge(edge, e) { 
       return; // Edge already in Graph, nothing to do 
     } 
     edges.add(e); 
    } 
    private boolean isSameEdge(Edge edge1, Edge edge2) { 
     return ((edge1.to.equals(edge2.to) && edge1.from.equals(edge2.from)) 
      || (edge1.to.equals(edge2.from) && edge1.from.equals(edge2.to))) 
    } 
}

을 BTW : 나는 to 및 fromvertex1 및 vertex2 이름을 바꿀 것이라고는 무향 그래프이기 때문에 to와 to는 방향을 나타냅니다. 그러나 그것은 단지 나의 행동입니다.

출처

2012-12-17 16:59:21

Java에서 무향 그래프의 가장자리

답변

관련 문제